Sharper Bounds for $\ell_p$ Sensitivity Sampling

David Woodruff, Taisuke YasudaICML 2023 · OpenReview

In large-scale machine learning, datasets are often too massive to process directly. "Subspace embeddings" offer a powerful solution by compressing an $n \times d$ matrix into a much smaller $m \times d$ representation while preserving its essential geometric properties, such as $\ell_p$ norms. A premier technique for achieving this is sensitivity sampling.

In a theoretical breakthrough presented at ICML 2023, David P. Woodruff and Taisuke Yasuda demonstrate that sensitivity sampling for $\ell_p$ norms is significantly more efficient than previously understood. By breaking a long-standing sample complexity barrier, their work provides the best-known guarantees for a wide class of structured matrices.

The Problem: The $\mathfrak{S}d$ Barrier

When creating a representative subset of data (a "coreset"), uniform sampling often fails because it misses crucial outliers. Sensitivity sampling solves this by assigning an importance score—or "sensitivity"—to each row. The sum of these scores across the dataset is the total sensitivity, denoted as $\mathfrak{S}$.

For over a decade, the standard sample complexity bound for sensitivity sampling was $O(\mathfrak{S}d/\epsilon^2)$, where $d$ is the dimension and $\epsilon$ is the error tolerance. However, researchers noticed a glaring gap: for the standard $\ell_2$ norm (least squares), the total sensitivity $\mathfrak{S}$ is exactly $d$, which predicts a requirement of $d^2$ samples. Yet, it has long been known that $O(d)$ samples are actually sufficient for $\ell_2$ subspace embeddings.

This "quadratic looseness" suggested that the general $\mathfrak{S}d$ bound was overly pessimistic. The authors set out to answer a fundamental question: Can we achieve sharper bounds for $\ell_p$ norms where $p \neq 2$?

Methodological Breakthroughs

To break the $\mathfrak{S}d$ barrier, the authors abandon simple union bounds in favor of sophisticated techniques from high-dimensional probability:

  1. Generalized Chaining: Instead of evaluating sampling error at a single scale, the authors use chaining arguments to analyze a sequence of increasingly fine-grained approximations (nets) of the subspace. This provides much tighter control over how sampling error behaves across the infinite set of vectors in a subspace.
  2. Gaussianization Reduction: They bound the sampling error by comparing it to a Rademacher (random sign) process, which is then related to a Gaussian process. This unlocks powerful mathematical tools, such as Dudley’s entropy integral.
  3. Flattening: To stabilize the random sampling process, rows with excessively high sensitivity are "split" into multiple rows with lower sensitivity. This preserves the geometry of the space while tightening the theoretical analysis.

Key Results and Theoretical Guarantees

The paper establishes several new, sharper bounds for the number of samples ($m$) required to achieve an accurate subspace embedding:

  • For $1 \le p < 2$: The sample complexity is reduced to roughly $\mathfrak{S}^{2/p}$. For random Gaussian matrices, this drops the requirement from $d^{p/2+1}$ to just $d$ (ignoring logarithmic factors), proving that this new bound is tight.
  • For $p > 2$: The bound improves to roughly $\mathfrak{S}^{2-2/p}$.
  • Root Leverage Scores: Practitioners often use root leverage score sampling (sampling proportional to the square root of $\ell_2$ importance) because it is computationally efficient. The authors provide the first near-optimal theoretical analysis showing that for $1 \le p < 2$, this method achieves a bound of roughly $d$ samples, matching the best-known specialized algorithms.
  • Hybrid Sampling: For $p > 2$, the authors show that combining leverage score and sensitivity sampling yields an improved bound of $d^{2/p}\mathfrak{S}^{2-4/p}$.

Why It Matters: Robustness and Structured Data

While alternative methods like "Lewis weight sampling" are theoretically optimal for worst-case matrices, they are notoriously brittle in practice. Adding a tiny amount of noise to a structured matrix can cause Lewis weights to explode.

Sensitivity sampling is inherently more robust to noise. The new bounds yield the best-known sample complexity for structured matrices—such as low-rank plus sparse perturbations, or matrices under polynomial feature maps (Vandermonde-like matrices)—that naturally exhibit small $\ell_p$ sensitivity.

Limitations and Future Directions

While the bounds for $p < 2$ are proven to be tight, the authors note that the $p > 2$ regime may still be improvable, conjecturing a possible complexity of $O(\mathfrak{S} + d)$. Additionally, extending these optimal sampling algorithms to robust loss functions like the Huber loss (which combines $\ell_1$ and $\ell_2$ penalties) remains an open challenge. Finally, achieving some of the most advanced bounds in the paper requires recursive sampling procedures, which may be more complex to implement in streaming environments than simple one-shot passes.

Summary updated

Abstract

In large scale machine learning, *random sampling* is a popular way to approximate datasets by a small representative subset of examples. In particular, *sensitivity sampling* is an intensely studied technique which provides provable guarantees on the quality of approximation, while reducing the number of examples to the product of the *VC dimension* $d$ and the *total sensitivity* $\mathfrak{S}$ in remarkably general settings. However, guarantees going beyond this general bound of $\mathfrak{S} d$ are known in perhaps only one setting, for *$\ell_2$ subspace embeddings*, despite intense study of sensitivity sampling in prior work. In this work, we show the first bounds for sensitivity sampling for $\ell_p$ subspace embeddings for $p\neq 2$ that improve over the general $\mathfrak{S} d$ bound, achieving a bound of roughly $\mathfrak{S}^{2/p}$ for $1\leq p<2$ and $\mathfrak{S}^{2-2/p}$ for $2<p<\infty$. For $1\leq p<2$, we show that this bound is tight, in the sense that there exist matrices for which $\mathfrak{S}^{2/p}$ samples is necessary. Furthermore, our techniques yield further new results in the study of sampling algorithms, showing that the *root leverage score sampling* algorithm achieves a bound of roughly $d$ for $1\leq p<2$, and that a combination of leverage score and sensitivity sampling achieves an improved bound of roughly $d^{2/p}\mathfrak{S}^{2-4/p}$ for $2<p<\infty$. Our sensitivity sampling results yield the best known sample complexity for a wide class of structured matrices that have small $\ell_p$ sensitivity.
BibTeX
@inproceedings{woodruff2023sharper,
  author = {David Woodruff and Taisuke Yasuda},
  title = {{Sharper Bounds for $\textbackslash\{\}ell\_p$ Sensitivity Sampling}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=3onrj9ua4l},
}
Figure