Variance Reduction Note 3: The Convergence of PAGE
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
- Semi-Stochastic Gradient Descent Methods
- Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
- Katyusha: The First Direct Acceleration of Stochastic Gradient Methods
- Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketching
- Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
- Inexact SARAH Algorithm for Stochastic Optimization
- ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation
- A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
- META-STORM: Generalized Fully-Adaptive Variance Reduced SGD for Unbounded Functions
- SVRG Meets AdaGrad: Painless Variance Reduction
- Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimization
- Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions
- Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
- Compositional Stochastic Average Gradient for Machine Learning and Related Applications
- Multi-Level Composite Stochastic Optimization via Nested Variance Reduction
- Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates
- Solving Finite-sum Coupled Compositional Optimization via Multi-block-Single-probe Estimator
- Stochastic Conditional Gradient++
- Projection-Free Multi-level Algorithms for Stochastic Constrained Compositional Optimization
- Distributed Learning with Compressed Gradient Differences
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise