mlsanityData to 14 Oct 2026

Optimal Oracle Complexity for Finite-Sum Monotone Inclusions

arXiv 2610.05038 ↗First posted 4 Oct 2026math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

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 (mathbbE|F(y)+g|2)1/2≤varepsilon using O(n+√nLR/varepsilon) 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 O(n). A matching Omega(n+√nLR/varepsilon) lower bound holds for randomized linear-span component-oracle algorithms with adaptive stopping and expected query budgets. Thus, for 0<varepsilon≤ LR/2, our method attains the optimal worst-case expected component complexity in this oracle model, up to universal constants.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 29 of its 36 references that are in the map. First posted on arXiv 4 Oct 2026.

Builds on

29 of 36 references.

References · 29

  1. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  2. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  3. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 119
  4. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 73
  5. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 61
  6. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 60
  7. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 57
  8. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 48
  9. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 47
  10. 2019Variance Reduction for Matrix Gamescited by 38
  11. 2018A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivitycited by 36
  12. 2019The Complexity of Making the Gradient Small in Stochastic Convex Optimizationcited by 34
17 more
  1. 2015An optimal randomized incremental gradient methodcited by 33
  2. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 32
  3. 2022Exact Optimal Accelerated Complexity for Fixed-Point Iterationscited by 25
  4. 2019A unified variance-reduced accelerated gradient method for convex optimizationcited by 24
  5. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 24
  6. 2022Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusioncited by 20
  7. 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 20
  8. 2020Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimizationcited by 19
  9. 2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 19
  10. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 11
  11. 2026Solving Stochastic Variational Inequalities without the Bounded Variance Assumptioncited by 5
  12. 2026Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularizationcited by 4
  13. 2026Computation of Strong Solutions to Stochastic Variational Inequalitiescited by 4
  14. 2024Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problemscited by 3
  15. 2026Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusionscited by 3
  16. 2025New Accelerated Past-Extragradient Methods with Variance Reduction for Generalized Equationscited by 2
  17. 2026How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyondcited by 2

Built on by

Not cited yet.