PaperlayerView exact revision on arXiv

Source-linked AI summary

GIANT: Globally Improved Approximate Newton Method for Distributed Optimization

Shusen Wang, Farbod Roosta-Khorasani, Peng Xu, Michael W. Mahoney

arXiv:1709.03528v5cs.LGcs.DCmath.OCstat.ML

TL;DR

Distributed empirical risk minimization needs optimization methods that reduce communication while exploiting distributed computation. GIANT averages locally computed approximate Newton directions into a globally improved direction, achieving improved convergence and strong empirical performance with a simple communication-efficient design. Its guarantees and formulation are scoped to smooth, strongly convex objectives, with extensions beyond this setting left for future work.

  • Problem

    Distributed optimization must handle massive datasets and communication-limited networks while retaining efficient convergence.

  • Method

    GIANT averages workers’ locally computed approximate Newton directions to form a globally improved direction without communicating exact Hessian matrices.

  • Results

    GIANT achieves improved theoretical convergence over comparable methods and empirically outperforms AGD, L-BFGS, and DANE.

  • Takeaways & Limitations

    GIANT offers communication-efficient distributed optimization with four or six communication rounds per iteration and one tuning parameter.

  • Takeaways & Limitations

    GIANT is developed only for unconstrained problems with smooth, strongly convex objectives; extensions to constrained, nonsmooth, and nonconvex settings remain future work.

Abstract

from arXiv · show

For distributed computing environment, we consider the empirical risk minimization problem and propose a distributed and communication-efficient Newton-type optimization method. At every iteration, each worker locally finds an Approximate NewTon (ANT) direction, which is sent to the main driver. The main driver, then, averages all the ANT directions received from workers to form a {\it Globally Improved ANT} (GIANT) direction. GIANT is highly communication efficient and naturally exploits the trade-offs between local computations and global communications in that more local computations result in fewer overall rounds of communications. Theoretically, we show that GIANT enjoys an improved convergence rate as compared with first-order methods and existing distributed Newton-type methods. Further, and in sharp contrast with many existing distributed Newton-type methods, as well as popular first-order methods, a highly advantageous practical feature of GIANT is that it only involves one tuning parameter. We conduct large-scale experiments on a computer cluster and, empirically, demonstrate the superior performance of GIANT.

1 Introduction

GIANT targets communication-efficient distributed optimization by increasing local computation while using second-order information. The paper establishes improved theoretical convergence and reports superior empirical performance, with one tuning parameter and few communication rounds.

  • 1 Introduction: The method addresses distributed settings where data exceed single-machine memory and where network bandwidth or latency makes communication costly.Federated settings especially motivate trading additional local computation for fewer communications.
  • 1 Introduction: GIANT combines local second-order computation with global aggregation to reduce communication in distributed empirical risk minimization.Its design follows the goal of performing more local computation before communicating across the network.
  • 1 Introduction: For quadratic objectives, GIANT has logarithmic condition-number dependence in iteration complexity, versus at least square-root dependence for prior methods.GIANT and DANE are identical for quadratic problems, while the convergence guarantee improves over DANE.
  • 1 Introduction: For general smooth objectives, GIANT achieves linear-quadratic local convergence, with significant theoretical improvement when data points greatly outnumber features.The analysis concerns convergence near the optimum and highlights big-data regimes.
  • 1 Introduction: GIANT requires only one tuning parameter and consistently outperforms AGD, L-BFGS, and DANE in computer-cluster experiments.The single parameter is the maximal iteration count of the local subproblem solvers.

2 Problem Formulation

The paper formulates distributed empirical risk minimization for supervised learning with smooth, strongly convex losses. Data and loss functions are partitioned across worker machines, primarily in the regime where samples greatly outnumber features.

  • 2 Problem Formulation: The objective minimizes empirical risk over feature vectors and responses in a supervised-learning problem.Each loss is convex, twice differentiable, and smooth.
  • 2 Problem Formulation: Strong convexity ensures a unique minimizer w⋆ for the empirical-risk objective.The formulation assumes the aggregate objective is strongly convex.
  • 2 Problem Formulation: The n training samples and corresponding loss functions are partitioned among m worker machines, with local sample size s = n/m.Theoretical results require s > d, although experiments reportedly work well when s < d.
  • 2 Problem Formulation: The analysis focuses on regimes with n much larger than d and local datasets larger than the feature dimension.For n much smaller than d, the paper suggests considering a dual formulation when it has compatible structure.

3 Algorithm Description

