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 minx∈ Xmaxy∈ Y f(x,y) with X⊆ℝn, a compact convex set and strongly convex with condition number κ, 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 ε with an accelerated method; it needs O(mlog(1/ε)) calls for y but O(m√κlog2(1/ε)) 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 ε-saddle point after O(√κlog(1/ε)) calls for x, up to an initialization term, and O(log(1/ε)) calls for y; both counts are optimal, even though f(x,·) 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+√(mκ))log(1/ε)) calls for x and the optimal O(mlog(1/ε)) calls for y. Under strong concavity in y, a two-point accelerated method makes the number of calls for x independent of m.
Related
- A parameterized block LU preconditioning for double saddle point problems
- The transposition method in saddle-point problems
- Fluid Problems Posed on Closed Hypersurfaces: Circumventing the Saddle-Point Structure
- Projection-Free Algorithms for Nonsmooth Stochastic Convex-Concave Saddle-Point Problems
- On a PSOR-like Method for Generalized Saddle Point Problems
BibTeX
@misc{fomin2026saddlepoint,
title = {{Saddle-Point Problems with a Low-Dimensional Block Do Not Need Accurate Inner Solves}},
author = {Ivan Fomin and Alexander V. Gasnikov},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32441},
eprint = {2609.32441},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32441},
}
RIS
TY - UNPB
TI - Saddle-Point Problems with a Low-Dimensional Block Do Not Need Accurate Inner Solves
AU - Ivan Fomin
AU - Alexander V. Gasnikov
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32441
UR - https://arxiv.org/abs/2609.32441
AB - 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∈ Xmax_y∈ Y f(x,y) with X⊆ℝ^n, a compact convex set and strongly convex with condition number κ, 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 ε with an accelerated method; it needs O(mlog(1/ε)) calls for y but O(m√κlog^2(1/ε)) 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 ε-saddle point after O(√κlog(1/ε)) calls for x, up to an initialization term, and O(log(1/ε)) calls for y; both counts are optimal, even though f(x,·) 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+√(mκ))log(1/ε)) calls for x and the optimal O(mlog(1/ε)) calls for y. Under strong concavity in y, a two-point accelerated method makes the number of calls for x independent of m.
ER -