Convergence Analysis of the ProbAbilistic Gradient Estimator Algorithm for Weakly Convex Finite-Sum Optimization

arXiv:2509.00737v3 Announce Type: replace-cross 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 au-weakly convex functions, providing a continuous interpolation between the general nonconvex L-smooth regime (au=L) and the convex regime (au=0). We establish new convergence rates for PAGE, showing that its complexity improves as au decreases.

Source: arXiv cs.LG | 2026-07-07