Sharper Bounds for ℓSensitivity Sampling

David P. Woodruff, Taisuke YasudaICML 2023 · OpenReview

Introduction

In the era of massive datasets, processing every single training example is often computationally prohibitive. To address this, machine learning practitioners rely on data reduction techniques to create a "coreset"—a small, weighted subset of the data that acts as a highly accurate proxy for the full dataset. Woodruff and Yasuda (ICML 2023) break a long-standing theoretical barrier in this domain by providing the first sharper bounds for $\ell_p$ sensitivity sampling. They prove that for $\ell_p$ subspace embeddings, we can approximate massive datasets using significantly fewer samples than classic bounds suggested, achieving nearly optimal complexity for a wide range of norms.

The Challenge of Data Reduction

Sensitivity sampling is a powerful technique for constructing coresets with provable accuracy guarantees. Historically, the theoretical "speed limit" for the number of samples required was bounded by $O(\mathfrak{S}d/\epsilon^2)$, where $\mathfrak{S}$ represents the total sensitivity (a measure of how much any single data point can influence the objective function) and $d$ is the dimension of the data.

While this $\mathfrak{S}d$ bound was known to be loose for standard least-squares ($\ell_2$) regression, it remained the best-known guarantee for other $\ell_p$ norms, such as the robust $\ell_1$ norm. The central question addressed by this paper is whether we can achieve sharper, more efficient sampling bounds for $\ell_p$ norms when $p \neq 2$.

Methodological Innovations

To move beyond simple union bounds, the authors employ sophisticated tools from high-dimensional probability:

  • Generalized Chaining Arguments: Instead of analyzing the data at a single scale, chaining allows the authors to bound the sampling error by examining a sequence of increasingly fine approximations (nets).
  • Gaussianization Reduction: The researchers relate the sampling error to the behavior of a Gaussian process, which is more tractable to analyze using established tools like Dudley’s entropy integral.
  • Auxiliary Subspace Embeddings: A key technical innovation involves constructing a "helper" embedding with desirable properties—such as "flat" sensitivities—to facilitate the proof of the main sampling result.
  • Flattening and Recursion: For $p > 2$, the authors utilize a recursive strategy that "flattens" high-sensitivity rows by splitting them into multiple smaller rows. This prevents any single point from dominating the variance during the sampling process.

Theoretical Testbeds

As a foundational theoretical work, the paper does not benchmark on standard empirical ML datasets like ImageNet. Instead, it utilizes specific mathematical structures to prove its claims:

  • Random Gaussian Matrices: These are used to prove that the newly established bounds are "tight" (meaning they cannot be improved further) for the $1 \le p < 2$ case.
  • Structured Matrices: The authors provide specific lemmas for Vandermonde matrices and low-rank plus sparse matrices. This demonstrates that their sensitivity sampling is robust to noise, succeeding in scenarios where previous algebraic tricks (like tensoring) would fail.

Key Insights and Results

The paper delivers several new state-of-the-art theoretical bounds for the number of samples ($m$) required to achieve a $(1 \pm \epsilon)$ approximation:

  • Breaking the $\mathfrak{S}d$ Barrier: The most significant breakthrough is the realization that the generic $\mathfrak{S}d$ bound is overly pessimistic for subspace embeddings. By exploiting the geometric structure of $\ell_p$ spaces, the authors show the sample complexity depends on $\mathfrak{S}$ with an exponent strictly less than 1.
  • For $1 \le p < 2$: $m \approx \mathfrak{S}^{2/p} / \epsilon^2$. This is the first improvement over $\mathfrak{S}d$ and is proven to be tight.
  • For $2 < p < \infty$: $m \approx \mathfrak{S}^{2-2/p} / \epsilon^2$.
  • Robustness to Noise: Unlike specialized sampling methods that rely on exact matrix rank, sensitivity sampling depends only on norms. This makes it highly robust, functioning perfectly even if the data is slightly corrupted by roundoff error or minor noise.
  • The Power of Root Leverage Scores: The paper provides a rigorous theoretical justification for "root leverage score sampling," a popular heuristic in practice. For $p < 2$, they prove this method achieves a bound of roughly $d/\epsilon^{4/p}$, a massive win for high-dimensional, low-sensitivity data.
  • Hybrid Sampling: By combining leverage scores and sensitivity, the authors achieve a bound of $d^{2/p}\mathfrak{S}^{2-4/p}$ for $p > 2$, representing the best-known result for matrices with small total sensitivity.

Limitations and Future Directions

While the paper makes substantial strides, several open questions remain:

  • The $p > 2$ Gap: Although the bounds for $p < 2$ are tight, the authors acknowledge that the results for $p > 2$ might still be improvable. They conjecture that a sample complexity of $O(\mathfrak{S} + d)$ might ultimately be possible.
  • Huber Loss: The authors hint that their techniques could be adapted to solve the sampling problem for the Huber loss (a common robust loss function), but a complete, optimal solution remains an open challenge.
  • One-Shot vs. Recursive Sampling: Currently, some of the best results for $p > 2$ require a recursive algorithm. Finding a "one-shot" sampling distribution that achieves identical results is a primary goal for future research.

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 $2root 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 Cite this Paper BibTeX @InProceedings{pmlr-v202-woodruff23a, title = {Sharper Bounds for $\ell_p$ Sensitivity Sampling}, author = {Woodruff, David and Yasuda, Taisuke}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {37238--37272}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/woodruff23a/woodruff23a.pdf}, url = {https://proceedings.mlr.press/v202/woodruff23a.html}, 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 $2root 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 Copy to Clipboard Download Endnote %0 Conference Paper %T Sharper Bounds for $\ell_p$ Sensitivity Sampling %A David Woodruff %A Taisuke Yasuda %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-woodruff23a %I PMLR %P 37238--37272 %U https://proceedings.mlr.press/v202/woodruff23a.html %V 202 %X 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 $2root 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 Copy to Clipboard Download APA Woodruff, D. & Yasuda, T.. (2023). Sharper Bounds for $\ell_p$ Sensitivity Sampling. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:37238-37272 Available from https://proceedings.mlr.press/v202/woodruff23a.html. Copy to Clipboard Download Related Material Download PDF OpenReview
BibTeX
@inproceedings{woodruff2023sharper,
  author = {David P. Woodruff and Taisuke Yasuda},
  title = {{Sharper Bounds for ℓSensitivity Sampling}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=OctkhtlLZT},
}

Loading related content...

Figure