Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration

Core framework

• Relative Lipschitzness unifies analyses of mirror prox and dual extrapolation for monotone variational inequalities, including convex optimization and convex-concave saddle-point problems.The condition relates the operator to the regularizer and is inspired by relative smoothness and area convexity.Source: §1 · p. 3

Extragradient methods directly yield acceleration

• Standard mirror prox and dual extrapolation recover accelerated rates for smooth strongly convex minimization through a Fenchel-game formulation.The analysis yields the optimal O(T −2) rate for smooth non-strongly convex minimization via reduction.Source: §1 · pp. 3–4

1 Introduction

• Acceleration remains difficult for relatively smooth functions, motivating further study of how this three-point condition relates to other acceleration frameworks.The paper identifies this relationship as an open direction [HRX18] [DTdB19].Source: §1 · pp. 3–4

Area convexity for bilinear box-simplex games

• The framework recovers improved rates for box-constrained ℓ∞ regression by relating local relative Lipschitzness to area convexity.The proof uses local stability of iterates and a Cauchy-Schwarz argument, while matching the rate implied by area convexity.Source: §1 · pp. 3–4

Randomized extragradient methods via local variance reduction

• A randomized extension uses local variance reduction to obtain O(T −1) rates for suitable variational inequalities with block-separable structure.Estimators share a random seed within an iteration, and the design exploits separability.Source: §1 · p. 5
• The randomized framework recovers accelerated rates for coordinate-smooth functions, matching known tight rates.The paper generalizes a related strategy from faster approximate maximum flow algorithms [ST18].Source: §1 · p. 5

Additional contributions

• The paper also derives fine-grained minimax rates under blockwise Hessian-norm and strong-convexity assumptions using a strongly monotone mirror prox variant.These rates improve the runtime of [LJJ20] for a range of parameters, while the relationship to optimistic mirror descent [RS13] is also discussed.Source: §1 · p. 5

General notation

• Variables lie in R^d, with an arbitrary norm and its dual norm defining the geometric framework.Source: §2 · p. 6

Bregman divergences

• A Bregman divergence is induced by a distance-generating convex function and supports the paper’s proximal operations.Source: §2 · p. 6

Saddle points

• For convex-concave h(x, y), the gradient operator is g(x, y) = (∇_x h(x, y), −∇_y h(x, y)), and saddle quality is measured by the duality gap.Source: §2 · p. 6

Monotone operators

• A monotone operator satisfies ⟨g(w) − g(z), w − z⟩ ≥ 0, with convex gradients and convex-concave gradient operators as examples.Source: §2 · p. 6
• The variational-inequality solution notion includes convex minimizers and convex-concave saddle points.Source: §2 · p. 6

Relative Lipschitzness

• Mirror prox and dual extrapolation are analyzed for monotone operators that satisfy a three-point relative Lipschitzness condition.The condition relates the operator g to the regularizer r and is tailored to standard extragradient analyses.Source: §3 · pp. 6–7

Extragradient methods

• The same convergence framework applies to dual extrapolation, viewed as a lazy mirror-prox variant that updates a dual-space state.Source: §3 · p. 6

Relative Lipschitzness

• Relative Lipschitzness contains standard Lipschitz-operator/strongly-convex-regularizer assumptions and relative smoothness of convex functions.Source: §3 · p. 7

Mirror prox convergence

• The mirror-prox iterates achieve an O(T^-1) decay of average regret over T iterations.The proof uses first-order optimality, relative Lipschitzness, and telescoping Bregman-divergence terms.Source: §3 · p. 7

Applications to games

• The regret guarantee converts to a duality-gap bound for averaged iterates in convex-concave games.Source: §3 · pp. 7–8

Acceleration via relative Lipschitzness

• Directly applying mirror prox to the Fenchel game recovers accelerated first-order minimization rates, with extensions to general norms.Source: §4 · p. 8

Fenchel-game analysis

• For an L-smooth, µ-strongly convex function, the Fenchel-game gradient operator is relatively Lipschitz with respect to a regularizer built from f and f*.Source: §4 · p. 8
• The proof expands the operator interaction across three points and controls the resulting terms using Cauchy-Schwarz, strong convexity of f*, and Young’s inequality.Source: §4 · p. 8

Implementation

• The primal-dual iterates admit recursive forms that enable efficient implementation of the extragradient method using Fenchel-conjugate relations.Source: §4 · pp. 8–9

