A Distributed Second-Order Algorithm You Can Trust

By Celestine Mendler-Dünner, Aurélien Lucchi, Matilde Gargiani, An Bian, Thomas Hofmann, Martin Jaggi. 2018

33 citations recorded by the source corpus.

Due to the rapid growth of data and computational resources, distributed optimization has become an active research area in recent years. While first-order methods seem to dominate the field, second-order methods are nevertheless attractive as they potentially require fewer communication rounds to converge. However, there are significant drawbacks that impede their wide adoption, such as the computation and the communication of a large Hessian matrix. In this paper we present a new algorithm for distributed training of generalized linear models that only requires the computation of diagonal blocks of the Hessian matrix on the individual workers. To deal with this approximate information we propose an adaptive approach that - akin to trust-region methods - dynamically adapts the auxiliary model to compensate for modeling errors. We provide theoretical rates of convergence for a wide class of problems including L1-regularized objectives. We also demonstrate that our approach achieves state-of-the-art results on multiple large benchmark datasets.

Subfields: Artificial Intelligence

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

Citations in the corpus

COLA: Decentralized Linear Learning (2018, methodology): “In the distributed setting with a central server, algorithms of the C O C O A family [Yang, 2013, Jaggi et al., 2014, Ma et al., 2015, Dünner et al., 2018]—see [Smith et al., 2018] for a recent overview— are targeted for problems of the forms (A) and (B).”
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.”
Ellipsoidal Trust Region Methods and the Marginal Value of Hessian Information for Neural Network Training (2019, methodology): “[31] Celestine Dünner, Aurelien Lucchi, Matilde Gargiani, An Bian, Thomas Hofmann, and Martin Jaggi.”
Adaptive norms for deep learning with regularized Newton methods (2019, background): “The latter observations suggests that advances in distributed second-order algorithms (e.g., Osawa et al. (2018); D¨unner et al. (2018)) constitute a promising direction of research towards the goal of a more widespread use of Newton-type methods in deep learning.”
Communication-Efficient Edge AI: Algorithms and Systems (2020, methodology): “ng only important gradients for minimizing communication bandwidth [47], [38] Second-Order Methods Stochastic quasi-Newton methods [48], [49], [50] Approximate Newton-type methods [51], [52], [53], [54] Federated Optimization Federated averaging algorithm [18] and dual coordinate ascent algorithm [5”