Accelerated Dual Method for Distributed Optimization: An Inexact-Gradient View of Local Updates

In distributed machine learning, efficiently training across multiple agents with heterogeneous data distributions remains a central challenge. We address the problem of stochastic, strongly convex distributed optimization by applying accelerated gradient ascent to the dual variables and multi-step stochastic gradient descent (SGD) to the primal variables in the Lagrangian formulation. This approach naturally enables local computation, as the inner SGD loops require no inter-agent communication. We prove that the method converges for any number of local updates, attaining the optimal communication complexity when local computation is sufficient. Our analysis builds on an inexact accelerated gradient framework, where the partial gradient of the Lagrangian with respect to the dual variables is treated as an inexact gradient of the dual function. A notable byproduct of this framework is an algorithm that achieves optimal reproducibility guarantees under biased gradient estimates.

Training modern machine learning models often requires many computers or devices to work together. A major challenge is that communication between these devices can be slow, expensive, or privacy-sensitive, especially when each device has different local data. This paper develops a new training method that lets each device perform several rounds of local computation before communicating with its neighbors. The method is designed so that these local updates can be used safely inside an accelerated training procedure, even when they only provide an approximate direction for improvement. We prove that the method works for any number of local updates, and that when enough local computation is available, it uses nearly the smallest possible number of communication rounds. Experiments on regression and classification tasks show that the method can reduce the number of communications needed to reach high accuracy.