WONDER: Weighted One-shot Distributed Ridge Regression in High Dimensions

Edgar Dobriban, Yue ShengJMLR 2020 · OpenReview

TL;DR

This paper introduces WONDER, a novel algorithm for distributed ridge regression that efficiently combines local estimates from multiple machines. WONDER achieves significant computational speedups (over 100x) with minimal loss in prediction accuracy, even when data is split across a vast number of machines, by employing a sophisticated weighting scheme derived from advanced random matrix theory.

What Problem Does This Paper Address?

As datasets grow exponentially, single-machine computing struggles to keep up. Distributed and parallel computing offer a solution by dividing data and computation across multiple machines. However, applying these methods to statistical problems like ridge regression, a cornerstone of supervised learning, presents challenges. Specifically, how can we effectively combine local ridge regression models computed on different machines to obtain a global model that is both accurate and computationally efficient? Traditional methods like simple averaging can be suboptimal, and the high-dimensional nature of modern datasets adds further complexity. This paper tackles the problem of performing ridge regression in a distributed setting, focusing on "one-shot" methods that combine local results without iterative communication, and aims to understand the theoretical underpinnings and practical implications of such approaches.

Methods

The core of this work lies in developing a theoretically grounded approach to combining local ridge regression estimates. The authors propose a "one-shot weighted" method, where local ridge regression estimators are computed on each machine, and then aggregated using carefully chosen weights. This is a departure from simple averaging. The key innovation is the use of sophisticated tools from random matrix theory (RMT) and free probability theory to analyze the mean squared error (MSE) of the distributed estimator. This allows them to derive optimal weights and understand the performance under various conditions, including high dimensions and arbitrary covariance structures. They introduce the WONDER (Weighted ONe-shot DistributEd Ridge regression) algorithm, which implements these findings.

Datasets

  • Million Song Dataset (MSD): Used as an empirical example to demonstrate WONDER's performance in a real-world scenario. The authors describe using a subset of 10,000 training samples and 1,000 test samples for prediction tasks.
  • Simulated Datasets: The paper extensively uses simulations to validate theoretical results. These simulations involve generating data under various conditions, including:
  • Isotropic covariance (features are uncorrelated).
  • Autoregressive (AR-1) covariance structure (features exhibit correlation).
  • Varying signal-to-noise ratios ($\alpha$) and aspect ratios ($\gamma = p/n$).

Key Insights and Ideas

  • Optimal weights don't sum to unity: Surprisingly, the optimal weights for combining local ridge estimators should sum to more than one. This is attributed to the inherent downward bias of ridge regression, and suggests that simple averaging is suboptimal.
  • "Infinite-worker limit": Even with an extremely large number of machines, the distributed estimator can maintain significant efficiency, a phenomenon the authors term the "infinite-worker limit." This is a crucial finding for scaling to massive distributed systems.
  • Decoupling for uncorrelated features: When features are uncorrelated (identity covariance matrix), the problem of choosing regularization parameters and calculating risks decouples across machines, simplifying the optimization process.
  • Debiasing through upweighting: The fact that optimal weights sum to more than unity can be interpreted as a form of debiasing, counteracting the bias introduced by ridge regression.
  • Blessing of dimensionality: In some regimes, increasing the dimensionality of the problem (larger $\gamma$) can actually make the distributed problem easier relative to the aggregated problem, leading to higher efficiency.

Key Results

  • Computational Speedup: WONDER can achieve at least a 100x reduction in computation time on the Million Song Dataset, while nearly preserving test accuracy.
  • Asymptotic Relative Efficiency (ARE): The paper provides theoretical bounds and characterizations for the ARE, showing it's generally high but decreases with the number of machines. Crucially, the infinite-worker limit is strictly positive, meaning efficiency is not entirely lost.
  • Optimal Regularization Parameters: For isotropic covariance, the optimal regularization parameters for local estimators can be chosen as a constant multiple of the globally optimal parameter.
  • Minimax Optimality: The WONDER estimator is shown to be asymptotically rate-minimax, meaning its risk is bounded by a constant times the minimax risk, even for distributed settings.

Limitations and Future Work

  • Practicality of Optimal Weights: While theoretically derived, the optimal weights depend on unknown parameters (like $\beta$ or functionals of $\Sigma$), making them difficult to use directly on real data. The authors suggest that for general covariance structures, practitioners might need to rely on techniques like cross-validation or assume simpler structures (like spherical data) to make weights usable.
  • Heuristic Nature of One-Shot Weighting: The authors acknowledge that one-shot weighting is fundamentally a heuristic. While WONDER provides a theoretically grounded approach, exploring iterative methods or hybrid strategies could potentially offer further improvements.
  • Intuitive Understanding: While the mathematical results are precise, developing a more intuitive understanding of why optimal weights sum to more than unity and the "infinite-worker limit" phenomenon is an ongoing area of interest.
  • Future Work: The authors suggest investigating how to up-adjust equal weights in practice and exploring more concrete methods for making optimal weights usable in real-world scenarios, especially for complex covariance structures.

Summary updated

Abstract

In many areas, practitioners need to analyze large data sets that challenge conventional single-machine computing. To scale up data analysis, distributed and parallel computing approaches are increasingly needed. Here we study a fundamental and highly important problem in this area: How to do ridge regression in a distributed computing environment? Ridge regression is an extremely popular method for supervised learning, and has several optimality properties, thus it is important to study. We study one-shot methods that construct weighted combinations of ridge regression estimators computed on each machine. By analyzing the mean squared error in a high-dimensional random-effects model where each predictor has a small effect, we discover several new phenomena. Infinite-worker limit: The distributed estimator works well for very large numbers of machines, a phenomenon we call 'infinite-worker limit'. Optimal weights: The optimal weights for combining local estimators sum to more than unity, due to the downward bias of ridge. Thus, all averaging methods are suboptimal. We also propose a new Weighted ONe-shot DistributEd Ridge regression algorithm (WONDER). We test WONDER in simulation studies and using the Million Song Dataset as an example. There it can save at least 100x in computation time, while nearly preserving test accuracy.
BibTeX
@article{dobriban2020wonder,
  author = {Edgar Dobriban and Yue Sheng},
  title = {{WONDER: Weighted One-shot Distributed Ridge Regression in High Dimensions}},
  journal = {J. Mach. Learn. Res.},
  year = {2020},
  url = {https://openreview.net/forum?id=y8O81j9j60},
}
Figure