Nested Distributed Gradient Methods with Stochastic Computation Errors

Abstract

In this work, we consider the problem of a network of agents collectively minimizing a sum of convex functions. The agents in our setting can only access their local objective functions and exchange information with their immediate neighbors. Motivated by applications where computation is imperfect, including, but not limited to, empirical risk minimization (ERM) and online learning, we assume that only noisy estimates of the local gradients are available. To tackle this problem, we adapt a class of Nested Distributed Gradient methods (NEAR-DGD) to the stochastic gradient setting. These methods have minimal storage requirements, are communication aware and perform well in settings where gradient computation is costly, while communication is relatively inexpensive. We investigate the convergence properties of our method under standard assumptions for stochastic gradients, i.e. unbiasedness and bounded variance. Our analysis indicates that our method converges to a neighborhood of the optimal solution with a linear rate for local strongly convex functions and appropriate constant steplengths. We also show that distributed optimization with stochastic gradients achieves a noise reduction effect similar to mini-batching, which scales favorably with network size. Finally, we present numerical results to demonstrate the effectiveness of our method.

References in corpus (14)

• Constrained Consensus
• Distributed Learning in Wireless Sensor Networks
• D${}^2$: Decentralized Training over Decentralized Data
• Adaptive Penalty-Based Distributed Stochastic Convex Optimization
• Asynchronous Decentralized Parallel Stochastic Gradient Descent
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• A Push-Pull Gradient Method for Distributed Optimization in Networks
• Communication-Efficient Distributed Strongly Convex Stochastic Optimization: Non-Asymptotic Rates
• Distributed Stochastic Gradient Tracking Methods
• Distributed stochastic optimization with gradient tracking over strongly-connected networks
• Decentralized Consensus Algorithm with Delayed and Stochastic Gradients
• Balancing Communication and Computation in Distributed Optimization
• A Flocking-based Approach for Distributed Stochastic Optimization
• Stochastic Subgradient Algorithms for Strongly Convex Optimization over Distributed Networks