Variance Reduction Note 3: The Convergence of PAGE

arXiv:2611.01523 · math.OC · Submitted 2026-11-01 · Read on arXiv

math.OC

Submitted: 2026-11-01

Updated: 2026-11-01

License: http://creativecommons.org/licenses/by/4.0/

The gist: The probabilistic gradient estimator (PAGE) alternates randomly between an accurate gradient refresh and a cheap recursive correction.

Terminology

Abstract

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,ε-2) for finite sums and O(ε-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.

Sources

Related papers