Metraipolis › archive › dc_5fc4e48ea764

Optimal Oracle Complexity for Finite-Sum Monotone Inclusions — arXiv:2610.05038

Source: arXiv
Original: https://arxiv.org/abs/2610.05038
License (as archived): CC0-1.0
Archived: 2026-10-06T05:32:15.552Z
SHA-256 of the archived text: 4fb455a7df1252f44849f3ac64965929e7c6e422ce15ab2c980fbcfd2446b765
Stable URL of this page: https://metraipolis.com/documento/dc_5fc4e48ea764

How to cite

Optimal Oracle Complexity for Finite-Sum Monotone Inclusions — arXiv:2610.05038 — arXiv, https://arxiv.org/abs/2610.05038 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5fc4e48ea764 (Metraipolis archive dc_5fc4e48ea764, sha256 4fb455a7df1252f44849f3ac64965929e7c6e422ce15ab2c980fbcfd2446b765)

BibTeX

@misc{dc5fc4e48ea764,
  title = {Optimal Oracle Complexity for Finite-Sum Monotone Inclusions — arXiv:2610.05038},
  howpublished = {arXiv},
  url = {https://arxiv.org/abs/2610.05038},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5fc4e48ea764; sha256 4fb455a7df1252f44849f3ac64965929e7c6e422ce15ab2c980fbcfd2446b765},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv, https://arxiv.org/abs/2610.05038. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\Omega(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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.05038 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T05:27:05.991Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).