# Optimal Oracle Complexity for Finite-Sum Monotone Inclusions

arXiv: https://arxiv.org/abs/2610.05038 · HTML: https://mlsanity.com/paper/2610.05038/

## 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 (most cited first, 29 of 29)

- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm](https://mlsanity.com/paper/2102.07922/) (2021)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021)
- [Variance Reduction for Matrix Games](https://mlsanity.com/paper/1907.02056/) (2019)
- [A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity](https://mlsanity.com/paper/1808.04162/) (2018)
- [The Complexity of Making the Gradient Small in Stochastic Convex Optimization](https://mlsanity.com/paper/1902.04686/) (2019)
- [An optimal randomized incremental gradient method](https://mlsanity.com/paper/1507.02000/) (2015)
- [Accelerated Single-Call Methods for Constrained Min-Max Optimization](https://mlsanity.com/paper/2210.03096/) (2022)
- [Exact Optimal Accelerated Complexity for Fixed-Point Iterations](https://mlsanity.com/paper/2201.11413/) (2022)
- [A unified variance-reduced accelerated gradient method for convex optimization](https://mlsanity.com/paper/1905.12412/) (2019)
- [Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction](https://mlsanity.com/paper/2103.08280/) (2021)
- [Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion](https://mlsanity.com/paper/2206.05248/) (2022)
- [Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization](https://mlsanity.com/paper/2208.05925/) (2022)
- [Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization](https://mlsanity.com/paper/2006.10281/) (2020)
- [Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions](https://mlsanity.com/paper/2203.09436/) (2022)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [Solving Stochastic Variational Inequalities without the Bounded Variance Assumption](https://mlsanity.com/paper/2602.05531/) (2026)
- [Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization](https://mlsanity.com/paper/2608.12043/) (2026)
- [Computation of Strong Solutions to Stochastic Variational Inequalities](https://mlsanity.com/paper/2609.04188/) (2026)
- [Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems](https://mlsanity.com/paper/2406.02413/) (2024)
- [Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions](https://mlsanity.com/paper/2603.15576/) (2026)
- [New Accelerated Past-Extragradient Methods with Variance Reduction for Generalized Equations](https://mlsanity.com/paper/2508.16791/) (2025)
- [How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond](https://mlsanity.com/paper/2609.08380/) (2026)

## 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.