  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.
