acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 with , where is smooth and strongly convex with condition number , and count oracle calls for and for separately. The standard approach runs a cutting-plane method over and solves each inner problem to accuracy with an accelerated method, costing oracle calls for but oracle calls for . We show that accurate inner solves are unnecessary. Our method, certificate transport, maintains a strongly convex lower model of one slice and uses it to warm-start a short accelerated run on the next. Each oracle call for then either cuts the localizer or, by concavity in , transports the lower model to a mixture of the two slices with a certified increase. For , this yields an -saddle point with oracle calls for and oracle calls for , which is optimal both in the number of oracle calls for and in the total number of oracle calls, even when is merely concave and Lipschitz. For general , assuming the center of gravity of the localizer can be computed efficiently, the method uses oracle calls for and an optimal oracle calls for .

Primary area:
optimization
Keywords:
optimization, saddle point problems, oracle complexity

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_U9QBOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies min max optimization problems with a low-dimensional block without inexact solvers. More specifically, the authors introduce a method certificate transport that maintains a strongly convex lower model of f (·, y) and uses it to warm-start a short accelerated run on the next one. Each oracle call for y is proved to either cut the localizer or transport the lower model to a mixture of the two slices with a certified increase. For m=1m=1 optimal convergence in terms of the number of oracles required in x and y is established, while for general m>0m > 0 assuming that the general center of gravity is computed exactly the established number of oracles required for x is O((m + √mκ) log(1/ε)). Experiments are provided indicating the regimes in which the proposed method outperforms the standard baseline.

Critical strengths
  1. The paper provides optimal convergence in terms of the number of oracles required in x and y for m=1m=1
  2. For general mm the established number of oracles required for x is O((m + √mκ) log(1/ε)).
  3. The experiments indicate significant speedups in the performance of the algorithm in the case of weak regularization.
  4. The paper seems well-organized and the code for reproducing the experiments is provided.
Critical weaknesses
  1. It was relatively difficult to follow the main text in the paper. I think a lot of technicalities are added early on that make the reader hard to follow the presentation of all the results.
  2. Exact oracles and knowledge of the parameters μ,L\mu, L are assumed even though acknowledged in the limitations of the work.
Questions for authors
  1. What is the exact definition of Gap(x, y) in the Theorems?
  2. Do you think that the case of inexact oracles would require a substantially different proof technique than yours? What changes and which elements remain the same?
1 comment

Thank you for the positive assessment and these questions.

1. Definition of the gap

Throughout the theorems, we use the primal–dual saddle-point gap defined in Section 2, Equation (2):

Gap⁡(x,y)=max⁡y′∈Yf(x,y′)−min⁡x′∈Xf(x′,y)=P(x)−ϕ(y)\operatorname{Gap}(x,y)=\max_{y'\in\mathcal Y}f(x,y')-\min_{x'\in\mathcal X}f(x',y)=P(x)-\phi(y)

It is nonnegative for every feasible pair, vanishes at a saddle point, and bounds primal suboptimality:

0≤P(x)−P⋆≤Gap⁡(x,y).0\le P(x)-P^\star\le \operatorname{Gap}(x,y).

The algorithm maintains an upper bound P(xˉ)≤aP(\bar x)\le a, obtained through primal recovery from the collected upper planes, and a lower bound ϕ(yb)≥b\phi(y_b)\ge b, supplied by the quadratic lower model. Consequently,

Gap⁡(xˉ,yb)≤a−b.\operatorname{Gap}(\bar x,y_b)\le a-b.

The stopping rule a−b≤εa-b\le\varepsilon therefore certifies the actual saddle-point gap without requiring knowledge of an optimal solution.

2. Extension to inexact oracles

The current results allow inaccurate inner solutions while assuming exact oracle information. Extending them to inaccurate oracle information depends on the error model.

2.1 For bounded function-value errors with exact gradients and supergradients

the certificate construction admits a direct correction. Suppose

∣v~−f(u,yc)∣≤δ.|\widetilde v-f(u,y_c)|\le\delta.

The upper plane can be replaced by

ℓ+(y)=v~+δ+⟨g,y−yc⟩,\ell^+(y)=\widetilde v+\delta+\langle g,y-y_c\rangle,

which still dominates f(u,y)f(u,y). The constant of the transported lower model can be computed as

b+=b+A(v~−δ)1+A.b^+=\frac{b+A(\widetilde v-\delta)}{1+A}.

Thus, the upper-plane and lower-model invariants remain valid. The progress argument must also incorporate error margins into the cut-or-transport decision; with fixed uncertainty, one should expect a noise-dependent accuracy floor.

