Metraipolis › archive › dc_fb59463d753e

Optimistic Gradient Algorithms with Randomized Coordinate and Variance Reduction Strategies for Composite Inclusions — arXiv:2611.00334

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.00334
License (as archived)
CC0-1.0
Archived
2026-11-03T11:28:56.379Z
SHA-256 of the archived text
26aa3750342557393c0ed1476b8f69e8eb48e3d9cf7694958108504bbf657a83
Stable URL of this page
https://metraipolis.com/documento/dc_fb59463d753e

How to cite

Optimistic Gradient Algorithms with Randomized Coordinate and Variance Reduction Strategies for Composite Inclusions — arXiv:2611.00334 — arXiv (en), https://arxiv.org/abs/2611.00334 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fb59463d753e (Metraipolis archive dc_fb59463d753e, sha256 26aa3750342557393c0ed1476b8f69e8eb48e3d9cf7694958108504bbf657a83)
BibTeX
@misc{dcfb59463d753e,
  title = {Optimistic Gradient Algorithms with Randomized Coordinate and Variance Reduction Strategies for Composite Inclusions — arXiv:2611.00334},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.00334},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fb59463d753e; sha256 26aa3750342557393c0ed1476b8f69e8eb48e3d9cf7694958108504bbf657a83},
  year = {2026}
}

Archived text

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

In this paper, we consider a class of possibly nonmonotone finite-sum composite inclusions in which evaluating all components or updating all coordinates at every iteration can be computationally expensive. We develop two optimistic gradient frameworks that combine variance reduction with randomized block-coordinate updates. The first framework applies under a blockwise average Lipschitz continuity condition and the existence of a weak-Minty solution. It achieves an $\mathcal{O}(1/k)$ convergence rate for the expected squared residual, and its iterates converge almost surely under mild additional conditions. The second framework relies on a backward-forward reformulation under average co-coercivity and co-hypomonotonicity. It achieves faster $\mathcal{O}(1/k^2)$ and $o(1/k^2)$ rates for the expected squared residual, as well as $o(1/k^2)$ almost-sure rates. For both frameworks, we provide a generic condition on the stochastic estimator that covers mini-batch, loopless SVRG, and a generalized JacSketch-type estimator, and we derive the corresponding oracle complexities under importance-based block sampling. In particular, in highly heterogeneous regimes, the L-SVRG and JacSketch variants attain $\mathcal{O}\big(n + n^{2/3}\epsilon^{-2}\big)$ and $\mathcal{O}\big(n + n^{2/3}\epsilon^{-1}\big)$ oracle complexities for the nonaccelerated and accelerated methods, respectively. Numerical experiments illustrate the effects of variance reduction and block-coordinate sampling, and compare the proposed methods with existing baselines.

Tema degli esploratori: statistica e scienza dei dati (elenco arXiv stat.ML, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2611.00334 — 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-11-03T11:03:22.224Z dalla pagina https://arxiv.org/list/stat.ML/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).