Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm

TaeHo Yoon; Ernest K. Ryu

Source-linked AI summary

Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm

TaeHo Yoon, Ernest K. Ryu

arXiv:2102.07922v2Feb 16, 2021math.OC

TL;DR

The paper addresses the unknown optimal complexity of reducing squared gradient magnitude in smooth minimax optimization, where the duality gap is difficult to measure directly. It introduces extra anchored gradient algorithms that combine extragradient steps with anchoring, achieves O(1/k^2) last-iterate convergence, and proves this rate optimal with a matching lower bound.

Problem
The optimal convergence rate and corresponding algorithms for squared gradient magnitude in smooth minimax problems were previously unknown, while the duality gap can be difficult to measure directly.
Method
The paper introduces extra anchored gradient algorithms that combine extragradient steps with anchoring.
Results
The algorithms achieve an O(1/k^2) last-iterate rate on squared gradient magnitude, matched by an Ω(1/k^2) complexity lower bound.
Takeaways & Limitations
The O(1/k^2) rate is optimal for gradient-based algorithms in the studied smooth convex-concave setting, and the deterministic result does not require averaging or best-iterate tracking.
Takeaways & Limitations
The presented algorithms use the simple choice β_k = 1/(k+2), although other parameter choices may improve the constant, and the relation to Nesterov acceleration remains open.

Abstract

from arXiv · show

In this work, we study the computational complexity of reducing the squared gradient magnitude for smooth minimax optimization problems. First, we present algorithms with accelerated $\mathcal{O}(1/k^2)$ last-iterate rates, faster than the existing $\mathcal{O}(1/k)$ or slower rates for extragradient, Popov, and gradient descent with anchoring. The acceleration mechanism combines extragradient steps with anchoring and is distinct from Nesterov's acceleration. We then establish optimality of the $ \mathcal{O}(1/k^2)$ rate through a matching lower bound.

1. Introduction

The paper studies squared gradient magnitude as an observable suboptimality measure for smooth minimax problems, where prior convergence rates and optimal algorithms were unknown. It introduces EAG algorithms that combine extragradient steps with anchoring to achieve an optimal last-iterate rate.

1. Introduction: The squared gradient magnitude is directly observable and remains meaningful for differentiable non-convex-concave minimax games.The paper motivates it as an alternative to the duality gap, which can be difficult to measure directly and is unclear to generalize beyond convex-concave settings.
1. Introduction: The EAG algorithms achieve an accelerated squared-gradient rate of O(R^2/k^2), improving on prior O(R^2/k) or slower rates.A matching Ω(R^2/k^2) lower bound establishes optimality for gradient-based algorithms.
1. Introduction: The optimal rate applies to the non-ergodic last iterate, so deterministic optimization does not require averaging or tracking the best iterate.This contrasts with analyses that obtain rates for best or averaged iterates.
1.1. Preliminaries and notation: For smooth convex-concave problems, the squared gradient magnitude is a natural suboptimality measure because saddle points are exactly zeros of the saddle operator.The saddle operator is monotone, and its norm equals the gradient norm despite the sign change in the y component.
1. Introduction: Prior minimax work spans duality-gap methods, nonsmooth and stochastic settings, strongly monotone problems, structured objectives, and proximal splitting methods.The paper positions EAG specifically in smooth convex-concave minimax optimization without relying on the broader structured-problem machinery.
1. Introduction: EAG combines extragradient steps with anchoring, with anchoring serving as the second main component of the acceleration.Existing extragradient methods attain O(R^2/k) bounds, while anchoring alone had slower last-iterate rates.

2. Accelerated algorithms: Extra anchored gradient

The extra anchored gradient algorithms combine extragradient steps with anchoring and achieve accelerated last-iterate convergence for smooth convex-concave problems. EAG-C favors simpler updates, while EAG-V favors a simpler convergence proof, and both extend to Lipschitz continuous monotone operators.

Algorithm design: EAG-C and EAG-V combine extragradient updates with anchoring, differing mainly in whether step-size or proof simplicity is prioritized.EAG-V uses a varying step-size with a simpler proof, whereas EAG-C uses a simpler constant step-size with a more complicated proof.
EAG-C: EAG-C admits a simple constant-step-size form, but its convergence proof is complicated and its stated constant is 260.The particular choice α = 1/(8R) appears in Corollary 1 under the theorem’s step-size conditions.
Generalization: The algorithms and proofs remain valid for R-Lipschitz continuous monotone operators, not only saddle operators arising from convex-concave functions.The stated argument relies on monotonicity of the subdifferentials rather than additional saddle-function properties.
EAG-V: EAG-V’s β_k = 1/(k+2) choice is convenient rather than optimal: numerical tuning reduces Corollary 2’s constant from 27 to 24.44.The authors also leave open whether a different form of β_k could improve the constant further.
Convergence analysis: Both algorithms achieve O(1/k^2) convergence of the squared gradient norm through linear growth of B_k and quadratic growth of A_k.For EAG-V, the analysis uses a nonincreasing Lyapunov function; the specified anchoring choice gives B_k = k + 1.

3. Optimality of EAG via a matching complexity lower bound

The paper proves a matching Ω(R2/k2) lower bound for deterministic gradient-based algorithms, establishing EAG's O(R2/k2) rate as optimal even over separately updated variables.

Ω(R2/k2) is a worst-case lower bound for deterministic gradient-based algorithms in the broader class Asep, so EAG is optimal.Asep allows separate access to x- and y-subgradients and contains the simultaneous-update class used by EAG.
The optimality claim applies to both separate and simultaneous algorithm classes, ruling out improvements from separately updating x and y.The comparison uses Asim ⊂ Asep and shows the relevant classes coincide under the skew-symmetric identification.
The lower bound is realized by R-smooth biaffine functions and cannot be improved within that function family.The construction uses biaffine losses, a subclass of smooth convex-concave functions.
Since biaffine functions are smooth convex-concave, the lower bound transfers to the full smooth convex-concave minimax setting.Corollary 3 applies the biaffine lower bound to smooth convex-concave problems.
The proof reduces biaffine minimax optimization to linear-equation complexity using matrix-vector products and Krylov-subspace restrictions.The reduction identifies algorithm classes and connects the minimax lower bound to established matrix-polynomial lower bounds.
A factor-near-100 gap remains between the upper and lower bounds, and non-biaffine constructions might improve the lower-bound constant.The authors leave possible improvements to the algorithm and lower bound for future work.

4. Experiments

Experiments compare EAG-C and EAG-V with EG, Popov, and SimGD-A, illustrating accelerated gradient-norm behavior and the role of anchoring in trajectory dynamics.

EAG-C and EAG-V are compared against EG, Popov, and SimGD-A on two smooth convex-concave examples.The experiments use theoretical parameter choices for each method and plot squared gradient magnitude against iteration count.
Figure 1 plots ∥G(zk)∥2 against iteration count with dashed theoretical upper bounds, while EG's visualization uses a best-iterate O(R2/k) bound.There is no known EG last-iterate guarantee for this metric; monotone decrease was observed in both experiments.
ODE Interpretation: SimGD-A progresses more slowly than EAG because it requires diminishing step-sizes both theoretically and experimentally.The figure comparison reports virtually coincident EAG-C and SimGD-A trajectories but slower progress for SimGD-A.
The first experiment uses a 1-smooth convex construction with α = 0.1, while the second uses n = 200 and distinct method-specific step-sizes.The second example is the Lagrangian of a linearly constrained quadratic minimization problem.
ODE Interpretation: EAG and SimGD-A trajectories resemble the anchored continuous-time flow, whose anchoring term dampens cycling and approaches the solution faster.The continuous-time comparison uses a bilinear regime where discrete trajectories closely follow their corresponding flows.

5. Conclusion

The conclusion presents EAG as achieving accelerated O(1/k2) squared-gradient rates by combining extragradient steps with anchoring, with a matching lower bound establishing optimality.

EAG achieves O(1/k2) rates on squared gradient magnitude for smooth convex-concave minimax problems, matched by an Ω(1/k2) lower bound.The conclusion frames the upper and lower bounds together as an optimality result.
The acceleration combines extragradient and anchoring mechanisms, which separately yield O(1/k) or slower rates.The conclusion distinguishes this mechanism from simply using either component alone.
The relationship between EAG's anchoring-based acceleration and Nesterov's momentum-based acceleration remains an open direction.The paper notes that anchoring dampens oscillations whereas momentum provides the opposite effect of dampening.

