- 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 optimal convergence in terms of the number of oracles required in x and y is established, while for general 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
- The paper provides optimal convergence in terms of the number of oracles required in x and y for
- For general the established number of oracles required for x is O((m + √mκ) log(1/ε)).
- The experiments indicate significant speedups in the performance of the algorithm in the case of weak regularization.
- The paper seems well-organized and the code for reproducing the experiments is provided.
Critical weaknesses
- 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.
- Exact oracles and knowledge of the parameters are assumed even though acknowledged in the limitations of the work.
Questions for authors
- What is the exact definition of Gap(x, y) in the Theorems?
- 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?
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)=maxy′∈Yf(x,y′)−minx′∈Xf(x′,y)=P(x)−ϕ(y)
It is nonnegative for every feasible pair, vanishes at a saddle point, and bounds primal suboptimality:
0≤P(x)−P⋆≤Gap(x,y).
The algorithm maintains an upper bound P(xˉ)≤a, obtained through primal recovery from the collected upper planes, and a lower bound ϕ(yb)≥b, supplied by the quadratic lower model. Consequently,
Gap(xˉ,yb)≤a−b.
The stopping rule a−b≤ε 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)∣≤δ.
The upper plane can be replaced by
ℓ+(y)=v+δ+⟨g,y−yc⟩,
which still dominates f(u,y). The constant of the transported lower model can be computed as
b+=1+Ab+A(v−δ).
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 remains valid for any feasible query point yc∈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 μ and L
The analysis requires valid bounds, rather than the tightest possible constants. A certified strong-convexity lower bound μ>0 and smoothness upper bound L suffice, with the complexity expressed using L/μ. 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.