2020/02/09 by Yossi Arjevani, Amit Daniely, Arjevani, Yossi +5 · 2 citations
Computer Science · Mathematics · #Applied mathematics #Convex analysis #Convex function #Convex optimization #FOS: Computer and information sciences #FOS: Mathematics #Geometry #Graph theory and applications #Limits and Structures in Graph Theory #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical economics #Mathematical optimization #Mathematics #Optimization and Control (math.OC) #Regular polygon #Stochastic Gradient Optimization Techniques #cs.LG #math.OC #stat.ML
paper · pdf · doi:10.48550/arxiv.2002.03273
published in arXiv (Cornell University) (Cornell University)
arxiv created 2020/02/09 · openalex publication_date 2020/02/09 · arxiv updated 2020/02/11 · openalex created_date 2020/02/14 · openalex updated_date 2026/07/28
Recent advances in randomized incremental methods for minimizing L-smooth μ-strongly convex finite sums have culminated in tight complexity of O((n+√(n L/μ))log(1/ε)) and O(n+√(nL/ε)), where μ>0 and μ=0, respectively, and n denotes the number of individual functions. Unlike incremental methods, stochastic methods for finite sums do not rely on an explicit knowledge of which individual function is being addressed at each iteration, and as such, must perform at least Ω(n2) iterations to obtain O(1/n2)-optimal solutions. In this work, we exploit the finite noise structure of finite sums to derive a matching O(n2)-upper bound under the global oracle model, showing that this lower bound is indeed tight. Following a similar approach, we propose a novel adaptation of SVRG which is both compatible with stochastic oracles, and achieves complexity bounds of O((n2+n√(L/μ))log(1/ε)) and O(n√(L/ε)), for μ>0 and μ=0, respectively. Our bounds hold w.h.p. and match in part existing lower bounds of Ω(n2+√(nL/μ)log(1/ε)) and Ω(n2+√(nL/ε)), for μ>0 and μ=0, respectively.