Optimal Oracle Complexity for Finite-Sum Monotone Inclusions

Qihao Zhou

math.OCOct 4, 2026

Optimal Oracle Complexity for Finite-Sum Monotone Inclusions

Authors: Qihao Zhou

Organizations: Independent Researcher.

Abstract

We present an oracle-optimal method for finite-sum monotone inclusions under mean-square Lipschitz continuity. Our switching regularization method finds a point $y$ and a certificate $g\in G(y)$ with $(\mathbb{E}\|F(y)+g\|^2)^{1/2}\le\varepsilon$ using $\mathcal{O}(n+\sqrt{n}LR/\varepsilon)$ expected component evaluations and resolvent evaluations. It removes the additive $n\log n$ cost of restarting a variance-reduced solver at every regularization stage by switching to a centered stochastic proximal iteration at regularization strength $L/\sqrt{n}$ . Carrying an operator estimate between the remaining stages limits their total cost to $\mathcal{O}(n)$ . A matching $Ω(n+\sqrt{n}LR/\varepsilon)$ lower bound holds for randomized linear-span component-oracle algorithms with adaptive stopping and expected query budgets. Thus, for $0<\varepsilon\le LR/2$ , our method attains the optimal worst-case expected component complexity in this oracle model, up to universal constants.

Figures & tables

Method	Component complexity	Reference
Full-operator acceleration	$\mathcal{O}(n+nLR/\varepsilon)$	Cai et al. [10] , Cai and Zheng [9]
Variance-reduced Halpern	$\widetilde{\mathcal{O}}(n+\sqrt{n}\,LR/\varepsilon)$	Cai et al. [8]
Recursive regularization, restart-only	$\mathcal{O}(n\log(2+n)+\sqrt{n}\,LR/\varepsilon)$	Appendix D
Switching regularization	$\mathcal{O}(n+\sqrt{n}\,LR/\varepsilon)$	Theorem 1
Lower bound	$\Omega(n+\sqrt{n}\,LR/\varepsilon)$	Theorem 2

Table 1: Component complexity for Assumption 1 . A full evaluation costs

n

component calls. Upper bounds control the expected inclusion residual. The lower bound assumes

0<\varepsilon\leq LR/2

and the linear-span oracle model of Section 4 .

Regime	Switching	Restart-only upper bound
$2\leq LR/\varepsilon\leq\sqrt{n}$	$\mathcal{O}(n)$	$\mathcal{O}(n\log(2+n))$
$\sqrt{n}<LR/\varepsilon<\sqrt{n}\log(2+n)$	$\mathcal{O}(\sqrt{n}\,LR/\varepsilon)$	$\mathcal{O}(n\log(2+n))$
$LR/\varepsilon\geq\sqrt{n}\log(2+n)$	$\mathcal{O}(\sqrt{n}\,LR/\varepsilon)$	$\mathcal{O}(\sqrt{n}\,LR/\varepsilon)$

Table 2: Dependence of the upper bounds on the accuracy regime, with

n\geq 4

and

0<\varepsilon\leq LR/2

. Universal constants are suppressed.

Figure 1: Top: for each method and game, the complete trajectory with the smallest final duality gap among 40 runs. Bottom: means over all 40 runs, with the full observed range shaded. Best-run curves are selected outcomes, not estimates of expected performance. Lower is better; one oracle epoch costs

n

component calls.

Explore similar work

Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems
Sep 24, 2026Ruichen Jiang, TaeHo YoonMonotone Variational Inequalities Proximal Operators
Google Research · Johns Hopkins University
Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps
Sep 8, 2026Jelena Diakonikolas, Cristóbal Guzmán, David Martínez-RubioFirst Order Oracle Complexity Fixed-Point Iteration
Department of Computer Sciences, University of Wisconsin-Madison · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile · IMDEA Software Institute, Madrid, Spain
How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond
Sep 8, 2026Ahmet AlacaogluMonotone Variational Inequalities Convex Optimization
Department of Mathematics, University of British Columbia

Sep 24, 2026, math.OCJ/K move · Enter open · S save

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

Ruichen Jiang, TaeHo Yoon

Google Research · Johns Hopkins University

Monotone Variational Inequalities Proximal Operators First Order Oracle Complexity Upper Bounds

Open paper AskPDF 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\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

\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

Abstract

Explore similar work

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

Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps

How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond