Computational-Statistical Tradeoffs

Core Idea

Computational-statistical tradeoffs arise when a problem is information-theoretically solvable with few samples but computationally intractable — more samples are needed if we restrict to polynomial-time algorithms. The statistical (information-theoretic) sample complexity is the number of samples needed by any algorithm (with unlimited computation); the computational sample complexity is the number needed by any efficient algorithm. When these differ, there is a gap that represents the cost of computational efficiency. Examples include sparse PCA (statistically solvable with O(k * log(d)) samples, but computationally requiring O(k^2) or more under planted clique hardness) and planted clique detection. These tradeoffs reveal a fundamental tension between computation and information in learning.

Explainer

Classical learning theory treats statistical and computational complexity as separate concerns: sample complexity bounds tell you how much data you need, and then you worry about finding an efficient algorithm separately. Computational-statistical tradeoffs reveal that these concerns are fundamentally entangled — for some problems, the amount of data required depends on how much computation you are willing to invest.

The simplest illustration is the planted clique problem. Given a random graph on n vertices, a clique of size k is planted (all k(k-1)/2 edges are added). The goal is to find the planted clique. Information-theoretically, the planted clique is detectable when k >= 2 * log(n) (a maximum clique in a random graph has size about 2 * log(n), so any larger clique stands out). But the best known polynomial-time algorithms require k >= sqrt(n) — an exponentially larger clique. The gap between 2 * log(n) (statistical) and sqrt(n) (computational) is believed to be inherent under the planted clique conjecture.

This gap has cascading consequences for learning problems. Many statistical problems can be reduced to planted clique, allowing the hardness to transfer. Sparse PCA, community detection in stochastic block models, and certain high-dimensional testing problems all exhibit computational-statistical gaps that can be explained (at least partially) by the hardness of planted clique or related problems. The reductions show that if you could solve the learning problem efficiently with the information-theoretically optimal number of samples, you could solve planted clique efficiently — which is conjectured to be impossible.

The practical implications are significant. When a computational-statistical gap exists, practitioners face a genuine tradeoff: use a fast algorithm that requires more data, or a slow algorithm that requires less. For big-data applications where data is abundant but computation is expensive, efficient algorithms that are statistically suboptimal may be preferred. For small-data applications (medical imaging, rare-event detection), the statistical limit is more relevant and may justify computationally expensive methods. Understanding where these gaps exist — and how large they are — informs the design of learning systems and the allocation of resources between data collection and computation. The field is still developing: proving unconditional computational-statistical gaps (without hardness assumptions) remains a major open problem in theoretical computer science.