2.2 For gradient errors, more substantial analysis is needed.

The accelerated-block proof uses gradients both to construct global quadratic lower models and to establish its estimate-sequence invariant. An extension would need conservative lower models and an explicit bound on the accumulated block error.

2.3 Approximate computation of the center of gravity

With exact oracle information, the certificate Gap⁡(xˉ,yb)≤a−b\operatorname{Gap}(\bar x,y_b)\le a-b remains valid for any feasible query point yc∈Yy_c\in\mathcal Y. The exact center is used to prove a constant-factor reduction in the localizer's volume, so preserving the convergence-rate guarantee with approximate centers requires a corresponding volume-reduction guarantee.

2.4 Final

Certificate validity and convergence rates should therefore be considered separately. A full complexity analysis under function-value and gradient errors is beyond the scope of the paper.

3. Knowledge of μ\mu and LL

The analysis requires valid bounds, rather than the tightest possible constants. A certified strong-convexity lower bound μ‾>0\underline\mu>0 and smoothness upper bound L‾\overline L suffice, with the complexity expressed using L‾/μ‾\overline L/\underline\mu. In our regularized learning experiments, the chosen ridge coefficient supplies the strong-convexity bound, and the feature matrices supply smoothness bounds. Removing the need for certified parameter bounds remains outside the present guarantees.

Reviewer_qBDtOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies efficient algorithms for minimax optimization problems involving a high-dimensional strongly convex variable and a low-dimensional concave variable. The authors propose a Certificate Transport algorithm that reduces first-order oracle complexity by avoiding highly accurate inner solves, with applications to Group DRO and constrained learning.

Critical strengths

1 The proposed Certificate Transport method avoids accurate inner solves while maintaining rigorous convergence guarantees.

2 The method significantly reduces first-order oracle complexity and achieves optimal complexity bounds when the low-dimensional block has dimension one.

Critical weaknesses
  1. The experiments compare oracle calls but not wall-clock time.
  2. The Group DRO reduces to minimizing the maximum of finitely many smooth convex losses. While the paper compares several generic minimax methods, it does not include optimization algorithms specifically designed for finite-max objectives.
Questions for authors

The author uses the "group DRO" as the application of the algorithm. However, where is the ambiguity set in the "DRO" problem? DRO problem should involve an maximization problem among an ambiguity set.

1 comment

Thank you for these comments.

1. Wall-clock comparisons

We have added serial wall-clock experiments that include center computation, initialization, oracle evaluations, LPs, stopping certificates, and output recovery (Figure 4 and Appendix D.4).

On quadratic DRO and a reduced 20Newsgroups benchmark, with m∈{16,19}m\in\{16,19\} and κ∈{106,107}\kappa\in\{10^6,10^7\}, CT-MC with the same sampling budget N=⌈64m2⌉N=\lceil64m^2\rceil throughout is 1.59–2.20× faster than the best measured Level configuration across all eight configurations, at the common certified gap target 10−610^{-6}. For example, at m=19m=19, κ=107\kappa=10^7, the 20News times are 109.2 seconds for CT versus 237.7 seconds for Level.

For Level, we select the faster of analytic centers and Monte Carlo centers with sampling factors α∈{4,16,64,150}\alpha\in\{4,16,64,150\}; its inner-accuracy fraction is fixed at c=0.3c=0.3. Measurements use one fixed CPU core and one BLAS/HiGHS thread. They are medians of two repeats on fixed instances, with unlocked CPU frequency. We therefore report them as descriptive solver-time measurements. Raw results, implementation details, and reproduction commands are included in the supplement.

2. The ambiguity set in Group DRO

Our experiments consider robustness to changes in group proportions. Let P^g\widehat P_g denote the empirical distribution within group gg, and let

Lg(x)=Ez∼P^g[ℓ(x;z)].L_g(x)=\mathbb E_{z\sim\widehat P_g}[\ell(x;z)].

The ambiguity set is

\mathcal Q=\left\\{\sum_{g=1}^{G}w_g\widehat P_g:w\in\Delta_G\right\\},\qquad\Delta_G=\{w\ge0:\mathbf1^\top w=1\}.

Thus, the regularized empirical DRO problem is

