Iterative Anchoring for Accelerated Optimization

21 concepts15 papers1 proposal

In the landscape of first-order optimization, Nesterov’s accelerated gradient descent stands as a gold standard. By incorporating momentum—effectively extrapolating a step based on the velocity of recent updates—it speeds up convergence from the standard $O(1/k)$ to $O(1/k^2)$ for convex functions.

However, Nesterov’s momentum has a critical blind spot: it is designed for minimization. When optimization moves beyond simple loss surfaces to minimax problems (such as training Generative Adversarial Networks) or general fixed-point equations, momentum often causes algorithms to fail. Instead of accelerating toward a solution, momentum can amplify the rotational forces inherent in saddle-point landscapes, causing the optimizer to cycle endlessly or spiral outward into divergence.

To solve this, a different acceleration paradigm has emerged: iterative anchoring. Instead of looking back at the immediate past to build momentum, anchoring periodically pulls the current iterate back toward a fixed reference point—typically the initial starting state. This simple mechanism acts as a stabilizing centripetal force, damping oscillations and unlocking optimal acceleration for complex operator equations.


The Core Mechanism: From Momentum to Anchoring

To understand why anchoring works, it is helpful to contrast it with classical fixed-point iterations. Suppose we want to find a fixed point of a nonexpansive operator $T$, meaning we want to solve $T(x) = x$. A standard Picard iteration simply applies the operator repeatedly: $x_{k+1} = T(x_k)$. If $T$ contains rotational components, this trajectory can easily loop forever.

The anchoring paradigm, rooted in classical Halpern iteration, modifies this update by taking a convex combination of the operator's output and the initial starting point $x_0$:

$$x_{k+1} = \beta_k x_0 + (1 - \beta_k) T(x_k)$$

Here, $\beta_k \in (0, 1)$ is a time-decaying sequence that dictates the strength of the pull toward the anchor.

Nesterov Momentum:   [x_k-1] ---> [x_k] ---> (Extrapolate forward based on velocity)
Iterative Anchoring: [x_0] <=== (Pull backward) === [x_k] ---> [T(x_k)]

As analyzed by Jisun Park et al. in Exact Optimal Accelerated Complexity for Fixed-Point Iterations, this anchoring mechanism is fundamentally more effective than momentum-based techniques for general fixed-point problems. While momentum accelerates by pushing the iterate further along its current trajectory, anchoring provides a robust way to damp oscillations and stabilize the trajectory toward the solution, achieving the exact theoretically optimal accelerated complexity bounds for contractive and nonexpansive operators.


Why It Works: Intuition from Three Perspectives

The success of anchoring across various optimization domains can be attributed to three distinct mathematical behaviors.

1. Vanishing Regularization and Artificial Monotonicity

In minimax optimization and variational inequalities, algorithms frequently struggle with non-monotone landscapes where gradients do not point cleanly toward the equilibrium. As explored by Motahareh Sohrabi et al. in Accelerated and Stable Convergence with Anchored Generalized Optimistic Method, the anchor term functions as a vanishing regularizer.

Early in the optimization process, when $\beta_k$ is relatively large, the anchor exerts a strong pull. This pull induces an "artificial strong monotonicity," effectively tilting a flat or treacherous landscape toward the anchor point and preventing the algorithm from wandering off. As the iterations progress and $\beta_k$ decays toward zero, this artificial bias fades away, ensuring that the algorithm ultimately converges to the true, unbiased solution of the original problem.

2. Damping Rotational Dynamics in Continuous Time

To build physical intuition, it is valuable to look at optimization through the lens of continuous-time ordinary differential equations (ODEs). In Continuous-time Analysis of Anchor Acceleration, Jaewook J. Suh et al. demonstrated how anchor acceleration balances the forward movement of an operator with a contractive force toward the starting state.

In a standard minimax system, the continuous trajectory behaves like an undamped pendulum, orbiting the saddle point indefinitely. The anchor term introduces a specific form of friction or damping that is relative to the origin $x_0$. This friction absorbs the kinetic energy generated by rotational gradients, forcing the continuous trajectory to spiral inward toward the equilibrium rather than outward.

3. Parameter-Free Robustness

Standard acceleration methods often require precise knowledge of problem-specific constants, such as the Lipschitz constant or the hyperparameter choices of the objective function. Halpern-style anchoring bypasses this requirement.

In Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities, Jelena Diakonikolas showed that the constant pull toward the anchor point allows fixed-point iterations to handle non-cocoercive operators and unbounded sets robustly without needing prior knowledge of these parameters, yielding a near-optimal $1/k$ convergence rate out of the box.


Taming Minimax Problems and Games

The most prominent application of anchoring is in smooth and structured minimax optimization, where Nesterov momentum fails completely.

Reaching the $O(1/k^2)$ Speed Limit

For a long time, it was an open question how to achieve an accelerated convergence rate for the squared gradient norm in smooth convex-concave minimax problems. TaeHo Yoon et al. solved this by introducing the Extra Anchored Gradient (EAG) algorithm in Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k^2) Rate on Squared Gradient Norm. By substituting Nesterov-style momentum with a reference to the starting state, EAG prevents the optimization path from cycling around saddle points and achieves the theoretically optimal $O(1/k^2)$ rate.

