PaperlayerView exact revision on arXiv

Source-linked AI summary

On the convergence of single-call stochastic extra-gradient methods

Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos

arXiv:1908.08465v2math.OCcs.GTcs.LG

TL;DR

The paper addresses the cost of Extra-Gradient’s two oracle calls in variational inequalities. It develops a synthetic view of single-call methods and shows O(1/t) convergence in deterministic monotone and stochastic strongly monotone settings, plus local last-iterate convergence for stochastic non-monotone problems.

  • Problem

    Extra-Gradient achieves O(1/t) for smooth monotone variational inequalities but requires two oracle calls per iteration, motivating lower-cost single-call alternatives.

  • Method

    The paper develops a synthetic approach to single-call extra-gradient algorithms and analyzes their deterministic, stochastic, monotone, and non-monotone convergence behavior.

  • Results

    O(1/t) convergence is achieved for deterministic monotone and stochastic strongly monotone variational inequalities, while the last iterate has O(1/t) local convergence for stochastic non-monotone problems under a second-order sufficient condition.

  • Takeaways & Limitations

    Single-call methods retain the optimal monotone rate while extending last-iterate convergence guarantees into stochastic non-monotone variational inequalities.

  • Takeaways & Limitations

    Stochastic local analysis must account for noise that can drive iterates outside a local solution’s attraction region, requiring substantially different and more intricate techniques.

Abstract

from arXiv · show

Variational inequalities have recently attracted considerable interest in machine learning as a flexible paradigm for models that go beyond ordinary loss function minimization (such as generative adversarial networks and related deep learning systems). In this setting, the optimal $\mathcal{O}(1/t)$ convergence rate for solving smooth monotone variational inequalities is achieved by the Extra-Gradient (EG) algorithm and its variants. Aiming to alleviate the cost of an extra gradient step per iteration (which can become quite substantial in deep learning applications), several algorithms have been proposed as surrogates to Extra-Gradient with a \emph{single} oracle call per iteration. In this paper, we develop a synthetic view of such algorithms, and we complement the existing literature by showing that they retain a $\mathcal{O}(1/t)$ ergodic convergence rate in smooth, deterministic problems. Subsequently, beyond the monotone deterministic case, we also show that the last iterate of single-call, \emph{stochastic} extra-gradient methods still enjoys a $\mathcal{O}(1/t)$ local convergence rate to solutions of \emph{non-monotone} variational inequalities that satisfy a second-order sufficient condition.

1 Introduction

The paper studies single-call surrogates for Extra-Gradient methods, motivated by the cost of two oracle calls, and establishes convergence guarantees across deterministic, stochastic, monotone, and non-monotone variational inequalities.

  • O(1/t) is the optimal convergence rate for smooth monotone variational inequalities and is achieved by Extra-Gradient and Mirror-Prox.
  • Single-call extra-gradient methods target lower oracle cost while retaining Extra-Gradient’s anticipatory behavior, which is valuable when gradient calculations are expensive.
  • O(1/t) is attained by 1-EG methods in deterministic monotone Lipschitz problems and stochastic strongly monotone problems for both ergodic averages and last iterates.
  • O(1/t) local convergence is obtained for the last iterate in stochastic non-monotone variational inequalities satisfying a second-order sufficient condition.
  • Stochastic geometric convergence techniques do not apply without maintained contraction, whereas the paper develops rate guarantees for stochastic settings without requiring bounded second moments.

2 Problem setup and blanket assumptions

