Saddle-Point Problems with a Low-Dimensional Block Do Not Need Accurate Inner Solves

Abstract

Many learning problems couple a high-dimensional block of parameters with a handful of adversarial or dual variables: worst-group risk over a few groups, or learning under a few constraints. We consider $\min_{x\in X}\max_{y\in Y} f(x,y)$ with $X\subseteq\mathbb{R}^n$, a compact convex set and strongly convex with condition number $\kappa$, and we count the oracle calls for $x$ and for $y$ separately. The textbook approach runs a cutting-plane method in $y$ and solves every inner problem to accuracy $\varepsilon$ with an accelerated method; it needs $O(m\log(1/\varepsilon))$ calls for $y$ but $O(m\sqrt{\kappa}\log^2(1/\varepsilon))$ calls for $x$. We show that the inner problems need not be solved accurately. Our method, certificate transport, keeps a strongly convex lower model of a single slice and uses it as a prior for a short accelerated run on the next slice. By concavity in $y$, every call for $y$ then either cuts the localizer or moves the lower model to a mixture of the two slices with a certified increase of the lower bound. For $m=1$ this gives an $\varepsilon$-saddle point after $O(\sqrt{\kappa}\log(1/\varepsilon))$ calls for $x$, up to an initialization term, and $O(\log(1/\varepsilon))$ calls for $y$; both counts are optimal, even though $f(x,\cdot)$ is only assumed to be concave and Lipschitz. For general $m$, with centers of gravity of the localizer treated as computable, the method needs $O((m+\sqrt{m\kappa})\log(1/\varepsilon))$ calls for $x$ and the optimal $O(m\log(1/\varepsilon))$ calls for $y$. Under strong concavity in $y$, a two-point accelerated method makes the number of calls for $x$ independent of $m$.