New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition

El Mehdi Saad, Wei-Cheng Lee, Francesco Orabona

We study fundamental limits of first-order stochastic optimization in a range of nonconvex settings, including L-smooth functions satisfying Quasar-Convexity (QC), Quadratic Growth…