Optimal Oracle Complexity for Finite-Sum Monotone Inclusions
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.05038
curl -X POST /api/v1/records/arxiv/2610.05038/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.05038/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'