Metraipolis › archive › dc_879df60cb708

Variance Reduction Note 3: The Convergence of PAGE — arXiv:2611.01523

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.01523
License (as archived)
CC0-1.0
Archived
2026-11-03T11:31:43.808Z
SHA-256 of the archived text
a699ef3a2044489161c955b9898f700b37d0157abc2aec3c96f44f5370323a34
Stable URL of this page
https://metraipolis.com/documento/dc_879df60cb708

How to cite

Variance Reduction Note 3: The Convergence of PAGE — arXiv:2611.01523 — arXiv (en), https://arxiv.org/abs/2611.01523 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_879df60cb708 (Metraipolis archive dc_879df60cb708, sha256 a699ef3a2044489161c955b9898f700b37d0157abc2aec3c96f44f5370323a34)
BibTeX
@misc{dc879df60cb708,
  title = {Variance Reduction Note 3: The Convergence of PAGE — arXiv:2611.01523},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.01523},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_879df60cb708; sha256 a699ef3a2044489161c955b9898f700b37d0157abc2aec3c96f44f5370323a34},
  year = {2026}
}

Archived text

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

The probabilistic gradient estimator (PAGE) alternates randomly between an accurate gradient refresh and a cheap recursive correction. This third expository note on recursive variance reduction explains the algorithm and gives a self-contained convergence proof for smooth nonconvex optimization. A Lyapunov function combines objective decrease with estimation error, turning the refresh probability into an explicit contraction parameter. The resulting expected oracle complexity is $O(n+\sqrt n\,\epsilon^{-2})$ for finite sums and $O(\epsilon^{-3})$ for online problems, with the other problem parameters fixed. Initialization, refreshes, and both evaluations in each gradient difference are counted. The presentation is pedagogical and makes no claim of a new algorithm or convergence rate.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2611.01523 — 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:04:22.234Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).