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\in G(y)$ with $(\mathbb{E}\Vert F(y)+g{\Vert }^2{)}^{1/2}\le \epsilon$ using $\mathcal{O}(n+\sqrt{n}LR/\epsilon )$ 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 $\Omega (n+\sqrt{n}LR/\epsilon )$ lower bound holds for randomized linear-span component-oracle algorithms with adaptive stopping and expected query budgets. Thus, for $0<\epsilon \le LR/2$, our method attains the optimal worst-case expected component complexity in this oracle model, up to universal constants.

arXiv comment21 pages, 1 figure, 2 tables