Almost Linear Constant-Factor Sketching for 𝓁1 and Logistic Regression

Alexander Munteanu, Simon Omlor, David P. Woodruff

TL;DR

This paper introduces a breakthrough in "sketching" techniques for $\ell_1$ and logistic regression, allowing massive datasets to be compressed into tiny summaries (sketches) that are nearly linear in size relative to the number of features ($d$). By "densifying" the sketch and using a multi-level hashing approach, the authors achieve a constant-factor approximation while significantly reducing the memory and communication costs required for large-scale, streaming, or distributed optimization.

What Problem Does This Paper Address?

In the era of Big Data, we often face scenarios where the number of data points ($n$) is far larger than the number of features ($d$). Processing such data directly is often impossible due to memory constraints or the high cost of moving data across a network.

The "sketch & solve" paradigm addresses this by multiplying the data matrix by a random "oblivious" sketching matrix $S$ to create a much smaller version of the data. You then solve the regression problem on this tiny sketch. However, doing this for $\ell_1$ (robust) regression and logistic regression is notoriously difficult.

Standard sketches (like those for $\ell_2$ regression) often fail here because:

  1. Asymmetry: Logistic loss is asymmetric; standard sketches often "confuse" the signs of data points, leading to massive errors.
  2. Complexity: Previous sketches for these problems required a sketching dimension that was a high-degree polynomial of $d$ (e.g., $d^5$), making them impractical for high-dimensional data.
  3. Streaming Constraints: The sketch needs to be "oblivious" (chosen without seeing the data) and work in "turnstile" streams (where data can be added or deleted).

Methods

The authors build upon a multi-level sketching framework but introduce several critical modifications:

  • Multi-Level CountMin Sketch: The data is subsampled at exponentially decreasing rates across $O(\log n)$ levels. At each level, elements are hashed into buckets (similar to a CountMin sketch).
  • Densified Level 0: The "aha" moment comes at Level 0, which processes the entire dataset. Instead of hashing each point to a single bucket, the authors hash each point to multiple buckets ($s > 1$). This "densification" helps isolate "heavy hitters"—individual data points that have a disproportionately large impact on the regression result (high leverage scores).
  • Sign Preservation: Unlike Cauchy-based sketches, this hashing approach preserves the signs of the coordinates, which is essential for the asymmetric nature of logistic loss.
  • Variance-Based Regularization: The authors extend the technique to handle a version of logistic regression that includes a data-dependent regularizer based on the variance of the losses, which helps improve the model's generalization.

Datasets

The authors evaluated their approach using several real-world benchmark datasets and a custom synthetic one:

  • Covertype: Forest cover type data (581,012 points, 54 features).
  • Webspam: Unigrams from spam/non-spam web pages (350,000 points, 127 features).
  • Kddcup: Network intrusion detection data (494,021 points, 41 features).
  • Synthetic Data: A dataset specifically engineered with "heavy hitters" to demonstrate where previous sketching methods (and standard Stochastic Gradient Descent) fail.

Key Insights and Ideas

  • The Power of Sparsity: By increasing the number of buckets an element is hashed into (the sparsity parameter $s$), you can separate influential points from the "noise" of other large coordinates much more effectively than by just making the sketch larger.
  • Bridging $\ell_1$ and $\ell_2$: The variance-regularized version of logistic regression requires preserving both $\ell_1$ and $\ell_2$ geometries simultaneously. The authors show their sketch can handle this dual requirement, though it introduces a $\sqrt{n}$ factor in the sketch size that appears unavoidable for this specific hashing method.
  • Overcoming Asymmetry: The paper proves that you don't need a massive sketch to handle asymmetric losses; you just need a sketch that respects the "important" parts of the data distribution (the heavy hitters) across different scales.

Key Results

  • Theoretical Bounds: They achieved a sketching dimension of $\tilde{O}(d^{1+c})$ for $\ell_1$ and $\tilde{O}(\mu d^{1+c})$ for logistic regression (where $\mu$ is a data-dependent complexity measure). This is a massive improvement over the previous state-of-the-art, which was roughly $O(\mu^7 d^5)$.
  • Empirical Performance: On the synthetic "heavy hitter" dataset, the new sketch achieved approximation ratios of ~2-3, while the previous state-of-the-art hovered around 7-8.
  • Efficiency: The sketching process is extremely fast, running in "input sparsity time," meaning it only takes as long as it takes to read the non-zero entries of the data.
  • Comparison to Cauchy: For $\ell_1$ regression, the new sketch significantly outperformed the traditional Cauchy sketch in terms of accuracy while being much faster to apply.

Limitations and Future Work

  • The $\mu$ Dependence: While the dependence on the complexity parameter $\mu$ is now quasi-linear, it remains a bottleneck for very "difficult" (highly imbalanced) datasets.
  • The $1+\epsilon$ Gap: Achieving a $(1+\epsilon)$ approximation (rather than just a constant factor) still requires a sketch size that grows exponentially with $1/\epsilon$. Finding a way to make this polynomial is a major open question.
  • Regularization Overhead: The $\sqrt{n}$ factor required for variance-based regularization is a significant jump in sketch size. The authors suggest investigating if other sketching methods (like Count-Sketch) could avoid this, though those methods currently struggle with the asymmetry of logistic loss.

Summary updated

Abstract

We improve upon previous oblivious sketching and turnstile streaming results for $\ell_1$ and logistic regression, giving a much smaller sketching dimension achieving $O(1)$-approximation and yielding an efficient optimization problem in the sketch space. Namely, we achieve for any constant $c>0$ a sketching dimension of $\tilde{O}(d^{1+c})$ for $\ell_1$ regression and $\tilde{O}(\mu d^{1+c})$ for logistic regression, where $\mu$ is a standard measure that captures the complexity of compressing the data. For $\ell_1$-regression our sketching dimension is near-linear and improves previous work which either required $\Omega(\log d)$-approximation with this sketching dimension, or required a larger $\operatorname{poly}(d)$ number of rows. Similarly, for logistic regression previous work had worse $\operatorname{poly}(\mu d)$ factors in its sketching dimension. We also give a tradeoff that yields a $1+\varepsilon$ approximation in input sparsity time by increasing the total size to $(d\log(n)/\varepsilon)^{O(1/\varepsilon)}$ for $\ell_1$ and to $(\mu d\log(n)/\varepsilon)^{O(1/\varepsilon)}$ for logistic regression. Finally, we show that our sketch can be extended to approximate a regularized version of logistic regression where the data-dependent regularizer corresponds to the variance of the individual logistic losses.
BibTeX
@inproceedings{munteanu2023almost,
  author = {Alexander Munteanu and Simon Omlor and David P. Woodruff},
  title = {{Almost Linear Constant-Factor Sketching for 𝓁1 and Logistic Regression}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=gu-SC0dpkvw},
}
Figure