PaperlayerView exact revision on arXiv

Source-linked AI summary

Communication Efficient Distributed Optimization using an Approximate Newton-type Method

Ohad Shamir, Nathan Srebro, Tong Zhang

arXiv:1312.7853v4cs.LGmath.OCstat.ML

TL;DR

Distributed learning must minimize a population objective using data split across machines while limiting expensive communication, and one-shot averaging can have unfavorable population suboptimality. The paper introduces DANE, an approximate Newton-like distributed method, and shows that for stochastic quadratic objectives its communication rounds can remain constant with growing local data or avoid dependence on total sample size under stated regimes.

  • Problem

    Distributed stochastic optimization seeks accurate population-objective solutions from data split across machines, but one-shot averaging can be much worse than the empirical minimizer when strong convexity is small.

  • Method

    DANE performs approximate Newton-like local optimization steps using each machine’s estimate of the problem geometry, without explicitly computing Hessians.

  • Results

    For stochastic quadratic objectives, DANE needs a constant number of communication rounds when L/λ is fixed and n is large, and roughly scales with m but not N = nm when λ scales as 1/√nm.

  • Takeaways & Limitations

    DANE provides a distributed optimization method with provable communication behavior that improves with data size for quadratic objectives and has supporting evidence on non-quadratic objectives.

  • Takeaways & Limitations

    For general non-quadratic objectives, the analysis proves convergence only under sufficiently small stepsize or sufficiently large regularization and does not establish an advantage over distributed gradient descent.

Abstract

from arXiv · show

We present a novel Newton-type method for distributed optimization, which is particularly well suited for stochastic optimization and learning problems. For quadratic objectives, the method enjoys a linear rate of convergence which provably \emph{improves} with the data size, requiring an essentially constant number of iterations under reasonable assumptions. We provide theoretical and empirical evidence of the advantages of our method compared to other approaches, such as one-shot parameter averaging and ADMM.

1 Introduction

The paper studies communication-efficient distributed optimization for stochastic learning, where machines alternate local optimization with communication to minimize an empirical objective. It motivates DANE as an approximate Newton-like alternative to one-shot averaging, gradient methods, quasi-Newton methods, and ADMM, with favorable quadratic convergence behavior.

  • Problem setting: Distributed optimization assigns local functions or samples to m machines and seeks to minimize their average objective.In the stochastic setting, N = nm independent samples are evenly distributed across machines, and the empirical objective approximates the population objective.
  • Problem setting: Communication-efficient methods alternate local optimization with simple map-reduce communication rounds because communication is costly in practice.The paper’s goal is to optimize the empirical objective using a minimal number of such iterations.
  • Existing approaches: One-shot parameter averaging can remain much worse for the population objective than the empirical minimizer and cannot generally reach arbitrary suboptimality ε.The paper argues that additional communication rounds are necessary rather than relying on more clever averaging.
  • Existing approaches: Gradient-based distributed methods require communication rounds that depend polynomially on conditioning, while small strong convexity can make this dependence grow with sample size.Accelerated gradient descent can require roughly 4√nm rounds when λ scales as 1/√nm.
  • DANE: DANE uses approximate Newton-like steps based on each machine’s local problem geometry, implicitly exploiting local Hessians for quadratic objectives without explicitly computing Hessians.The method is applicable to smooth, strongly convex problems, although its strongest theoretical analysis focuses on quadratics.
  • DANE: For stochastic quadratic objectives, DANE’s iteration count can be constant when L/λ is fixed and n is large, and can scale roughly with m but not total sample size N = nm when λ scales as 1/√nm.The paper presents this as the first algorithm known to have such behavior and reports similar evidence for non-quadratic objectives.

2 Stochastic Optimization and One-shot Parameter Averaging

With finite stochastic data, one-shot averaging can appear statistically efficient but is highly sensitive to strong convexity, especially as regularization decreases with sample size. The paper shows that this sensitivity can prevent one-shot averaging from benefiting from data distributed across machines.

  • Stochastic optimization: The population objective cannot be minimized arbitrarily accurately from only N = nm samples, even using the exact empirical minimizer.This motivates comparing distributed methods with the statistical accuracy attainable from the full sample.
  • One-shot parameter averaging: One-shot averaging was reported to achieve a 1/(nm) population-suboptimality rate under bounded derivative-moment assumptions.The cited analysis also allows O(n^-2) terms to be reduced to O(n^-3) with bias correction.
  • One-shot parameter averaging: The bound’s dependence on the strong convexity parameter λ becomes problematic because λ commonly decreases with sample size.In regularized stochastic optimization, λ can scale as 1/√nm, making the resulting bound useless even in its first term.
  • One-shot parameter averaging: For λ ≤ O(1/√n), one-shot averaging can have population suboptimality no better than using only n samples, despite a total of nm samples.Thus, adding machines and data does not necessarily improve the one-shot estimator’s population accuracy.
  • One-shot parameter averaging: When λ is small, local minimizers can be substantially biased away from the population minimizer, and averaging does not reduce this bias.The paper states that the proposed bias correction does not remedy the problem.

