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 $\tau$-weakly convex functions, which provides a continuous interpolation between the general nonconvex $L$-smooth case ($\tau =L$) and the convex case ($\tau =0$). We establish new convergence rates for PAGE, showing that its complexity improves as $\tau$ decreases.