Large-Scale Machine Learning with Stochastic Gradient Descent
Published 1 January 2010
Léon Bottou
Citations5,634
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A more precise analysis uncovers qualitatively different tradeoffs for the case of small-scale and large-scale learning problems.
Abstract
During the last decade, the data sizes have grown faster than the speed of processors. In this context, the capabilities of statistical machine learning methods is limited by the computing time rather than the sample size. A more precise analysis uncovers qualitatively different tradeoffs for the case of small-scale and large-scale learning problems. The large-scale case involves the computational complexity of the underlying optimization algorithm in non-trivial ways. Unlikely optimization algorithms such as stochastic gradient descent show amazing performance for large-scale problems. In particular, second order stochastic gradient and averaged stochastic gradient are asymptotically efficient after a single pass on the training set.
Keywords
Computer ScienceDecision Sciences
Journal of the Royal Statistical Society Series B (Statistical Methodology)Regression Shrinkage and Selection Via the Lasso
51,790 Citations1996Robert Tibshirani
A new method for estimation in linear models called the lasso, which minimizes the residual sum of squares subject to the sum of the absolute value of the coefficients being less than a constant, is proposed.
Machine LearningSupport-Vector Networks
33,035 Citations1995Corinna Cortes, Vladimir Vapnik
High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated and the performance of the support- vector network is compared to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Some methods for classification and analysis of multivariate observations
22,787 Citations1967James B. MacQueen
Learning Internal Representations by Error Propagation
16,235 Citations1985David E. Rumelhart, Geoffrey E. Hinton +1 more
ScholarlyCommons (University of Pennsylvania)Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
12,978 Citations2001John Lafferty, Andrew McCallum +1 more
This work presents iterative parameter estimation algorithms for conditional random fields and compares the performance of the resulting models to HMMs and MEMMs on synthetic and natural-language data.
Society for Industrial and Applied Mathematics eBooksNumerical Methods for Unconstrained Optimization and Nonlinear Equations
7,651 Citations1996J. E. Dennis, Robert B. Schnabel
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
3,175 Citations2015Vladimir Vapnik, Alexey Chervonenkis
This chapter reproduces the English translation by B. Seckler of the paper by Vapnik and Chervonenkis in which they gave proofs for the innovative results they had obtained in a draft form in July 1966 and announced in 1968 in their note in Soviet Mathematics Doklady.
Journal of Machine Learning ResearchRCV1: A New Benchmark Collection for Text Categorization Research
2,600 Citations2004David Lewis, Yiming Yang +2 more
This work describes the coding policy and quality control procedures used in producing the RCV1 data, the intended semantics of the hierarchical category taxonomies, and the corrections necessary to remove errorful data.
Training linear SVMs in linear time
1,947 Citations2006Thorsten Joachims
A Cutting Plane Algorithm for training linear SVMs that provably has training time 0(s,n) for classification problems and o(sn log (n)) for ordinal regression problems and several orders of magnitude faster than decomposition methods like svm light for large datasets.
SIAM Journal on Control and OptimizationAcceleration of Stochastic Approximation by Averaging
1,811 Citations1992B. T. Polyak, Anatoli Juditsky
Convergence with probability one is proved for a variety of classical optimization and identification problems and it is demonstrated for these problems that the proposed algorithm achieves the highest possible rate of convergence.
The MIT Press eBooksThe Tradeoffs of Large-Scale Learning
1,185 Citations2011Léon Bottou, Olivier Bousquet
This contribution develops a theoretical framework that takes into account the effect of approximate optimization on learning algorithms and shows distinct tradeoffs for the case of small-scale and large-scale learning problems.
The Annals of StatisticsOptimal aggregation of classifiers in statistical learning
577 Citations2004A. B. Tsybakov
The main result of the paper concerns optimal aggregation of classifiers: a classifier that automatically adapts both to the complexity and to the margin, and attains the optimal fast rates, up to a logarithmic factor.
HAL (Le Centre pour la Communication Scientifique Directe)SGD-QN: Careful Quasi-Newton Stochastic Gradient Descent
344 Citations2009Antoine Bordes, Léon Bottou +1 more
The SGD-QN algorithm is a stochastic gradient descent algorithm that makes careful use of second-order information and splits the parameter update into independently scheduled components.
Trust region Newton methods for large-scale logistic regression
287 Citations2007Chih‐Jen Lin, Ruby C. Weng +1 more
This paper applies a trust region Newton method to maximize the log-likelihood of the logistic regression model, which uses only approximate Newton steps in the beginning, but achieves fast convergence in the end.
SVM optimization
247 Citations2008Shai Shalev‐Shwartz, Nathan Srebro
Tests are presented demonstrating how a simple subgradient descent approach indeed displays such behavior, at least for linear kernels, as the runtime of SVM optimization should decrease as the size of the training data increases.
Annales de la faculté des sciences de Toulouse MathématiquesSome applications of concentration inequalities to statistics
239 Citations2000Pascal Massart
arXiv (Cornell University)Towards Optimal One Pass Large Scale Learning with Averaged Stochastic Gradient Descent
120 Citations2011Wei Xu
A finite sample analysis for the method of Polyak and Juditsky (1992) shows that it indeed usually takes a huge number of samples for ASGD to reach its asymptotic region for improperly chosen learning rate, and a simple way to properly set learning rate is proposed.
Applied Stochastic Models in Business and IndustryOn‐line learning for very large data sets
103 Citations2005Léon Bottou, Y. Le Cun
This paper reconsiders the convergence speed in terms of how fast a learning algorithm optimizes the testing error and shows the superiority of the well designed stochastic learning algorithm.
IEEE Transactions on Information TheoryThe importance of convexity in learning with squared loss
96 Citations1998Wee Sun Lee, Peter L. Bartlett +1 more
Concentration Inequalities and Empirical Processes Theory Applied to the Analysis of Learning Algorithms
83 Citations2002Olivier Bousquet
Cambridge University Press eBooksA Statistical Study of On-line Learning
58 Citations1999Noboru Murata