PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Optimality of Averaging in Distributed Statistical Learning

Jonathan Rosenblatt, Boaz Nadler

arXiv:1407.2724v2stat.MLmath.STstat.TH

TL;DR

The paper asks when averaging estimates from randomly split data matches centralized learning. It analyzes this strategy for empirical risk minimization and finds fixed-p agreement to leading order, but an accuracy loss in the high-dimensional generative linear setting.

  • Problem

    The paper asks how accurate simple averaging is relative to centralized estimation and when averaging is optimal.

    Source: §1 · p. 2

  • Method

    The authors study uniformly random data splits across m machines and average the machines’ empirical-risk-minimizing estimates.

    Source: §1 · p. 2, §2 · p. 4

  • Results

    When each machine has many observations per parameter, averaging has the centralized solution’s MSE; in high-dimensional generative linear models, splitting incurs an accuracy loss.

    Source: §1 · p. 3, §7 · p. 18

  • Takeaways & Limitations

    The analysis gives conditions for using parallelization to reduce runtime while preserving accuracy, though highly nonlinear models may have considerably larger excess parallelization error.

    Source: §7 · p. 18

    The analysis assumes samples are allocated uniformly at random; relaxing this assumption and studying other aggregation schemes remain future work.

    Source: §7 · p. 18

Abstract

from arXiv · show

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.

1. Introduction

The paper studies simple averaging of machine-wise M-estimates after uniformly random data splitting, comparing its statistical error with a centralized solution. It analyzes fixed- and growing-dimension regimes and the practical choice of machine count.

1. Introduction

  • The paper extends earlier bounds and comparisons of averaged estimators, including work on multinomial regression [Mcdonald et al., 2009, Theorem 3] and general learning tasks [Zinkevich et al., 2010].Zhang et al. [2013b, Theorem 1] derived leading-order MSE bounds and higher-order rates.Source: §1 · p. 2
  • For fixed p and n ≫ p, averaging matches the centralized solution’s MSE to leading order under suitable conditions.The paper derives an asymptotic expansion with exact MSE constants.Source: §1 · pp. 2–3
  • The fixed-p expansion also exposes higher-order accuracy loss from split-and-average, beyond its leading-order equivalence to centralized estimation.These terms can be derived up to second order.Source: §1 · p. 3
  • In the high-dimensional regime p/n → κ ∈ (0,1), splitting incurs a first-order accuracy loss that increases approximately linearly with the number of machines.The analysis is restricted to generative linear models.Source: §1 · p. 3
  • Simulations indicate that random splitting and averaging is attractive computationally and statistically for linear models with abundant data, while nonlinear models can incur considerable accuracy loss.The simulations cover both fixed-p and high-dimensional regimes.Source: §1 · p. 3
  • Varying the machine count traces an accuracy-complexity tradeoff that can inform deployment choices under a desired error level.The paper formulates machine-count choices as optimization problems for memory-constrained and runtime-driven parallelization.Source: §1 · p. 3

2. Problem Setup

The setup defines the target as the parameter minimizing population risk and the empirical estimator as the minimizer of sample loss. In the distributed setting, machines fit local estimators and a central node averages them; the paper asks how this compares with centralized estimation.

2. Problem Setup

  • M-estimation, or empirical risk minimization, estimates the target parameter by minimizing empirical risk over the observed samples.The framework covers common supervised and unsupervised learning tasks.Source: §2 · p. 4
  • With N samples randomly allocated across m machines, each machine computes an M-estimator on n = N/m samples, and the central node uses simple averaging.This is the aggregation procedure studied in the paper.Source: §2 · p. 4
  • The central questions concern averaged-estimator accuracy versus the centralized estimator, statistical properties, optimality, and how many machines to deploy.The target parameter θ* is assumed to exist uniquely in the parameter space.Source: §2 · p. 4

3. Fixed-p Setting

In the fixed-p setting, as each machine’s sample size grows, averaging has the same first-order statistical properties as centralized estimation. Higher-order terms reveal additional bias and MSE effects, with results illustrated for OLS and ridge regression.

