Optimal Distributed Online Prediction Using Mini-Batches

By Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, Lin Xiao. 2010

724 citations recorded by the source corpus.

Online prediction methods are typically presented as serial algorithms running on a single processor. However, in the age of web-scale prediction problems, it is increasingly common to encounter situations where a single processor cannot keep up with the high rate at which inputs arrive. In this work, we present the distributed mini-batch algorithm, a method of converting many serial gradient-based online prediction algorithms into distributed algorithms. We prove a regret bound for this method that is asymptotically optimal for smooth convex loss functions and stochastic inputs. Moreover, our analysis explicitly takes into account communication latencies between nodes in the distributed environment. We show how our method can be used to solve the closely-related distributed stochastic optimization problem, achieving an asymptotically linear speed-up over multiple processors. Finally, we demonstrate the merits of our approach on a web-scale online prediction problem.

Subfields: Optimization & Training, Statistical Learning Theory

How researchers see this paper

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

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, neutral): “for convex objectives [256, 119, 132].”
Federated Optimization in Heterogeneous Networks (2018, methodology): “Large-scale machine learning, particularly in data center settings, has motivated the development of numerous distributed optimization methods in the past decade (see, e.g., Boyd et al., 2010; Dekel et al., 2012; Dean et al., 2012; Zhang et al., 2013; Li et al., 2014a; Shamir et al., 2014; Reddi et ”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “By choosing the fully connected matrix W = 1 n11 > we recover • centralized mini-batch SGD (Dekel et al., 2012) and by choosing an arbitrary connected W , we recover • decentralized SGD (Lian et al.”
Is Local SGD Better than Minibatch SGD? (2020, methodology): “…A, we define its worst-case performance with respect to F(H,λ,B, σ2) as: A = max (f,D)∈F(H,λ,B,σ2) F (x̂A)− F (x∗) (4) The worst-case performance of minibatch SGD for general convex objectives is tightly understood (Dekel et al., 2012; Nemirovsky and Yudin, 1983): MB-SGD = Θ ( HB2 R + σB√ MKR ) .”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, methodology): “, 2019), CHOCO-SGD with momentum (Algorithm 2) and standard (all-reduce) mini-batch SGD with momentum and without compression (Dekel et al., 2012).”
On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization (2019, background): “For large-scale distributed machine learning problems, such as training deep neural networks, a parallel version of SGD, known as parallel minibatch SGD, is widely adopted (Dean et al., 2012; Dekel et al., 2012; Li et al., 2014).”
Communication trade-offs for synchronized distributed SGD with large step size (2019, methodology): “In other words, for α = 2/3, we need P ≤ X1/3: the number of machines as to be smaller than the number of iterations to the power 1/3, in other words, for 1000 iterations, one could only use 10 machines to reach the asymptotic regime where OSA performs similarly to MBA.”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, background): “Mini-batch SGD (Dekel et al., 2012) is the natural parallelization of SGD for (1) in the centralized setting, i.e. when a master node collects the updates from all worker nodes, and serves a baseline here.”
Don't Use Large Mini-Batches, Use Local SGD (2018, background): “Thirdly, the mini-batch size controls the noise in the gradients, and in turn controls variance reduction (Dekel et al., 2012).”
Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms (2018, methodology): “SGD is an iterative algorithm which has been widely used to solve (1) (Dekel et al., 2012).”
Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning (2018, methodology): “…parallel method to solve problem (1) is to sample each worker’s local stochastic gradient in parallel, aggregate all gradients in a single server to obtain the average, and update each worker’s local solution using the averaged gradient in its SGD step1 (Dekel et al. 2012) (Li et al. 2014).”
Local SGD Converges Fast and Communicates Little (2018, background): “[8] show that batch sizes b = T , for δ ∈ (0, 12 ) are asymptotically optimal for mini-batch SGD, however they also note that this asymptotic bound might be crude for practical purposes.”
Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD (2018, neutral): “Smaller mini-batches result in higher variance of the gradients, which affects convergence and error floor [Bottou et al., 2016, Dekel et al., 2012, Li et al., 2014].”
Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints (2018, background): “…also an increasing number of applications in which data is generated in a distributed manner and it (or features of it) are communicated over bandwidth-limited links to central processors Boyd et al. (2011); Balcan et al. (2012); Daume III et al. (2012); Daumé et al. (2012); Dekel et al. (2012).”
Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “…(C-PSGD) algorithms, the most popular implementation is based on the parameter server, which is essentially the mini-batch SGD admitting a convergence rate ofO(1/ √ Kn) [Agarwal and Duchi, 2011, Dekel et al., 2012, Lian et al., 2015], where in each iteration n stochastic gradients are evaluated.”
Better Mini-Batch Algorithms via Accelerated Gradient Methods (2011, background): “That is for every z ∈ Z and w , w (cid:48) ∈ W , (cid:107)∇ (cid:96) ( w , z ) − ∇ (cid:96) ( w (cid:48) , z ) (cid:107) ≤ H (cid:107) w − w (for more general Banach space case, the norm on the left hand side is the dual norm).”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “ethods, which involve extending classical stochastic methods to process multiple data points at a time, have emerged as a popular paradigm for distributed machine learning in data center environments [28, 88, 96, 102, 103]. In practice, however, they have been shown to have limited ﬂexibility to ada”