In classical statistics, we are taught that more data is always better because it reduces variance. However, in high-dimensional settings—where the number of features $d$ is much larger than the number of samples $n$—data serves a second, less intuitive purpose: it acts as a computational resource.
For many fundamental problems, there exists a "no man's land" between what is mathematically possible and what is computationally feasible. This phenomenon, known as the Statistical-Computational Gap, suggests that we often need significantly more data than information theory requires just to make the problem solvable by a computer in a reasonable amount of time.
Data as a Computational Lubricant
The core intuition behind this gap is that data can "smooth" a difficult optimization landscape. As Amit Daniely, Nathan Linial, and Shai Shalev-Shwartz demonstrate in More data speeds up training time in learning halfspaces over sparse vectors, certain learning tasks are intractable with a small amount of data but become easy once the sample size passes a specific threshold.
In these regimes, the information-theoretic minimum of data allows for a solution to exist, but finding it requires an exhaustive, exponential-time search—essentially checking every possible combination of features. Providing "redundant" data allows for a new class of polynomial-time algorithms to function, effectively trading samples for clock cycles.
The Quadratic Barrier
The most famous manifestation of this gap is the quadratic barrier in sparse estimation. Suppose we want to find a signal that is $k$-sparse (only $k$ out of $d$ dimensions are relevant).
Information theory tells us we should only need roughly $n \approx k \log d$ samples to identify the signal. However, for many problems like Sparse PCA or Sparse Mean Estimation, all known efficient algorithms require $n \approx k^2$ samples.
This isn't just a lack of algorithmic ingenuity. Tengyu Ma and Avi Wigderson proved in Sum-of-Squares Lower Bounds for Sparse PCA that even the powerful Sum-of-Squares (SoS) hierarchy—a generalized framework for convex relaxation—cannot break this $k^2$ barrier. The geometry of the problem is such that the "signal" only becomes visible to polynomial-time tools once the sample size is large enough to suppress the noise in the second-order moments (the covariance matrix).
Robustness Widens the Gap
The gap becomes even more pronounced when the data is "dirty." In Robust Statistics, we assume an adversary can corrupt a small fraction of our samples.
Researchers like Ilias Diakonikolas and Daniel Kane have shown that robustness introduces its own computational tax. In Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions, they highlight that while we can theoretically estimate a sparse mean with very few samples, any algorithm that is both robust to outliers and runs in polynomial time must obey the $k^2$ sample complexity.
This suggests a fundamental trade-off:
- Statistical Optimality: Requires $k$ samples but takes exponential time.
- Computational Efficiency: Requires $k^2$ samples but runs in polynomial time.
- Robustness: Further complicates the landscape, often requiring even more complex filtering or higher-degree relaxations to maintain accuracy under corruption.
The Geometry of Hardness
Why does this gap exist? Think of the optimization landscape as a dark room.
- With $k$ samples, the room is pitch black, but there is a single, deep hole (the solution). To find it, you must crawl over every inch of the floor (exhaustive search).
- With $k^2$ samples, someone "turns on the lights." The landscape becomes a smooth funnel leading toward the hole. Now, you can simply follow the slope (gradient descent) to find the center.
In Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps, Jonathan Kelner, Frederic Koehler, and Raghu Meka explore how latent correlations between features create these "dark rooms." They show that when features are highly correlated, standard methods like the Lasso fail unless the sample size is large enough to "un-correlate" the features through adaptation.
Bypassing the Barrier
Is the $k^2$ barrier absolute? Recent work suggests we can sometimes cheat the gap by changing the rules.
Ankit Pensia has developed algorithms that achieve subquadratic runtimes ($d^{2-\epsilon}$) for robust estimation. As detailed in A Subquadratic Time Algorithm for Robust Sparse Mean Estimation, these methods use fast correlation detection—originally designed for the "light-bulb problem"—to avoid computing the full $d \times d$ covariance matrix. While these methods still require more samples than the information-theoretic minimum, they represent a new frontier in balancing the three-way tension between sample efficiency, computational speed, and robustness.