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

arXiv: https://arxiv.org/abs/2609.30212 · HTML: https://mlsanity.com/paper/2609.30212/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 68 references that are in the map.
- First posted on arXiv 24 Sep 2026.

## Builds on (most cited first, 11 of 11)

- [Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusions](https://mlsanity.com/paper/2110.08150/) (2021)
- [ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problems](https://mlsanity.com/paper/1905.10899/) (2019)
- [Generalized Optimistic Methods for Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2202.09674/) (2022)
- [Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities](https://mlsanity.com/paper/2205.06167/) (2022)
- [Tensor methods for strongly convex strongly concave saddle point problems and strongly monotone variational inequalities](https://mlsanity.com/paper/2012.15595/) (2020)
- [A Theory of Composition and Duality of Extremal Optimal Fixed-Point Algorithms](https://mlsanity.com/paper/2605.02231/) (2026)
- [Moving Anchor Extragradient Methods For Smooth Structured Minimax Problems](https://mlsanity.com/paper/2308.12359/) (2023)
- [Matching Higher-Order Oracle Complexity for Smooth Monotone Variational Inequalities](https://mlsanity.com/paper/2609.13462/) (2026)
- [Solving Convex-Concave Problems with tildeO(ε-4/(3p+1)) pth-Order Oracle Complexity](https://mlsanity.com/paper/2604.19462/) (2026)
- [Higher-Order Derivatives Do Not Accelerate the Computation of Fixed Points](https://mlsanity.com/paper/2607.05947/) (2026)
- [Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalities](https://mlsanity.com/paper/2608.08463/) (2026)

## Abstract (arXiv)

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≥ 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 pth-order method that finds a point with tangent residual at most varepsilon in widetildeO(varepsilon-2/(3p-1)) oracle calls. This improves all prior upper bounds for pth-order methods: in particular, it improves the previous best-known widetildeO(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 Omega(varepsilon-2/(3p-1)) for every deterministic algorithm in the pth-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≥2.