PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ruichen Jiang, TaeHo Yoon

arXiv:2609.30212v1math.OCcs.LGstat.ML

TL;DR

The optimal deterministic higher-order oracle complexity for monotone inclusions under the tangent-residual criterion was open. AEP combines anchored extrapolation with an inexact anchored proximal update, using Taylor models and bisection line search for higher-order methods. It takes ˜O(ε−2/(3p−1)) oracle calls in the worst case to find a point with tangent residual at most ε; for every p ≥2, upper and lower bounds differ only by logarithmic factors.

  • Problem

    The optimal deterministic higher-order oracle complexity for monotone inclusions under the tangent-residual criterion was open.

    Source: §1 · p. 2

  • Method

    AEP combines anchored extrapolation with an inexact anchored proximal update, using Taylor models and bisection line search for higher-order methods.

    Source: §1 · p. 3

  • Results

    It takes ˜O(ε−2/(3p−1)) oracle calls in the worst case to find a point with tangent residual at most ε; for every p ≥2, upper and lower bounds differ only by logarithmic factors.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The upper and lower bounds establish optimal dependence on ε for every p ≥2, up to logarithmic factors.

    Source: §1 · p. 3, §7 · p. 22

    The ideal anchored proximal point method is not directly practical under the oracle model because each iteration requires resolving the full operator F + H.

    Source: §3.1 · p. 7

Abstract

from arXiv · show

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 $\Omega(\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$.

1 Introduction

The paper asks for optimal higher-order oracle complexity for composite monotone inclusions under the tangent-residual criterion. It introduces AEP and establishes matching upper and lower bounds, up to logarithmic factors.

1 Introduction

  • The higher-order result addresses an open complexity question: prior methods had ˜O(ε^-1/p) tangent-residual complexity, while other bounds used weaker duality-gap criteria.The cited restricted lower bound left a polynomial gap to the then-best-known upper bound.Source: §1 · p. 2
  • ˜O(ε^-2/(3p-1)) oracle calls suffice to find tangent residual at most ε for every p ≥2, under the stated derivative smoothness assumption.The (p −1)th derivative of F must be Lipschitz continuous.Source: §1 · p. 3
  • AEP combines anchored extrapolation with an inexact anchored proximal update satisfying an HPE-type relative-error condition.Its higher-order versions use a Taylor model centered at the extrapolated point, with bisection line search taking O(log(1/ε)) trials per iteration.Source: §1 · p. 3
  • AEP offers a unified interpretation as a natural higher-order generalization of FEG, rather than a nested-loop construction.Its first-order unconstrained special case recovers FEG.Source: §1 · p. 3
  • The matching lower bound applies to every deterministic algorithm in the pth-order oracle model, without restricting updates to tensor steps.The proof adapts a hard fixed-point construction and a resisting-oracle argument to tangent residuals.Source: §1 · p. 3
  • Concurrent work establishes the same optimal dependence through a distinct multi-hierarchy acceleration approach and a distinct lower-bound operator construction.That work uses inexact extrapolated Halpern iteration, whereas AEP directly uses higher-order Taylor models.Source: §1 · p. 3

2 Preliminaries and Related Work

The preliminaries connect monotone inclusions to several problem classes and explain how tangent residual relates to other optimality measures. The related-work discussion places first- and higher-order methods in context.

2.2 Optimality measures

  • Tangent residual is the paper's target criterion, and the preliminaries state that it upper-bounds commonly used optimality measures.The discussion uses this relationship to distinguish the paper's faster rate from a weakening of the criterion.Source: §2 · p. 4, §2.2 · p. 5

2.1 Min-max optimization, variational inequalities, and fixed-point problems

  • Convex-concave min-max optimization, composite variational inequalities, and nonexpansive fixed-point problems can be represented as special cases of monotone inclusions.For the min-max problem, convexity in x and concavity in y give the monotone-inclusion formulation; a fixed point of a nonexpansive T is a zero of I − T.Source: §2.1 · p. 4

2.2 Optimality measures

  • A bound on tangent residual controls other optimality measures, including the min-max duality gap and specified weak and strong solution notions.For composite variational inequalities, the lemma also relates tangent residual to a bound involving the distance to points in the domain.Source: §2.2 · p. 5

2.3 Additional Related Work

  • Prior work established first-order anchor acceleration and developed second- and higher-order methods with bounds for several gap and residual criteria.The cited literature includes higher-order methods with O(ε^-2/(p+1)) averaged-iterate bounds and O(ε^-2/p) best-iterate bounds under stated criteria.Source: §2.3 · p. 6
  • Higher-order accelerated proximal methods for smooth convex minimization attained ˜O(ε^-2/(3p+1)) complexity, with matching lower bounds establishing optimal dependence there.The cited works later removed an additional logarithmic factor.Source: §2.3 · p. 6

3 Anchored Extra-Proximal Method

The section develops AEP by replacing an ideal anchored proximal-point update with an inexact, surrogate-based update that preserves its tangent-residual guarantee. It recovers composite Fast Extragradient as a first-order special case and supports higher-order extensions.

3 Anchored Extra-Proximal Method

  • AEP replaces the generally unavailable exact resolvent update with an inexact anchored proximal update while retaining the ideal method’s tangent-residual guarantee.The surrogate operator can be chosen to make the update tractable.Source: §3 · p. 6, §3.2 · p. 9

3.1 Proximal Point Method with Anchoring

  • Anchored PPM allows arbitrary positive, time-varying step sizes, and its tangent-residual guarantee depends on their cumulative sum.Its exact update requires evaluating the resolvent of the full operator F + H, which is generally unavailable under the oracle model.Source: §3.1 · pp. 7–8

3.2 Anchored Extra-Proximal Framework

  • AEP combines an anchored extrapolation with an inexact anchored proximal update, whose relative-error condition preserves the anchored PPM convergence guarantee.The anchor enters both updates; replacing F with a surrogate, such as a Taylor model, yields higher-order methods.Source: §3.2 · pp. 9–10

3.3 Fast Extragradient as First-Order AEP

  • With a Lipschitz operator and step size 1/L1, composite FEG is a first-order AEP special case and recovers its known monotone-setting convergence guarantee.The construction uses F evaluated at the extrapolated point as the surrogate.Source: §3.3 · p. 10

4 Anchored Extra-Proximal Newton Method

AEP Newton uses a Jacobian-based affine Taylor model in its anchored proximal subproblem, and a bisection line search handles the coupled step-size choice. The analysis establishes tangent-residual decay and improves prior pointwise bounds, matching the deterministic second-order lower bound up to logarithmic line-search cost.

4 Anchored Extra-Proximal Newton Method

  • AEP Newton uses a second-order oracle and an affine Taylor model at the extrapolated point in the proximal subproblem.When H is zero, that subproblem reduces to a linear system.Source: §4 · pp. 10–11

4.1 Bisection Line Search

  • Bisection resolves the coupling between step size and trial iterates while enforcing the relative-error condition, accepting a suitably large step or returning an ε-accurate point.The step-size choice depends on a displacement known only after solving the corresponding trial subproblem.Source: §4 · p. 12, §4.1 · p. 13

4.2 Complexity Analysis

  • O(L2||z0 - z*||^2/T^(5/2)) is the tangent-residual bound for AEP Newton, which improves prior pointwise guarantees and matches the deterministic second-order lower bound up to line-search logarithms.The method assumes an L2-Lipschitz continuous Jacobian.Source: §4 · p. 10, §4.2 · p. 15

5 Anchored Extra-Proximal Tensor Methods

The AEP Tensor method extends anchored proximal updates using higher-order Taylor models, with regularization and a bisection line search supporting its convergence guarantee. Its outer-iteration rate improves with oracle order and matches the lower bound up to the line search’s logarithmic cost.

5 Anchored Extra-Proximal Tensor Methods

  • The Taylor model may be nonmonotone, so the method regularizes it to restore monotonicity and make the surrogate inclusion well-posed.The resulting regularized Taylor model is maximal monotone and has domain R^d.Source: §5 · p. 16
  • The higher-order model permits larger step sizes as the displacement between iterates shrinks, providing the stated acceleration mechanism.A bisection line search enforces the step-size conditions unless it already finds an ε-accurate point.Source: §5 · pp. 17–18
  • O(k^(-(3p-1)/2)) is the stated convergence rate, and under the smoothness assumption the method returns a point with tangent residual at most ε.The rate follows from growth of the accumulated step-size sequence; constants may depend on p.Source: §5 · p. 18
  • Each line-search trial uses one pth-order oracle call and solves one regularized Taylor-model inclusion.The line search returns after a bounded number of trial evaluations at each outer iteration.Source: §5 · p. 18
  • The oracle complexity improves with p and matches the lower bound up to the logarithmic cost of line search.The lower bound applies to every deterministic pth-order method, not only methods using a prescribed tensor step.Source: §5 · p. 18

6 Lower Bounds

The lower-bound construction shows that no deterministic pth-order method can improve the established complexity exponent for monotone inclusions, even in the unconstrained setting. Its interpretation distinguishes this result from fixed-point lower bounds whose initial distance is not arbitrary.

6 Lower Bounds

  • The lower bound rules out improving the complexity exponent with another deterministic pth-order method, including in the unconstrained setting H = 0.It covers every deterministic algorithm in the pth-order oracle model, rather than only methods with prescribed tensor steps.Source: §6 · p. 19

6.1 The lower bound result and its proof

  • For every deterministic pth-order method, the construction supplies a monotone operator with a unique zero at distance D from the starting point and forces a residual lower bound after N queries.The construction uses a resisting-oracle argument, choosing directions successively so later directions do not affect earlier oracle responses.Source: §6.1 · pp. 19–21
  • The lower bound matches the AEP Tensor method’s outer complexity, leaving only the line search’s logarithmic cost between the bounds.For p = 2, the lower bound is Ω((L2||z0 − z*||^2/ε)^(2/5)).Source: §6.1 · p. 21

6.2 Discussion and interpretation

  • Unlike the cited fixed-point construction, this lower bound permits arbitrary initial distance D, consistent with its scale-free residual quantity.The discussion attributes this flexibility to coordinate rescaling, which is admissible because the problem class requires monotonicity rather than a fixed strong-monotonicity parameter.Source: §6.2 · p. 21

7 Conclusion

The paper extends anchor acceleration from first-order monotone inclusions to higher-order tensor methods through the AEP framework. The resulting method achieves the stated tangent-residual complexity, with a matching lower bound up to logarithmic factors.

7 Conclusion

  • AEP extends anchor acceleration for first-order monotone inclusions to second- and higher-order tensor methods.It uses an anchored proximal-point perspective and approximates each proximal step using higher-order derivatives of the operator.Source: §7 · p. 22
  • The method attains ˜O(ε^-2/(3p-1)) complexity for tangent residual at most ε, and a matching lower bound makes the rate optimal up to logarithmic factors.Source: §7 · p. 22
  • Open directions include closing the logarithmic gap and extending AEP to weakly nonmonotone or stochastic settings and to quasi-Newton variants.The authors also identify Nesterov-momentum reformulations and alternative acceleration mechanisms as directions to investigate.Source: §7 · p. 22

Statement of AI usage and history

The authors report using generative AI for parts of the proof development and writing, while identifying the conceptual AEP framework and its iteration-complexity analysis as not AI-developed. They state that authors reviewed the AI-assisted work and take responsibility for the final paper.

Statement of AI usage and history

  • Generative AI aided hypothesis testing, parts of proofs, and drafting, but not development of the main AEP framework or its iteration-complexity analysis.The authors say they reviewed the AI-assisted proofs and writing, checked correctness, and take responsibility for the final contents.Source: Statement of AI usage and history · p. 22

A.1 Proof of Proposition 3.1

The proofs establish Lyapunov descent for anchored PPM and AEP, then use it to derive tangent-residual and stability bounds.

A.1 Proof of Proposition 3.1

  • Lyapunov descent for anchored PPM yields the tangent-residual bound in Proposition 3.1.The proof establishes V_{k+1} ≤ V_k and uses this descent to bound the residual.Source: §A.1 · pp. 24–25

A.2 Proof of Theorem 3.2

  • For AEP with ρ ∈ [0, 1], Lyapunov descent gives V_{k+1} ≤ 0, after which the Proposition 3.1 argument applies.The proof also identifies the relative-error condition as contributing an additional nonpositive term to the one-step bound.Source: §A.2 · pp. 25–26

A.3 Proof of Lemma 4.1

  • The proof of Lemma 4.1 combines its preceding inequalities and uses ρ < 1 to establish (21).Source: §A.3 · p. 27

B.1 Proof of Lemma 4.2

The proofs show that an accepted trial step meets the tangent-residual target and that bisection reaches an acceptable trial in finitely many unsuccessful steps.

B.1 Proof of Lemma 4.2

  • A trial step satisfying the stated merit-function condition yields a point with tangent residual at most ε.At the selected step size, each term in the residual bound is at most ε/2.Source: §B.1 · p. 28

B.2 Proof of Lemma 4.3

  • Bisection cannot perform as many unsuccessful steps as the ceiling in (31), so its next trial lies in the acceptance range.The argument bounds the shrinking interval using the Lipschitz variation of the merit function.Source: §B.2 · p. 28

C Proofs of the Second-Order Complexity Bounds

The second-order complexity proofs connect accepted steps to an outer-iteration stopping bound and control the line search through merit-function regularity and a logarithmic trial count.

C.1 Outer iteration complexity

  • The outer-iteration argument applies a sequence-growth lemma to its recursion, obtaining B_t ≥ c t/2.Source: §C.1 · p. 29
  • The outer-iteration proof obtains A_T ≥ 2∥z_0 − z*∥/ε and shows the stopping test returns z_T unless termination occurred earlier.Source: §C.1 · p. 29

C.2 Line-Search Complexity

  • The line-search analysis bounds the total number of trial evaluations by a logarithmic expression in q.The proof first controls merit-function Lipschitz variation using bounds on the trial displacement.Source: §C.2 · pp. 30–31

D.1 Proof of Lemma C.3

These proofs bound the trial displacement and its variation, establish uniform trajectory estimates, and use a higher-order merit test to certify the tangent-residual target.

D.1 Proof of Lemma C.3

  • The trial displacement is related to the midpoint displacement and the current residual, with the Taylor remainder entering the bound.Source: §D.1 · pp. 32–33
  • Before termination, the iterates satisfy bounds on both ∥z_0 − z_k − A_k(F(z_k) + v_k)∥ and ∥z_k − z_0∥ by 3∥z_0 − z*∥.Source: §D.1 · p. 33

D.2 Proof of Lemma C.4

  • The trial displacement d_k(a) is Lipschitz continuous on [0, ā_k], including the endpoint a = 0.The proof extends the bound to zero using d_k(a) → 0 as a decreases to zero and d_k(0) = 0.Source: §D.2 · p. 37

E.1 Bisection Line Search

  • If ψ_k(ā_k) ≤ p!ρ, the trial point has tangent residual at most ε.The proof uses the residual terms bounded at ā_k and the inclusion v_{k+1}(ā_k) ∈ H(z_{k+1}(ā_k)).Source: §E.1 · p. 38

E.2 Complexity Analysis

The analysis establishes an outer-iteration bound for accepted tensor steps and controls the bisection line search through regularity of the tensor merit function. It derives that regularity from bounds on the trial displacement and its variation with the trial step size.

E.2 Complexity Analysis

  • Accepted tensor steps satisfy the AEP relative-error condition, allowing the outer-iteration analysis to apply its trajectory bound and establish the stated order for the stopping horizon.The stopping test returns z_T unless the method terminates earlier.Source: §E.2 · p. 39
  • The bisection analysis uses continuity and regularity of the tensor merit function; unsuccessful trials halve the interval, yielding a bound on the number of trials.The proof also bounds total trial evaluations after an initial evaluation at the upper trial value.Source: §E.2 · p. 40

F Regularity of the Tensor Merit Function

  • The tensor merit function's Lipschitz modulus is reduced to uniform and Lipschitz bounds on the trial-displacement map, while the analysis also establishes merit continuity.The sensitivity lemma applies when the displacement map is Lipschitz on the trial-step interval.Source: F Regularity of the Tensor Merit… · pp. 41–42

F.1 Proof of Lemma F.2

  • The trial-displacement bound is proved separately for the initial and later iterations, using monotonicity and bounds along the accepted AEP trajectory.The result applies for each positive trial step up to the upper trial value.Source: F Regularity of the Tensor Merit… · p. 41, §F.1 · p. 43

F.2 Proof of Lemma F.3

Loading 2609.30212v1…