Planted Problems and the High-Dimensional Limit

Here is a question practitioners ask constantly and rarely answer precisely: is there enough signal in this data to recover what I want?

Usually the question gets answered empirically. Run some algorithms. If they all fail, conclude the signal is not there and move on.

That inference is wrong, and the reason is the subject of this path. A problem can contain more than enough information to determine the answer uniquely, while every algorithm that runs in reasonable time fails to find it. Information and tractability are different resources, and the gap between them is not a gap in our cleverness. In several well-studied problems it appears to be a structural feature of the problem itself.

The field that mapped this most precisely came from an unexpected direction: statistical physics. Lenka Zdeborova, who holds professorships in both physics and computer science at EPFL and leads the Statistical Physics of Computation Laboratory, works on exactly this boundary, using tools built for studying how water freezes to predict when algorithms fail.

The connection is not a loose analogy. It is a structural correspondence.

Statistical physics studies systems with an enormous number of interacting components, where you cannot track individuals but the aggregate behaves predictably. A litre of water contains far too many molecules to simulate, yet it freezes at a sharp, reproducible temperature.

That sharpness is the key phenomenon. A phase transition is a point where a small change in a parameter, one degree of temperature, produces a qualitative change in the system's global state. Not gradual thickening: liquid, then solid.

High-dimensional inference has the same structure. A problem with many variables and many constraints is a system of interacting components. Tune a parameter, how much data you have, and something similar happens: below a threshold no algorithm recovers the signal, above it recovery is easy, and the transition can be sharp rather than gradual.

The mathematics developed over a century to handle magnets and glasses transfers, because the underlying object, a probability distribution over many coupled variables, is the same.

To study when recovery is possible you need problems where you know the right answer. That is what a planted model provides.

The recipe has two steps. First, generate a ground truth signal from a known distribution. Second, generate observed data from that signal through a known noisy channel.

Three canonical examples recur throughout this path.

The stochastic block model. Assign each of n nodes a hidden group label. Then connect nodes with probability that depends on whether they share a label: higher within groups, lower across. Observe only the graph. Recover the labels.

Planted clique. Take a random graph where every edge appears with probability one half. Choose k vertices and make them fully connected. Observe the graph. Find the clique.

Sparse PCA. Generate a sparse hidden direction, observe noisy samples correlated with it, recover the direction.

The artificiality is deliberate and productive. Because you generated the truth, you can measure exactly how well any algorithm recovered it, and ask what the best possible performance would be.

The second ingredient is a specific way of taking limits, and it is what makes sharp thresholds appear at all.

Classical statistics fixes the number of parameters and lets the sample size grow. Modern problems do not look like that: as you collect more data you also track more variables.

So the high-dimensional limit sends both to infinity together, holding their ratio fixed. Write n for the number of variables and m for the number of observations, and let both grow with $\alpha = m/n$ constant. That ratio, the amount of data per unit of unknown, becomes the control parameter, and it plays the role temperature plays in physics.

Two things happen in this limit, and both are essential.

Quantities that fluctuate at finite size concentrate: the error achieved on a random instance stops varying and converges to a deterministic value depending only on $\alpha$. That is why a statement like "recovery is impossible below this threshold" can be exact rather than probabilistic.

And transitions become sharp. At finite n the change is smooth; as n grows it steepens, and in the limit it is a genuine discontinuity.

The final ingredient is a reference point that no algorithm can beat.

In a planted model you know the distribution that generated the signal and the channel that produced the data. So the posterior distribution over the signal given the data is fully specified, and the best possible estimator is the one derived from it. No procedure, however clever or however slow, does better.

This matters because it separates two questions that are usually tangled together.

Is the information present? Answered by whether the Bayes-optimal estimator succeeds. This is a property of the problem, not of any algorithm.

Can it be extracted efficiently? Answered by whether some polynomial-time procedure achieves the same thing.

When a practitioner's algorithms all fail, they conflate these. The planted-model framework keeps them apart, and the whole subject exists because the answers can differ.

Computing the Bayes-optimal error requires an integral over an exponentially large space, which is where the physics tooling enters: the replica method and the cavity method were built to evaluate exactly this kind of object.

Each ingredient is doing specific work. The planted model supplies ground truth, the high-dimensional limit makes quantities deterministic and thresholds sharp, and the Bayes-optimal benchmark separates what is knowable from what is computable.

Consider the stochastic block model with two equal groups, and let the within-group and across-group connection probabilities differ by an amount controlled by a parameter.

Strong signal:  within-group edges much more likely
  -> the graph visibly splits into two dense blobs
  -> simple methods recover the labels

Weak signal:  probabilities nearly equal
  -> each node's neighbours look like a random sample
  -> no procedure can do better than guessing

The interesting question is what happens in between, and the answer is not "gradually worse".

There is a threshold. Above it, the group structure is detectable and efficient algorithms find it. Below it, the observed graph is statistically indistinguishable from one with no group structure at all, so failure is not a limitation of your method: the information is genuinely absent.

That much is already a strong statement, and it was proven for this model. But the two-group case is the easy one, because the two thresholds coincide.

Add more groups and they separate, opening a region where the information is present and no efficient algorithm finds it. That region is the subject of the next lesson.

Being precise about scope matters, because results in this area are both stronger and narrower than casual summaries suggest.

Two caveats deserve emphasis. First, average-case is not worst-case. These results describe typical instances drawn from a distribution. Classical complexity theory asks about the hardest instance, and the two notions genuinely differ.

Second, much of the hardness is conjectural. Physics methods produce exact predictions that have repeatedly been confirmed by later rigorous proofs, which is a strong track record, but a predicted hard phase is generally not a theorem that no algorithm exists.

What you get in return is precision unavailable elsewhere: not "this seems difficult" but "below this exact threshold, recovery is impossible; between these two thresholds, it is possible but apparently intractable".