Variance Reduction Note 3: The Convergence of PAGE
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.01523
curl -X POST /api/v1/records/arxiv/2611.01523/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.01523/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'