A. Algorithm specifications

This appendix specifies the baseline algorithms and develops identities used in the EAG analysis, relying on monotonicity and Lipschitz continuity of the saddle operator.

The appendix defines simultaneous, alternating, extragradient, Popov, and anchored gradient methods in joint-variable saddle-operator notation.The saddle operator incorporates the sign change in the y-gradient.
Alternating gradient descent-ascent updates x first and then uses the updated x iterate to update y.This distinguishes its update structure from simultaneous methods.
SimGD-A uses diminishing step-sizes governed by p ∈ (1/2, 1), with a reported convergence rate O(1/k^(2−2p)).The paper states that its experiments use γ = 1 and p approaching 1.
The EAG proof derives identities from its iterate definitions, then combines monotonicity, Lipschitzness, cancellation, and Young's inequality.These algebraic steps produce the potential inequalities used in the convergence analysis.

B.2. Proof of Lemma 1

The proof establishes that the sequence of step-size-related coefficients remains bounded within a prescribed interval and decreases to a positive limit.

B.2. Proof of Lemma 1: Consequently, α_k converges downward to a limit α satisfying α ≥ (1 − γ)α_N.This conclusion follows directly from the monotone bounded sequence argument.
B.2. Proof of Lemma 1: The sequence α_N+k decreases while remaining between (1 − γ)α_N and ρ for every k ≥ 0.The argument uses induction together with the recurrence and monotonicity of {α_k}.
B.2. Proof of Lemma 1: The induction step follows by summing bounds on successive differences α_N+j − α_N+j+1.The resulting inequality yields (1 − γ)α_N < α_N+k+1 < α_N < ρ.
B.2. Proof of Lemma 1: For α_0 = 0.618 and N = 1000, direct calculation places α_N between 0.4366 and 0.437.The proof then selects ρ = 0.437 for this instance.

B.3. Proof of Theorem 1

The proof constructs a nonincreasing Lyapunov function by selecting coefficients that preserve positive semidefiniteness and force quadratic growth of the auxiliary sequence A_k.

B.3. Proof of Theorem 1: The Lyapunov construction combines monotonicity and Lipschitz inequalities with coefficients (k + 1)(k + 2) and τ_k ≥ 0.These weighted inequalities are assembled into V_k − V_k+1 through a matrix semidefiniteness argument.
B.3. Proof of Theorem 1: Quadratic growth of A_k combined with B_k = k + 1 yields an O(1/k^2) convergence argument.The proof reduces acceleration to choosing τ_k so that the semidefiniteness constraints hold while the Lyapunov function grows quadratically.
B.3. Proof of Theorem 1: The proof maintains A_k within an interval I_k = [ℓ_k, u_k], which guarantees the required quadratic growth.The interval bounds also support the construction of τ_k and positive semidefiniteness of S_k.
B.3. Proof of Theorem 1: The more intricate Case 2 analysis is unnecessary unless extending the convergence range for α beyond 0.1265.The authors recommend Case 1 when that extension is not needed.

C.1. Proof of Theorem 3

The proof derives a polynomial characterization of the linear lower-bound problem, identifies Chebyshev polynomials as optimal, and transfers the resulting bound to general linear operators.

C.1. Proof of Theorem 3: The minimax polynomial problem over degree-k polynomials with p(0) = 1 is solved by a Chebyshev-based construction.The proof uses equioscillation and alternating extrema to establish optimality.
C.1. Proof of Theorem 3: The optimal polynomial satisfies |p*_k(λ_j)| = R / 2^⌊k/2⌋ + 1 at the specified extremal eigenvalues.These eigenvalues are distributed across the interval [−R, R] according to the Chebyshev extrema.
C.1. Proof of Theorem 3: The polynomial optimization can be represented as a second-order cone program with a matching dual problem.This formulation supplies the primal-dual structure used to construct a hard matrix instance.
C.1. Proof of Theorem 3: A diagonal operator with the extremal eigenvalues realizes the lower-bound instance for algorithms restricted to polynomial iterates.The resulting construction has a solution norm equal to D and transfers the polynomial bound to linear residuals.
C.1. Proof of Theorem 3: The same rate extends from symmetric operators to arbitrary operators by applying the symmetric polynomial argument to |B| = (B^⊤B)^1/2.The eigenvalues of |B| lie in [0, R], enabling application of the preceding bound.

