Questions: Computational-Statistical Tradeoffs

Question 1

A statistical problem requires n = O(log d) samples to solve information-theoretically but n = O(sqrt(d)) samples for any known polynomial-time algorithm. If someone proves that no polynomial-time algorithm can match the O(log d) bound, what type of result is this?

• A. An information-theoretic lower bound, since it limits all algorithms
• B. A computational lower bound, showing that efficient algorithms fundamentally require more samples than the information-theoretic minimum — demonstrating a genuine computational-statistical gap
• C. A VC dimension bound, since it relates to sample complexity
• D. A minimax result, since it involves optimal rates

Answer: (B)

This is a computational lower bound: it shows that polynomial-time algorithms cannot match the information-theoretic sample complexity. The information-theoretic lower bound is O(log d) — unlimited-computation algorithms CAN solve it with this many samples. The gap between O(log d) (statistical) and O(sqrt(d)) (computational) is the computational-statistical tradeoff. These lower bounds are conditional on complexity-theoretic assumptions (like P ≠ NP or the hardness of planted clique) because unconditional computational lower bounds are notoriously hard to prove.

Question 2

Computational-statistical tradeoffs can only exist if P ≠ NP.

• T. True
• F. False

Answer: False

While P ≠ NP is one assumption that can generate computational-statistical gaps, tradeoff results in learning theory are typically based on different hardness assumptions — most commonly the planted clique conjecture, the hardness of random SAT, or the hardness of certain average-case problems. These assumptions are believed to be true but are not equivalent to P ≠ NP. In fact, the relevant hardness is often average-case rather than worst-case: the statistical problem involves random data, not adversarially chosen instances, so worst-case hardness assumptions like P ≠ NP may not directly apply. The field uses a variety of hardness assumptions, and the tradeoffs exist under any of them.

Question 3

In sparse PCA, the goal is to find a sparse leading eigenvector of a covariance matrix. The statistical sample complexity is O(k * log(d/k)), but the best known polynomial-time algorithm requires O(k^2) samples. This gap is believed to be inherent.

• T. True
• F. False

Answer: True

This is one of the most studied computational-statistical gaps. Information-theoretically, O(k * log(d/k)) samples suffice to detect a k-sparse eigenvector in d dimensions (achievable by exhaustive search over all k-sparse subsets, which takes exponential time). The best polynomial-time algorithms (semidefinite programming relaxations, diagonal thresholding) require O(k^2) or O(k * sqrt(d)) samples. Under the planted clique conjecture, this gap is unavoidable: no polynomial-time algorithm can achieve the information-theoretic limit. The gap is quadratic in k, which can be enormous when k is large.

Question 4

Explain why computational-statistical tradeoffs are important for machine learning practice, beyond being a purely theoretical concern.

Model answer: Computational-statistical tradeoffs tell practitioners that collecting more data can compensate for limited computing power — and conversely, that some problems cannot be solved with practical algorithms no matter how much data is available (at least not to the information-theoretic limit). For example, if a sparse learning problem has a computational-statistical gap, a practitioner can either: (1) use more data with a fast algorithm (polynomial-time, larger sample complexity), or (2) use less data with a slow algorithm (exponential-time, smaller sample complexity). The tradeoff quantifies this exchange rate between data and computation. For large-scale ML applications where computation is the bottleneck, understanding these tradeoffs guides algorithm selection and resource allocation. They also explain why some theoretically elegant methods are not used in practice — their computational cost may not justify the statistical benefit.

The tradeoffs also have implications for adversarial settings (e.g., cryptography and differential privacy) where computational hardness is deliberately exploited: a computationally bounded adversary cannot extract information that an unbounded adversary could, providing a security/privacy guarantee.