3.1. First Order Statistical Properties of Averaging

  • Under Assumption Set 1, as n grows with p fixed, the averaged estimator is first-order equivalent to the centralized solution.The analysis considers the split-and-average estimator when data are abundant and p and m are fixed.Source: §3 · p. 4, §3.1 · p. 5
  • For Huber-loss M-estimators, averaging preserves the stated asymptotic robustness; machine-level outlier handling suffices only when overloaded machines and failures are negligible.Otherwise, the paper points to robust aggregation functions.Source: §3.1 · p. 6

3.2. Second Order Terms

  • Averaging reduces first-order variance but not second-order bias, which is m times the centralized bias; the second-order MSE comparison depends on risk curvature.The paper derives higher-order terms to reveal the accuracy loss of split-and-average schemes.Source: §3.2 · p. 7, §3.2.2 · p. 8

3.2.1. Notation and Assumptions

  • The second-order analysis uses a higher-order expansion of the machine-wise M-estimator; the stated conditions with s = 4 suffice for that expansion.The paper follows Rilstone et al. [1996] for the expansion and notation.Source: §3.2.1 · pp. 7–8

3.2.2. Second Order Bias

  • Under Assumption Set 2 with s = 3, the second-order bias is δ/N centrally and δ/n for the averaged estimator.Since n = N/m, the averaged estimator’s second-order bias is m times the centralized bias.Source: §3.2.2 · p. 8

3.2.3. Second Order MSE

  • Under Assumption Set 2 with s = 4, the paper gives an explicit second-order MSE matrix and excess-error expression; a positive-definiteness condition implies accuracy deterioration up to second order.The condition is that γ2 + γ′2 + γ3 + γ4 + γ′4 is positive definite.Source: §3.2.3 · p. 9

3.3.2. Ridge Regression

  • For ridge regression, parallelization has excess bias and excess second-order MSE, though higher-order terms can make it more accurate for particular parameter values.The paper notes this possibility for fixed-penalty ridge regression with null coefficients; it is not uniform over the parameter space.Source: §3.3 · p. 9, §3.2.3 · p. 9, §3.3.2 · p. 11

3.3.1. OLS

  • For a generative linear model, OLS parallelization has zero second-order bias but a positive-definite second-order excess MSE.The OLS result is derived from the error moments and the second-order MSE expression.Source: §3.3.1 · p. 10

4. High-Dimensional Approximation

The high-dimensional analysis studies generative linear models when p and n grow together, under assumptions including Gaussian predictors and a smooth, strongly convex loss. Unlike the fixed-p setting, averaging then incurs first-order accuracy loss; the paper also characterizes the estimator’s distribution and the loss’s dependence on model and noise conditions.

4. High-Dimensional Approximation

  • The analysis is restricted to generative linear models, with assumptions including Gaussian predictors with invertible covariance and a smooth, strongly convex loss.The paper notes that some assumptions can be relaxed, but its perturbation analysis as κ → 0 requires a loss with at least six bounded derivatives.Source: §4 · pp. 11–12
  • Each machine-wise estimate is inconsistent in this regime, and its asymptotic fluctuation is scaled by a deterministic r(κ) depending on κ, the loss, and the noise distribution.The fluctuation is represented using a Gaussian vector.Source: §4 · p. 12
  • Averaging is not first-order equivalent to the centralized solution when p and n grow together with p/n → κ ∈ (0, 1).The analysis describes this loss as typically moderate.Source: §4 · pp. 11–12
  • For several loss functions with Gaussian or Laplace errors, r2/r1 is approximately one; the paper says splitting’s accuracy loss is small when this ratio is small.The paper gives κ ≤ 0.2 as the value under a five-observations-per-parameter rule of thumb.Source: §4 · p. 13
  • The averaged estimator’s limiting distribution has m times less variance than the centralized estimator’s.The distributional result is stated for a fixed contrast under the assumptions of Lemma 1.Source: §4 · p. 13

5. Simulations

Simulations examine fixed-p and high-dimensional settings across linear and nonlinear tasks. They broadly support the theoretical contrast: fixed-p error ratios approach one at large sample sizes, while nonlinear models and high-dimensional splitting show accuracy costs.

