Distributed Primal-Dual Optimization for Non-uniformly Distributed Data

Minhao Cheng, Cho-Jui Hsieh

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.

Performance on the epsilon dataset with clustered (non-uniform) data distribution, highlighting the robustness of non-uniform weights.

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

Abstract

Distributed primal-dual optimization has received many focuses in the past few years. In this framework, training samples are stored in multiple machines. At each round, all the machines conduct a sequence of updates based on their local data, and then the local updates are synchronized and merged to obtain the update to the global model. All the previous approaches merge the local updates by averaging all of them with a uniform weight. However, in many real world applications data are not uniformly distributed on each machine, so the uniform weight is inadequate to capture the heterogeneity of local updates. To resolve this issue, we propose a better way to merge local updates in the primal-dual optimization framework. Instead of using a single weight for all the local updates, we develop a computational efficient algorithm to automatically choose the optimal weights for each machine. Furthermore, we propose an efficient way to estimate the duality gap of the merged update by exploiting the structure of the objective function, and this leads to an efficient line search algorithm based on the reduction of duality gap. Combining these two ideas, our algorithm is much faster and more scalable than existing methods on real world problems.
BibTeX
@inproceedings{cheng2018distributed,
  author = {Minhao Cheng and Cho-Jui Hsieh},
  title = {{Distributed Primal-Dual Optimization for Non-uniformly Distributed Data}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/280},
}
Figure