Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss

By Yuchen Zhang, Lin Xiao. 2015

75 citations recorded by the source corpus.

We consider distributed convex optimization problems originating from sample average approximation of stochastic optimization, or empirical risk minimization in machine learning. We assume that each machine in the distributed computing system has access to a local empirical loss function, constructed with i.i.d. data sampled from a common distribution. We propose a communication-efficient distributed algorithm to minimize the overall empirical loss, which is the average of the local empirical losses. The algorithm is based on an inexact damped Newton method, where the inexact Newton steps are computed by a distributed preconditioned conjugate gradient method. We analyze its iteration complexity and communication efficiency for minimizing self-concordant empirical loss functions, and discuss the results for ridge regression, logistic regression and binary classification with a smoothed hinge loss. In a standard setting for supervised learning where the condition number of the problem grows with square root of the sample size, the required number of communication rounds of the algorithm does not increase with the sample size, and only grows slowly with the number of machines.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition, Optimization & Training

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 Computational Mechanics

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Federated Optimization: Distributed Optimization Beyond the Datacenter (2015, methodology): “Such algorithms perform a large amount of computation locally, before each round of communication, ideally balancing the cost of computation and communication[10, 11, 4, 7, 14].”
Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “Some of them are Boyd et al. (2011) (ADMM), Shamir et al. (2014) (DANE), Zhang and Xiao (2015) (DiSCO), Reddi et al. (2016) (AIDE), Ma et al. (2017); Smith et al. (2016); Ma et al. (2015) (COCOA) and some of the references therein.”
Communication-Efficient Learning of Deep Networks from Decentralized Data (2016, background): “In the convex setting, the problem of distributed optimization and estimation has received significant attention [4, 15, 33], and some algorithms do focus specifically on communication efficiency [45, 34, 40, 27, 43].”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, background): “In this spirit, (Shamir et al., 2014b; Zhang & Xiao, 2015) have proposed distributed Newton-type algorithms.”
Communication Complexity of Distributed Convex Learning and Optimization (2015, methodology): “For quadratics, this bound is matched by (up to constants and logarithmic factors) by the recentlyproposed DISCO algorithm [26].”
Tight Complexity Bounds for Optimizing Composite Objectives (2016, background): “Several methods have recently been suggested for optimizing a sum or average of several functions using prox accesses to each component, both in the distributed setting where each components might be handled on a diﬀerent machine (e.g. ADMM [7], DANE [18], DISCO [20]) or for functions that can be de”
Distributed Stochastic Optimization via Adaptive SGD (2018, methodology): “Algorithms that use Newton’s method typically make the assumption that D is a distribution over quadratic losses [20, 22, 16, 21], and leverage the fact that the expected Hessian is constant to compute a Newton step in parallel.”
Without-Replacement Sampling for Stochastic Gradient Methods (2016, background): “Over the past few years, there has been much research on this question in the machine learning community, with just a few examples including [24, 2, 1, 5, 4, 10, 20, 19, 25, 13].”
Partitioning Data on Features or Samples in Communication-Efficient Distributed Optimization? (2015, methodology): “We describe how the original algorithm has to be modified to allow partitioning on features and show its efficiency both in theory and also in practice.”
DiSCO: Distributed Optimization for Self-Concordant Empirical Loss (2015, background): “See Zhang & Xiao (2015) for the proof of the following lemma.”
Communication-Efficient Distributed Statistical Inference (2016, background): “Supplementary materials for this article are available online.”
Communication Lower Bounds for Distributed Convex Optimization: Partition Data on Features (2016, background): “Many of them are under the setting where data is partitioned on samples, i.e. each machine stores a subset of the data matrix A ’s rows [16, 17, 2, 3, 15, 8, 5, 10].”
Federated Learning of Deep Networks using Model Averaging (2016, background): “…optimization and estimation has received significant attention (Balcan et al., 2012; Fercoq et al., 2014; Shamir & Srebro, 2014), and some algorithms do focus specifically on communication efficiency (Zhang et al., 2013; Shamir et al., 2013; Yang, 2013; Ma et al., 2015; Zhang & Xiao, 2015).”
Communication-Efficient Edge AI: Algorithms and Systems (2020, background): “They established a lower bound on the rounds of communication, which is shown to be achieved by the algorithm of [165] for quadratic and strongly convex functions.”
Efficient Distributed Learning with Sparsity (2016, background): “Shamir et al. (2014) and Zhang and Xiao (2015) proposed truly communication-efficient distributed optimization algorithms which leveraged the local second-order information, resulting in milder dependence on the condition number, compared to the first-order approaches (Boyd et al., 2011; Shamir and…”