Research
Optimal Oracle Complexity for Finite-Sum Monotone Inclusions
arXiv:2610.05038v1 Announce Type: cross Abstract: We present an oracle-optimal method for finite-sum monotone inclusions under mean-square Lipschitz continuity. Our switching regularization method fin
arXiv:2610.05038v1 Announce Type: cross 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 gin G(y) with (E|F(y)+g|^2)^{1/2}learepsilon using O(n+sqrt{n}LR/arepsilon) 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/sqrt{n}. Carrying an operator estimate between the remaining stages limits their total cost to O(n). A matching Omega(n+sqrt{n}LR/arepsilon) lower bound holds for randomized linear-span component-oracle algorithms with adaptive stopping and expected query budgets. Thus, for 0<arepsilonle LR/2, our method attains the optimal worst-case expected component complexity in this oracle model, up to universal constants.
Related
- Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems
- Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
- The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
Source: arXiv cs.LG | 2026-10-06