C.5. Proof of Theorem 4

The proof constructs a sequence of rotated biaffine objectives that remain indistinguishable to deterministic gradient-based algorithms while preserving a large final gradient.

C.5. Proof of Theorem 4: For any deterministic black-box gradient-based algorithm and initial point, the construction produces a biaffine problem whose k-th iterate satisfies the theorem’s lower-bound guarantee.The theorem applies when the dimension satisfies n ≥ 3k + 2.
C.5. Proof of Theorem 4: Each rotation preserves all oracle information seen so far, so the algorithm’s iterates do not change when the objective is replaced by the next rotated objective.This sequentially adjusts the objective after each inquiry point to resist efficient optimization.
C.5. Proof of Theorem 4: The final gradient norm is bounded below by twice the squared norm of the minimum-norm solution, establishing the hard instance’s residual.The bound follows from the two rotated polynomial residual components.
C.5. Proof of Theorem 4: The orthogonal matrices are chosen to preserve the Krylov subspaces generated by previous oracle information while expanding the hidden null-space component.The induction maintains U_i b = b and bounds the dimension of the auxiliary subspace by 2i.

D. Experimental details

The supplied passages describe EG-related convergence bounds, continuous-time flows, and EAG’s relationship to CLI algorithm classes. They also note that EG lacks a last-iterate gradient-norm guarantee despite empirical monotonicity in Figure 1.

D.2. Best-iterate gradient norm bound for EG: EG has an O(R^2/k) best-iterate squared-gradient bound, but no known theoretical last-iterate guarantee for ∥G(z_k)∥^2.The paper uses the best-iterate bound to visualize EG’s theoretical upper bound in Figure 1.
D. Experimental details: The EG analysis applies monotonicity and R-Lipschitz continuity of G to derive the convergence inequality.The cited proof applies Lemma 6 to consecutive iterates and sums the resulting inequalities.
D.3. ODE flows for L(x, y) = xy: For L(x,y)=xy, the paper presents exact continuous-time solutions and corresponding Moreau–Yosida regularized flow results.The supplied equations give explicit x(t) and y(t) expressions for the unregularized and regularized flows.
E. Connection to CLI lower bounds: EAG is not 1-SCLI because its anchoring coefficients vary with iteration, while it belongs to the broader 2-CLI class.The discussion identifies the varying coefficient 1/(k+2) as the source of non-stationarity.

E.2. Understanding EAG as a CLI algorithm

This section characterizes EAG within CLI algorithm classes. EAG is a non-stationary 2-CLI method and, after translation, achieves a rate that rules out extending the Θ(1/k) lower bound to these broader classes.

E.2. Understanding EAG as a CLI algorithm: EAG is 2-CLI but not stationary, because its iteration-dependent anchoring coefficients vary with k.The section introduces m-CLI algorithms with coefficients that may depend on the iteration index.
E.2. Understanding EAG as a CLI algorithm: The CLI framework includes algorithms generated from multiple previous iterates, with stationary methods as the special case of iteration-independent coefficient mappings.When m=1, the stationary definition coincides with 1-SCLI; multiple previous iterates are represented by assigning them to the m state variables.
E.2. Understanding EAG as a CLI algorithm: EAG’s O(1/k^2) rate shows that the Θ(1/k) 1-SCLI lower bound cannot extend to 2-CLI algorithms.The paper reformulates EAG using previous iterates, establishing its 2-CLI interpretation.
E.2. Understanding EAG as a CLI algorithm: EAG is a translated 1-CLI algorithm, so its O(1/k^2) rate rules out generalizing the Θ(1/k) 1-SCLI lower bound to translated 1-CLI methods.Translation sets z_0=0 and preserves the relevant algorithmic form under a translated objective.