Accelerated and Stable Convergence with Anchored Optimistic Method

• URL: http://arxiv.org/abs/2606.21528v1
• Date: Fri, 19 Jun 2026 15:26:10 GMT
• Title: Accelerated and Stable Convergence with Anchored Optimistic Method
• Abstract summary: We study first-order methods for solving monotone variational inequalities arising in min-max optimization.<n>We propose a family of Generalized Optimistic Methods with Anchoring (GOMA), which combine two-time-scale optimistic updates with an anchoring term inspired by Halpern iteration.
• Score: 39.242061448272615
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study first-order methods for solving monotone variational inequalities arising in min-max optimization. Classical approaches such as the extragradient method rely on two gradient queries per iteration, which limits their analysis and applicability in the online and stochastic settings. We propose a family of Generalized Optimistic Methods with Anchoring (GOMA), which combine two-time-scale optimistic updates with an anchoring term inspired by Halpern iteration. In the deterministic setting, GOMA achieves the optimal accelerated last-iterate rate $O(1/k^2)$ on the squared gradient norm for monotone Lipschitz operators. In the stochastic setting with unbounded variance, a simplified single-call variant of GOMA achieves a last-iterate convergence rate of $O(1/\sqrt{k})$ on the squared gradient norm. To the best of our knowledge, this is the first such guarantee for stochastic monotone Lipschitz variational inequalities in the unconstrained setting without variance reduction or growing batches.

Related papers

• Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities [8.350639529216876]
  This algorithm is single-loop and single-call since it uses one unbiased sample of the operator at every iteration to be applicable to monotone games with noisy feedback.<n>We prove the anytime last-iterate convergence rate of $O(t-1/4)$ for both gradient-mapping norm and restricted gap.
  arXiv  Detail & Related papers  (2026-09-14T09:17:23Z)
• The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization [50.59470683896735]
  min-max optimization has attracted increasing attention due to its applications in modern machine learning.<n>We provide a comprehensive theoretical of gradient descent (SGDA)<n>We develop new clipping-free algorithms, i.e., Stoc-GDAM and Stoc-TRmax, and they both can achieve the optimal dependence on the target accuracy without using gradient clipping.
  arXiv  Detail & Related papers  (2026-09-05T12:49:28Z)
• OptMuon: Closed-Loop Orthogonalized Momentum Methods for Stochastic Optimization with Zero-Noise Optimality [23.28384210732827]
  We show that closed-loop scalar momentum.<n>optimization can be combined with Muon-style momentum.<n>optimization while retaining noise adaptivity and zero-noise optimality up to logarithmic factors.<n>These results show that OptMuon-A achieves the noise-rate.<n>(tildemathcal O(T-1/2+1/2T--1/2)) under average smoothness, while OptMuon-I achieves the noise-rate.<n>(tildemathcal O(T-1/2+
  arXiv  Detail & Related papers  (2026-06-07T18:59:24Z)
• Stochastic Auto-conditioned Fast Gradient Methods with Optimal Rates [3.083659340977661]
  We propose a variant of the auto-conditioned fast gradient method, referred to as AC-FGM.<n>The proposed method is fully adaptive to the Lipschitz constant, the horizon, and the noise level, enabling both adaptive stepsize selection and adaptive mini-batch sizing without line-search procedures.
  arXiv  Detail & Related papers  (2026-04-07T23:43:48Z)
• OptEMA: Adaptive Exponential Moving Average for Stochastic Optimization with Zero-Noise Optimality [23.28384210732827]
  We introduce OptEMA and analyze two novel variants: OptEMA-M and OptEMA-V.<n>OptEMA is closed-loop and Lipschitz-free in the sense that its effective stepsizes are trajectory-dependent and do not require the Lipschitz constant for parameterization.<n>Both variants achieve a noise-adaptive convergence rate of $widetildemathcalO(T-1/2+1/2 T-1/4)$ for the average gradient norm, where $$ is the noise level.
  arXiv  Detail & Related papers  (2026-03-10T17:19:54Z)
• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  We focus on the class of (strongly) convex $(L0)$-smooth functions and derive new convergence guarantees for several existing methods.<n>In particular, we derive improved convergence rates for Gradient Descent with smoothnessed Gradient Clipping and for Gradient Descent with Polyak Stepsizes.
  arXiv  Detail & Related papers  (2024-09-23T13:11:37Z)
• Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
  We propose a new first-order optimization algorithm -- AcceleratedGradient-OptimisticGradient (AG-OG) Ascent. We show that AG-OG achieves the optimal convergence rate (up to a constant) for a variety of settings. We extend our algorithm to extend the setting and achieve the optimal convergence rate in both bi-SC-SC and bi-C-SC settings.
  arXiv  Detail & Related papers  (2022-10-31T17:59:29Z)
• Accelerated Single-Call Methods for Constrained Min-Max Optimization [5.266784779001398]
  Existing methods either require two gradient calls or two projections in each iteration, which may costly in some applications. In this paper, we first show that a variant of the Optimistic Gradient (RGOG) has a rich set of non-comonrate min-max convergence rate problems. Our convergence rates hold for standard measures such as and the natural and the natural.
  arXiv  Detail & Related papers  (2022-10-06T17:50:42Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  We show that an increasing large momentum parameter for the first-order moment is sufficient for adaptive scaling.<n>We also give insights for increasing the momentum in a stagewise manner in accordance with stagewise decreasing step size.
  arXiv  Detail & Related papers  (2021-04-30T08:50:24Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.