Distributed adaptive Newton methods with global superlinear convergence

DOI10.1016/J.AUTOMATICA.2021.110156MaRDI QIDQ2123229zbMATH OpenOpenAlexFDO

Authors Jiaqi Zhang, Keyou You, Tamer Başar

Publication date 8 April 2022

Published in Automatica (Search for Journal in Brave)

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

zbMATH Keywords

distributed optimizationlow-rank approximationNewton methodsuperlinear convergence

Mathematics Subject Classification ID

Newton-type methods (49M15) Networked control (93B70) Adaptive control/observation systems (93C40) Finite-time stability (93D40) Consensus (93D50)

Abstract: This paper considers the distributed optimization problem where each node of a peer-to-peer network minimizes a finite sum of objective functions by communicating with its neighboring nodes. In sharp contrast to the existing literature where the fastest distributed algorithms converge either with a global linear or a local superlinear rate, we propose a distributed adaptive Newton (DAN) algorithm with a global quadratic convergence rate. Our key idea lies in the design of a finite-time set-consensus method with Polyak's adaptive stepsize. Moreover, we introduce a low-rank matrix approximation (LA) technique to compress the innovation of Hessian matrix so that each node only needs to transmit message of dimension $mathcalO(p)$ (where $p$ is the dimension of decision vectors) per iteration, which is essentially the same as that of first-order methods. Nevertheless, the resulting DAN-LA converges to an optimal solution with a global superlinear rate. Numerical experiments on logistic regression problems are conducted to validate their advantages over existing methods.

Recommendations

• Event and Its Application in Algebraic Structures
• Newton-like method with diagonal correction for distributed optimization
• Distributed Newton methods for strictly convex consensus optimization problems in multi-agent networks
• Optimal convergence rates for convex distributed optimization in networks
• Distributed Newton algorithm for a special quadratic programming problem

Cites work

• A Characterization of Superlinear Convergence and Its Application to Quasi-Newton Methods
• A Fast Distributed Asynchronous Newton-Based Optimization Algorithm
• A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization
• Accelerated Distributed Nesterov Gradient Descent
• Accelerated Dual Descent for Network Flow Optimization
• Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
• AsySPA: An Exact Asynchronous Algorithm for Convex Optimization Over Digraphs
• Consensus Problems in Networks of Agents With Switching Topology and Time-Delays
• Cooperative Target Tracking Using Decentralized Particle Filtering and RSS Sensors
• Decentralised minimum-time consensus
• Decentralized Quasi-Newton Methods
• Distributed Convex Optimization with Inequality Constraints over Time-Varying Unbalanced Digraphs
• Distributed Finite-Time Average-Consensus With Limited Computational and Storage Capability
• Distributed Heavy-Ball: A Generalization and Acceleration of First-Order Methods With Gradient Tracking
• Distributed Newton Method for Large-Scale Consensus Optimization
• EXTRA: an exact first-order algorithm for decentralized consensus optimization
• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• Lectures on convex optimization
• Linear Convergence in Optimization Over Directed Graphs With Row-Stochastic Matrices
• Low rank approximation. Algorithms, implementation, applications
• Network Newton Distributed Optimization Methods
• Newton-Raphson Consensus for Distributed Convex Optimization
• Speeding up finite-time consensus via minimal polynomial of a weighted graph -- a numerical approach

Cited in

(13)

• On convergence of distributed approximate Newton methods: globalization, sharper bounds and beyond
• Distributed Newton Methods for Deep Neural Networks
• Newton-like method with diagonal correction for distributed optimization
• Event and Its Application in Algebraic Structures
• SHED: a Newton-type algorithm for federated learning based on incremental Hessian eigenvector sharing
• Communication-efficient distributed cubic Newton with compressed lazy Hessian
• Distributed adaptive greedy quasi-Newton methods with explicit non-asymptotic convergence bounds
• Distributed accelerated gradient methods with restart under quadratic growth condition
• Adaptive pruning-based Newton's method for distributed learning
• Distributed mirror descent for online bandit saddle point problem
• Distributed inexact Newton method with adaptive step sizes
• Range value-at-risk and its optimization in vehicle insurance
• Escaping saddle points in distributed nonconvex optimization via cubic regularization

Describes a project that uses

Uses Software

• UCI
• AsySPA
• DiSCO

This page was built for publication: Distributed adaptive Newton methods with global superlinear convergence

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