\max_{Q\in\mathcal Q}\mathbb E_Q[\ell(x;z)] +\frac{\mu}{2}\|x\|^2 \right\\}=\min_x\max_{w\in\Delta_G} \left\\{ \sum_{g=1}^{G}w_gL_g(x)+\frac{\mu}{2}\|x\|^2 \right\\}.$$ The within-group empirical distributions are fixed, while their mixture weights are uncertain. This is the standard group-shift ambiguity set used by [Sagawa et al. (ICLR 2020, Section 2)](https://arxiv.org/abs/1911.08731). In our notation, the small block parametrizes this simplex in its affine hull, so $m=G-1$. ### 3. Specialized finite-max methods and theoretical positioning You are correct that, for this ambiguity set, $$\max_{w\in\Delta_G}\sum_gw_gL_g(x)=\max_g L_g(x).$$ Consequently, specialized finite-max algorithms are relevant comparators. There is already a substantial theory of these methods: [Carmon et al. (COLT 2021)](https://proceedings.mlr.press/v134/carmon21a.html) establish optimal dependence on the number of component functions up to logarithmic factors, and [A Whole New Ball Game](https://arxiv.org/abs/2311.10886) gives oracle complexity for smooth losses that is optimal up to logarithmic factors when the number of functions is large. Our result concerns a different combination of assumptions and oracle accounting: a smooth, strongly convex large block, a low-dimensional concave block, and separate bounds on the calls to the two oracles. The cited works count evaluations of individual component functions. In our Group DRO setting, a small-block query provides information about all group losses, while a large-block query returns a weighted aggregate gradient. Matching upper and lower bounds in the component-oracle model therefore do not by themselves establish the separate complexity bounds studied in our work. Appendix E discusses the relation to the finite-max literature. Group DRO is an interpretable special case of the broader problem: our method allows an arbitrary concave, Lipschitz dependence on the small block and does not require the objective to be represented as a maximum of finitely many functions. The nested and level-method comparisons test the central mechanism: whether certificate transport can reuse an unfinished inner solve and yield a runtime advantage. Our contribution is this mechanism and its associated split-oracle guarantees; the reported timings establish an advantage over the evaluated methods in the specified regimes.
Reviewer_4BAQOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies saddle-point problems with a large, smooth, strongly convex block and a small concave block that may be nonsmooth. Standard nested approaches repeatedly solve the large inner problem to high accuracy before making progress on the small block. The proposed certificate-transport method instead reuses a quadratic lower model across different slices of the objective. Each outer query either reduces the search region or improves the certified lower bound, so useful progress does not require an accurate inner solution. The resulting oracle bounds improve on the nested approach, with matching bounds in the one-dimensional case and experiments identifying where the method is most competitive.

Critical strengths
  1. Reusing partial primal progress while maintaining a valid gap certificate addresses the central difficulty of avoiding accurate inner solves.
  2. The separate primal and dual oracle bounds are supported by experiments using certified accuracy targets and substantive nested and level-method baselines.
Critical weaknesses

The practical runtime advantage remains unresolved. The analysis excludes the cost of computing centers, and the experiments show that this overhead can become substantial as the smaller block grows. Controlled runtime comparisons would establish when the oracle savings translate into faster optimization.

Questions for authors

When the cost of computing centers is included, in which regimes of block dimension and condition number does your method outperform the tuned level-method baseline in actual runtime?

1 comment
AuthorsOpenReview ↗

Practical runtime advantage

Thank you for highlighting this issue. We agree that oracle savings alone do not establish a practical runtime advantage. We have added serial wall-clock experiments that include the cost of computing centers, reported in Figure 4 main part and Appendix D.4.

In the tested regime m∈{16,19}m\in\{16,19\}, κ∈{106,107}\kappa\in\{10^6,10^7\}, CT with Monte Carlo centers is 1.59–2.20× faster than the best measured Level configuration in all eight benchmark configurations, including center computation. The table reports seconds to reach the same certified saddle-gap target, 10−610^{-6}:

Problemmmκ\kappaCT-MC (s)Best measured Level (s)Speedup
Quadratic DRO1610610^611.618.31.59×
Quadratic DRO1610710^731.970.22.20×
Quadratic DRO1910610^614.524.41.69×
Quadratic DRO1910710^737.983.22.20×
20News DRO1610610^632.955.51.69×
20News DRO1610710^797.7202.12.07×
20News DRO1910610^640.266.71.66×
20News DRO1910710^7109.2237.72.18×

CT-MC uses the same sampling budget, N=⌈64m2⌉N=\lceil64m^2\rceil, throughout this table. For Level, we take the faster of its analytic-center variant and its best successful Monte Carlo configuration over α∈{4,16,64,150}\alpha\in\{4,16,64,150\}, where N=⌈αm2⌉N=\lceil\alpha m^2\rceil. The Level inner-accuracy fraction is fixed at c=0.3c=0.3; this timing experiment does not sweep that parameter.

Values are medians of two repeats on fixed problem instances.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.