Density Estimation
Kernels, histograms and the curse of dimensionality.
Estimating a density from samples is the purest unsupervised problem, and the one where the curse of dimensionality bites hardest. This lesson derives the optimal bandwidth and rate of kernel density estimation, proves that no estimator can beat without stronger assumptions, and follows the two escape routes of modern generative models: exact likelihoods through a change of variables, and scores in place of densities.
What you’ll learn
- Derive the bias, variance and AMISE of the kernel density estimator, its optimal bandwidth and rate, and data-driven bandwidth selection.
- State the minimax rate for smooth densities, sketch the Assouad lower bound, and quantify the curse of dimensionality.
- Use nearest-neighbor and mixture estimates, and evaluate density models by held-out likelihood, knowing its pitfalls.
- Derive the change-of-variables likelihood of normalizing flows and the score-matching objective, and connect score estimation to diffusion sampling.
Kernel density estimation, precisely
Bias. Substitute and Taylor-expand (twice continuously differentiable). With and , the first-order term cancels:
Variance. averages i.i.d. terms , and :
Integrate over (with ) to get the asymptotic MISE: squared bias grows like , variance falls like :
Setting the derivative to zero balances the terms. The optimum converges like , slower than the parametric :
The kernel matters little: among nonnegative kernels the Epanechnikov kernel minimizes the constant, and the Gaussian kernel reaches about 95% of its efficiency. The bandwidth matters a lot, and it depends on the unknown . Practical choices: the normal reference rule, which plugs in a Gaussian and gives for a Gaussian kernel; least-squares cross-validation, which minimizes , an unbiased estimate of (Rudemo, 1982; Bowman, 1984); likelihood cross-validation, which maximizes ; and plug-in rules that estimate from a pilot fit (Sheather & Jones, 1991). Histograms obey the same logic with a worse rate: and (Scott, 1979).
In dimensions, with bandwidth in every direction, the bias is still order but the variance is , so and .
Minimax rates and the curse of dimensionality
A hypercube of hypotheses. Cut into cubes of side , and in cube place a smooth bump with . For each , perturb the uniform density; for small every is a density in , because rescaling by multiplies the -th derivatives by :
Separation. Flipping one coordinate of changes the density, in squared distance, by the energy of one bump:
Indistinguishability. For neighbors, the KL divergence between the distributions of samples is about . Choose so this stays bounded: no test can reliably tell which way any single bump points.
Assouad's lemma adds up the unavoidable errors over the independent coordinates:
| Dimension | Rate for | for error (constants ignored) |
|---|---|---|
| 1 | ||
| 2 | ||
| 5 | ||
| 10 | ||
| 50 |
Draw 500 points uniformly in the unit ball in . What is the median distance from the center to the nearest of them? (It equals .)
Show the answer
0.52
The nearest point lies beyond radius with probability ; setting this to gives (Hastie, Tibshirani & Friedman, 2009, §2.5). The nearest of 500 neighbors is more than halfway to the boundary: in ten dimensions nothing is local, which is why neighborhood methods need exponentially many points.
The rate's escape hatches are its assumptions. If the data lie near a -dimensional manifold, kernel and nearest-neighbor methods can adapt to instead of (e.g. Ozakin & Gray, 2009; Kpotufe, 2011). Structural assumptions (independence, additivity, sparse graphical models, mixtures of few components) bring back near-parametric rates. Deep generative models bet on strong, learned inductive biases.
Neighbors, mixtures and the likelihood yardstick
The -nearest-neighbor estimate (Loftsgaarden & Quesenberry, 1965) fixes the number of points instead of the window: , where is the distance to the -th nearest sample and the volume of the unit ball. Its bandwidth adapts to the local density, and it is consistent when and , but it is not itself a density: its tails decay like , so it integrates to infinity.
Mixture models sit between parametric and nonparametric: a Gaussian mixture with enough components approximates any smooth density, and EM fits it (k-Means, EM & Mixture Models). Few components act as a strong structural assumption; many act like a kernel estimate with adaptive bandwidths.
How do you compare density models? By held-out log-likelihood. For test points from ,
so ranking models by average test log-likelihood ranks them by their KL divergence from the truth; the entropy is a common, unknown offset (Information Theory for AI). For images it is reported as bits per dimension, . Two cautions: likelihood and sample quality can be largely independent (Theis, van den Oord & Bethge, 2016), and deep density models trained on one dataset can assign higher likelihood to a different one, as flows trained on CIFAR-10 do to SVHN digits (Nalisnick et al., 2019), so likelihood alone is a poor detector of out-of-distribution inputs.
Escape routes: flows and scores
A normalizing flow learns an invertible, differentiable map that sends data to a simple base density , usually . The likelihood is exact, so training is plain maximum likelihood, and sampling inverts the map. Everything hinges on computing the Jacobian determinant cheaply.
For with invertible, probability is conserved, , and the Jacobian measures how stretches volume:
Compose simple layers, with and ; log-determinants add:
Affine coupling (RealNVP; Dinh, Sohl-Dickstein & Bengio, 2017): split , keep , and transform elementwise with scale and shift networks of . The Jacobian is block triangular, so its determinant is the product of the diagonal, whatever and are:
The inverse is just as cheap, , and alternating which half is kept lets every coordinate interact. Autoregressive flows (Papamakarios, Pavlakou & Murray, 2017) and continuous-time flows extend the same principle (survey: Papamakarios et al., 2021).
The second route drops the normalizing constant altogether. If , the score does not involve . Score matching (Hyvärinen, 2005) fits a model score to the data's score without knowing it: integrating by parts (assuming at infinity),
Denoising score matching (Vincent, 2011) avoids the trace: for , minimizing recovers the score of the noised density. Learning scores at many noise levels and then reversing the noising process is the recipe of diffusion models (Song & Ermon, 2019; Ho, Jain & Abbeel, 2020), developed in Diffusion Models.
An affine coupling layer maps , where and are deep networks. What is ?
- , because the layer is invertible
- It requires an determinant of the networks' Jacobians
Show the answer
D.
The Jacobian is block lower-triangular: the identity on , and on . The off-diagonal block, which contains the networks' derivatives, does not enter the determinant, so it costs .
Key takeaways
- Kernel density estimation has bias and variance ; the optimal bandwidth scales as and the MISE as , or and in dimensions. The bandwidth matters far more than the kernel.
- Choose by a normal-reference rule, least-squares or likelihood cross-validation (always leave-one-out), or plug-in estimates of .
- The minimax rate over -smooth densities is (Assouad's hypercube of bumps proves the lower bound), so the sample size for fixed accuracy grows exponentially with unless the data have more structure.
- Held-out log-likelihood ranks models by , but it tracks sample quality and out-of-distribution detection poorly.
- Normalizing flows make likelihoods exact with triangular Jacobians; score matching removes the normalizer, and learned scores at many noise levels drive diffusion sampling, whose discretization error the widget isolates.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
For a one-dimensional kernel density estimate of a twice-differentiable density, how do the optimal bandwidth and the optimal MISE scale with ?
- and
- and
- and
- constant and
Show the answer
B. and
Balancing squared bias against variance gives , and then both terms scale like . Nonparametric estimation pays for its flexibility with a rate slower than the parametric .
For densities with smoothness in dimensions, what is the best possible worst-case rate of the MISE?
- , as in one dimension
Show the answer
C.
, and no estimator does better over the whole class (Assouad's hypercube of bumps). Halving the error takes times more data.
Why can't you choose the bandwidth by maximizing the in-sample log-likelihood ?
- Because it is maximized at
- Because the likelihood does not depend on
- Because log-likelihoods cannot be compared between bandwidths
- Because each point's own kernel spike makes it grow without bound as ; leaving each point out fixes this
Show the answer
D. Because each point's own kernel spike makes it grow without bound as ; leaving each point out fixes this
includes the term , which diverges as : the in-sample criterion rewards interpolation, the density version of overfitting. Likelihood cross-validation uses , which excludes point 's own kernel.
Why does score matching not need the normalizing constant of an unnormalized model ?
- Because : the constant disappears under the gradient in
- Because it estimates by Monte Carlo along the way
- Because it only applies to Gaussian models, where is known
- Because it maximizes the likelihood, in which cancels
Show the answer
A. Because : the constant disappears under the gradient in
depends on but not on , so it vanishes from the score, and integration by parts removes the unknown data score from the objective. That is what makes energy-based and score-based models trainable.
Further reading
- M. Rosenblatt, "Remarks on some nonparametric estimates of a density function," Annals of Mathematical Statistics 27(3), 832–837 (1956).
- E. Parzen, "On estimation of a probability density function and mode," Annals of Mathematical Statistics 33(3), 1065–1076 (1962).
- A. B. Tsybakov, Introduction to Nonparametric Estimation (Springer, 2009).
- A. Hyvärinen, "Estimation of non-normalized statistical models by score matching," Journal of Machine Learning Research 6, 695–709 (2005).
- G. Papamakarios, E. Nalisnick, D. J. Rezende, S. Mohamed & B. Lakshminarayanan, "Normalizing flows for probabilistic modeling and inference," Journal of Machine Learning Research 22(57), 1–64 (2021).