Optimal method improves monotone inclusion problem complexity
Optimal Oracle Complexity for Finite-Sum Monotone Inclusions
Machine Learning
Summary
Solving certain mathematical problems called monotone inclusions can be very slow and expensive. The authors present a new method that solves these problems using the fewest possible steps on average, based on a careful balance of calculations and randomness. Their approach avoids costly restarts and keeps the total work low, achieving the best performance any similar method can have. This result helps clarify the limits of how efficiently these problems can be solved.
What this means in practice
- •For optimization engineers: Design faster algorithms for large-scale optimization problems using monotone inclusion frameworks with optimal component evaluation complexity.
- •For machine learning developers: Implement efficient solvers for finite-sum operator problems arising in training models with monotone inclusion structures.
A theory result. No direct application yet.
Authors
Qihao Zhou
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.