Convergence Analysis of the ProbAbilistic Gradient Estimator Algorithm for Weakly Convex Finite-Sum Optimization
Abstract
The ProbAbilistic Gradient Estimator algorithm (PAGE), a stochastic algorithm introduced by Li et al. in 2021, was designed to find stationary points for the average of smooth nonconvex functions. In this work, we study PAGE within the broad framework of $$\tau $$ -weakly convex functions, providing a continuous interpolation between the general nonconvex L-smooth regime ( $$\tau =L$$ ) and the convex regime ( $$\tau =0$$ ). We establish new convergence rates for PAGE, showing that its complexity improves as $$\tau $$ decreases.
Fields of Study & Subjects
Optimization and Search Problems
Publication details
- Journal / source
- Journal of Optimization Theory and Applications
- Volume
- 210
- Issue
- 2
- Publication date
- 28 July 2026
- Language
- EN