The paper formulates variational inequalities through an operator and feasible set, measures solution quality with error functions, and analyzes stochastic oracle feedback under monotonicity and regularity assumptions.

  • Variational inequalities: A variational inequality seeks x⋆ ∈ X such that ⟨V(x⋆), x − x⋆⟩ ≥ 0 for every x ∈ X.
  • Examples: Variational inequalities encompass minimization, saddle-point, Nash equilibrium, and fixed-point problems.
  • Error measures: For monotone operators, the error and restricted error functions characterize solutions: a solution has zero error, and zero restricted error for sufficiently large domains implies a solution.
  • Assumptions: The baseline assumptions include a nonempty solution set, Lipschitz continuity, and monotonicity, with strong monotonicity imposed in some cases.
  • Stochastic oracle: A stochastic oracle returns noisy operator estimates, with deterministic perfect feedback recovered when the noise variance is zero.

3 Algorithms

The paper organizes single-call Extra-Gradient variants as proxies for the missing gradient, then shows when these methods coincide and when projections distinguish them.

  • Extra-Gradient uses a current-state oracle call to form a leading state, then updates the base state with information from that leading state.This anticipatory structure motivates single-call approximations.
  • Single-call variants retain the leading-state oracle call while replacing the intermediate update with proxies for the missing gradient.The paper examines PEG, RG, and OG as representative schemes.
  • PEG reuses the previous gradient, RG estimates the gradient from successive iterates, and OG combines the past-gradient proxy with a modified base-state update.RG and OG omit projection in the specified proxy updates.
  • The methods share a broad family structure determined by the proxy, the updated state, and the placement of projection operators.The paper notes that these choices generate a broad array of single-call Extra-Gradient methods.
  • Under identical initialization, constant step size, and no constraints, all presented 1-EG methods generate identical iterates.This equivalence holds for X = R^d; projected updates are closely related but no longer equivalent.

4 Deterministic analysis

The deterministic analysis establishes global ergodic and, under stronger conditions, last-iterate convergence for single-call Extra-Gradient variants, then derives local geometric convergence for regular non-monotone problems.

  • Global convergence: O(1/t) ergodic convergence holds for 1-EG algorithms on monotone problems with Lipschitz continuous operators.The result matches the optimal rate associated with the two-call Extra-Gradient method.
  • Global convergence: Theorem 1 assumes perfect oracle feedback and a constant step-size γ < 1/(cβ), with c depending on the algorithmic variant.Here c = 1 + √2 for RG and c = 2 for PEG and OG.
  • Global convergence: The global ergodic proof uses a quasi-descent inequality and a lemma tailored to time-averaged sequences.The argument compares successive iterates using Lipschitz continuity of V and treats the 1-EG variants in a unified way.
  • Global convergence: Under stronger assumptions, the last iterate converges geometrically to the unique solution at rate ∥X_t − x⋆∥ = O(exp(−ρt)).The guarantee applies when V satisfies Assumptions 1, 2, and 3(s), with a sufficiently small constant step-size.
  • Local convergence: For a regular solution, deterministic 1-EG initialized sufficiently nearby with a sufficiently small constant step-size converges locally at rate ∥X_t − x⋆∥ = O(exp(−ρt)).Regularity requires local C1 smoothness and a Jacobian that is positive-definite along rays from the solution.
  • Local convergence: The local proof shows that V behaves like a smooth, strongly monotone operator nearby and that the iterates remain inside the neighborhood.This localizes the global geometric-convergence argument to the attraction region.

5 Stochastic analysis

The stochastic analysis establishes O(1/t) convergence for single-call methods in both strongly monotone and locally non-monotone settings. Experiments illustrate these rates and report that 1-EG consistently outperforms EG in oracle calls at fixed step-size.

  • Global convergence: The PEG variant is analyzed using stochastic oracle feedback, with a decreasing step-size γ_t = γ/(t + b).The stated conditions require γ > 1/α and sufficiently large b.
  • Experiments: In experiments, 1-EG consistently outperforms EG in oracle calls at fixed step-size, while observed rates match the paper’s theoretical rates.The experiments include deterministic linear convergence, deterministic ergodic O(1/t), and stochastic non-monotone local O(1/t) settings.
  • Global convergence: The last-iterate proof uses stochastic quasi-Fejér properties and sequence estimates rather than contraction or averaging.These tools control the summability error under the method’s specific step-size.
  • Local convergence: For regular solutions of non-monotone variational inequalities, the method remains in a neighborhood with arbitrarily high probability and achieves a local O(1/t) rate.The result is conditioned on an event that all iterates remain inside the local neighborhood.
  • Local convergence: The certified initialization basin and convergence rate trade off through the neighborhood size: enlarging it increases the basin but worsens the rate constants.Specifically, M increases while α decreases as the neighborhood grows.