GIANT avoids communicating full Hessian matrices by having workers compute local approximate Newton directions and aggregating only d-dimensional vectors. Its harmonic-mean construction preserves a close approximation to the true Newton direction under incoherent data while permitting Hessian-free iterative solves.

  • 3.1 Gradient and Hessian: GIANT reduces each iteration's communication complexity to ˜O(d) words by aggregating d-dimensional vectors instead of d × d Hessian matrices.Each iteration uses four broadcast/reduce rounds, while exact Hessian aggregation would require ˜O(d2) communication.
  • 3.2 Approximate NewTon Direction: Workers compute Approximate NewTon directions from local Hessian systems, using conjugate gradient to avoid explicitly forming or inverting dense Hessians.The resulting solves use only Hessian-vector products in a Hessian-free manner.
  • 3.3 Globally Improved ANT Direction: With sufficiently large local sample sizes, local Hessians provide spectral approximations to the global Hessian, supporting the quality of the aggregated direction.The analysis assumes workers hold random local samples; data-independent partitions are equivalent to uniform sampling for i.i.d. data.
  • 3.3 Globally Improved ANT Direction: The driver forms the GIANT direction by averaging workers' local ANT directions, corresponding to the inverse of a harmonic-mean Hessian approximation.The harmonic mean is close to the arithmetic mean, and thus the GIANT direction closely approximates the true Newton direction when data are incoherent.
  • 3.4 Complexity Analysis: Each worker's per-iteration computation costs O(sdq), or O(ϱsdq) in expectation for sparse feature matrices.Here s is local sample size, q is the number of conjugate-gradient iterations, and ϱ is feature sparsity.

4 Theoretical Analysis

The analysis establishes global convergence for quadratic objectives, linear-quadratic local convergence for smooth non-quadratic losses, and similar rates when local Newton systems are solved inexactly. These guarantees rely on sample-size, coherence, Hessian smoothness, and local-solution assumptions.

  • 4.1 Quadratic Loss: The quadratic analysis treats a fixed Hessian, while the general-loss analysis tracks an iteration-dependent Hessian whose coherence may change over time.For quadratic loss, the Hessian does not depend on w; for general loss, the analysis uses H_t and coherence μ_t.
  • 4.1 Quadratic Loss: GIANT reaches fixed precision with only logarithmic dependence on the condition number for quadratic objectives when the total sample size is sufficiently large.The theorem requires a local sample-size condition involving row coherence, dimension, and the number of partitions; the iteration count is logarithmic in κ.
  • 4.2 General Smooth Loss: For smooth non-quadratic losses, GIANT has linear-quadratic local convergence under an L-Lipschitz Hessian assumption.The quadratic term matches standard Newton convergence, while the linear term arises from Hessian approximation and becomes smaller with larger local sample size.
  • 4.2 General Smooth Loss: Near the optimum, the condition-number dependence can be expressed using the Hessian at the solution rather than the Hessian at every iteration.This follows from the Lipschitz-Hessian assumption and the local-neighborhood condition.
  • 4.3 Inexact Local Solves: Inexact local Newton solves preserve the exact algorithm's convergence results when the solve error is on the order of η√m + η2.Theorem 4 extends the quadratic and general-loss guarantees to approximate local solutions, with conjugate-gradient conditions supplied separately.

5 Experiments

Experiments evaluate GIANT against AGD, L-BFGS, and DANE on large logistic-regression problems, emphasizing convergence, time efficiency, and scalability. GIANT converges faster at equal wall-clock time and remains effective as data and node counts grow.

  • 5.1 Compared Methods: The evaluation uses logistic regression with ℓ2 regularization, random Fourier features, and datasets including MNIST8M, Epsilon, and Covtype.
  • 5.1 Compared Methods: Using the same wall-clock time, GIANT converges faster than AGD, DANE, and L-BFGS in training objective value and test classification error.
  • 5.3 Experiments on Time Efficiency: GIANT converges in all experiments even though the local sample size is about half the feature dimension, below the theory’s required threshold.
  • 5.3 Experiments on Time Efficiency: On datasets enlarged fivefold and twenty-fivefold with proportionally more compute nodes, GIANT and DANE are almost unaffected while AGD and L-BFGS converge more slowly.
  • 5.4 Experiments on Scalability: As nodes increase from 75 to 375, per-iteration time rises 367% for AGD, 112% for L-BFGS, and 19% for GIANT.
  • 5.4 Experiments on Scalability: GIANT’s scalability reflects computation-intensive iterations with only 6 communication rounds, limiting the effect of rising communication costs.

6 Conclusions and Future Work

GIANT is a communication-efficient Newton-type method for distributed empirical risk minimization, combining local approximate Newton directions with practical implementation advantages. Its analysis uses sketching and approximate subproblem solutions, while extensions beyond smooth strongly convex unconstrained problems remain future work.

  • Conclusions: Each GIANT iteration requires four or six communication rounds with complexity ˜O(d), while convergence requires sufficiently large n relative to dm.Here d is the feature count and m is the number of partitions.
  • Future Work: GIANT is developed only for unconstrained problems with smooth, strongly convex objectives; extensions to constrained, nonsmooth, and nonconvex settings are left for future work.The paper notes that strong convergence bounds for these extensions appear nontrivial.
  • Sketching: Uniform, leverage-score, Gaussian, Rademacher, and subsampled randomized Hadamard sketches can satisfy the required sketching assumption, with nonuniform alternatives removing coherence dependence.The alternatives are more expensive to implement, creating a communication-computation trade-off.
  • Method: Local approximate Newton directions are formed from sketched quadratic subproblems and combined into local and global approximate Newton directions.The analysis defines the quadratic auxiliary function and studies exact and inexact solutions to its sketched subproblems.

