In classical statistics, if you want to understand a probability distribution over $N$ possible outcomes, the rule of thumb is simple: you need a number of samples proportional to $N$. To know the probability of every face of a 1,000,000-sided die, you must roll it millions of times. This is the learning regime.
However, a growing body of research shows that if your goal is not to reconstruct the distribution, but merely to verify a property of it—such as whether it is uniform, whether it matches a known model, or what its entropy is—you can often succeed with significantly less data. This is the sub-learning regime, where the sample complexity is often sub-linear (e.g., $\sqrt{N}$) or even independent of the domain size.
The Intuition of the Birthday Paradox
The fundamental reason verification is easier than learning is rooted in the "Birthday Paradox." To learn the exact birth date of every person in a room, you must ask everyone. But to verify if the distribution of birthdays is "highly non-uniform" (i.e., people share birthdays more often than expected), you only need about $\sqrt{365} \approx 23$ people.
As Ilias Diakonikolas, Themistoklis Gouleakis, and John Peebles demonstrate in Optimal Identity Testing with High Probability, the transition from the "birthday regime" to the "learning regime" can be characterized by a single mathematical expression. This allows researchers to determine exactly how many samples are needed to be "very sure" about a distribution's identity without ever seeing most of the possible outcomes.
Identity Testing vs. Estimation
A key insight in this field is that identity testing (comparing an unknown distribution $P$ to a known reference $Q$) is quadratically more efficient than estimation (calculating a property of $P$ from scratch).
Consider entropy. In Entropy and Inference, Revisited, Ilya Nemenman, F. Shafee, and William Bialek introduced the NSB estimator, showing that summary statistics like entropy can be inferred even when the number of samples is orders of magnitude smaller than the outcome space.
More recently, Clement Louis Canonne and Joy Qiping Yang explored this in Entropy testing and its application to testing Bayesian networks. They found that while estimating the entropy of an unknown distribution requires $O(N/\log N)$ samples, testing if that distribution matches the entropy of a known reference requires only $O(\sqrt{N})$ samples. By using the reference model as a baseline, the algorithm only needs to detect deviations, which manifest as "collisions" or patterns much earlier than the full distribution emerges.
Exploiting Structural Constraints
The sample complexity drops even further when we know the distribution has a specific structure, such as being $k$-modal (having $k$ peaks) or being a sum of independent variables.
- Histograms and Bayesian Networks: Ilias Diakonikolas and Daniel Kane have shown that for multidimensional histograms and Bayesian networks, one can verify model fit using quadratically fewer samples than parameter estimation would require (Testing Identity of Multidimensional Histograms; Testing Bayesian Networks).
- Fourier Sparsity: In Fourier-Based Testing for Families of Distributions, Alistair Stewart and colleagues demonstrate that structured distributions often have "sparse" Fourier spectra. By operating in the frequency domain, testers can break the $\sqrt{N}$ barrier entirely, sometimes requiring samples proportional only to the fourth root of the domain size.
Verification as the "P vs NP" of Learning
This research direction suggests a "P vs NP" analogy for statistical learning: it is fundamentally easier to verify a claim about a model than to generate the model itself. Jonathan Shafer and Saachi Mutreja formalize this in PAC Verification of Statistical Algorithms, proving that for many tasks, the number of samples needed to verify a model's optimality is quadratically lower than the number needed for initial training.
This has practical implications for Fairness Auditing. As Tom Yan and Chicheng Zhang argue in Active fairness auditing, regulators don't need to reconstruct a company's secret proprietary model to check if it is biased. They only need enough queries to estimate global statistical properties like demographic parity, which is a much lighter lift.
Interactive Verification
The most extreme version of this speedup occurs in interactive settings. Tal Herman and Guy N. Rothblum describe a protocol where an untrusted "prover" (who has seen all the data) makes a claim about a distribution's property (How to Verify Any (Reasonable) Distribution Property). The verifier can then use a tiny number of samples—roughly $\sqrt{N}$—to "catch" the prover if they are lying. By forcing the prover to commit to a specific distribution, the verifier turns a difficult property-testing problem into a simpler identity-testing problem.