On the Optimality of Averaging in Distributed Statistical Learning

By Jonathan D. Rosenblatt, Boaz Nadler. 2014

125 citations recorded by the source corpus.

A common approach to statistical learning with big-data is to randomly split it among $m$ machines and learn the parameter of interest by averaging the $m$ individual estimates. In this paper, focusing on empirical risk minimization, or equivalently M-estimation, we study the statistical error incurred by this strategy. We consider two large-sample settings: First, a classical setting where the number of parameters $p$ is fixed, and the number of samples per machine $n\to\infty$. Second, a high-dimensional regime where both $p,n\to\infty$ with $p/n \to \kappa \in (0,1)$. For both regimes and under suitable assumptions, we present asymptotically exact expressions for this estimation error. In the fixed-$p$ setting, under suitable assumptions, we prove that to leading order averaging is as accurate as the centralized solution. We also derive the second order error terms, and show that these can be non-negligible, notably for non-linear models. The high-dimensional setting, in contrast, exhibits a qualitatively different behavior: data splitting incurs a first-order accuracy loss, which to leading order increases linearly with the number of machines. The dependence of our error approximations on the number of machines traces an interesting accuracy-complexity tradeoff, allowing the practitioner an informed choice on the number of machines to deploy. Finally, we confirm our theoretical analysis with several simulations.

Subfields: Artificial Intelligence, Management Science and Operations Research

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 Management Science and Operations Research

Citations in the corpus

Is Local SGD Better than Minibatch SGD? (2020, background): “(Zinkevich et al., 2010; Zhang et al., 2012; Li et al., 2014; Rosenblatt and Nadler, 2016; Godichon-Baggioni and Saadane, 2017; Jain et al., 2017).”
Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “Rosenblatt and Nadler (2016) have also discussed the asymptotic equivalence of OSA with vanilla-SGD by providing an analysis up to the second order terms.”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, methodology): “An important class of algorithms are based on one-round aggregation methods (Rosenblatt and Nadler, 2016, Zhang et al., 2012, 2015).”
Communication-efficient Sparse Regression (2017, background): “Even more recently, Rosenblatt and Nadler (2014) studied the optimality of averaged ERM in two asymptotic settings: N →∞, m, p fixed and p, n→∞, pn → µl ∈ (0, 1), where n = Nm is the number of samples per machine.”
Distributed Statistical Estimation and Rates of Convergence in Normal Approximation (2017, background): “Li, Srivastava and Dunson (2016); Scott et al. (2016); Shang and Cheng (2015); Minsker et al. (2014) have investigated closely related problems for distributed Bayesian inference.”
Parallelizing Stochastic Approximation Through Mini-Batching and Tail-Averaging (2016, methodology): “The framework established as a part of Theorem 1 can be extended in a very straightforward manner to provide sharp ﬁnite sample generalization error bounds for parameter mixing/model averaging schemes [2, 3, 25, 26].”
Communication trade-offs for Local-SGD with large step size (2019, unknown): “Rosenblatt and Nadler [35] have also discussed the asymptotic equivalence of OSA with vanilla-SGD by providing an analysis up to the second order terms.”
Efficient Distributed Learning with Sparsity (2016, background): “At iteration t 0, the master machine minimizes the following program β̂0 arg minL1pβq λ0||β||1.”
Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification (2016, background): “As mentioned in Rosenblatt and Nadler (2014), these schemes do not appear to offer improvements in the bias error while offering near linear parallelization speedups on the variance.”
Accelerating Stochastic Gradient Descent (2017, background): “992) demonstrated that averaged SGD obtains statistically optimal estimation rates. Several works have obtained non-asymptotic statistical rates for averaged SGD (Bach and Moulines, 2011; Bach, 2014; Rosenblatt and Nadler, 2014; Dieuleveut and Bach, 2015) for various stochastic approximation problem”
Communication-efficient sparse regression: a one-shot approach (2015, background): “Even more recently, Rosenblatt and Nadler (2014) studied the optimality of averaged ERM in two asymptotic settings: N → ∞, m, p fixed and p, n → ∞, p n → μl ∈ (0, 1), where n = N m is the number of samples per machine.”