2020/06/18 by Robert M. Gower, Othmane Sebbouh, Gower, Robert M. +4 · 8 citations
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2006.10311
openalex publication_date 2020/06/18 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
Stochastic Gradient Descent (SGD) is being used routinely for optimizing\nnon-convex functions. Yet, the standard convergence theory for SGD in the\nsmooth non-convex setting gives a slow sublinear convergence to a stationary\npoint. In this work, we provide several convergence theorems for SGD showing\nconvergence to a global minimum for non-convex problems satisfying some extra\nstructural assumptions. In particular, we focus on two large classes of\nstructured non-convex functions: (i) Quasar (Strongly) Convex functions (a\ngeneralization of convex functions) and (ii) functions satisfying the\nPolyak-Lojasiewicz condition (a generalization of strongly-convex functions).\nOur analysis relies on an Expected Residual condition which we show is a\nstrictly weaker assumption than previously used growth conditions, expected\nsmoothness or bounded variance assumptions. We provide theoretical guarantees\nfor the convergence of SGD for different step-size selections including\nconstant, decreasing and the recently proposed stochastic Polyak step-size. In\naddition, all of our analysis holds for the arbitrary sampling paradigm, and as\nsuch, we give insights into the complexity of minibatching and determine an\noptimal minibatch size. Finally, we show that for models that interpolate the\ntraining data, we can dispense of our Expected Residual condition and give\nstate-of-the-art results in this setting.\n