math.OCMay 29, 2026

A Unifying View of Anchoring via Operator-Side Tikhonov Regularization

Authors: Zihao Chen

Organizations: UC Berkeley

Abstract

Anchored fixed point and monotone equation methods, including Halpern iteration, extra anchored gradient, and their relatives, add a vanishing pull toward a reference point to obtain last-iterate guarantees. Existing anchored variants often achieve sharp last-iterate guarantees, but from the update-level perspective the placement of the anchor can be algorithm-specific and conceptually opaque. We show that anchoring admits a single operator-side construction: regularize the operator queried by the base method with a vanishing Tikhonov term, then run the unmodified base method. Applied to the Picard iteration, this recipe reproduces the Halpern iteration; applied to the forward step, extragradient (EG), and past extragradient (PEG, also known as Popov's method), it yields three variants whose anchor placements inherit the base method's query pattern. The forward-step instantiation gives a new residual convergence guarantee, while the EG and PEG instantiations give new regularized variants. The four analyses share a residual recurrence, recovering the O(1/k)O(1/k) Halpern residual-norm convergence rate, giving O(1/k)O(1/\sqrt{k}) for the regularized forward step, and giving O(1/k)O(1/k) for the regularized EG and PEG variants in the unconstrained monotone Lipschitz setting.

Explore similar work

CardsList
Jun 19, 2026math.OC

Accelerated and Stable Convergence with Anchored Optimistic Method

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/k2)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/k)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.
Motahareh Sohrabi, Jianxin You, Simon Lacoste-Julien +2
Convergence AnalysisFlat MinimaConvergenceAcceleration
AskPDF
Aug 9, 2026math.OC

Halpern Iteration Achieves \tilde{\mathcal{O}}(ε^{-1/p}) pth-Order Oracle Complexity for Monotone Variational Inequalities

We study second- and higher-order methods for solving smooth monotone variational inequalities (MVI). Monteiro and Svaiter (SIAM J. Optim., 2012) showed that a second-order method, NPE, converges at the rate of O(T−1.5)\mathcal{O}(T^{-1.5}). For convex-concave minimax optimization, a subset of MVI problems, Chen, Liu, Luo, and Zhang (COLT 2025) recently improved the complexity to O~(T−1.75)\tilde{\mathcal{O}}( T^{-1.75}) . However, it is open whether the conjectured complexity for MVI can be improved. In this paper, by using a large-step inexact Halpern iteration, we propose a novel Halpern-NPE method that achieves an even faster rate of O~(T−2)\tilde{\mathcal{O}}(T^{-2}) for solving MVIs. We also provide the ppth-order generalization of our method. We first introduce an Anchored Tensor Method (ATM) that achieves the rate of O(T−(p−1))\mathcal{O}(T^{-(p-1)}), and then combine it with the Halpern iteration to achieve a faster convergence rate of O~(T−p)\tilde{\mathcal{O}}(T^{-p}). This improves all prior results for p≥2p \ge 2 and matches the classical extragradient method for p=1p=1.
Lesi Chen, Xinliang Zhang, Hengyu Wang +3
Alternating Direction Method Of MultiplierSharp Joint-Kl Oracle TheoryOptimal Sample Complexity
AskPDF
Sep 14, 2026math.OC

Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities

We analyze a stochastic algorithm with Halpern anchoring for constrained convex-concave problems and monotone variational inequalities. This algorithm is single-loop and single-call since it uses one unbiased sample of the gradient operator at every iteration to be applicable to monotone games with noisy feedback. With tt denoting the iteration counter, we prove the anytime last-iterate convergence rate of O(t−1/4)O(t^{-1/4}) for both gradient-mapping norm and restricted gap, improving the best-known rate O(t−1/5)O(t^{-1/5}) that was obtained for the restricted gap function. Our rates cover constrained problems with a potentially unbounded feasible set as well as a structured class of stochastic oracles without a bounded variance.
Jun-Hyun Kim, Ahmet Alacaoglu
Stochastic Smooth Convex OptimizationResidual Anchoring
AskPDF