A reliable effective terascale linear learning system

By Alekh Agarwal, Olivier Chapelle, Miroslav Dud'ik, J. Langford. 2011

425 citations recorded by the source corpus.

We present a system and a set of techniques for learning linear predictors with convex losses on terascale data sets, with trillions of features, billions of training examples and millions of parameters in an hour using a cluster of 1000 machines. Individually none of the component techniques are new, but the careful synthesis required to obtain an efficient implementation is. The result is, up to our knowledge, the most scalable and efficient linear learning system reported in the literature. We describe and thoroughly evaluate the components of the system, showing the importance of the various design choices.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Control and Systems Engineering, 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 Computer Vision and Pattern Recognition

In Control and Systems Engineering

In Optimization & Training

Citations in the corpus

FastText.zip: Compressing text classification models (2016, methodology): “On top of standard tricks commonly used in linear text classiﬁcation (Agarwal et al., 2014; Wang & Manning, 2012; Weinberger et al., 2009), Joulin et al. (2016) use a low rank constraint to reduce the computation burden while sharing information between different classes.”
Bag of Tricks for Efficient Text Classification (2016, background): “They also have the potential to scale to very large corpus (Agarwal et al., 2014).”
Compressing Neural Networks with the Hashing Trick (2015, background): “, 2009), Vowpal Wabbit, a large-scale learning system, is able to scale to terafeature datasets (Agarwal et al., 2014).”
Recognizing Image Style (2013, methodology): “We use an open-source implementation of Stochastic Gradient Descent with adaptive subgradient [1].”
Communication-Efficient Distributed Optimization using an Approximate Newton-type Method (2013, methodology): “ADMM and other approaches Another popular approach is distributed alternating direction method of multipliers (ADMM, e.g. Boyd et al. 2011), where the machines alternate between computing shared dual variables in a distributed manner, and solving augmented Lagrangian problems with respect to their…”
Communication Complexity of Distributed Convex Learning and Optimization (2015, background): “As datasets continue to increase in size, and parallel computing platforms becoming more and more common (from multiple cores on a single CPU to large-scale and geographically distributed computing grids), distributed learning and optimization methods have been the focus of much research in recent y”
Freeze-Thaw Bayesian Optimization (2014, methodology): “We used the implementation from [23] and report average perplexity on a held out validation set of 10% of the data.”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, background): “Some examples include: • Communication constraints in distributed learning: There has been much work in recent years on learning when the training data is distributed among several machines (with [14, 2, 28, 47, 25, 31, 9, 17, 38] being just a few examples).”
Accelerated Mini-Batch Stochastic Dual Coordinate Ascent (2013, methodology): “• If each node holds a d-dimensional vector, we can compute the sum of these vectors in time O(d log(s)) by applying a “tree-structure” summation (see for example the All-Reduce architecture in Agarwal et al. [2011]).”
A distributed block coordinate descent method for training $l_1$ regularized linear classifiers (2014, methodology): “Step (d) can be carried out using an AllReduce operation (Agarwal et al., 2013) over the nodes and then y becomes available in all the nodes.”
Distributed Coordinate Descent for L1-regularized Logistic Regression (2014, methodology): “The Algorithm 2 from [1] is implemented in the Vowpal Wabbit project 3 .”
GLMix: Generalized Linear Mixed Models For Large-Scale Response Prediction (2016, methodology): “Here we adopt the all-reduce [1] type of implementation for generalized linear models as in MLlib [12].”
Edge Learning for B5G Networks With Distributed Signal Processing: Semantic Communication, Edge Computing, and Wireless Sensing (2022, positive): “In AllReduce , the topology of compute nodes forms a tree structure.”
A Survey on Distributed Machine Learning (2019, methodology): “(primarily maintained by Facebook) distributes ML through, once again, AllReduce algorithms.”
TuPAQ: An Efficient Planner for Large-scale Predictive Analytic Queries (2015, background): “[7, 40, 36] Unfortunately, the application of supervised learning techniques to a new input dataset is computationally demanding and technically challenging.”
The Fast Convergence of Incremental PCA (2013, methodology): “The first step is similar to using a learning rate of the form γn = c/(n + no), as is often done in stochastic gradient descent implementations [1].”
A Coordinate Descent Primal-Dual Algorithm and Application to Distributed Asynchronous Optimization (2014, background): “Instances of this problem appear in learning applications where massive training data sets are distributed over a netw ork and processed by distinct machines [33], [34], in resource allocation problems for communication networks [21], or in statistical estimation problems by sensor networks [20], [ ”