Weighted SGD for $\ell_p$ Regression with Randomized Preconditioning

Jiyan Yang, Yinlam Chow, Christopher Ré, Michael W. Mahoney

In the world of large-scale optimization, two titans usually dominate the conversation: Stochastic Gradient Descent (SGD) and Randomized Linear Algebra (RLA). SGD is the industry workhorse—simple to implement and incredibly scalable—but it can be finicky, often requiring careful tuning and struggling with poorly conditioned data. RLA, on the other hand, offers rock-solid theoretical guarantees by "sketching" (compressing) data, but it’s often restricted to specific problems and handles constraints poorly.

A team of researchers from Stanford and UC Berkeley has proposed a way to get the best of both worlds. Their paper introduces PWSGD (Preconditioned Weighted SGD), a hybrid algorithm that uses RLA to "prep" a problem so that SGD can sprint to a solution.

TL;DR

PWSGD is a hybrid algorithm that combines Randomized Linear Algebra (RLA) for preconditioning with a weighted Stochastic Gradient Descent (SGD) to solve large-scale $\ell_1$ and $\ell_2$ regression. It achieves a convergence rate that is independent of the number of data points ($n$) and depends only on the number of features ($d$), making it significantly faster for massive, overdetermined datasets.

What Problem Does This Paper Address?

The authors target overdetermined linear regression problems, where you have far more observations ($n$) than features ($d$). Specifically, they look at $\ell_p$ regression (minimizing $\|Ax - b\|_p$), with a focus on:

  • $\ell_2$ (Least Squares): The standard for most regression tasks.
  • $\ell_1$ (Least Absolute Deviations): Preferred for its robustness against outliers.

The challenge is that while vanilla SGD is fast, its performance degrades if the matrix $A$ is "ill-conditioned" (meaning the features are highly correlated or vary wildly in scale). RLA methods can fix this by solving a smaller, sketched version of the problem, but if you have constraints on your solution (like $x$ must be non-negative), RLA becomes computationally expensive. PWSGD aims to provide a solver that is robust to conditioning, handles constraints gracefully, and scales to "terabyte-sized" inputs.

Methods

PWSGD operates in two distinct phases:

  1. The RLA Phase (Preconditioning & Sampling):
    • Sketching: The algorithm uses a random projection (like a Sparse Cauchy Transform) to create a tiny summary of the massive matrix $A$.
  2. Preconditioning: From this summary, it computes a preconditioning matrix $R$. This $R$ essentially "straightens out" the optimization landscape, making it more spherical and easier for SGD to navigate.
  3. Importance Sampling: It calculates "leverage scores"—a measure of how influential each row of the data is. Instead of picking rows at random (uniform sampling), PWSGD picks "important" rows more often.
  4. The SGD Phase (Iterative Refinement):
    • The algorithm runs a weighted version of SGD on the preconditioned system. Because the system is now well-conditioned and the sampling is "smart," the number of iterations needed to reach a certain accuracy depends only on the number of features $d$, not the total number of rows $n$.

Datasets

The authors evaluated PWSGD on both synthetic and real-world datasets:

  • Synthetic 1 & 2: Custom-generated matrices designed to have "skewed" leverage scores or specific condition numbers to test the limits of the algorithm.
  • YearPredictionMSD: A subset of the Million Song Dataset ($5 \times 10^5$ rows, 90 features) used to predict the release year of a song.
  • Buzz in Social Media: A dataset ($5 \times 10^5$ rows, 77 features) used to predict the "buzz" or popularity of topics.

Key Insights and Ideas

  • The $n$-Independence: The most striking insight is that after RLA preconditioning, the "complexity" of the data is effectively capped by $d$. You could add a billion redundant rows to your dataset, and PWSGD wouldn't need significantly more iterations to converge.
  • Smart Sampling is Essential: Uniform sampling in SGD can fail if a few "outlier" rows contain all the critical information. By using leverage-score-based importance sampling, PWSGD ensures these critical rows are seen early and often.
  • $\ell_1$ Efficiency: For $\ell_1$ problems, traditional RLA requires solving a sub-problem using an interior-point method, which is slow. PWSGD replaces this with simple SGD updates, which are much cheaper per iteration.

Key Results

  • Theoretical Speedup: For unconstrained $\ell_1$ regression, PWSGD achieves a complexity of $O(\log n \cdot \text{nnz}(A) + \text{poly}(d)/\epsilon^2)$. This is "uniformly better" than previous RLA methods.
  • Medium-Precision Sweet Spot: PWSGD is particularly dominant when you need "medium precision" (e.g., an error of $10^{-3}$). It reaches this level much faster than vanilla SGD or other state-of-the-art RLA solvers like Randomized IPCPM.
  • Empirical Performance: On the Buzz dataset (which is notoriously ill-conditioned), vanilla SGD and other competitors struggled to converge, while PWSGD-full (using the full preconditioning matrix) dropped the error by several orders of magnitude almost immediately.

Limitations and Future Work

  • The Curse of Dimensionality for General Loss: While PWSGD works beautifully for $\ell_p$ regression, the authors prove a "negative result" for more general loss functions (like hinge loss). They show that for some problems, the "total sensitivity" (a measure of how many rows you need to sample) can grow exponentially with $d$, meaning the "coreset" approach might not easily generalize beyond linear regression.
  • Hyperparameter Tuning: Like all SGD methods, PWSGD still requires choosing a step size ($\eta$), though the authors provide theoretical guidance on optimal values.
  • Future Directions: The authors suggest that new ideas are needed to extend RLA-style preconditioning to more general convex optimization problems where the current sensitivity-based sampling becomes inefficient.

Summary updated

Abstract

In recent years, stochastic gradient descent (SGD) methods and randomized linear algebra (RLA) algorithms have been applied to many large-scale problems in machine learning and data analysis. We aim to bridge the gap between these two methods in solving constrained overdetermined linear regression problems---e.g., $\ell_2$ and $\ell_1$ regression problems. We propose a hybrid algorithm named pwSGD that uses RLA techniques for preconditioning and constructing an importance sampling distribution, and then performs an SGD-like iterative process with weighted sampling on the preconditioned system. We prove that pwSGD inherits faster convergence rates that only depend on the lower dimension of the linear system, while maintaining low computation complexity. Particularly, when solving $\ell_1$ regression with size $n$ by $d$, pwSGD returns an approximate solution with $\epsilon$ relative error in the objective value in $\mathcal{O}(\log n \cdot \text{nnz}(A) + \text{poly}(d)/\epsilon^2)$ time. This complexity is uniformly better than that of RLA methods in terms of both $\epsilon$ and $d$ when the problem is unconstrained. For $\ell_2$ regression, pwSGD returns an approximate solution with $\epsilon$ relative error in the objective value and the solution vector measured in prediction norm in $\mathcal{O}(\log n \cdot \text{nnz}(A) + \text{poly}(d) \log(1/\epsilon) /\epsilon)$ time. We also provide lower bounds on the coreset complexity for more general regression problems, indicating that still new ideas will be needed to extend similar RLA preconditioning ideas to weighted SGD algorithms for more general regression problems. Finally, the effectiveness of such algorithms is illustrated numerically on both synthetic and real datasets.
BibTeX
@article{yang2018weighted,
  author = {Jiyan Yang and Yinlam Chow and Christopher Ré and Michael W. Mahoney},
  title = {{Weighted SGD for $\textbackslash\{\}ell\_p$ Regression with Randomized Preconditioning}},
  journal = {Journal of Machine Learning Research},
  year = {2018},
}

Loading related content...

Figure