Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method

Abstract

We develop and analyze a procedure for gradient-based optimization that we refer to as stochastically controlled stochastic gradient (SCSG). As a member of the SVRG family of algorithms, SCSG makes use of gradient estimates at two scales, with the number of updates at the faster scale being governed by a geometric random variable. Unlike most existing algorithms in this family, both the computation cost and the communication cost of SCSG do not necessarily scale linearly with the sample size $n$; indeed, these costs are independent of $n$ when the target accuracy is low. An experimental evaluation on real datasets confirms the effectiveness of SCSG.

Add Lemma B.4

References in corpus (7)

• Federated Optimization:Distributed Optimization Beyond the Datacenter
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Stochastic Variance Reduction for Nonconvex Optimization
• Communication-Efficient Distributed Dual Coordinate Ascent
• Proximal Stochastic Dual Coordinate Ascent
• Stop Wasting My Gradients: Practical SVRG
• Tight Complexity Bounds for Optimizing Composite Objectives

Cited by in corpus (11)

• Non-convex Finite-Sum Optimization Via SCSG Methods
• Catalyst Acceleration for Gradient-Based Non-Convex Optimization
• Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity
• A Convergence Analysis for A Class of Practical Variance-Reduction Stochastic Gradient MCMC
• ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
• MISO is Making a Comeback With Better Proofs and Rates
• Stochastic Variance-Reduced Hamilton Monte Carlo Methods
• Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee
• SGD with Variance Reduction beyond Empirical Risk Minimization
• The Lingering of Gradients: Theory and Applications
• Greedy Step Averaging: A parameter-free stochastic optimization method