Asymptotic Properties of $\mathcal{S}$-$\mathcal{A}\mathcal{B}$ Method with Diminishing Stepsize

Abstract

The popular $\mathcal{A}\mathcal{B}$/push-pull method for distributed optimization problem may unify much of the existing decentralized first-order methods based on gradient tracking technique. More recently, the stochastic gradient variant of $\mathcal{A}\mathcal{B}$/Push-Pull method ($\mathcal{S}$-$\mathcal{A}\mathcal{B}$) has been proposed, which achieves the linear rate of converging to a neighborhood of the global minimizer when the step-size is constant. This paper is devoted to the asymptotic properties of $\mathcal{S}$-$\mathcal{A}\mathcal{B}$ with diminishing stepsize. Specifically, under the condition that each local objective is smooth and the global objective is strongly-convex, we first present the boundedness of the iterates of $\mathcal{S}$-$\mathcal{A}\mathcal{B}$ and then show that the iterates converge to the global minimizer with the rate $\mathcal{O}\left(1/\sqrt{k}\right)$. Furthermore, the asymptotic normality of Polyak-Ruppert averaged $\mathcal{S}$-$\mathcal{A}\mathcal{B}$ is obtained and applications on statistical inference are discussed. Finally, numerical tests are conducted to demonstrate the theoretic results.

References in corpus (8)

• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• Stability and Performance Limits of Adaptive Primal-Dual Networks
• Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
• Gradient-Tracking over Directed Graphs for solving Leaderless Multi-Cluster Games
• Quantized Distributed Gradient Tracking Algorithm with Linear Convergence in Directed Networks
• A Hybrid-Order Distributed SGD Method for Non-Convex Optimization to Balance Communication Overhead, Computational Complexity, and Convergence Rate