3 Distributed Approximate Newton-type Method

DANE alternates global gradient aggregation with local objective optimization and averaging, producing a distributed approximation to Newton-like steps without communicating Hessians. Its approximation becomes especially favorable when local objectives are similar, while the strongest global guarantees are established for quadratic objectives.

  • Method overview: DANE uses two distributed averaging computations per iteration and converges to the empirical optimum under suitable parameter choices.The synchronized iterate is formed by averaging local iterates after separate local optimizations.
  • Method overview: Each machine solves a local optimization problem using its local objective and the averaged global gradient at the current iterate.This local step is the core computational operation of DANE.
  • Newton-type approximation: When all local objectives are equal and μ = 0, DANE reaches the overall empirical optimum in a single iteration.This is described as an ideal Newton-type iteration with a potential function perfectly aligned with the objective.
  • Convergence behavior: As local sample sizes grow, increasingly similar local objectives can make DANE approach the ideal Newton-type iteration and reduce the required number of iterations.The paper explicitly connects this improvement to n →∞ in the stochastic setting.
  • Newton-type approximation: For quadratic objectives, DANE approximates Newton steps by using local Hessian information implicitly, without explicitly computing or communicating Hessians.Its update replaces the inverse average Hessian with an average of inverse local Hessians, possibly regularized.
  • Convergence behavior: Global convergence is analyzed rigorously for quadratic objectives, while the non-quadratic analysis gives guarantees for small η or large μ but does not establish an advantage over distributed gradient descent.For non-quadratic objectives, the paper additionally shows improved convergence as local problems become more similar.

4 DANE for Quadratic Objectives

For quadratic objectives, DANE’s convergence is governed by how well locally estimated Hessians approximate the global Hessian, improving as stochastic sample sizes make those estimates more similar. Under strong-convexity assumptions, this yields constant or sample-size-independent communication behavior in important regimes.

  • Quadratic analysis: If ||I − η H̃^-1H||2 < 1, DANE converges linearly; the rate improves when η is near 1 and H̃ approximates H.For sufficiently similar local Hessians and a well-conditioned global Hessian, H̃^-1H is close to I.
  • Quadratic analysis: For quadratic objectives, Lemma 1 sets η = 1 and chooses μ from the Hessian-deviation bound β and global curvature λ to obtain a contraction guarantee.The stated choice is μ = max{0, 8β^2/λ − λ}.
  • Quadratic analysis: DANE uses approximate Newton steps based on local Hessians, while stochastic analysis controls convergence through their deviation from the global Hessian.The method’s quadratic guarantee combines a Hessian-approximation condition with concentration bounds for stochastic local objectives.
  • Stochastic quadratic problems: In stochastic quadratic problems, matrix concentration makes local Hessians close to their average, enabling Theorem 3 to guarantee ε-suboptimality with probability at least 1 − δ.The analysis first bounds local Hessian deviations and then plugs that bound into the quadratic convergence results.
  • Stochastic quadratic problems: When L/λ is fixed and n is sufficiently large, DANE needs a constant or even a single iteration for any target accuracy ε.The required sample size is only logarithmically large in the target accuracy under the stated theorem.
  • Regularized objectives: With regularization inducing λ = Θ(1/√N), DANE’s communication rounds do not increase with total sample size N and scale only linearly with the number of machines m.This contrasts with distributed gradient methods whose iteration count can grow with sample size in the same regime.

5 Convergence Analysis for Non-Quadratic Objectives