Main convergence result

• After O(L/µ) iterations, mirror prox halves the function error; repetition yields an accelerated linear rate and optimal O(T^-2) non-strongly convex rates.Source: §4 · p. 9

General norms

• An alternative strongly-monotone analysis extends acceleration to general norms, though its rates lose an L/µ factor in the logarithm relative to the main theorem.Source: §4 · p. 10

Local relative Lipschitzness

• Local relative Lipschitzness need only hold on triples of algorithm iterates, extending extragradient convergence analysis to structured box-simplex games.This local condition is formalized as an extension of the main convergence proposition.Source: §5 · p. 10

Applications

• The box-simplex formulation generalizes box-constrained ℓ∞ regression through a reduction that at most doubles the input size.The reduction stacks A and b with their negated copies.Source: §5 · pp. 10–11

Area convexity connection

• Standard mirror prox and dual extrapolation recover the rate previously obtained with area convexity for box-simplex games.The analysis uses the area-convex regularizer from but avoids its partial-differential-equation proof.Source: §5 · pp. 10–11

Preprocessing

• After preprocessing, the method assumes b ∈ [0, 2∥A∥∞→∞]^m without changing the maximized game value or additive-error objective.Rows with sufficiently large b_i can be removed, and the remaining coordinates shifted in linear time.Source: §5 · p. 11

Complexity

• The resulting regularizer has range O(∥A∥∞→∞ log m), yielding O(∥A∥∞→∞ log m / ε) iterations for an ε-additive solution.Subproblems can be solved to sufficient accuracy with logarithmic dependence on problem parameters using alternating minimization.Source: §5 · pp. 10, 11, 13

Coordinate smoothness

• Coordinate smoothness supplies the expected relative-Lipschitzness properties needed by the randomized convergence proposition.The construction targets functions that are L_i-smooth in individual coordinates.Source: §6 · pp. 13–14

Randomized extragradient framework

• For separable domains, a local-variance-reduction framework for randomized extragradient methods yields O(T^-1) stochastic rates under an expected variant of relative Lipschitzness.The relative-Lipschitzness condition need only hold for algorithm iterates, rather than globally.Source: §6 · pp. 13–14

Shared randomness

• The coordinate method samples a shared coordinate for both updates, producing estimators that are unbiased at the current iterate but not necessarily at the extrapolated point.The shared randomness is essential to the proof and underlies the local variance-reduction argument.Source: §6 · pp. 13–14

Algorithm and complexity

• Algorithm 5 obtains the accelerated coordinate-minimization complexity stated in Theorem 3, with each iteration implementable using two generalized partial-derivative oracle queries.The query and maintenance guarantee is given by Lemma 8.Source: §6 · pp. 14–15

7 Discussion

• Relative Lipschitzness gives extragradient algorithms a general O(T^-1) convergence condition, with locality, randomization, and strong monotonicity enabling tighter structured-instance guarantees.The framework is intended as a recipe for sharper convergence analyses across variational inequalities.Source: §7 · p. 15
• The paper leaves open whether the framework can recover tight rates for finite-sum stochastic optimization and composite optimization.These are proposed as future applications of the general condition.Source: §7 · p. 15
• Additional open questions concern interpolating the minimax algorithm with momentum-based methods and extending the toolkit to convex-concave games and variational inequalities.The discussion frames these as directions for connecting extragradient and other algorithmic frameworks.Source: §7 · p. 15

A Preliminaries

• The preliminaries establish the bridge from smoothness or strong convexity to relative Lipschitzness using Fenchel duality, conjugate Bregman divergences, and coordinate smoothness.These lemmas support the later primal-dual and randomized constructions.Source: A Preliminaries · pp. 19, 21

Unaccelerated smooth convex optimization

• Applying extragradient methods directly to g(x)=∇f(x) recovers an O(1/T) function-error rate for smooth convex minimization.This is the unaccelerated baseline for the later Fenchel-game construction.Source: B Unaccelerated smooth convex… · pp. 21–22

Strongly convex extension

• For smooth strongly convex functions, the corresponding primal-dual Fenchel-game analysis yields an accelerated linear rate, while strong convexity converts function error to squared-distance control.The linear rate follows from the stated O(L/µ) iteration behavior and repeated application.Source: B Unaccelerated smooth convex… · p. 22

