Stochastic Constrained Decentralized Optimization for Machine Learning
  with Fewer Data Oracles: a Gradient Sliding Approach
Hoang Huy Nguyen Yan Li Tuo Zhao
In modern decentralized applications, ensuring communication efficiency and
privacy for the users are the key challenges. In order to train
machine-learning models, the algorithm has to communicate to the data center
and sample data for its gradient computation, thus exposing the data and
increasing the communication cost. This gives rise to the need for a
decentralized optimization algorithm that is communication-efficient and
minimizes the number of gradient computations. To this end, we propose the
primal-dual sliding with conditional gradient sliding framework, which is
communication-efficient and achieves an $\varepsilon$-approximate solution with
the optimal gradient complexity of
$O(1/\sqrt{\varepsilon}+\sigma^2/{\varepsilon^2})$ and
$O(\log(1/\varepsilon)+\sigma^2/\varepsilon)$ for the convex and strongly
convex setting respectively and an LO (Linear Optimization) complexity of
$O(1/\varepsilon^2)$ for both settings given a stochastic gradient oracle with
variance $\sigma^2$. Compared with the prior work \cite{wai-fw-2017}, our
framework relaxes the assumption of the optimal solution being a strict
interior point of the feasible set and enjoys wider applicability for
large-scale training using a stochastic gradient oracle. We also demonstrate
the efficiency of our algorithms with various numerical experiments.