  We consider the decentralized convex optimization problem, where multiple
agents must cooperatively minimize a cumulative objective function, with each
local function expressible as an empirical average of data-dependent losses.
State-of-the-art approaches for decentralized optimization rely on gradient
tracking, where consensus is enforced via a doubly stochastic mixing matrix.
Construction of such mixing matrices is not straightforward and requires
coordination even prior to the start of the optimization algorithm. This paper
puts forth a primal-dual framework for decentralized stochastic optimization
that obviates the need for such doubly stochastic matrices. Instead, dual
variables are maintained to track the disagreement between neighbors. The
proposed framework is flexible and is used to develop decentralized variants of
SAGA, L-SVRG, SVRG++, and SEGA algorithms. Using a unified proof, we establish
that the oracle complexity of these decentralized variants is $O(1/\epsilon)$,
matching the complexity bounds obtained for the centralized variants.
Additionally, we also present a decentralized primal-dual accelerated SVRG
algorithm achieving $O(1/\sqrt{\epsilon})$ oracle complexity, again matching
the bound for the centralized accelerated SVRG. Numerical tests on the
algorithms establish their superior performance as compared to the
variance-reduced gradient tracking algorithms.