For general smooth, strongly convex objectives, DANE has a convergence guarantee under curvature assumptions, but the generic analysis is weaker than the quadratic analysis and does not capture similarity among local objectives. A variant can recover a linear rate that improves as local objectives become more similar.

  • Assumptions: The generic analysis assumes each local objective is smooth and strongly convex, while the combined objective is also smooth and strongly convex.These assumptions are expressed through lower and upper Hessian bounds for local and combined objectives.
  • Generic convergence: If ρ > 0, DANE’s objective gap contracts geometrically as φ(w(t)) − φ(ŵ) ≤ (1 − ρ)^t[φ(w(0)) − φ(ŵ)].The theorem gives linear convergence in terms of the parameter ρ.
  • Generic convergence: With μ > 0 and a sufficiently small η, DANE converges to ŵ; when local objectives are strongly convex, μ = 0 is also possible with sufficiently small η.Taking μ → ∞ and η = μ/L recovers distributed gradient descent and its familiar guarantee.
  • Similarity-sensitive analysis: The generic theorem is weak because it does not use relationships among local objectives, whereas a DANE variant improves its linear rate as those objectives become more similar to the global objective.This similarity-sensitive result is presented as a partial bridge to the stronger quadratic analysis.
  • Empirical comparison: Figure 2 compares DANE and ADMM across machine counts and sample sizes using iteration number on the x-axis and log10 suboptimality on the y-axis.DANE appears in the top row and ADMM in the bottom row.
  • Empirical comparison: Figure 3 reports iterations to reach < 10^-6 accuracy across three datasets and varying machine counts, marking non-convergence after 100 iterations with an asterisk.It compares DANE settings η = 1 with μ = 0, λ, and 3λ against ADMM.

6 Experiments

Experiments show that DANE converges linearly on quadratic objectives, with convergence improving as data size increases, and generally reaches target accuracy in fewer iterations than ADMM on non-quadratic datasets. Multi-round methods approach the regularized-loss optimum, whereas one-shot averaging can remain significantly suboptimal.

  • Quadratic objectives: DANE exhibits linear convergence on the synthetic ridge-regression problem, and its convergence rate improves as the total data size increases.The comparison varies the number of machines while increasing the total number of examples.
  • Quadratic objectives: ADMM becomes more accurate with additional data after a fixed iteration count, but its convergence rate is slower and does not improve with data size.The paper notes that ADMM does not exploit statistical similarity across machines.
  • Non-quadratic objectives: DANE generally reaches 10^-6 accuracy in fewer iterations than ADMM on COV1, ASTRO-PH, and MNIST-47.The experiments use η = 1 and compare µ = 0 and µ = 3λ across different machine counts.
  • Non-quadratic objectives: For µ = 0 and many machines, DANE may fail to converge; increasing µ restores convergence but slows the average convergence rate.This unfavorable regime corresponds to very small data size per machine.
  • Test loss: With 64 machines, DANE and ADMM converge to the regularized-loss minimizer’s test loss, while bias-corrected one-shot averaging can remain significantly suboptimal.Figure 4 compares average regularized smooth-hinge test loss across iterations.

A.1 Proof of Theorem 1

The proof constructs a strongly convex stochastic example in which each machine’s local optimum remains biased as sample size grows, showing that bias-corrected one-shot averaging need not approach the global optimum. The resulting lower bound establishes persistent suboptimality under small regularization.

  • Bias construction: When λ is smaller than O(1/√n), local predictors can retain non-decaying deviations whose distribution depends on the data distribution and loss shape.The proof emphasizes that the predictors are generally biased, not merely variable.
  • Bias construction: The constructed loss is λ-strongly convex over W = [−2/λ, log(1/λ)] under standard Gaussian examples, with Ez[f′(w; z)2] ≤ 9.These conditions define the stochastic instance used for the counterexample.
  • Bias construction: The local optimum is represented as the unique root w(˜z) of the stationarity equation, with ˜z retaining a standard Gaussian distribution.The proof uses this representation to calculate the expected local solution.
  • Bias lower bound: E[ŵ1] ≤ −1/(6λ√n), while the true optimum satisfies w∗ = −0.5671... > −3/5 under λ ≤ 1/(9√n).The separation between the expected local optimum and w∗ yields a bias lower bound.
  • Bias lower bound: E[(w∗−w̄)2] ≥ 1/(100λ2n), establishing a nonzero mean-squared error for averaged local solutions.The theorem combines this bias bound with the remaining inequalities in the proof.
  • Bias correction: Bias correction with r = 1/2 and λ = 1/(10√n) still gives E[ŵk] ≈ −1.8 versus w∗ = −0.5671..., so the bias remains constant with data size.The corrected solution is formed as ŵk = 2ŵk,1 − ŵk,2.

C Proof of Lemma 1