• The minimax objective assumes μ_y-strong concavity in y and μ_x-strong convexity in x, with blockwise smoothness parameters L_xx, L_xy, and L_yy.The analysis uses L := max(L_xx, L_xy, L_yy).Source: C Minimax optimization · pp. 22, 24
• The framework obtains an upper bound on gradient queries for ε Euclidean distance to the saddle point, improving [LJJ20] in some cases.The resulting distance guarantee can also be converted into a duality-gap bound.Source: C Minimax optimization · p. 22
• The section presents Algorithm 3, strongly monotone mirror prox, as the computational method underlying the bound.The algorithm is initialized with a distance-generating regularizer and a relatively Lipschitz monotone operator.Source: C Minimax optimization · p. 23
• Proposition 3 strengthens a known relative-Lipschitzness derivation and supplies the convergence bound used for the minimax analysis.Its proof combines strongly monotone mirror prox with relative Lipschitzness and divergence inequalities.Source: C Minimax optimization · p. 23
• A distance bound converts to a duality-gap bound while increasing only the logarithmic runtime term.The conversion uses best responses and smoothness-related bounds for the associated functions.Source: C Minimax optimization · pp. 23–25

D.1 Strongly monotone mirror prox

• D.1 Strongly monotone mirror prox: Proposition 3 bounds the iterates of Algorithm 3 relative to the VI solution under relative Lipschitzness and strong monotonicity.The proof uses first-order optimality, nonnegative Bregman divergence, and iteration of the resulting inequality.Source: §D.1 · p. 25

D.2 Dual extrapolation

• D.2 Dual extrapolation: the simplified algorithm achieves the same relative-Lipschitzness convergence rate as mirror prox.Its analysis uses a helper lemma and combines two extrapolation inequalities with relative Lipschitzness.Source: §D.2 · pp. 25–26
• D.2 Dual extrapolation: all acceleration results are implementable with dual extrapolation as the base method.The paper states that the extension follows by arguments analogous to those used for mirror prox.Source: §D.2 · p. 26

• The general-norm setting requires f to be L-smooth in a norm and μ-strongly convex relative to a 1-strongly convex regularizer ω.This replaces the Euclidean strong-convexity formulation used in the basic acceleration result.Source: E Extragradient acceleration in… · p. 27
• Writing h(x)=f(x)−μω(x) reduces minimization to an equivalent saddle-point problem whose gradient operator is strongly monotone and relatively Lipschitz.The saddle point is z*= (x*, ∇h(x*)).Source: E Extragradient acceleration in… · p. 27
• Lemma 20 states that, in the setting of Lemma 19, g is 1 + µ-relatively Lipschitz with respect to r.Source: E Extragradient acceleration in… · p. 27
• Theorem 4 shows that each iteration uses a constant number of proximal problems in ω and constant additional d-dimensional vector operations.The iterates maintain the form (x_t, ∇h(v_t)) for explicitly computed v_t.Source: E Extragradient acceleration in… · p. 28
• The resulting error guarantee follows by applying the strongly monotone extragradient framework and using smoothness of f together with strong convexity of ω.The proof applies Proposition 3 with the bounds established in Lemmas 19 and 20.Source: E Extragradient acceleration in… · pp. 27–28

F Missing proofs from Section 6

• F Missing proofs from Section 6: Lemma 7 establishes expected relative Lipschitzness for the randomized coordinate analysis.The parameter uses the coordinate smoothness values L_i and the quantity S_1/2, with expectations taken over the sampled iteration coordinate.Source: F Missing proofs from Section 6 · p. 29
• F Missing proofs from Section 6: EG-Coord-Accel samples coordinates and uses generalized partial-derivative queries to implement sparse updates efficiently.The implementation maintains implicit representations and updates them with two oracle queries and constant additional work.Source: F Missing proofs from Section 6 · pp. 30–31
• F Missing proofs from Section 6: the coordinate proof exploits one- and two-sparse updates to maintain the required implicit iterates.These representations permit the updates to be computed through partial derivative queries.Source: F Missing proofs from Section 6 · pp. 29, 31

G Optimism

• G Optimism: relative Lipschitzness can sharpen optimistic mirror descent because its proof couples terms rather than applying Cauchy–Schwarz directly.Under Lipschitzness, choosing M_t=g(z_t) and η=1/L recovers the mirror-prox procedure.Source: G Optimism · pp. 31–32