A Distributed Quasi-Newton Algorithm for Empirical Risk Minimization with Nonsmooth Regularization

By Ching-pei Lee, Cong Han Lim, Stephen J. Wright. 2018

29 citations recorded by the source corpus.

We propose a communication- and computation-efficient distributed optimization algorithm using second-order information for solving ERM problems with a nonsmooth regularization term. Current second-order and quasi-Newton methods for this problem either do not work well in the distributed setting or work only for specific regularizers. Our algorithm uses successive quadratic approximations, and we describe how to maintain an approximation of the Hessian and solve subproblems efficiently in a distributed manner. The proposed method enjoys global linear convergence for a broad range of non-strongly convex problems that includes the most commonly used ERMs, thus requiring lower communication complexity. It also converges on non-convex problems, so has the potential to be used on applications such as deep learning. Initial computational results on convex problems demonstrate that our method significantly improves on communication cost and running time over the current state-of-the-art methods.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

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 Numerical Analysis

Citations in the corpus

COLA: Decentralized Linear Learning (2018, methodology): “Other centralized algorithm representatives are parallel SGD variants such as [Agarwal and Duchi, 2011, Zinkevich et al., 2010] and more recent distributed second-order methods [Zhang and Lin, 2015, Reddi et al., 2016, Gargiani, 2017, Lee and Chang, 2017, Dünner et al., 2018, Lee et al., 2018].”
CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “, 2017), second-order algorithm extensions (Gargiani, 2017; Lee and Chang, 2017; Dünner et al., 2018; Lee et al., 2018), and accelerated methods (Ma et al.”
A Distributed Second-Order Algorithm You Can Trust (2018, background): “Line-search techniques are a popular way to guarantee convergence and they have recently been explored in distributed settings, e.g., (Hsieh et al., 2016; Lee & Chang, 2017; Troﬁmov & Genkin, 2017; Mahajan et al., 2017; Lee et al., 2018).”
Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks (2019, methodology): “…a master node that can coordinate the computations is not available unlike the master/slave architecture studied in the literature (see e.g. Mishchenko et al. (2018); Agarwal and Duchi (2011); Hakimi et al. (2019); Lee et al. (2018); Meng et al. (2016); Jaggi et al. (2014); Xin and Khan (2018)).”