Decentralized Quasi-Newton Methods
arXiv:1605.00933 · doi:10.1109/TSP.2017.2666776
Abstract
We introduce the decentralized Broyden-Fletcher-Goldfarb-Shanno (D-BFGS) method as a variation of the BFGS quasi-Newton method for solving decentralized optimization problems. The D-BFGS method is of interest in problems that are not well conditioned, making first order decentralized methods ineffective, and in which second order information is not readily available, making second order decentralized methods impossible. D-BFGS is a fully distributed algorithm in which nodes approximate curvature information of themselves and their neighbors through the satisfaction of a secant condition. We additionally provide a formulation of the algorithm in asynchronous settings. Convergence of D-BFGS is established formally in both the synchronous and asynchronous settings and strong performance advantages relative to first order methods are shown numerically.
References in corpus (4)
Cited by in corpus (27)
- An Exact Quantized Decentralized Gradient Descent Algorithm
- Distributed Optimization for Smart Cyber-Physical Networks
- AsySPA: An Exact Asynchronous Algorithm for Convex Optimization Over Digraphs
- Asynchronous Gradient-Push
- A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization
- Stochastic L-BFGS: Improved Convergence Rates and Practical Acceleration Strategies
- A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
- Variance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning: Part I
- Achieving Linear Convergence in Distributed Asynchronous Multi-agent Optimization
- DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate
- Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings
- Optimization over time-varying directed graphs with row and column-stochastic matrices
- Asynchronous Decentralized Successive Convex Approximation
- Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication
- Superlinearly Convergent Asynchronous Distributed Network Newton Method
- Balancing Communication and Computation in Distributed Optimization
- Scalable Distributed Optimization of Multi-Dimensional Functions Despite Byzantine Adversaries
- A Survey of Distributed Optimization Methods for Multi-Robot Systems
- Geometric Convergence for Distributed Optimization with Barzilai-Borwein Step Sizes
- Distributed Linear Model Clustering over Networks: A Tree-Based Fused-Lasso ADMM Approach
- A Distributed Cubic-Regularized Newton Method for Smooth Convex Optimization over Networks
- A general framework for decentralized optimization with first-order methods
- GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning
- FlexPD: A Flexible Framework Of First-Order Primal-Dual Algorithms for Distributed Optimization
- Decentralized Approximate Newton Methods for Convex Optimization on Networked Systems
- L-DQN: An Asynchronous Limited-Memory Distributed Quasi-Newton Method
- Asynchronous Parallel Stochastic Quasi-Newton Methods