SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation

Understand

Stochastic Gradient Descent (SGD) is being used routinely for optimizing non-convex functions.

• Yet, the standard convergence theory for SGD in the smooth non-convex setting gives a slow sublinear convergence to a stationary point.
• In this work, we provide several convergence theorems for SGD showing convergence to a global minimum for non-convex problems satisfying some extra structural assumptions.
• In particular, we focus on two large classes of structured non-convex functions: (i) Quasar (Strongly) Convex functions (a generalization of convex functions) and (ii) functions satisfying the Polyak-Lojasiewicz condition (a generalization of strongly-convex functions).