6 Concluding remarks

The concluding remarks frame the paper as a synthetic treatment of single-call Extra-Gradient surrogates with optimal rates across deterministic, stochastic, and non-monotone settings. They also identify broader proximal and adaptive extensions as future work.

  • Concluding remarks: The paper provides a synthetic view of single-call surrogates to Extra-Gradient across deterministic, stochastic, and non-monotone settings.The stated goal is to establish optimal convergence rates in this range of settings.
  • Future work: The authors leave extensions to more general Bregman proximal settings and adaptive versions for future work.The adaptive direction is linked to recent work on two-call methods.
  • Technical support: The appendix develops projection inequalities and sequence lemmas that support the convergence analysis.These include projection identities, Young’s inequality, and a Chung-type numerical-sequence lemma.
  • Technical support: Regular solutions yield local Lipschitz and coercivity properties used in the non-monotone local analysis.A neighborhood is constructed where V is β-Lipschitz and satisfies a quadratic inner-product bound with α > 0.

B.1 Proof of Lemma 2

The proof of Lemma 2 bounds the cumulative variational-inequality error by telescoping distance terms and monotonicity.

  • Proof strategy: Summing the fundamental inequality produces a telescoping bound involving the initial and final distances and auxiliary terms.The bound is formed over the iterates and retains a cumulative inner-product term.
  • Proof strategy: Monotonicity and boundedness over the restricted set control the initial-distance term by R^2.For p in X_R, the proof uses ||X_1 − p||^2 ≤ R^2.
  • Proof strategy: Dividing by the cumulative step-size sum converts the bound into an ergodic convergence estimate.The normalization is performed by dividing through by 2 times the partial sum of step sizes.

B.2 Proof of Theorem 1

The proof of Theorem 1 treats PEG, OG, and RG through a common projection inequality and method-specific telescoping bounds. These bounds establish a shared convergence framework and yield loss-minimization and min-max consequences.

  • Reflected Gradient: RG is handled analogously, with initialization constraints arising from its specific formulation.The proof uses different initial states for RG and obtains the same result structure.
  • Common framework: PEG, OG, and RG are analyzed with the same technical projection lemma and common step-size structure.The proof explicitly emphasizes a shared analysis through Lemma A.2.
  • Past Extra-Gradient: For PEG, Lipschitz continuity and projection inequalities produce a telescoping error bound.The resulting bound applies under the method’s step-size conditions.
  • Applications: For monotone loss minimization, Jensen’s inequality converts the variational-inequality bound into a guarantee for the averaged point.The argument uses V = ∇f and monotonicity-induced convexity.
  • Applications: For convex-concave min-max problems, the same analysis controls solution quality through the Nikaido–Isoda function.The operator is V = (∇θL, −∇φL), and the proof applies convex-concavity.

B.4 Proof of Theorem 4

