Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems

Ruichen Jiang; TaeHo Yoon

math.OCSep 24, 2026

Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems

Authors: Ruichen Jiang, TaeHo Yoon

Organizations: Google Research · Johns Hopkins University

Abstract

We study the deterministic oracle complexity of finding approximate solutions to composite monotone inclusion problems, formed by the sum of a smooth single-valued monotone operator and a maximally monotone set-valued operator, under the tangent-residual criterion. We introduce the Anchored Extra-Proximal (AEP) framework, which combines an anchored extrapolation step with an inexact anchored proximal update satisfying a relative-error condition. The framework recovers the composite Fast Extragradient method in the first-order setting and yields natural second- and higher-order extensions by replacing the operator in the implicit update with its Taylor approximation at the extrapolated point. For every $p\geq 2$ , assuming that the $(p-1)$ th derivative of the single-valued operator is Lipschitz continuous, we combine this construction with a bisection line search to obtain a $p$ th-order method that finds a point with tangent residual at most $\varepsilon$ in $\widetilde{O}(\varepsilon^{-2/(3p-1)})$ oracle calls. This improves all prior upper bounds for $p$ th-order methods: in particular, it improves the previous best-known $\widetilde{O}(\varepsilon^{-1/p})$ tangent-residual complexity as well as the classical $O(\varepsilon^{-2/(p+1)})$ bound of higher-order hybrid proximal extragradient methods under the weaker duality-gap criterion. We complement this result with a worst-case lower bound of $Ω(\varepsilon^{-2/(3p-1)})$ for every deterministic algorithm in the $p$ th-order oracle model, without restricting the algorithm to tensor steps or any other prescribed update structure. Thus, the proposed method attains the optimal dependence on $\varepsilon$ , up to logarithmic factors, for all $p\geq2$ .

Figures & tables

\vskip-9.24994pt{\bm{r}}_{k+1}\in a_{k}\mathds{F}({\bm{z}}_{k+1})+a_{k}\mathds{H}({\bm{z}}_{k+1})+{\bm{z}}_{k+1}-\Bigl(\frac{a_{k}}{A_{k}+a_{k}}{\bm{z}}_{0}+\frac{A_{k}}{A_{k}+a_{k}}{\bm{z}}_{k}\Bigr),\hskip 9.24994pt\|{\bm{r}}_{k+1}\|\leq\rho\|{\bm{z}}_{k+1}-{\bm{z}}_{k+\frac{1}{2}}\|.

Algorithm 1 Anchored Extra-Proximal Method

\vskip-9.24994pt0\in a_{k}\bigl(\mathds{F}({\bm{z}}_{k+\frac{1}{2}})+D\mathds{F}({\bm{z}}_{k+\frac{1}{2}})({\bm{z}}_{k+1}-{\bm{z}}_{k+\frac{1}{2}})\bigr)+a_{k}\mathds{H}({\bm{z}}_{k+1})+{\bm{z}}_{k+1}-\frac{a_{k}}{A_{k}+a_{k}}{\bm{z}}_{0}-\frac{A_{k}}{A_{k}+a_{k}}{\bm{z}}_{k}

Algorithm 2 Anchored Extra-Proximal Newton Method

0\in a_{k}\mathds{T}_{\lambda}^{(p-1)}({\bm{z}}_{k+1};{\bm{z}}_{k+\frac{1}{2}})+a_{k}\mathds{H}({\bm{z}}_{k+1})+{\bm{z}}_{k+1}-\frac{a_{k}}{A_{k}+a_{k}}{\bm{z}}_{0}-\frac{A_{k}}{A_{k}+a_{k}}{\bm{z}}_{k}

Algorithm 3 Anchored Extra-Proximal Tensor Method

Explore similar work

Aug 9, 2026math.OC

Halpern Iteration Achieves $\tilde{\mathcal{O}}(ε^{-1/p})$ $p$ th-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

\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

\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

\tilde{\mathcal{O}}(T^{-2})

for solving MVIs. We also provide the

p

th-order generalization of our method. We first introduce an Anchored Tensor Method (ATM) that achieves the rate of

\mathcal{O}(T^{-(p-1)})

, and then combine it with the Halpern iteration to achieve a faster convergence rate of

\tilde{\mathcal{O}}(T^{-p})

. This improves all prior results for

p \ge 2

and matches the classical extragradient method for

p=1

Lesi Chen, Xinliang Zhang, Hengyu Wang +3

1IIIS, Tsinghua University · Apex Intelligence · School of Mathematical Sciences, Tongji University +2

Monotone Variational Inequalities First Order Oracle Complexity Newton Optimal Sample Complexity

Ask PDF

May 29, 2026math.OC

A Unifying View of Anchoring via Operator-Side Tikhonov Regularization

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)

Halpern residual-norm convergence rate, giving

O(1/\sqrt{k})

for the regularized forward step, and giving

O(1/k)

for the regularized EG and PEG variants in the unconstrained monotone Lipschitz setting.

Zihao Chen

UC Berkeley

Monotone Variational Inequalities Proximal Operators Newton Convergence Regularization Perspective

Ask PDF

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/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.

Motahareh Sohrabi, Jianxin You, Simon Lacoste-Julien +2

Universit´e de Montr´eal · Mila - Quebec AI Institute · CIFAR AI Chair +1

Monotone Variational Inequalities Convergence Acceleration

Ask PDF

Abstract

Explore similar work

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

A Unifying View of Anchoring via Operator-Side Tikhonov Regularization

Accelerated and Stable Convergence with Anchored Optimistic Method

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