MG-Skip: Random Multi-Gossip Skipping Method for Nonsmooth Distributed
  Optimization
Luyao Guo Luqing Wang Xinli Shi Jinde Cao
Distributed optimization methods with probabilistic local updates have
recently gained attention for their provable ability to communication
acceleration. Nevertheless, this capability is effective only when the loss
function is smooth and the network is sufficiently well-connected. In this
paper, we propose the first linear convergent method MG-Skip with probabilistic
local updates for nonsmooth distributed optimization. Without any extra
condition for the network connectivity, MG-Skip allows for the multiple-round
gossip communication to be skipped in most iterations, while its iteration
complexity is $\mathcal{O}\left(\kappa \log \frac{1}{\epsilon}\right)$ and
communication complexity is only
$\mathcal{O}\left(\sqrt{\frac{\kappa}{(1-\rho)}} \log
\frac{1}{\epsilon}\right)$, where $\kappa$ is the condition number of the loss
function and $\rho$ reflects the connectivity of the network topology. To the
best of our knowledge, MG-Skip achieves the best communication complexity when
the loss function has the smooth (strongly convex)+nonsmooth (convex) composite
form.