Distributed Newton Method for Large-Scale Consensus Optimization

DOI10.1109/TAC.2019.2907711MaRDI QIDQ5211152zbMATH OpenOpenAlexWikidataFDO

Authors Rasul Tutunov, Haitham Bou-Ammar, Ali Jadbabaie

Publication date 28 January 2020

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.06593

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Convex programming (90C25) Methods of quasi-Newton type (90C53)

Abstract: In this paper, we propose a distributed Newton method for consensus optimization. Our approach outperforms state-of-the-art methods, including ADMM. The key idea is to exploit the sparsity of the dual Hessian and recast the computation of the Newton step as one of efficiently solving symmetric diagonally dominant linear equations. We validate our algorithm both theoretically and empirically. On the theory side, we demonstrate that our algorithm exhibits superlinear convergence within a neighborhood of optimality. Empirically, we show the superiority of this new method on a variety of machine learning problems. The proposed approach is scalable to very large problems and has a low communication overhead.

Cited in

(11)

• Distributed adaptive Newton methods with global superlinear convergence
• Distributed approximate Newton algorithms and weight design for constrained optimization
• Distributed Newton methods for strictly convex consensus optimization problems in multi-agent networks
• Distributed Newton Methods for Deep Neural Networks
• Are we forgetting about compositional optimisers in Bayesian optimisation?
• First-Order Newton-Type Estimator for Distributed Estimation and Inference
• Distributed adaptive greedy quasi-Newton methods with explicit non-asymptotic convergence bounds
• Asynchronous ADMM for nonlinear continuous-time systems
• Fully distributed and attack-immune protocols for linear multiagent systems by linear time-varying feedback
• Fully distributed leader-follower consensus of multiagent systems by observer based linear time-varying protocol
• Forgetting-factor regrets for distributed second-order online optimisation

This page was built for publication: Distributed Newton Method for Large-Scale Consensus Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211152)