5. Simulations

  • At large n, the fixed-p error ratio approaches one; at small to moderate n, splitting may add non-negligible error, especially for nonlinear models.Figure 1 reports medians and median absolute deviations across 500 replications for OLS, ridge, nonlinear least squares, and logistic regression.Source: §5 · p. 14, Figure 1 · p. 14
  • For OLS with fixed N, the parallelized estimate shows no excess bias, while both MSE approximations underestimate error as p/n departs from zero.The fixed-p and high-dimensional MSE approximations are described as quite accurate for small m, corresponding to large n.Source: §5 · p. 14, Figure 2 · p. 15
  • For ridge regression, splitting produces bias; at larger m the empirical error is smaller than the fixed-p second-order approximation predicts.The authors suggest higher-order error terms in the MSE matrix are negative definite.Source: §5 · p. 14
  • In high dimensions, the MSE ratio does not approach one even for large n; the OLS approximations are accurate over a wide range of n.The comparison holds κ and m fixed.Source: §5 · p. 14
  • Nonlinear models show considerable parallelization excess error in the fixed-p simulations.The simulation discussion identifies nonlinear models as a setting where splitting-related accuracy loss can be considerable.Source: §5 · p. 15

6. Practical Considerations

The section frames machine count as a choice between accuracy, runtime, and cost, with different constraints for fixed total data and fixed per-machine sample size. It uses error approximations to select machine counts for desired absolute or relative accuracy.

6. Practical Considerations

  • Fixed N trades accuracy for runtime, while fixed n reflects storage limits and the cost of processing more data; both settings define different machine-count choices.For fixed N, the goal is to minimize runtime while maintaining an error target; for fixed n, it is to minimize costs while attaining the target accuracy.Source: §6 · pp. 15–16
  • The section contrasts parallelization with subsampling, recommending parallelization when subsampling cannot deliver satisfactory accuracy.For fixed N, increasing m reduces runtime but also decreases accuracy, tracing an accuracy-complexity tradeoff.Source: §6 · p. 15
  • Second-order fixed-p error approximations make machine-count optimization meaningful, while the high-dimensional approximation uses a first-order error term.The leading fixed-p MSE term is independent of m; the section therefore uses the second-order expression for optimization.Source: §6 · p. 16
  • With N = 10^6, p = 100, and σ^2 = 10, the OLS absolute per-coordinate MSE target of 0.2 allows m ≤ 9,901; with n ≤ 10^4, m ≥ 51 meets the derived error level.The first bound is for fixed N; the second is for fixed n.Source: §6 · p. 17
  • For a 10% excess-error allowance in the OLS example, fixed N permits m ≤ 991, while fixed n permits m ≤ 102.Both examples use p = 100 and σ^2 = 10; the fixed-N example has N = 10^6 and the fixed-n example has n = 10^4.Source: §6 · p. 17

7. Discussion

The discussion finds that splitting and averaging can preserve leading-order accuracy in the classical regime when each machine has many observations per parameter, but incurs an accuracy cost in the analyzed high-dimensional setting. It also identifies uniform random allocation and simple aggregation as boundaries for future extensions.

7. Discussion

  • When n ≫ p, splitting loses little accuracy, although excess parallelization error can be considerable for highly nonlinear models.The discussion contrasts this result with prior work under different assumptions that found large or unbounded error.Source: §7 · p. 18
  • In the high-dimensional analysis, currently confined to generative linear models, splitting with few observations per parameter incurs an accuracy cost that remains quantifiable despite non-degenerate random limits.The discussion contrasts this behavior with the classical fixed-p regime.Source: §7 · p. 18
  • Uniform random allocation facilitates analysis but may be restrictive; future work could allow systematic machine differences and examine richer aggregation schemes.The authors specifically mention minimum Kullback-Leibler divergence aggregation and applications to image, sound, and graph data.Source: §7 · p. 18

A. Proof of Theorem 1

The proof develops asymptotic expansions for machine-wise and centralized estimators, then compares their leading behavior for a fixed number of machines.