Single-Call Efficiency and Point Convergence

Traditional accelerated methods often require multiple gradient evaluations per step, which doubles the computational overhead. Iterative anchoring removes this necessity. Yang Cai et al. demonstrated in Accelerated Single-Call Methods for Constrained Min-Max Optimization that integrating anchoring into single-call gradient methods acts as a regularizer that unlocks optimal acceleration speeds without multi-call overhead.

Furthermore, in non-monotone landscapes—which are notoriously difficult because algorithms can oscillate indefinitely without settling—the authors proved in Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion that anchoring guarantees point convergence, ensuring the algorithm actually stabilizes on a specific equilibrium. This property is vital in game theory; for instance, Yang Cai et al. utilized anchored updates in Doubly Optimal No-Regret Learning in Monotone Games to achieve the fastest possible last-iterate convergence to a Nash Equilibrium while maintaining optimal adversarial regret bounds.


Robustness to Noise and Unbounded Spaces

Real-world optimization rarely happens with perfect gradients; stochastic noise is a constant challenge. When optimization domains are unconstrained or unbounded, noise can compound, causing standard extragradient methods to drift and blow up. Anchoring provides a mathematical safety net in these scenarios.

Without Anchoring: [Noise Accumulates] ---> Iterate drifts further away ---> Noise increases ---> Divergence
With Anchoring:    Iterate drifts ---> [Anchor Pulls Back] ---> Trajectory stabilized

In Solving Stochastic Variational Inequalities without the Bounded Variance Assumption, Ahmet Alacaoglu et al. analyzed settings where gradient noise grows proportionally to the magnitude of the optimization variables. They showed that pulling iterates toward a fixed reference point provides the necessary stabilization to prevent divergence in unbounded search spaces, even when the standard assumption of bounded variance is completely discarded.

Similarly, Jiseok Chae et al. showed in Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements that anchoring updates via a convex combination of an epoch's starting and ending points effectively cancels out high-order noise, preventing stochastic trajectories from spiraling away from the optimal solution.


Application Beyond Gradients: Reinforcement Learning

Because anchoring is fundamentally a tool for accelerating fixed-point iterations, its utility extends far beyond gradient-based optimization. A prime example is Value Iteration (VI) in Reinforcement Learning, which aims to find the fixed point of the Bellman optimality operator.

Standard Value Iteration converges slowly when the discount factor $\gamma$ is close to 1, and it can fail to converge entirely in undiscounted, average-reward settings due to value drift (where the value function grows uniformly without bounding).

Standard Value Iteration:  V_k+1 = B(V_k)          (Drifts or slows down as gamma -> 1)
Anchored Value Iteration:  V_k+1 = B_k V_0 + (1-B_k) B(V_k)  (Stabilizes values, forces O(1/k) convergence)

To address this, JongMin Lee et al. introduced Anc-VI in Accelerating Value Iteration with Anchoring. By blending the Bellman update with an initial value function estimate $V_0$, they stabilized the contractive operator and achieved an optimal $O(1/k)$ convergence rate for Bellman error, even when the contraction factor is near unity. The authors extended this principle to average-reward Markov Decision Processes in Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes, demonstrating that the anchor provides a rigid mathematical constraint that prevents value drift in environments where a standard fixed point does not explicitly exist.


Broader Optimization Context

While anchoring is primarily celebrated for fixed-point and minimax problems, its stabilizing properties also offer benefits in pure minimization. For instance, in highly non-convex landscapes where optimization trajectories can become chaotic, Zeyuan Allen-Zhu demonstrated in Natasha: Faster Non-Convex Stochastic Optimization via Strongly Non-Convex Parameter that regularizing updates toward a periodic anchor point prevents chaotic trajectories in regions of negative curvature. This allows the use of larger learning rates and ensures a more systematic exploration of the parameter space. Furthermore, Hideaki Iiduka showed in Proximal Point Algorithms for Nonsmooth Convex Optimization with Fixed Point Constraints that anchoring is highly effective for selecting a unique, stable solution from a set of multiple optimal points in nonsmooth convex optimization.

Ultimately, anchoring shifts our perspective on acceleration. While Nesterov momentum accelerates by looking backward to push forward, anchoring accelerates by looking backward to pull inward. For the complex, rotational, and noisy landscapes of modern machine learning, this stabilizing pull is exactly what is needed to keep optimization on track.

Key Foundational Work

Natasha: Faster Non-Convex Stochastic Optimization via Strongly Non-Convex Parameter (2017) — contributed 2 concept elements to this direction.
Proximal Point Algorithms for Nonsmooth Convex Optimization with Fixed Point Constraints (2016) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_halpern_iteration_2e209e52,
  title = {Halpern iteration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/halpern-iteration/rdr_2e209e52bfa74c70a11f8ce5ad6a803c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_halpern_iteration_2e209e52_v1,
  title = {Halpern iteration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/halpern-iteration/rdr_2e209e52bfa74c70a11f8ce5ad6a803c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake