Optimal Oracle Complexity for Finite-Sum Monotone Inclusions
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∈ G(y) with (𝔼|F(y)+g|2)1/2≤ε using 𝒪(n+√nLR/ε) expected component evaluations and resolvent evaluations. It removes the additive nlog n cost of restarting a variance-reduced solver at every regularization stage by switching to a centered stochastic proximal iteration at regularization strength L/√n. Carrying an operator estimate between the remaining stages limits their total cost to 𝒪(n). A matching Ω(n+√nLR/ε) lower bound holds for randomized linear-span component-oracle algorithms with adaptive stopping and expected query budgets. Thus, for 0<ε≤ LR/2, our method attains the optimal worst-case expected component complexity in this oracle model, up to universal constants.
Related
- Matching Higher-Order Oracle Complexity for Smooth Monotone Variational Inequalities
- Optimal Oracle Complexity of Dual Halpern Iteration in Normed Spaces
- On the Optimal Linear Minimization Oracle Complexity of Active-Hull Methods for Minimizing Convex Hölder Smooth Functions
- Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization
- Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity
BibTeX
@misc{zhou2026optimal,
title = {{Optimal Oracle Complexity for Finite-Sum Monotone Inclusions}},
author = {Qihao Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05038},
eprint = {2610.05038},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05038},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Oracle Complexity for Finite-Sum Monotone Inclusions
AU - Qihao Zhou
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.05038
UR - https://arxiv.org/abs/2610.05038
AB - 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∈ G(y) with (𝔼|F(y)+g|^2)^1/2≤ε using 𝒪(n+√nLR/ε) expected component evaluations and resolvent evaluations. It removes the additive nlog n cost of restarting a variance-reduced solver at every regularization stage by switching to a centered stochastic proximal iteration at regularization strength L/√n. Carrying an operator estimate between the remaining stages limits their total cost to 𝒪(n). A matching Ω(n+√nLR/ε) lower bound holds for randomized linear-span component-oracle algorithms with adaptive stopping and expected query budgets. Thus, for 0<ε≤ LR/2, our method attains the optimal worst-case expected component complexity in this oracle model, up to universal constants.
ER -