Towards Optimal One Pass Large Scale Learning with Averaged Stochastic Gradient Descent

Abstract

For large scale learning problems, it is desirable if we can obtain the optimal model parameters by going through the data in only one pass. Polyak and Juditsky (1992) showed that asymptotically the test performance of the simple average of the parameters obtained by stochastic gradient descent (SGD) is as good as that of the parameters which minimize the empirical cost. However, to our knowledge, despite its optimal asymptotic convergence rate, averaged SGD (ASGD) received little attention in recent research on large scale learning. One possible reason is that it may take a prohibitively large number of training samples for ASGD to reach its asymptotic region for most real problems. In this paper, we present a finite sample analysis for the method of Polyak and Juditsky (1992). Our analysis shows that it indeed usually takes a huge number of samples for ASGD to reach its asymptotic region for improperly chosen learning rate. More importantly, based on our analysis, we propose a simple way to properly set learning rate so that it takes a reasonable amount of data for ASGD to reach its asymptotic region. We compare ASGD using our proposed learning rate with other well known algorithms for training large scale linear classifiers. The experiments clearly show the superiority of ASGD.

Cited by in corpus (28)

• No More Pesky Learning Rates
• Learning Feature Hierarchies with Centered Deep Boltzmann Machines
• Analysis and Optimization of Convolutional Neural Network Architectures
• Strong error analysis for stochastic gradient descent optimization algorithms
• Insensitive Stochastic Gradient Twin Support Vector Machine for Large Scale Problems
• Unit Tests for Stochastic Optimization
• Deep Learning Theory Review: An Optimal Control and Dynamical Systems Perspective
• Deep LSTM for Large Vocabulary Continuous Speech Recognition
• Optimal Margin Distribution Machine
• CROSSBOW: Scaling Deep Learning with Small Batch Sizes on Multi-GPU Servers
• Towards stability and optimality in stochastic gradient descent
• Minimum weight norm models do not always generalize well for over-parameterized problems
• Stochastic gradient descent methods for estimation with large data sets
• Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization
• Optimizing Multi-GPU Parallelization Strategies for Deep Learning Training
• Convergence diagnostics for stochastic gradient descent with constant step size
• On the Convergence of A Family of Robust Losses for Stochastic Gradient Descent
• b-Bit Minwise Hashing in Practice: Large-Scale Batch and Online Learning and Using GPUs for Fast Preprocessing with Simple Hash Functions
• Exponential Moving Average Model in Parallel Speech Recognition Training
• Lsh-sampling Breaks the Computation Chicken-and-egg Loop in Adaptive Stochastic Gradient Estimation
• A Survey on Large-scale Machine Learning
• An Empirical Evaluation of Sequence-Tagging Trainers
• e-Distance Weighted Support Vector Regression
• Large Margin Distribution Machine
• A Bayesian Approach for Online Classifier Ensemble
• Scalable Nonlinear AUC Maximization Methods
• On Generalization of Adaptive Methods for Over-parameterized Linear Regression
• On stochastic optimization methods for Monte Carlo least-squares problems