Variance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning
- 1 February 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 71 (1053587X) , 311-326
Abstract
In this work, we investigate stochastic quasi-Newton methods for minimizing a finite sum of cost functions over a decentralized network. We first develop a general algorithmic framework, in which each node constructs a local, inexact quasi-Newton direction that asymptotically approaches the global, exact one at each time step. To do so, a local gradient approximation is constructed using dynamic average consensus to track the average of variance-reduced local stochastic gradients over the entire network, followed by a proper local Hessian inverse approximation. We show that under standard convexity and smoothness assumptions on the cost functions, the methods obtained from our framework converge linearly to the optimal solution if the local Hessian inverse approximations used have uniformly bounded positive eigenvalues. To construct the Hessian inverse approximations with the said boundedness property, we design two fully decentralized stochastic quasi-Newton methods—namely, the damped regularized limited-memory DFP (Davidon-Fletcher-Powell) and the damped limited-memory BFGS (Broyden-Fletcher-Goldfarb-Shanno)—which use a fixed moving window of past local gradient approximations and local decision variables to adaptively construct Hessian inverse approximations. A noteworthy feature of these methods is that they do not require extra sampling or communication. Numerical results show that the proposed decentralized stochastic quasi-Newton methods are much faster than the existing decentralized stochastic first-order algorithms.Keywords
Funding Information
- NSF China (72192832)
This publication has 39 references indexed in Scilit:
- DQM: Decentralized Quadratically Approximated Alternating Direction Method of MultipliersIEEE Transactions on Signal Processing, 2016
- On the Convergence of Decentralized Gradient DescentSIAM Journal on Optimization, 2016
- A Stochastic Quasi-Newton Method for Large-Scale OptimizationSIAM Journal on Optimization, 2016
- Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes2015
- EXTRA: An Exact First-Order Algorithm for Decentralized Consensus OptimizationSIAM Journal on Optimization, 2015
- Multi-Agent Distributed Optimization via Inexact Consensus ADMMIEEE Transactions on Signal Processing, 2014
- RES: Regularized Stochastic BFGS AlgorithmIEEE Transactions on Signal Processing, 2014
- On the Use of Stochastic Hessian Information in Optimization Methods for Machine LearningSIAM Journal on Optimization, 2011
- Discrete-time dynamic average consensusAutomatica, 2010
- Fastest Mixing Markov Chain on a GraphSIAM Review, 2004