Abstract
Distributed optimization often consists of two updating phases: local optimization and inter-node communication. Conventional approaches require working nodes to communicate with the server every one or few iterations to guarantee convergence. In this paper, we establish a completely different conclusion that each node can perform an arbitrary number of local optimization steps before communication. Moreover, we show that the more local updating can reduce the overall communication, even for an infinity number of steps where each node is free to update its local model to near-optimality before exchanging information. The extra assumption we make is that the optimal sets of local loss functions have a non-empty intersection, which is inspired by the over-parameterization phenomenon in large-scale optimization and deep learning. Our theoretical findings are confirmed by both distributed convex optimization and deep learning experiments.
Introduction
In large-scale distributed machine learning, communication between worker nodes and a central server is often the primary bottleneck. Conventional wisdom suggests that frequent synchronization is necessary to prevent "client drift," where local models diverge too far from the global optimum. However, this paper challenges that paradigm by introducing the Intersection Assumption.
For over-parameterized models—such as modern deep neural networks—different data shards can often be perfectly fit by the same set of model parameters. When this intersection of local optima exists, the trade-off between local work and communication changes fundamentally: performing more local training steps actually reduces the total number of communication rounds required for convergence.
The Intersection Assumption and Geometric Intuition
The core of this research is the assumption that the set of optimal solutions for each local node has a non-empty intersection. This means there exists at least one parameter set that is simultaneously optimal for every node's local data. This is a natural consequence of over-parameterization, where models have sufficient capacity to interpolate their training data.
Geometrically, the convergence speed is governed by the "angle of separation" between these local optimal sets. Unlike classical settings where local training is viewed as a source of error, the authors demonstrate that if a common optimum exists, local training steps actually pull the model closer to the global solution. This allows for "Infinite Local Steps" ($T_i = \infty$), where nodes can train to local optimality before every synchronization without risking divergence.
Theoretical Framework
The authors analyze a standard Model Averaging algorithm across several mathematical landscapes:
- General Convex Cases: Proving sublinear convergence for any number of local steps $T_i$.
- Restricted Strongly Convex Cases: Demonstrating linear convergence rates.
- Quasi-Convex Cases: Extending the theory to non-convex settings where optimal sets form affine subspaces, a common proxy for neural network loss surfaces.
Experimental Validation
The theory was tested using synthetic benchmarks and real-world datasets, including the Colon-cancer dataset (regression), MNIST (LeNet), and CIFAR-10 (ResNet-18).
As shown in the experimental results, increasing the number of local steps $T_i$ consistently leads to faster loss reduction per communication round. In over-parameterized regression tasks, linear convergence was observed regardless of $T_i$. Furthermore, the necessity of the Intersection Assumption was confirmed by comparing high-capacity models against under-parameterized ones; without the intersection, gradient residuals failed to vanish, and the distributed model could not match centralized performance.
Conclusion and Future Work
This work highlights over-parameterization not just as a tool for model expressivity, but as a critical feature for efficient distributed systems. By leveraging the existence of a common optimal intersection, practitioners can significantly slash communication costs by allowing nodes to train locally for longer periods.
Future research directions include extending these proofs to Stochastic Gradient Descent (SGD) and refining the affine subspace assumptions to better capture the complex manifold structures of real-world deep learning loss landscapes.
Summary updated