Min-Max Optimization with a Low-Dimensional Block Without Accurate Inner Solves

Many learning problems couple a high-dimensional block of parameters with a few adversarial or dual variables, e.g., worst-group risk over a few groups or learning with a few constraints. We study ${\min }_{x\in {\mathbb{R}}^n}{\max }_{y\in {\mathbb{R}}^m}f(x,y)$ with $m\ll n$, where $f(\cdot ,y)$ is smooth and strongly convex with condition number $\kappa$, and count oracle calls for $x$ and for $y$ separately. The standard approach runs a cutting-plane method over $y$ and solves each inner problem to accuracy $\epsilon$ with an accelerated method, costing $O(m\log (1/\epsilon ))$ oracle calls for $y$ but $O(m\sqrt{\kappa }{\log }^2(1/\epsilon ))$ oracle calls for $x$. We show that accurate inner solves are unnecessary. Our method, certificate transport, maintains a strongly convex lower model of one slice $f(\cdot ,y)$ and uses it to warm-start a short accelerated run on the next. Each oracle call for $y$ then either cuts the localizer or, by concavity in $y$, transports the lower model to a mixture of the two slices with a certified increase. For $m=1$, this yields an $\epsilon$-saddle point with $O(\sqrt{\kappa }\log (1/\epsilon ))$ oracle calls for $x$ and $O(\log (1/\epsilon ))$ oracle calls for $y$, which is optimal both in the number of oracle calls for $y$ and in the total number of oracle calls, even when $f(x,\cdot )$ is merely concave and Lipschitz. For general $m$, assuming the center of gravity of the localizer can be computed efficiently, the method uses $O((m+\sqrt{m\kappa })\log (1/\epsilon ))$ oracle calls for $x$ and an optimal $O(m\log (1/\epsilon ))$ oracle calls for $y$.