mlsanityData to 14 Oct 2026

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

arXiv 2509.00737 ↗First posted 31 Aug 2025math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

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

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 15 of its 22 references that are in the map. First posted on arXiv 31 Aug 2025.

Builds on

15 of 22 references.

References · 15

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  3. 2016Deep Learning without Poor Local Minimacited by 234
  4. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  5. 2018Stochastic model-based minimization of weakly convex functionscited by 159
  6. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 135
  7. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 133
  8. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 119
  9. 2016A Geometric Analysis of Phase Retrievalcited by 92
  10. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 82
  11. 2019Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loopcited by 68
  12. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 24
3 more
  1. 2019On the Convergence of SARAH and Beyondcited by 10
  2. 2022Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Samplingcited by 10
  3. 2024On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Conditioncited by 2

Built on by

Not cited yet.