Newton-like method with diagonal correction for distributed optimization
From MaRDI portal
Abstract: We consider distributed optimization problems where networked nodes cooperatively minimize the sum of their locally known convex costs. A popular class of methods to solve these problems are the distributed gradient methods, which are attractive due to their inexpensive iterations, but have a drawback of slow convergence rates. This motivates the incorporation of second-order information in the distributed methods, but this task is challenging: although the Hessians which arise in the algorithm design respect the sparsity of the network, their inverses are dense, hence rendering distributed implementations difficult. We overcome this challenge and propose a class of distributed Newton-like methods, which we refer to as Distributed Quasi Newton (DQN). The DQN family approximates the Hessian inverse by: 1) splitting the Hessian into its diagonal and off-diagonal part, 2) inverting the diagonal part, and 3) approximating the inverse of the off-diagonal part through a weighted linear function. The approximation is parameterized by the tuning variables which correspond to different splittings of the Hessian and by different weightings of the off-diagonal Hessian part. Specific choices of the tuning variables give rise to different variants of the proposed general DQN method -- dubbed DQN-0, DQN-1 and DQN-2 -- which mutually trade-off communication and computational costs for convergence. Simulations demonstrate the effectiveness of the proposed DQN methods.
Recommendations
- Event and Its Application in Algebraic Structures
- Distributed Newton Methods for Deep Neural Networks
- Distributed Newton algorithm for a special quadratic programming problem
- Distributed adaptive Newton methods with global superlinear convergence
- Distributed approximate Newton algorithms and weight design for constrained optimization
Cites work
- scientific article; zbMATH DE number 852532 (Why is no real title available?)
- A Distributed Newton Method for Network Utility Maximization–I: Algorithm
- A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization
- A stochastic quasi-Newton method for large-scale optimization
- Block diagonally dominant matrices and generalizations of the Gerschgorin circle theorem
- Consensus in Ad Hoc WSNs With Noisy Links—Part I: Distributed Estimation of Deterministic Signals
- DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
- Diffusion LMS Strategies for Distributed Estimation
- Distributed Gradient Methods with Variable Number of Working Nodes
- Distributed Optimization With Local Domains: Applications in MPC and Network Flows
- Distributed Parameter Estimation in Sensor Networks: Nonlinear Observation Models and Imperfect Communication
- Distributed Subgradient Methods for Multi-Agent Optimization
- Distributed multi-agent optimization with state-dependent communication
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Distributed stochastic subgradient projection algorithms for convex optimization
- EXTRA: an exact first-order algorithm for decentralized consensus optimization
- Fast Distributed Gradient Methods
- Global convergence of online limited memory BFGS
- Hybrid Random/Deterministic Parallel Algorithms for Convex and Nonconvex Big Data Optimization
- Hybrid deterministic-stochastic methods for data fitting
- Inexact Newton Methods
- Line search methods with variable sample size for unconstrained optimization
- Newton-Raphson Consensus for Distributed Convex Optimization
- Newton-like method with modification of the right-hand-side vector
- Nonmonotone line search methods with variable sample size
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- On the convergence of decentralized gradient descent
- On the use of stochastic Hessian information in optimization methods for machine learning
- RES: Regularized Stochastic BFGS Algorithm
- Sample size selection in optimization methods for machine learning
Cited in
(14)- Distributed inexact Newton method with adaptive step sizes
- Distributed adaptive greedy quasi-Newton methods with explicit non-asymptotic convergence bounds
- Distributed optimization over directed graphs with row stochasticity and constraint regularity
- First-Order Newton-Type Estimator for Distributed Estimation and Inference
- Distributed adaptive Newton methods with global superlinear convergence
- Distributed Newton algorithm for a special quadratic programming problem
- Event and Its Application in Algebraic Structures
- Distributed Newton Methods for Deep Neural Networks
- A decentralized proximal gradient tracking algorithm for composite optimization on Riemannian manifolds
- Exact spectral-like gradient method for distributed optimization
- A split Levenberg-Marquardt method for large-scale sparse problems
- Distributed quasi-Newton derivative-free optimization method for optimization problems with multiple local optima
- Communication-efficient distributed cubic Newton with compressed lazy Hessian
- Linear convergence rate analysis of a class of exact first-order distributed methods for weight-balanced time-varying networks and uncoordinated step sizes
This page was built for publication: Newton-like method with diagonal correction for distributed optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5275293)
