  In distributed machine learning, efficient training across multiple agents
with different data distributions poses significant challenges. Even with a
centralized coordinator, current algorithms that achieve optimal communication
complexity typically require either large minibatches or compromise on gradient
complexity. In this work, we tackle both centralized and decentralized settings
across strongly convex, convex, and nonconvex objectives. We first demonstrate
that a basic primal-dual method, (Accelerated) Gradient Ascent Multiple
Stochastic Gradient Descent (GA-MSGD), applied to the Lagrangian of distributed
optimization inherently incorporates local updates, because the inner loops of
running Stochastic Gradient Descent on the primal variable require no
inter-agent communication. Notably, for strongly convex objectives, we show
(Accelerated) GA-MSGD achieves linear convergence in communication rounds
despite the Lagrangian being only linear in the dual variables. This is due to
a unique structural property where the dual variable is confined to the span of
the coupling matrix, rendering the dual problem strongly concave. When
integrated with the Catalyst framework, our approach achieves nearly optimal
communication complexity across various settings without the need for
minibatches. Moreover, in stochastic decentralized problems, it attains
communication complexities comparable to those in deterministic settings,
improving over existing algorithms.
