Communication-Efficient Distributed Strongly Convex Stochastic Optimization: Non-Asymptotic Rates

Abstract

We examine fundamental tradeoffs in iterative distributed zeroth and first order stochastic optimization in multi-agent networks in terms of \emph{communication cost} (number of per-node transmissions) and \emph{computational cost}, measured by the number of per-node noisy function (respectively, gradient) evaluations with zeroth order (respectively, first order) methods. Specifically, we develop novel distributed stochastic optimization methods for zeroth and first order strongly convex optimization by utilizing a probabilistic inter-agent communication protocol that increasingly sparsifies communications among agents as time progresses. Under standard assumptions on the cost functions and the noise statistics, we establish with the proposed method the $O(1/(C_{\mathrm{comm}}{)}^{4/3-\zeta })$ and $O(1/(C_{\mathrm{comm}}{)}^{8/9-\zeta })$ mean square error convergence rates, for the first and zeroth order optimization, respectively, where $C_{\mathrm{comm}}$ is the expected number of network communications and $\zeta >0$ is arbitrarily small. The methods are shown to achieve order-optimal convergence rates in terms of computational cost~$C_{\mathrm{comp}}$, $O(1/C_{\mathrm{comp}})$ (first order optimization) and $O(1/(C_{\mathrm{comp}}{)}^{2/3})$ (zeroth order optimization), while achieving the order-optimal convergence rates in terms of iterations. Experiments on real-life datasets illustrate the efficacy of the proposed algorithms.

arXiv comment32 pages. Submitted for journal publication. Initial Submission: September 2018

References in corpus (6)

• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Convergence Rates of Distributed Nesterov-like Gradient Methods on Random Networks
• Zeroth Order Nonconvex Multi-Agent Optimization over Networks
• Distributed Gradient Methods with Variable Number of Working Nodes
• Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development
• Communication Optimality Trade-offs For Distributed Estimation

Cited by in corpus (6)

• MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
• Communication-Efficient Edge AI: Algorithms and Systems
• Distributed Zero-Order Optimization under Adversarial Noise
• FlexPD: A Flexible Framework Of First-Order Primal-Dual Algorithms for Distributed Optimization
• Distributed Stochastic Optimization With Unbounded Subgradients Over Randomly Time-Varying Networks
• Nested Distributed Gradient Methods with Stochastic Computation Errors