Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
arXiv:1603.00570
Abstract
Stochastic gradient methods for machine learning and optimization problems are usually analyzed assuming data points are sampled \emph{with} replacement. In practice, however, sampling \emph{without} replacement is very common, easier to implement in many cases, and often performs better. In this paper, we provide competitive convergence guarantees for without-replacement sampling, under various scenarios, for three types of algorithms: Any algorithm with online regret guarantees, stochastic gradient descent, and SVRG. A useful application of our SVRG analysis is a nearly-optimal algorithm for regularized least squares in a distributed setting, in terms of both communication complexity and runtime complexity, when the data is randomly partitioned and the condition number can be as large as the data size per machine (up to logarithmic factors). Our proof techniques combine ideas from stochastic optimization, adversarial online learning, and transductive learning theory, and can potentially be applied to other stochastic optimization and learning problems.
arXiv commentFixed a few minor typos, and slightly tightened Corollary 1
References in corpus (12)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
- Communication Efficient Distributed Optimization using an Approximate Newton-type Method
- A Reliable Effective Terascale Linear Learning System
- Why Random Reshuffling Beats Stochastic Gradient Descent
- Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
- Note on sampling without replacing from a finite collection of matrices
- Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
- Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences
- A Parallel SGD method with Strong Convergence
Cited by in corpus (8)
- High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
- Proving Expected Sensitivity of Probabilistic Programs
- Stochastic Learning under Random Reshuffling with Constant Step-sizes
- Convergence Analysis of Distributed Stochastic Gradient Descent with Shuffling
- Stochastic Nonconvex Optimization with Large Minibatches
- Variance-Reduced Stochastic Learning under Random Reshuffling
- Decentralized Differentially Private Without-Replacement Stochastic Gradient Descent
- Dimension-Free Iteration Complexity of Finite Sum Optimization Problems