A. Proof of Theorem 1

  • Under Assumption Set 1, the proof invokes classical statistical theory for estimators obtained by empirical-risk optimization.The supplied passage introduces the machine-wise estimator expansion.Source: A. Proof of Theorem 1 · p. 18
  • The leading error term is linear in the influence functions, and the machine-wise estimators are averaged across machines.The proof applies an expansion to the average and separately to the centralized solution.Source: A. Proof of Theorem 1 · pp. 18–19
  • For fixed m, the cited proof step equates the remainder scales oP(N^-1/2) and oP(n^-1/2), then concludes that Eq. (4) follows.Source: A. Proof of Theorem 1 · p. 19

B. Proof of Theorem 2

The proofs use asymptotic expansions to analyze the error terms in Theorems 2 and 3. The supplied passages identify the expansion conditions and some steps in the termwise calculations.

B. Proof of Theorem 2

  • Under Assumption Set 2 with s = 3, the proof uses an expansion of the centralized estimator to decompose the error.The expansion is attributed to Proposition 3.2 of Rilstone et al. (1996).Source: B. Proof of Theorem 2 · p. 19
  • The proof notes that δ depends on problem parameters but is independent of n.This statement appears in the discussion of the second-order term.Source: B. Proof of Theorem 2 · p. 19

C. Proof of Theorem 3

  • Under Assumption Set 2 with s = 4, the proof expands the averaged estimate, substitutes it into M2, and collects terms.It then analyzes summands separately, including terms where k = l.Source: C. Proof of Theorem 3 · pp. 19–20

D. Proof of Proposition 1

The appendices compute the matrices used in the OLS and ridge proofs, then collect Wishart identities that support those calculations.

D. Proof of Proposition 1

E. Proof of Proposition 2

  • In the ridge proof, γ0 is evaluated as λ2,6(1 + p)2B, with the simplifying case Σ = I used in the derivation.The proof also states that none of the terms cancel in the ridge setup.Source: E. Proof of Proposition 2 · pp. 21–22

F. Properties of Wishart Matrices

  • The Wishart appendix states expectation identities for independent Wishart matrices, including E[S1BS1] and E[S1BS2BS1].These identities are used in the proposition proofs; the appendix also notes that some results extend to Wishart matrices with general covariance.Source: F. Properties of Wishart Matrices · pp. 22–23

G.1. Proof of Lemma 1

The proofs compare centralized and averaged estimation error, then use small-parameter expansions to analyze the residual-noise equations as κ approaches zero.

G.1. Proof of Lemma 1

  • The parallelization accuracy loss is obtained by comparing the centralized and m-machine averaged mean-squared errors.The proof first gives the centralized error and the averaged-estimator error, then compares them.Source: §G.1 · p. 24
  • For a three-times-differentiable loss with bounded third derivative, the small-c proximal-operator expansion uses the solution branch that tends to zero.The alternative branch diverges as c approaches zero.Source: §G.1 · p. 25

G.2. Approximating The Residual Noise Equations

  • As κ approaches zero, the coupled equations for r(κ) and c(f, κ) admit an asymptotic form whose coefficients are determined by matching powers of κ.The derivation assumes a power-series expansion and compares terms of equal order.Source: §G.2 · pp. 26–27

H. Scope of Theorem 1

Theorem 1 is illustrated across several regression and classification settings, subject to the stated regularity conditions.

H. Scope of Theorem 1

  • Nonlinear least squares is an example under suitable regularity conditions on the function family gθ.The linear case is also discussed in the cited examples.Source: H. Scope of Theorem 1 · p. 28
  • Nonlinear quantile regression uses tilted hinge loss, with its nondifferentiability handled when X is continuous.The passage states that the probability of nondifferentiability at θ* is then zero.Source: H. Scope of Theorem 1 · p. 28
  • Nonlinear robust regression with the Huber loss is included among the example applications.The passage introduces this setting without further conditions in the supplied text.Source: H. Scope of Theorem 1 · pp. 27–28
  • Binary regression with a known, sufficiently regular link function covers Logistic, Probit, and Complementary Log-Log regression.The example takes the loss to be negative log likelihood.Source: H. Scope of Theorem 1 · p. 28
  • An l2-regularized SVM is another example; its risk regularity and differentiability conditions are addressed for continuous X.The passage cites Shamir [2012] for the risk regularity assumption.Source: H. Scope of Theorem 1 · p. 28

Related papers

Loading 1407.2724v2…