Variance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning: Part I
arXiv:2201.07699 · doi:10.1109/TSP.2023.3240652
Abstract
In this work, we investigate stochastic quasi-Newton methods for minimizing a finite sum of cost functions over a decentralized network. In Part I, we develop a general algorithmic framework that incorporates stochastic quasi-Newton approximations with variance reduction so as to achieve fast convergence. At each time each node constructs a local, inexact quasi-Newton direction that asymptotically approaches the global, exact one. To be specific, (i) A local gradient approximation is constructed by using dynamic average consensus to track the average of variance-reduced local stochastic gradients over the entire network; (ii) A local Hessian inverse approximation is assumed to be positive definite with bounded eigenvalues, and how to construct it to satisfy these assumptions will be given in Part II. Compared to the existing decentralized stochastic first-order methods, the proposed general framework introduces the second-order curvature information without incurring extra sampling or communication. With a fixed step size, we establish the conditions under which the proposed general framework linearly converges to an exact optimal solution.
References in corpus (13)
- Harnessing Smoothness to Accelerate Distributed Optimization
- Multi-Agent Distributed Optimization via Inexact Consensus ADMM
- RES: Regularized Stochastic BFGS Algorithm
- DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
- Global Convergence of Online Limited Memory BFGS
- Decentralized Quasi-Newton Methods
- DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
- Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
- Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
- A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization
- A Variance Reduced Stochastic Newton Method
- Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization
- Variance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning: Part I