In modern machine learning, we often face the "curse of dimensionality": as the number of features $p$ grows, the amount of data needed to learn a model typically grows exponentially. However, a significant body of research demonstrates that if the underlying signal is sparse—meaning only a small subset of features $k$ actually matters—we can bypass this curse. The core intuition across these papers is that the required sample size $n$ scales logarithmically with the total number of dimensions ($n \propto \log p$).
The Geometry of Sparsity
The reason we can recover a signal from $p$ dimensions using far fewer than $p$ samples is that sparsity drastically reduces the "search space" of possible models. Instead of searching the entire high-dimensional space, we are looking for a small number of active coordinates.
Bo Chen and Andreas Krause show in Joint Optimization and Variable Selection of High-dimensional Gaussian Processes that this logarithmic scaling holds even for complex, non-linear functions. When only a handful of variables are "active," the cost of discovering them remains manageable even as the number of irrelevant "noise" features grows to the thousands or millions.
Scaling Laws Across Domains
This logarithmic relationship is a universal principle that applies to various statistical tasks beyond simple regression:
- Clustering: Aarti Singh and Larry A. Wasserman demonstrate in Efficient Sparse Clustering of High-Dimensional Non-spherical Gaussian Mixtures that we can group data points effectively even when relevant features are hidden among thousands of noise features, provided the sample size grows with $\log p$.
- Classification: In Feature Selection in High-Dimensional Classification, Mladen Kolar and Han Liu prove that classification is just as efficient as regression, requiring a sample size that scales linearly with the number of relevant features $k$ but only logarithmically with the total count $p$.
- Robust Estimation: Even when data is corrupted by outliers, Simon S. Du and Sivaraman Balakrishnan show in Computationally Efficient Robust Estimation of Sparse Functionals that the $\log p$ scaling persists, making robust statistics viable in high dimensions.
From Theory to Practice: Screening and Testing
The logarithmic scaling property enables a powerful two-stage experimental design. If we know that $n$ only needs to grow with $\log p$, we can conduct a small "pilot study" to screen for relevant variables before committing to a large-scale experiment.
Alfred O. Hero and colleagues describe this in Predictive Correlation Screening, where a screening phase identifies a candidate subset of variables. Similarly, Utkarsh Porwal and Ce Zhang take inspiration from "group testing" in Parallel Feature Selection Inspired by Group Testing. By testing groups of features together rather than one by one, they achieve the same logarithmic efficiency, allowing for feature selection on datasets with millions of dimensions.
Why It Works
The intuition is similar to a game of "20 Questions." To find one specific item out of a million ($p=10^6$), you don't need a million questions; you only need about 20 ($\log_2 10^6 \approx 20$). In high-dimensional sparse recovery, each sample acts like a "question" that narrows down the space of possible active features. Because each sample provides information about many dimensions simultaneously, we can identify the needle in the haystack with surprisingly little data.