Distributed stochastic optimization with gradient tracking over strongly-connected networks

Abstract

In this paper, we study distributed stochastic optimization to minimize a sum of smooth and strongly-convex local cost functions over a network of agents, communicating over a strongly-connected graph. Assuming that each agent has access to a stochastic first-order oracle ($\mathcal{S}\mathcal{FO}$), we propose a novel distributed method, called $\mathcal{S}$-$\mathcal{A}\mathcal{B}$, where each agent uses an auxiliary variable to asymptotically track the gradient of the global cost in expectation. The $\mathcal{S}$-$\mathcal{A}\mathcal{B}$ algorithm employs row- and column-stochastic weights simultaneously to ensure both consensus and optimality. Since doubly-stochastic weights are not used, $\mathcal{S}$-$\mathcal{A}\mathcal{B}$ is applicable to arbitrary strongly-connected graphs. We show that under a sufficiently small constant step-size, $\mathcal{S}$-$\mathcal{A}\mathcal{B}$ converges linearly (in expected mean-square sense) to a neighborhood of the global minimizer. We present numerical simulations based on real-world data sets to illustrate the theoretical results.

References in corpus (2)

• Optimization over time-varying directed graphs with row and column-stochastic matrices
• Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient tracking

Cited by in corpus (6)

• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• On the linear convergence of distributed Nash equilibrium seeking for multi-cluster games under partial-decision information
• Gradient-Free Nash Equilibrium Seeking in N-Cluster Games with Uncoordinated Constant Step-Sizes
• Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking--Part I: GT-SAGA
• On the Convergence of Consensus Algorithms with Markovian Noise and Gradient Bias
• Nested Distributed Gradient Methods with Stochastic Computation Errors