The proof establishes local geometric convergence by choosing sufficiently small constant stepsizes and sufficiently close initial points so all iterates remain in a suitable neighborhood.

  • Local invariance: The proof targets local geometric convergence by ensuring all iterates remain in K, using sufficiently small constant stepsizes and nearby initialization.The argument relies on Theorem 2 after establishing the required local positivity condition.
  • Local invariance: The operator is Lipschitz on the compact neighborhood K, enabling the one-call extra-gradient methods’ quasi-descent bound for sufficiently small γ.The proof invokes the Lipschitz property of V on K and the bound from Appendix B.2.
  • Feasibility: For PEG and OG, feasibility of intermediate iterates follows from their construction, while RG requires strengthening the regular-solution condition to tangent-span directions.RG may evaluate V at infeasible points, so the condition must cover all z in the tangent span of X.
  • Feasibility: A sufficiently small γ controls the intermediate-step displacement through boundedness of V and projection non-expansiveness.The proof chooses γ ≤ r/(2M), where M bounds the operator on K.
  • Inductive conclusion: Induction preserves both the distance bound to x⋆ and membership of intermediate iterates in K across all iterations.The initialization is selected so the first-step conditions hold, after which the inductive argument applies repeatedly.
  • Stochastic setup: The PEG proof uses its natural filtration so the intermediate iterate is measurable and the stochastic oracle noise has conditional mean zero.For PEG, F_t = F_{t+1/2}, making the zero-mean condition applicable conditionally on F_t.

C.1 Proof of Theorem 5

The proof derives last-iterate and ergodic convergence from a stochastic one-step inequality, then obtains the ergodic result by applying Jensen’s inequality to the last-iterate analysis.

  • Last iterate convergence: The proof applies Lemma A.2 to the algorithmic iterates and the solution x⋆ to derive the central stochastic inequality.The trial-point substitution includes the generated iterates, operator estimates, and x⋆.
  • Last iterate convergence: Conditional expectation, Young’s inequality, Lipschitz continuity, and projection non-expansiveness control the stochastic error terms.The proof bounds operator differences and noise contributions before taking expectations.
  • Last iterate convergence: The solution’s uniqueness supplies the variational-inequality relation used to control the inner product involving V(x⋆).This relation enters the one-step estimate for the generated intermediate iterate.
  • Last iterate convergence: The resulting recurrence yields the last-iterate convergence bound after choosing q = αγ, q′ = 6γ^2σ^2, and t0 = 2.The positive second term on the left-hand side allows the stated inequality to follow directly.
  • Ergodic convergence: The ergodic convergence of the weighted average follows from the last-iterate estimate by Jensen’s inequality.The proof directly transfers the established bound to the averaged sequence.

C.2 Proof of Theorem 6

The proof establishes local stochastic convergence by controlling iterates on nested high-probability events, deriving a recurrence, and then choosing the batch size sufficiently large.

  • Event construction: The proof defines nested events and shows that remaining in the controlled neighborhood propagates from one iteration to the next.Lemma C.1 establishes H_{T−1} ⊆ E_T by induction, beginning with the initialization event.
  • Event construction: Initialization and projection non-expansiveness provide the base-case distance and intermediate-iterate bounds needed for induction.The first intermediate step is shown to remain within the neighborhood using the initial distance assumption and a displacement bound.
  • Inductive control: The inductive step preserves the distance bound and neighborhood membership, with ∥X_{T+1} − x⋆∥^2 ≤ 7r^2/16 on the controlled event.The proof combines the induction hypothesis with the one-step estimate and event definitions.
  • Stochastic recurrence: A recurrence for the auxiliary quantity Q_t is obtained by decomposing it into S_t^2 and R_t and exploiting the conditional zero-mean noise term.The martingale contribution vanishes after conditioning on the filtration.
  • Stochastic recurrence: Bounding the noise and operator terms yields the recurrence inequality, which is then summed to control the probability of leaving the neighborhood.The proof combines the component bounds and substitutes them into the recurrence before summation.
  • High-probability conclusion: Because Γ tends to zero as b grows, choosing a sufficiently large batch size gives P(E_T) ≥ 1 − δ for all T.The event sequence is decreasing, allowing the probability guarantee to extend across iterations.
  • Scope of assumptions: The stochastic assumptions need only hold locally on the event that the intermediate iterate lies in U, rather than globally.This yields a local noise-boundedness requirement for the local convergence guarantee.
Loading 1908.08465v2…