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

By Wei Xu. 2011

159 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Optimization & Training

Citations in the corpus

No more pesky learning rates (2012, background): “Learning rates in SGD are generally decreased according a schedule of the form η ( t ) = η 0 (1 + γt ) − 1 .”
Optimization Methods for Large-Scale Machine Learning (2016, background): “) This asymptotic behavior is difficult to achieve in practice, but is possible in some circumstances with careful selection of the stepsize sequence [154].”
Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields (2015, methodology): “Vishwanathan et al. [2006] did not compare to ASG, because applying ASG to large/sparse data requires the recursion of Xu [2010].”
Large-scale image classification: Fast feature extraction and SVM training (2011, methodology): “We adopt the following step size scheduling [23]:”
On the Convergence of a Family of Robust Losses for Stochastic Gradient Descent (2016, methodology): “We also choose ASGD [13] with Logistic Loss (ASGD(Log)) and PEGASOS [8] as baseline methods.”
Consistency versus Realizable H-Consistency for Multiclass Classification (2013, methodology): “One algorithm learned the weights v 1 , ..., v k to minimize L logit (y, v 1 · x, ..., v k · x) using 100 epochs of ASGD (Polyak & Juditsky, 1992; Xu, 2011; Bottou, 2010) and the other was the same, except with L CS .”
Adaptive Sampling for SGD by Exploiting Side Information (2016, unknown): “Setting the learning rate to decay as γt = γ0(1 + λγ0t)−1 has been empirically found to work well (Xu, 2011).”
Stochastic Gradient Descent Tricks (2012, background): “Although an adequate choice of the learning rates helps [27], the problem worsens when the dimension d of the inputs xt increases.”
Analysis and Optimization of Convolutional Neural Network Architectures (2017, background): “Available: http://lear.inrialpes.fr/people/marszalek/data/ig02/ [MDA15] D. Maclaurin, D. Duvenaud, and R. Adams, “Gradient-based hyperparameter optimization through reversible learning,” in International Conference on Machine Learning (ICML), 2015, pp. 2113–2122.”
Scalable hands-free transfer learning for online advertising (2014, methodology): “A popular and e ↵ ective algorithm for building linear models with large-yet-sparse, data is Stochastic Gradient Descent (SGD) [4, 9, 15].”
Large-Scale Machine Learning with Stochastic Gradient Descent (2010, methodology): “When the gains decrease too slowly, the variance of the parameter estimate wt decreases equally slowly. When the gains decrease too quickly, the expectation of the parameter estimate wt takes a very long time to approach the optimum. Under sufficient regularity conditions (e.g. Murata (1998)), the b”