Abstract
Standard distributed optimization frameworks often assume that data is spread uniformly across machines. However, real-world data is frequently heterogeneous, leading to suboptimal convergence when using uniform averaging of updates. This paper introduces Stochastic BlockLS, a novel method that assigns optimized, non-uniform weights to updates from different machines. By employing Gaussian sketching for efficient correlation estimation and a stochastic line search on the duality gap, Stochastic BlockLS significantly accelerates convergence in non-uniform data scenarios.
Introduction
In large-scale machine learning, datasets are typically partitioned across a cluster of machines. Distributed primal-dual frameworks, such as CoCoA, solve these problems by having each machine calculate a local update, which a central "master" node then merges. Traditionally, these updates are merged using a single uniform weight, assuming statistical similarity across partitions.
In practice, data is often non-uniformly distributed (heterogeneous), as seen in federated learning environments. In such cases, a "one-size-fits-all" weight is suboptimal. This paper addresses the challenge of merging updates intelligently without incurring prohibitive communication costs.
Methodology
The authors propose three primary innovations to enhance the standard distributed primal-dual framework:
1. Non-uniform Weights (Block-wise Step Sizes)
Instead of a global step size, the algorithm calculates a vector of weights ($\beta_1, \dots, \beta_K$) for the $K$ machines. These weights are determined by solving a small optimization problem designed to maximize the reduction in the dual objective function.
2. Sketching for Efficiency
Calculating optimal weights requires knowledge of the correlations between updates from different machines. To avoid the high cost of transmitting full update matrices, the authors utilize Gaussian sketching. This dimensionality reduction technique approximates correlations with minimal communication overhead, maintaining linear convergence.
3. Stochastic Line Search on the Duality Gap
Optimizing solely for the dual objective can lead to oscillations in the duality gap. The authors introduce a line search that minimizes an estimated duality gap by sub-sampling a small portion (e.g., 1%) of the training data to approximate the primal objective, ensuring more stable convergence.
Experimental Results
The approach was evaluated on three benchmarks: rcv1 (sparse news articles), epsilon (dense synthetic data), and covtype (forest cover types). To simulate real-world heterogeneity, K-Means clustering was applied to the epsilon dataset, ensuring machines held distinct data clusters.
Superior Speed and Scalability
Stochastic BlockLS consistently outperformed existing methods like CoCoA, CoCoA+, and BQO. It reached target duality gaps in fewer epochs and less wall-clock time across all datasets. As the number of machines increases—which naturally increases data imbalance—the method scales better than CoCoA by adapting to the imbalance rather than being hindered by it.
Robustness to Non-uniformity
On the clustered epsilon dataset, the performance advantage of Stochastic BlockLS over standard averaging was particularly pronounced. This validates the effectiveness of treating heterogeneity as a signal rather than a hurdle. Furthermore, the stochastic line search provided a smoother and more reliable convergence path compared to previous methods like BQO.
Conclusion
Stochastic BlockLS demonstrates that intelligent merging of local updates can significantly improve distributed optimization. While the 1% sub-sampling for duality gap estimation is a heuristic and calculating weights adds some communication overhead, the gains in convergence speed and stability are substantial. Future work may explore the theoretical reliability of sub-sampling in "long-tail" distributions and extend the framework to more general loss functions.
Summary updated