Convergence Analysis of the PAGE Stochastic Algorithm for Weakly Convex Finite-Sum Optimization

PAGE, a stochastic algorithm introduced by Li et al. [2021], was designed to find stationary points of averages of smooth nonconvex functions. In this work, we study PAGE in the broad framework of $τ$-weakly convex functions, which provides a continuous interpolation between the general nonconvex L-smooth case ($τ= L$) and the convex case ($τ= 0$). We establish new convergence rates for PAGE, showing that its complexity improves as $τ$ decreases.