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

By Anit Kumar Sahu, Dusan Jakovetic, Dragana Bajovic, Soummya Kar. 2018

15 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, background): “Other communication efficient schemes [25, 31], which focus on reducing the number of communications by sparsifying communications over time have also been proposed which do not take into account communication delays.”