A.3 Analysis of Uniform Sampling

The uniform-sampling analysis shows that sufficiently large local sketches satisfy the required subspace-embedding condition with high probability. Alternative sketches can remove coherence dependence but are more expensive to implement.

  • Analysis of Uniform Sampling: Uniform sampling satisfies the required sketching properties with probability at least 1 −δ when the sample size is sufficiently large relative to coherence and rank.The stated condition uses s ≥3µρ/δ.
  • Analysis of Uniform Sampling: Leverage-score, Gaussian, Rademacher, and subsampled randomized Hadamard sketches also satisfy the required assumption and remove dependence on matrix coherence.These methods are more expensive than simple uniform sampling, motivating a communication-computation trade-off.

A.4 Analysis of the Approximate Newton Step

The approximate Newton-step analysis connects the quality of a sketched direction to the auxiliary quadratic function and shows that sufficiently accurate directions are descending under a Lipschitz-Hessian assumption.

  • Analysis of the Approximate Newton Step: If an approximate Newton direction is sufficiently close to the exact step in terms of φt, it is provably a good descending direction.The result uses the classical local convergence analysis of Newton’s method.
  • Analysis of the Approximate Newton Step: Lemma 9 bounds the next-step error through the approximate quadratic minimization quality, with the bound depending on α and the local Hessian geometry.The displayed result relates the error measure to min p φt(p) and ∆T_t H_t ∆t.

A.5 Completing the Proofs

The proof completion combines sketching guarantees, approximate-subproblem bounds, and Hessian regularity to establish high-probability convergence results for GIANT under stated sampling and local-size conditions.

  • A.5 Completing the Proofs: With probability 1 −δ, uniform sampling and the preceding lemmas yield the main GIANT convergence results under a local sample-size condition tied to coherence and feature dimension.Theorem 10 assumes s ≥3µd/δ for some η, δ ∈(0, 1).
  • A.5 Completing the Proofs: Theorem 11 extends the high-probability result using iteration-dependent coherence µt and local sample sizes st satisfying a corresponding lower bound.The condition is stated as st ≥3µtd/δ.
  • A.5 Completing the Proofs: The proof controls Hessian variation through the Lipschitz condition ∥Ht −H⋆∥2 ≤L∥∆t∥2 and derives a lower bound on σmin(Ht).The stated bound is L σmin(Ht) ≤ 3/2 L σmin(H⋆).
  • A.5 Completing the Proofs: The approximate-solver theorem follows by replacing the exact-subproblem lemma with the inexact version and replacing α by α′.The proof then proceeds analogously to the earlier theorems and corollary.
  • A.5 Completing the Proofs: Conjugate-gradient analysis relates the local solver cost to the condition number of the sketched Hessian, whose condition number is bounded relative to that of Ht.The bounds use η to relate ˜κt and κ(Ht).

B Proof of Lemma 6 (Model Averaging)

The proof uses Assumption 3 and matrix approximations to establish bounds needed for the model-averaging lemma.

  • Assumption 3 yields a matrix inequality relating the global matrix H and local approximation ˜H_i.
  • The approximation is represented through a matrix Υ_i whose spectral bounds depend on η.
  • The proof applies an inverse-matrix identity for nonsingular matrices to derive the required relation.
  • A thin SVD of A is introduced as part of the matrix analysis.
  • The lemma is concluded after combining the preceding inequalities and intermediate results.

C Proof of Lemma 7 (Effect of Inexact Solution)

The proof bounds the effect of an inexact solution by combining approximation assumptions, quadratic-form bounds, and the triangle inequality.

  • The proof first establishes a bound using Assumption 3 and the closeness of ˜p′_i to ˜p_i.
  • A quadratic-form expression involving ˜p_i and ˜H_i appears in the resulting bound.
  • The triangle inequality is used to control the combined error terms.
  • The final bound follows by applying the previously established relations labeled (20) and (21).

D Proof of Lemma 9 (Convergence of GIANT)

The proof analyzes the GIANT update through error differences, the optimality condition g(w⋆)=0, and Lipschitz-based inequalities.

  • The update and error variables are defined through w_t, ˜p_t, w⋆, and their successive differences.
  • Subtracting two equations produces an expression involving g_t and the quadratic form ∆_t^T H_t ∆_t.
  • The proof uses the condition g(w⋆)=0 to simplify one of the equalities.
  • Jensen’s inequality and the assumption that the objective is L-Lipschitz support the subsequent bounds.
  • Combining the resulting inequalities completes the convergence lemma.
Loading 1709.03528v5…