The proof bounds the deviation between the averaged local Hessian and the global Hessian through spectral perturbation arguments. A regularization parameter µ is selected to control this deviation under a Hessian-dispersion assumption.

  • Spectral bounds: Lemma 3 relates the spectral deviation of a regularized inverse-Hessian expression to the smallest eigenvalue λ of H.The proof identifies the relevant diagonal-matrix quantity as λ/(λ + µ).
  • Spectral bounds: Lemma 4 bounds averaged inverse perturbations when A is positive definite, its minimal eigenvalue exceeds µ, and each perturbation norm is at most β < γ.The proof applies the bound with A = H + µI and Δi = Hi − H.
  • Choice of regularization: Assuming β < 1/2(λ + µ), the proof derives an upper bound on the Hessian approximation error and optimizes it over µ.The stronger condition is used to control the right-hand side of the perturbation inequality.
  • Choice of regularization: The proof handles separate cases depending on whether λ2 > 8β2, yielding either µ = 0 or a positive µ choice proportional to β2.For µ = 0, the bound becomes 4β2/λ2.
  • Choice of regularization: The required condition on β is justified by the selected µ and the inequality max{x, 8/x} > 2 for positive x.This closes the consistency check for the lemma’s assumptions.

D Proof of Lemma 2

The proof controls local-to-global Hessian deviations using matrix concentration. Because local Hessians average n samples while the global Hessian averages mn samples, the resulting bounds depend logarithmically on dimension and machine count.

  • Hessian concentration: H is the average Hessian of mn i.i.d. quadratic functions, while each Hi averages n functions with eigenvalues at most L.This distinction sets the sample sizes for the global and local concentration bounds.
  • Hessian concentration: Matrix Hoeffding concentration gives local Hessian deviation bounds scaling as 8L2 log(d/δ)/n.The bound holds for each machine with probability 1 − δ over its samples.
  • Hessian concentration: The corresponding simultaneous bound across machines scales as 8L2 log(dm/δ)/n.The machine count enters through the logarithmic confidence adjustment.
  • Hessian concentration: The proof also obtains a bound of 32L2 log(dm/δ)/n for the aggregate Hessian comparison.This bound is used in the subsequent lemma argument.

E Proof of Theorem 3

The proof derives iteration bounds for achieving optimization error at most ϵ, using strong convexity and a case analysis of the bound’s denominator.

  • Strong-convexity condition: Strong convexity of ˆF(w) is used when applying Lemma 1 to derive the iteration requirement.The passage notes that strong convexity of the instantaneous losses implies ˆF(w) is λ-strongly convex.
  • Iteration bound: The required iteration count is formulated for reaching optimization error ≤ϵ.
  • Case analysis: The proof analyzes the iteration bound separately according to the two cases in (28).For the first case, the denominator in (29) is bounded below by 2 log(2).
  • Case analysis: In the first case, the iteration requirement is expressed using an O(·) bound.
  • Case analysis: In the second case, an additional inequality yields an upper bound on iteration bound (29).

F Proof of Theorem 4

The proof establishes a contraction inequality for the objective gap and recursively applies it, under the theorem’s smoothness, strong-convexity, and stated assumptions.

  • Lemma 5: Lemma 5 states inequalities that hold under the conditions of Theorem 4.
  • Assumption scope: A footnote distinguishes strong convexity of ˆF(w) from requiring strong convexity of every individual loss and notes a condition involving λ, L, and n.
  • Convexity and conjugacy: The proof uses that the relevant function is 1/(L_i+µ)-strongly convex and relates gradients through the conjugate h*.
  • Convexity and conjugacy: Strong convexity provides a lower bound relating ∥∇φ(w)−∇φ(ŵ)∥_2 to λ∥w−ŵ∥_2.
  • Proof steps: At iteration t, the proof starts from a first-order equation and uses smoothness, strong convexity, Jensen’s inequality, and prior inequalities.
  • Contraction: The objective gap contracts by a factor of 1−ρ at each iteration.
  • Contraction: Recursively applying the contraction inequality yields the desired bound.

G Proof of Theorem 5

The proof rewrites the objective at the optimum through Bregman-divergence identities, then applies relative divergence assumptions to obtain the desired result.

  • Bregman expansion: The proof begins with an expansion of φ(ŵ) around w(t−1) using the gradient and Bregman divergence Dφ.
  • Bregman expansion: The expansion is rewritten in terms of φ(w(t)), the step from w(t−1) to w(t), and divergences at both iterates.
  • Divergence assumptions: The proof uses the assumption Dφ(w(t);w(t−1))≤η^-1Dh(w(t);w(t−1)).
  • Divergence assumptions: This assumption yields inequality (33), linking Dh(w(t−1);w(t)) and the objective-gradient term to the objective gap.
  • Final bound: The final chain uses inequality (33), φ(ŵ)≤φ(w(t)), and Dφ(ŵ;w(t−1))≥γDh(ŵ;w(t−1)).
  • Final bound: Applying these inequalities produces the desired result.
Loading 1312.7853v4…