OP-0046OpenHigh-dimensional statistics

Is the computational-statistical gap for sparse PCA real?

Detection is information-theoretically possible well below the threshold where any polynomial-time algorithm is known to work.

MSC 62 · Statistics

Inferred from the community field; finer classification has not been reviewed.

0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

In the spiked covariance model, observe $n$ samples from $\mathcal{N}(0, I_p + \theta vv^\top)$ where $v$ is $k$ -sparse and unit norm. Information-theoretically, detection is possible once $n \gtrsim k\log p / \theta^2$ . Every known polynomial-time algorithm requires $n \gtrsim k^2/\theta^2$ .

Prove that no polynomial-time algorithm succeeds in the intermediate regime, under a standard complexity assumption — or give an algorithm that closes the gap.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

Berthet and Rigollet (2013) gave the first reduction from the planted clique problem, showing hardness in the intermediate regime conditional on planted clique hardness. Brennan and Bresler subsequently developed a general framework of average-case reductions between statistical problems.

Why it matters

Sparse PCA is the canonical example of a computational-statistical gap, a phenomenon now conjectured across community detection, tensor PCA, and sparse regression. A proof from a standard assumption — rather than from planted clique, itself only conjecturally hard — would put the whole area on firm footing.

Known partial results

Conditional hardness from the planted clique conjecture (Berthet–Rigollet; Brennan–Bresler; Wang–Berthet–Samworth).
Unconditional lower bounds are known in restricted models: the statistical query model, low-degree polynomial tests, and the sum-of-squares hierarchy at low degrees.
No unconditional separation is known, and no reduction from an NP-hard worst-case problem exists.

References

[1]Q. Berthet, P. Rigollet, Complexity theoretic lower bounds for sparse principal component detection, COLT 2013.
[2]M. Brennan, G. Bresler, Reducibility and statistical-computational gaps from secret leakage, COLT 2020. link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.