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:
- 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.
- 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.
- 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