Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression

Alexander Munteanu, Simon Omlor, David Woodruff

Introduction

In the era of massive datasets, scenarios where the number of data points ($n$) vastly exceeds the number of features ($d$) are increasingly common. Standard optimization algorithms become prohibitively slow or impossible to execute when data cannot fit into memory. To address this, researchers employ oblivious sketching: multiplying the data matrix by a random, data-independent matrix $S$ to create a significantly smaller "sketch," and subsequently solving the optimization problem in this reduced space. Because the sketch is generated without examining the data, it is highly effective for streaming environments (where data arrives sequentially) and distributed systems.

While oblivious sketching for $\ell_2$ regression (standard least squares) is well-established, extending these techniques to $\ell_1$ regression (which is robust to outliers) and logistic regression (the cornerstone of classification) has proven difficult. Previous oblivious sketches for these problems either required impractically large sketch sizes (e.g., $d^5$) or yielded poor approximation factors. This paper introduces a novel sketching algorithm that reduces data size to a near-linear sketch while maintaining a constant-factor approximation, dramatically outperforming prior state-of-the-art methods in both theoretical complexity and practical performance.

Methodology: The "Sketch & Solve" Paradigm

The authors adopt the "Sketch & Solve" framework, which consists of computing $SX$ (where $S$ is a random oblivious linear map) and finding the optimal parameters $\beta$ using the sketched data. The paper introduces several key innovations to optimize this process:

  • Multi-level Subsampling: The sketch utilizes $O(\log n)$ levels, with each level subsampling the data at an exponentially decreasing rate.
  • Densified Base Level: In prior work, the base level (level 0) mapped each data point to a single bucket using a CountMin-style sketch. This paper densifies this level by mapping each point to multiple buckets ($s > 1$). This redundancy resolves collisions for "heavy hitters"—influential data points that disproportionately impact the model.
  • Refined Analysis: Rather than bounding the expected contributions of weight classes, the authors employ a "reverse perspective" to analyze which weight classes are adequately represented at each level. This analytical shift tightens the approximation factor from $\ge 8$ down to a 2-approximation.

Key Theoretical Insights

The theoretical contributions of this work bridge the gap between $\ell_1$ and logistic regression sketching. By incorporating a data-dependent parameter $\mu$—which measures the complexity of compressing the data—the authors successfully adapt $\ell_1$ techniques for logistic regression.

Crucially, the asymmetric nature of logistic loss means that, unlike standard $\ell_p$ norms, signs cannot simply be flipped. The authors' reliance on CountMin-style sketches (which sum elements) rather than Count-sketches (which use random signs) is vital for preserving coordinate signs, an essential property for logistic regression.

These insights lead to a significant theoretical leap: for logistic regression, the sketching dimension is improved from roughly $\tilde{O}(\mu^7 d^5)$ to $\tilde{O}(\mu d^{1+c})$ for any constant $c > 0$. For $\ell_1$ regression, the dimension is reduced to $\tilde{O}(d^{1+c})$. Both achieve an $O(1)$-approximation, moving from high-degree polynomial dependencies to nearly linear ones.

Empirical Evaluation

The authors evaluated their method on three real-world benchmarks (Covertype, Webspam, and Kddcup) and a challenging synthetic dataset ($n=40,000, d=100$) engineered with multiple heavy hitters to stress-test previous sketching methods.

  • Robustness to Heavy Hitters: On the synthetic dataset, the new sketch achieved approximation ratios near 2. In contrast, previous state-of-the-art methods struggled, yielding ratios between 7 and 8.
  • Superiority over Cauchy Sketches: For $\ell_1$ regression, the proposed method outperformed classic Cauchy-based sketches in both accuracy and computational efficiency.

Limitations and Future Directions

While the proposed sketching algorithm represents a major step forward, several limitations and open questions remain:

  • Regularization Cost: Extending the sketch to handle variance-based regularized logistic regression introduces an additional $\sqrt{n}$ factor to the sketch size. The authors prove that for their specific CountMin-style approach, this $\Theta(\sqrt{n})$ dependence is unavoidable.
  • Sparsity Trade-offs: Achieving a $(1+\epsilon)$-approximation requires an exponential dependence on $1/\epsilon$, a common bottleneck in the $\ell_1$ embedding literature.
  • Optimal Bounds: A primary open question is whether the upper bound can be further reduced to exactly $O(\mu d)$, or if the current lower bound of $\Omega(\mu + d)$ can be raised to close the theoretical gap.

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 Woodruff},
  title = {{Almost Linear Constant-Factor Sketching for $\textbackslash\{\}ell\_1$ and Logistic Regression}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=gu-SC0dpkvw},
}
Figure