Stochastic Moving Anchor Algorithms and a Popov’s Scheme with Moving Anchor

James K. Alcala, Yat Tin Chow, Mahesh Sunkula · 2025

Read Stochastic Moving Anchor Algorithms and a Popov’s Scheme with Moving Anchor by James K. Alcala, Yat Tin Chow, Mahesh Sunkula (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-07290.txt.

Introduction

James Alcala, Yat Tin Chow, and Mahesh Sunkula give moving-anchor algorithms a stochastic form in two thousand twenty-five. Anchor methods speed up extragradient schemes for saddle problems, the tug-of-war tasks behind much machine learning. Their proofs, though, assumed exact answers from the oracle, while real problems use noisy samples.

The team moves the anchor step by step rather than fixing it, and lets the oracle answer with random draws. They prove fast convergence still holds in that noisy world, and bench tests back the math. A trial Popov variant, a leaner cousin scheme, also shows promise, hinting at a wider theory still to be built. The work bridges tidy proofs and messy practice.

Catalog record

CREATORJames K. Alcala, Yat Tin Chow, Mahesh Sunkula
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-07290

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Stochastic Moving Anchor Algorithms and a Popov’s Scheme with Moving Anchor Thanks: James K. Alcala was partially supported by a UCR Dissertation Year Program Award. Thanks: Yat Tin Chow is partially supported by a Regents’ Faculty Fellowship at the University of California, Riverside, and by NSF DMS-2409903 and ONR N00014-24-S-B001. James K. Alcala, Yat Tin Chow, Mahesh Sunkula Abstract . Since their introduction, anchoring methods in extragradient-type saddlepoint problems have inspired a flurry of research due to their ability to provide order-optimal rates of accelerated convergence in very general problem settings. Such guarantees are especially important as researchers consider problems in artificial intelligence (AI) and machine learning (ML), where large problem sizes demand immense computational power. Much of the more recent works explore theoretical aspects of this new acceleration framework, connecting it to existing methods and order-optimal convergence rates from the literature. However, in practice introducing stochastic oracles allows for more computational efficiency given the size of many modern optimization problems. To this end, this work provides the moving anchor variants [ 1 ] of the original anchoring algorithms [ 36 ] with stochastic implementations and robust analyses to bridge the gap from deterministic to stochastic algorithm settings. In particular, we demonstrate that an accelerated convergence rate theory for stochastic oracles also exists for our moving anchor scheme, itself a generalization of the original fixed anchor algorithms, and provide numerical results that validate our theoretical findings. We also develop a tentative moving anchor Popov scheme based on the work in [ 33 ] , with promising numerical results pointing towards an as-of-yet uncovered general convergence theory for such methods. 1. Introduction Saddle point problems of the form (1.1) \displaystyle\min_{x\in\mathbb{R}^{n}}\max_{y\in\mathbb{R}^{m}}f(x,y), also known as minimax or min-max problems, continue to be the object of intense study amongst researchers in a wide variety of disciplines. Applications of such problems classically include economics and game theory, with more recent applications including mean field games [ 28 ] , as well as artificial intelligence and machine learning applications such as generative adversarial nets [ 5 ] , [ 13 ] and reinforcement learning [ 10 ] . Recently, researchers have explored the Halpern iteration [ 16 ] , [ 23 ] as an acceleration mechanism in monotone inclusion problems [ 9 ] and for minimax problems more specifically with a Halpern-inspired method known as anchoring [ 30 ] . This latter line of inquiry has proved especially fruitful, as the well-established extragradient method [ 18 ] combined with anchoring yields an accelerated \Omega(1/k^{2}) convergence rate on the squared gradient norm for smooth-structured convex-concave minimax problems - this remarkable order-optimal result is thanks to the introduction of the extra-anchored gradient, or EAG, method and its variants [ 36 ] . This anchoring mechanism has been applied, for example, to develop an anchored Popov’s scheme [ 29 ] and a splitting version of EAG [ 33 ] , and has recently been connected [ 32 ] to Nesterov’s classical Accelerated Gradient Method, or AGM [ 27 ] . Another important work [ 20 ] extended the initial results of the EAG methods to problem settings involving negative comonotone operators via the similar fast extra gradient algorithm, or FEG, which extends this fast acceleration rate to certain nonconvex-nonconcave problems. This latter work also introduced the first stochastic anchored algorithm, which to our knowledge was the first instance of stochastic oracles involving anchored algorithms. These authors also introduced the ‘semi’-anchoring [ 21 ] in a multi-step descent/ascent framework with a unique anchor occurring at each step of the multi-step, a generalization of the initial anchoring mechanism that relies solely on the initial point to be the anchor. In this vein, [ 1 ] recently developed variants of EAG [ 36 ] and FEG [ 20 ] algorithms by introducing a moving anchor into both frameworks. These ‘moving anchor’ algorithms retain order-optimal convergence rates on the squared gradient norm in both convex-concave and the negative comonotone settings, and generalize the analyses of the previous works to acommodate this new moving anchor structure. Most notably, the numerical experiments featured in this work show that moving anchor variants of EAG and FEG algorithms are faster than their fixed-anchor counterparts by a constant across numerous problem settings. However, the strengths of the moving anchor algorithms over their fixed-anchor cousins are poorly understood, and most numerical examples are deterministic and toy examples. To wit, the contributions of this paper are as follows. (1) Stochastic moving anchor algorithms are developed following [ 1 ] . Specifically, stochastic EAG moving anchor algorithms are defined and analyzed via a conventional Lyapunov functional analysis. These analyses follow in the footsteps of the stochastic complexity results of [ 20 ] but generalize to the moving anchor setting. Convergence results follow with minimal assumptions tacked on to the deterministic algorithm assumptions in [ 1 ] , and rely on control over variance terms. (2) Numerous numerical examples further compare stochastic moving anchor algorithms to their fixed-anchor counterparts to characterize further the nature of the moving anchor’s convergence improvements. (3) A moving anchor Popov’s scheme with preliminary numerical results showing accelerated order-optimal convergence rates that are faster than their fixed anchor counterparts by a constant. The theory for these methods is underdeveloped, but our preliminary work suggests a robust underlying convergence theory that greatly generalizes the fixed anchor methods found in [ 33 ] . 2. Literature Review 2.1. Stochastic Saddlepoint Algorithms Because of the computational advantages of stochastic optimization algorithms in modern optimization, the current literature on stochastic saddlepoint problems is deep and rich. For general saddlepoint algorithms, we restrict ourselves to a few recent and interesting results. For the setting with decision-dependent distributions, focusing on certain fixed points of training enables the construction of powerful derivative-free algorithms [ 34 ] . It has also been shown that stochastic saddlepoint algorithms with guarantees on their ‘strong gap’ (as opposed to their weak gap, a primal-dual gap taken in expectation over the sample space) avoid spurious convergence rate discrepancies on even simple problems [ 3 ] . Researchers also used the Maurey Sparsification Lemma to obtain a stochastic saddlepoint algorithm in the polyhedral setting that isn’t based on Frank-Wolfe methods, the first of its kind [ 12 ] . The setting of stochastic extragradient algorithms is also particularly well-studied, and is of interest to the authors of this paper. In [ 14 ] , a general framework is developed to study and prove results for a variety of specific stochastic extragradient methods. The authors of [ 22 ] show that in the bilinear problem setting when equipped with iteration averaging and restarting, stochastic extragradient goes beyond converging to a fixed neighborhood of the Nash equilibrium solution, and eventually reaches the equilibrium point. The last work we mention combines the celebrated Nesterov acceleration [ 27 ] with extragradient, known as AG-EG [ 38 ] , brings optimal convergence rates for strongly monotone variational inequalities (of which saddlepoint problems are a special class), and even attains convergence rates matching lower bounds for bilinearly-coupled strongly-convex strongly-concave saddlepoint problems. 2.2. Extragradient and Halpern Variants in Optimization The Halpern iteration [ 16 ] is an algorithm that finds fixed-points given a nonexpanding map, and has proven

Read the complete text