Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems
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≥ 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 ε in Õ(ε−2/(3p−1)) oracle calls. This improves all prior upper bounds for pth-order methods: in particular, it improves the previous best-known Õ(ε−1/p) tangent-residual complexity as well as the classical O(ε−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 Ω(ε−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 ε, up to logarithmic factors, for all p≥2.
Related
- An Inexact Halpern-accelerated Preconditioned Generalized Proximal Point Algorithm for the Maximal Monotone Inclusion Problem
- A Time-Varying Coefficient-Based Fixed-Time Neurodynamic Approach for Generalized Monotone Inclusion Problems and Its Applications
- Single-call Polyak-Type Extragradient Methods for Monotone Root-Finding Problems
- Stochastic Linesearch Methods for Stochastic Variational Inequality Problems: Parameter-Free Schemes and Non-Monotone Variants
- Polyak-Type Extragradient Methods for Monotone Root-Finding Problems
BibTeX
@misc{jiang2026anchored,
title = {{Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems}},
author = {Ruichen Jiang and TaeHo Yoon},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30212},
eprint = {2609.30212},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30212},
}
RIS
TY - UNPB
TI - Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems
AU - Ruichen Jiang
AU - TaeHo Yoon
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.30212
UR - https://arxiv.org/abs/2609.30212
AB - 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 ε in Õ(ε^−2/(3p−1)) oracle calls. This improves all prior upper bounds for pth-order methods: in particular, it improves the previous best-known Õ(ε^−1/p) tangent-residual complexity as well as the classical O(ε^−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 Ω(ε^−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 ε, up to logarithmic factors, for all p≥2.
ER -