{"id":"arxiv/2611.01523","url":"https://arxiv.org/abs/2611.01523","tags":["math.OC"],"score":0,"title":"Variance Reduction Note 3: The Convergence of PAGE","domain":"math.OC","source":"arxiv","authors":["Alina Lodhi"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-01","reactions":{}}