Source-linked AI summary
A Reliable Effective Terascale Linear Learning System
Alekh Agarwal, Olivier Chapelle, Miroslav Dudik, John Langford
TL;DR
The paper addresses how to train linear predictors on terascale datasets when data are distributed across clusters and existing platforms make iterative learning and state synchronization difficult. It develops a Hadoop-compatible AllReduce system combined with a hybrid online-plus-batch optimizer. The resulting system achieves accurate prediction and short training times at scales including 500M features/s on 1000 nodes.
Problem
Large datasets may require distributed learning because subsampling can fail when many examples are needed, while existing large-cluster approaches often have inadequate throughput and platform support.
Method
The system combines Hadoop-compatible AllReduce communication with a hybrid optimizer that uses online learning for initialization and batch L-BFGS refinement.
Results
500M features/s on 1000 nodes was achieved, about 5× faster than a single node’s 1Gb/s network interface, while the system produced accurate prediction and short training time.
Takeaways & Limitations
Careful synthesis of communication and optimization techniques enables linear predictors to be trained on datasets larger than those in previous published works.
Takeaways & Limitations
The display-advertising comparison could not be tuned and evaluated because of prohibitive running time, and timing varied substantially between runs.
Abstract
from arXiv · showhide
We present a system and a set of techniques for learning linear predictors with convex losses on terascale datasets, with trillions of features, {The number of features here refers to the number of non-zero entries in the data matrix.} 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 (as of 2011 when our experiments were conducted). We describe and thoroughly evaluate the components of the system, showing the importance of the various design choices.
1. Introduction
The paper targets large-scale distributed learning where data volume, decentralized storage, and existing platform limitations make single-machine or straightforward parallel approaches inadequate. It presents a Hadoop-compatible system that combines efficient communication with minimal code changes and achieves high learning throughput.
- Motivation: Distributed learning is motivated by datasets that are collected and stored across clusters, where centralizing data creates transfer bottlenecks.Large numbers of examples may be necessary to learn a good model, making simple subsampling insufficient.
- Motivation: Existing large-cluster learning systems often have lower throughput than the I/O interface of a single machine.Throughput is measured as input size divided by total wall-clock training time.
- Results: 500M features/s was achieved on 1000 nodes, about 5× faster than one node’s 1Gb/s network interface.Each node processed local examples 10 times at 5M features/s.
- Contribution: The system addresses data-transfer and state-synchronization challenges by running on Hadoop-compatible MapReduce clusters with only a few strategic library calls.This supports moving existing single-machine learning implementations to large clusters without extensive rewriting.
- Contribution: Its communication infrastructure accumulates and broadcasts values across nodes while remaining compatible with Hadoop, supporting automatic restarts and speculative execution.The optimization algorithm combines online and batch learning with rapid convergence and small synchronization overhead.
- Scope: The paper evaluates design choices, compares the system with existing algorithms, and provides theoretical intuition for the distributed approach.The paper’s structure includes an approach description, experiments, theory, and discussion.
2. Computation and Communication Framework
The framework uses Hadoop-compatible AllReduce to synchronize compact parameter-related state during iterative learning, then combines asynchronous online initialization with synchronized batch refinement. This design supports straightforward parallelization while keeping communication small relative to local computation.
- Hadoop-compatible AllReduce: AllReduce sums values across nodes through reduce and broadcast phases, leaving every node with the global sum.For long vectors, the two phases can be pipelined over entries to reduce effective tree latency.
- Hadoop-compatible AllReduce: AllReduce parallelizes gradient descent, L-BFGS, statistical query algorithms, and parameter averaging by aggregating local information.For gradient methods, nodes compute local gradients and obtain the global gradient through AllReduce.
- Hadoop-compatible AllReduce: The Hadoop implementation builds a nearly balanced binary tree among mapper nodes using a gateway server.Nodes receive parent and child addresses for communication within the tree.
- Proposed Algorithm: The hybrid algorithm uses an initial asynchronous online pass to reach a useful neighborhood, followed by synchronized L-BFGS updates for higher accuracy.Online learning converges quickly initially, while quasi-Newton methods are effective near the optimum.
- Proposed Algorithm: The online stage forms a confidence-weighted average of node parameters and scaling states before starting the L-BFGS optimization.Weights for each dimension reflect how many examples containing the corresponding feature each node has seen.
- Alternative Strategy: Repeated online averaging can quickly achieve moderately small test error, but its convergence slows and may not reach optimal test error efficiently.The strategy averages weights and scaling matrices after each online pass before beginning another pass.
- Communication and Computation: Each iteration passes through local data, performs AllReduce on a vector of parameter size, and then updates the local parameter vector.The communicated vector is typically much smaller than the local dataset, making the iterative structure suitable for distributed processing.
- Proposed Algorithm: The implementation is organized as a MapReduce-compatible learning architecture using stochastic gradient descent for the initial pass and L-BFGS afterward.The algorithm sketch computes local states, averages them with AllReduce, and then iteratively aggregates local batch gradients.
3. Experiments
Experiments evaluate the system on display advertising and splice-site recognition, showing that full datasets, hybrid optimization, and Hadoop-compatible communication support accurate and fast large-scale learning. Performance is strong overall, but cluster stragglers and communication overhead affect scaling.
- Datasets and metrics: 2.3B examples were used for display advertising, while splice-site recognition used 50M training and 4.6M test samples with 11,725,480 features.Display advertising used logistic regression with L2 regularization; splice-site recognition followed the established degree-20 kernel protocol.
- Datasets and metrics: Subsampling reduced display-advertising accuracy, while smaller splice-site training sets reduced test auPRC, so both tasks required their full training datasets for optimal performance.The paper reports that even modest accuracy losses in advertising can substantially affect revenue.
- Scaling and systems: Scaling was limited mainly by slow nodes rather than communication: speculative execution mitigated stragglers, but their likelihood increased with cluster size.The display-advertising speed-up experiment was repeated 10 times, whereas splice-site timing experiments were not repeated and therefore had greater uncertainty.
- Optimization strategies: One online pass followed by L-BFGS was the most effective strategy, and the initial online pass saved about 10–15 L-BFGS iterations.Figure 4 compares pure online, pure L-BFGS, and hybrid strategies with one or five online passes.
- Optimization strategies: An initial online pass plus 14 L-BFGS iterations achieved splice-site auPRC 0.581 in 1960 seconds on 500 machines, a 68× speed-up over the reported single-machine time.The result was just above the result reported by Sonnenburg and Franc (2010), while explicit features imposed significant overhead.
- Scaling and systems: AllReduce outperformed iterative MapReduce for gradient aggregation, while oversampled SGD was competitive on advertising but converged much more slowly on splice-site data.On splice-site data, L-BFGS finished 20 passes in under an hour, whereas the compared SGD configuration took 40 hours and had much lower performance.
4. Communication and Computation Complexity
The section analyzes the hybrid system’s computation and communication complexity under simplifying assumptions, showing how online warmstarts reduce batch optimization effort and how communication patterns affect scalability.
- Computational complexity: The analysis assumes m nodes, n uniformly distributed examples, one online pass per node, and uniform weight averaging before extending intuition to the deployed scheme.It also assumes differentiable, smooth, locally strongly convex objectives for the convergence analysis.
- Computational complexity: The hybrid method first performs one stochastic-gradient online pass per node, producing local weights that approximately minimize each node’s expected regularized loss.The resulting weights are then used to initialize the batch optimization phase.
- Computational complexity: When n ≫ m, the online warmstart can substantially reduce the additional L-BFGS passes needed to reach precision ϵ compared with an arbitrary initialization.The argument is not specific to L-BFGS and extends to reasonable quasi-Newton methods.
- Computational complexity: In noisy problems targeting ϵ = 1/n, the hybrid method can nearly halve the number of passes when m ≪ n, although pure online methods may also succeed.The comparison is against pure batch optimization, whose pass count scales as κ log(n) in the stated regime.
- Computational complexity: The hybrid approach is generally competitive with purely online or batch methods in computational complexity, while its gains depend on noise level and target accuracy.For essentially noiseless data, the warmstart advantage is less pronounced, while online methods may struggle to achieve very high accuracy.
- Communication complexity: The hybrid algorithm’s per-node communication cost is Θ(dT_hybrid), typically with T_hybrid ≈ 15, and remains below the dataset size under the stated data layout.By contrast, replicated online optimization can have per-node cost Θ(ns) because data transfer dominates parameter averaging.
5. Discussion
The discussion presents a Hadoop-compatible AllReduce architecture and hybrid optimizer that combine accurate prediction with short training time, while noting unaddressed Hadoop overheads. It reports that careful synthesis of design choices enables linear prediction at dataset scales unmatched in prior published work.
- Discussion: A Hadoop-compatible AllReduce architecture combines accurate prediction, short training time, and an easy programming style.The architecture is presented as a new basis for parallel learning.
- Discussion: The hybrid optimizer combines rapid initial progress from online learning with the high precision of batch optimization when the last performance improvements matter.The discussion attributes the system’s benefits to using both optimization phases.
- Discussion: Data loading and node scheduling overheads are not discussed in detail, although the authors found they are typically amortized as one-time AllReduce costs rather than per-iteration MapReduce costs.The discussion notes that improved scheduling could further improve performance.
- Discussion: The resulting system trains linear predictors on datasets described as unmatched in size by previous published works.The paper emphasizes that its contribution is the careful synthesis of existing techniques and design choices.