Saddle-Point Problems with a Low-Dimensional Block Do Not Need Accurate Inner Solves
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 $κ$, 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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.32441
curl -X POST /api/v1/records/arxiv/2609.32441/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.32441/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'