Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

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 n−2β/(2β+d)n^{-2\beta/(2\beta+d)} 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 n−2β/(2β+d)n^{-2\beta/(2\beta+d)} 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

DerivationBias, variance and the optimal bandwidth (d = 1)
  1. E p^h(x)=∫K(u) p(x−hu) du=p(x)+h22 μ2(K) p′′(x)+o(h2)\E\,\hat p_h(x)=\int K(u)\,p(x-hu)\,du=p(x)+\frac{h^2}2\,\mu_2(K)\,p''(x)+o(h^2)

    Bias. Substitute y=x−huy=x-hu and Taylor-expand pp (twice continuously differentiable). With ∫K=1\int K=1 and ∫uK=0\int uK=0, the first-order term cancels:

  2. Var⁡ p^h(x)=1n(EKh(x−X)2−(EKh(x−X))2)=R(K) p(x)nh+o(1nh)\Var\,\hat p_h(x)=\frac1n\Big(\E K_h(x-X)^2-\big(\E K_h(x-X)\big)^2\Big)=\frac{R(K)\,p(x)}{nh}+o\Big(\frac1{nh}\Big)

    Variance. p^h(x)\hat p_h(x) averages nn i.i.d. terms Kh(x−Xi)K_h(x-X_i), and EKh(x−X)2=1h∫K(u)2p(x−hu) du\E K_h(x-X)^2=\frac1h\int K(u)^2p(x-hu)\,du:

  3. AMISE(h)=h44 μ2(K)2R(p′′)+R(K)nh\mathrm{AMISE}(h)=\frac{h^4}4\,\mu_2(K)^2R(p'')+\frac{R(K)}{nh}

    Integrate over xx (with ∫p=1\int p=1) to get the asymptotic MISE: squared bias grows like h4h^4, variance falls like 1/(nh)1/(nh):

  4. h∗=(R(K)μ2(K)2R(p′′) n)1/5,AMISE(h∗)=54(μ2(K)2R(K)4R(p′′))1/5n−4/5h^*=\Big(\frac{R(K)}{\mu_2(K)^2R(p'')\,n}\Big)^{1/5},\qquad\mathrm{AMISE}(h^*)=\frac54\big(\mu_2(K)^2R(K)^4R(p'')\big)^{1/5}n^{-4/5}

    Setting the derivative to zero balances the terms. The optimum converges like n−4/5n^{-4/5}, slower than the parametric 1/n1/n:

The kernel matters little: among nonnegative kernels the Epanechnikov kernel 34(1−u2)+\tfrac34(1-u^2)_+ minimizes the constant, and the Gaussian kernel reaches about 95% of its efficiency. The bandwidth matters a lot, and it depends on the unknown R(p′′)R(p''). Practical choices: the normal reference rule, which plugs in a Gaussian pp and gives h=(4/(3n))1/5σ^≈1.06 σ^n−1/5h=\big(4/(3n)\big)^{1/5}\hat\sigma\approx1.06\,\hat\sigma n^{-1/5} for a Gaussian kernel; least-squares cross-validation, which minimizes ∫p^h2−2n∑ip^h,−i(Xi)\int\hat p_h^2-\frac2n\sum_i\hat p_{h,-i}(X_i), an unbiased estimate of MISE(h)−R(p)\mathrm{MISE}(h)-R(p) (Rudemo, 1982; Bowman, 1984); likelihood cross-validation, which maximizes ∑ilog⁡p^h,−i(Xi)\sum_i\log\hat p_{h,-i}(X_i); and plug-in rules that estimate R(p′′)R(p'') from a pilot fit (Sheather & Jones, 1991). Histograms obey the same logic with a worse rate: h∗∝n−1/3h^*\propto n^{-1/3} and MISE∗∝n−2/3\mathrm{MISE}^*\propto n^{-2/3} (Scott, 1979).

In dd dimensions, with bandwidth hh in every direction, the bias is still order h2h^2 but the variance is R(K)p(x)/(nhd)R(K)p(\mathbf x)/(nh^d), so h∗∝n−1/(d+4)h^*\propto n^{-1/(d+4)} and MISE∗∝n−4/(d+4)\mathrm{MISE}^*\propto n^{-4/(d+4)}.

Minimax rates and the curse of dimensionality

DerivationWhy no estimator does better (Assouad, sketch)
  1. pω(x)=1+∑j=1mdωj ψj(x)p_\omega(\mathbf x)=1+\sum_{j=1}^{m^d}\omega_j\,\psi_j(\mathbf x)

    A hypercube of hypotheses. Cut [0,1]d[0,1]^d into mdm^d cubes of side 1/m1/m, and in cube jj place a smooth bump ψj(x)=c m−βψ(m(x−xj))\psi_j(\mathbf x)=c\,m^{-\beta}\psi\big(m(\mathbf x-\mathbf x_j)\big) with ∫ψ=0\int\psi=0. For each ω∈{0,1}md\omega\in\{0,1\}^{m^d}, perturb the uniform density; for small cc every pωp_\omega is a density in P(β,L)\mathcal P(\beta,L), because rescaling by mm multiplies the β\beta-th derivatives by mβm^\beta:

  2. ∥pω−pω′∥22=∥ψj∥22≍m−2β⋅m−d(ω,ω′ differ in coordinate j)\norm{p_\omega-p_{\omega'}}_2^2=\norm{\psi_j}_2^2\asymp m^{-2\beta}\cdot m^{-d}\qquad(\omega,\omega'\text{ differ in coordinate }j)

    Separation. Flipping one coordinate of ω\omega changes the density, in squared L2L_2 distance, by the energy of one bump:

  3. DKL(pω⊗n ∥ pω′⊗n)≍n m−2β−d=O(1)form≍n1/(2β+d)\KL\big(p_\omega^{\otimes n}\,\big\|\,p_{\omega'}^{\otimes n}\big)\asymp n\,m^{-2\beta-d}=O(1)\quad\text{for}\quad m\asymp n^{1/(2\beta+d)}

    Indistinguishability. For neighbors, the KL divergence between the distributions of nn samples is about n∥ψj∥22n\norm{\psi_j}_2^2. Choose m≍n1/(2β+d)m\asymp n^{1/(2\beta+d)} so this stays bounded: no test can reliably tell which way any single bump points.

  4. inf⁡p^max⁡ωE∥p^−pω∥22 ≳ md⋅m−2β−d=m−2β≍n−2β/(2β+d)\inf_{\hat p}\max_\omega\E\norm{\hat p-p_\omega}_2^2\ \gtrsim\ m^d\cdot m^{-2\beta-d}=m^{-2\beta}\asymp n^{-2\beta/(2\beta+d)}

    Assouad's lemma adds up the unavoidable errors over the mdm^d independent coordinates:

Dimension ddRate for β=2\beta=2nn for error 0.010.01 (constants ignored)
1n−0.80n^{-0.80}≈3×102\approx3\times10^2
2n−0.67n^{-0.67}10310^3
5n−0.44n^{-0.44}≈3×104\approx3\times10^4
10n−0.29n^{-0.29}10710^7
50n−0.07n^{-0.07}102710^{27}
Reaching error ε\varepsilon takes n≍ε−(2β+d)/(2β)n\asymp\varepsilon^{-(2\beta+d)/(2\beta)} samples: exponential in dd. This is the curse of dimensionality as a theorem, not an anecdote.
Predict before you look

Draw 500 points uniformly in the unit ball in R10\R^{10}. What is the median distance from the center to the nearest of them? (It equals (1−2−1/500)1/10(1-2^{-1/500})^{1/10}.)

Show the answer

0.52

The nearest point lies beyond radius rr with probability (1−r10)500(1-r^{10})^{500}; setting this to 12\tfrac12 gives r=(1−2−1/500)1/10≈0.52r=(1-2^{-1/500})^{1/10}\approx0.52 (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 kk-dimensional manifold, kernel and nearest-neighbor methods can adapt to kk instead of dd (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 kk-nearest-neighbor estimate (Loftsgaarden & Quesenberry, 1965) fixes the number of points instead of the window: p^(x)=k/(nVdrk(x)d)\hat p(\mathbf x)=k/(nV_dr_k(\mathbf x)^d), where rk(x)r_k(\mathbf x) is the distance to the kk-th nearest sample and VdV_d the volume of the unit ball. Its bandwidth adapts to the local density, and it is consistent when k→∞k\to\infty and k/n→0k/n\to0, but it is not itself a density: its tails decay like ∥x∥−d\norm{\mathbf x}^{-d}, 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 pp,

Ex∼p[log⁡p^(x)]=−H(p)−DKL(p ∥ p^),\E_{\mathbf x\sim p}\big[\log\hat p(\mathbf x)\big]=-H(p)-\KL(p\,\|\,\hat p),

so ranking models by average test log-likelihood ranks them by their KL divergence from the truth; the entropy H(p)H(p) is a common, unknown offset (Information Theory for AI). For images it is reported as bits per dimension, −log⁡2p^(x)/d-\log_2\hat p(\mathbf x)/d. 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 fθ:Rd→Rdf_\theta:\R^d\to\R^d that sends data to a simple base density pZp_Z, usually N(0,I)\mathcal N(\mathbf 0,I). The likelihood is exact, so training is plain maximum likelihood, and sampling inverts the map. Everything hinges on computing the Jacobian determinant cheaply.

DerivationChange of variables, and a coupling layer
  1. pX(x)=pZ(f(x)) ∣det⁡∂f∂x(x)∣p_X(\mathbf x)=p_Z\big(f(\mathbf x)\big)\,\Big|\det\frac{\partial f}{\partial\mathbf x}(\mathbf x)\Big|

    For z=f(x)\mathbf z=f(\mathbf x) with ff invertible, probability is conserved, Pr⁡(X∈A)=Pr⁡(Z∈f(A))\Pr(X\in A)=\Pr(Z\in f(A)), and the Jacobian measures how ff stretches volume:

  2. log⁡pX(x)=log⁡pZ(zL)+∑ℓ=1Llog⁡∣det⁡∂fℓ∂zℓ−1∣\log p_X(\mathbf x)=\log p_Z(\mathbf z_L)+\sum_{\ell=1}^L\log\Big|\det\frac{\partial f_\ell}{\partial\mathbf z_{\ell-1}}\Big|

    Compose simple layers, f=fL∘⋯∘f1f=f_L\circ\dots\circ f_1 with z0=x\mathbf z_0=\mathbf x and zℓ=fℓ(zℓ−1)\mathbf z_\ell=f_\ell(\mathbf z_{\ell-1}); log-determinants add:

  3. za=xa,zb=xb⊙es(xa)+t(xa)⟹log⁡∣det⁡∂z∂x∣=∑jsj(xa)\mathbf z_a=\mathbf x_a,\quad\mathbf z_b=\mathbf x_b\odot e^{s(\mathbf x_a)}+t(\mathbf x_a)\quad\Longrightarrow\quad\log\Big|\det\frac{\partial\mathbf z}{\partial\mathbf x}\Big|=\sum_js_j(\mathbf x_a)

    Affine coupling (RealNVP; Dinh, Sohl-Dickstein & Bengio, 2017): split x=(xa,xb)\mathbf x=(\mathbf x_a,\mathbf x_b), keep xa\mathbf x_a, and transform xb\mathbf x_b elementwise with scale and shift networks s,ts,t of xa\mathbf x_a. The Jacobian is block triangular, so its determinant is the product of the diagonal, whatever ss and tt are:

  4. max⁡θ 1n∑i=1nlog⁡pθ(xi)  ⟺  min⁡θ DKL(p^data ∥ pθ)\max_\theta\ \frac1n\sum_{i=1}^n\log p_\theta(\mathbf x_i)\iff\min_\theta\ \KL\big(\hat p_{\text{data}}\,\big\|\,p_\theta\big)

    The inverse is just as cheap, xb=(zb−t(za))⊙e−s(za)\mathbf x_b=(\mathbf z_b-t(\mathbf z_a))\odot e^{-s(\mathbf z_a)}, 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 pθ=p~θ/Zθp_\theta=\tilde p_\theta/Z_\theta, the score ∇xlog⁡pθ=∇xlog⁡p~θ\nabla_{\mathbf x}\log p_\theta=\nabla_{\mathbf x}\log\tilde p_\theta does not involve ZθZ_\theta. Score matching (Hyvärinen, 2005) fits a model score sθ\mathbf s_\theta to the data's score without knowing it: integrating by parts (assuming p sθ→0p\,\mathbf s_\theta\to0 at infinity),

12Ep∥sθ−∇log⁡p∥2=Ep[12∥sθ(x)∥2+tr⁡∇xsθ(x)]+const.\tfrac12\E_p\norm{\mathbf s_\theta-\nabla\log p}^2=\E_p\Big[\tfrac12\norm{\mathbf s_\theta(\mathbf x)}^2+\operatorname{tr}\nabla_{\mathbf x}\mathbf s_\theta(\mathbf x)\Big]+\text{const}.

Denoising score matching (Vincent, 2011) avoids the trace: for x~=x+σε\tilde{\mathbf x}=\mathbf x+\sigma\boldsymbol\varepsilon, minimizing E∥sθ(x~)+(x~−x)/σ2∥2\E\norm{\mathbf s_\theta(\tilde{\mathbf x})+(\tilde{\mathbf x}-\mathbf x)/\sigma^2}^2 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.

Check your understanding

An affine coupling layer maps (xa,xb)↦(xa, xb⊙es(xa)+t(xa))(\mathbf x_a,\mathbf x_b)\mapsto\big(\mathbf x_a,\ \mathbf x_b\odot e^{s(\mathbf x_a)}+t(\mathbf x_a)\big), where ss and tt are deep networks. What is log⁡∣det⁡J∣\log\abs{\det J}?

  1. 00, because the layer is invertible
  2. ∑jtj(xa)\sum_jt_j(\mathbf x_a)
  3. It requires an O(d3)\order{d^3} determinant of the networks' Jacobians
  4. ∑jsj(xa)\sum_js_j(\mathbf x_a)
Show the answer

D. ∑jsj(xa)\sum_js_j(\mathbf x_a)

The Jacobian is block lower-triangular: the identity on xa\mathbf x_a, and diag⁡(es(xa))\operatorname{diag}(e^{s(\mathbf x_a)}) on xb\mathbf x_b. The off-diagonal block, which contains the networks' derivatives, does not enter the determinant, so it costs O(d)\order{d}.

Key takeaways

  • Kernel density estimation has bias h22μ2(K)p′′\tfrac{h^2}2\mu_2(K)p'' and variance R(K)p/(nh)R(K)p/(nh); the optimal bandwidth scales as n−1/5n^{-1/5} and the MISE as n−4/5n^{-4/5}, or n−1/(d+4)n^{-1/(d+4)} and n−4/(d+4)n^{-4/(d+4)} in dd dimensions. The bandwidth matters far more than the kernel.
  • Choose hh by a normal-reference rule, least-squares or likelihood cross-validation (always leave-one-out), or plug-in estimates of R(p′′)R(p'').
  • The minimax rate over β\beta-smooth densities is n−2β/(2β+d)n^{-2\beta/(2\beta+d)} (Assouad's hypercube of bumps proves the lower bound), so the sample size for fixed accuracy grows exponentially with dd unless the data have more structure.
  • Held-out log-likelihood ranks models by DKL(p∥p^)\KL(p\|\hat p), 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.

Question 1

For a one-dimensional kernel density estimate of a twice-differentiable density, how do the optimal bandwidth and the optimal MISE scale with nn?

  1. h∗∝n−1/2h^*\propto n^{-1/2} and MISE∝n−1\mathrm{MISE}\propto n^{-1}
  2. h∗∝n−1/5h^*\propto n^{-1/5} and MISE∝n−4/5\mathrm{MISE}\propto n^{-4/5}
  3. h∗∝n−1/3h^*\propto n^{-1/3} and MISE∝n−2/3\mathrm{MISE}\propto n^{-2/3}
  4. h∗h^* constant and MISE∝n−1\mathrm{MISE}\propto n^{-1}
Show the answer

B. h∗∝n−1/5h^*\propto n^{-1/5} and MISE∝n−4/5\mathrm{MISE}\propto n^{-4/5}

Balancing squared bias ∝h4\propto h^4 against variance ∝1/(nh)\propto1/(nh) gives h5∝1/nh^5\propto1/n, and then both terms scale like n−4/5n^{-4/5}. Nonparametric estimation pays for its flexibility with a rate slower than the parametric 1/n1/n.

Question 2

For densities with smoothness β=2\beta=2 in d=20d=20 dimensions, what is the best possible worst-case rate of the MISE?

  1. n−4/5n^{-4/5}, as in one dimension
  2. n−1n^{-1}
  3. n−1/6n^{-1/6}
  4. e−ne^{-n}
Show the answer

C. n−1/6n^{-1/6}

n−2β/(2β+d)=n−4/24=n−1/6n^{-2\beta/(2\beta+d)}=n^{-4/24}=n^{-1/6}, and no estimator does better over the whole class (Assouad's hypercube of bumps). Halving the error takes 26=642^6=64 times more data.

Question 3

Why can't you choose the bandwidth by maximizing the in-sample log-likelihood ∑ilog⁡p^h(Xi)\sum_i\log\hat p_h(X_i)?

  1. Because it is maximized at h→∞h\to\infty
  2. Because the likelihood does not depend on hh
  3. Because log-likelihoods cannot be compared between bandwidths
  4. Because each point's own kernel spike makes it grow without bound as h→0h\to0; leaving each point out fixes this
Show the answer

D. Because each point's own kernel spike makes it grow without bound as h→0h\to0; leaving each point out fixes this

p^h(Xi)\hat p_h(X_i) includes the term K(0)/(nh)K(0)/(nh), which diverges as h→0h\to0: the in-sample criterion rewards interpolation, the density version of overfitting. Likelihood cross-validation uses p^h,−i(Xi)\hat p_{h,-i}(X_i), which excludes point ii's own kernel.

Question 4

Why does score matching not need the normalizing constant of an unnormalized model p~θ(x)/Zθ\tilde p_\theta(\mathbf x)/Z_\theta?

  1. Because ∇xlog⁡(p~θ/Zθ)=∇xlog⁡p~θ\nabla_{\mathbf x}\log(\tilde p_\theta/Z_\theta)=\nabla_{\mathbf x}\log\tilde p_\theta: the constant disappears under the gradient in x\mathbf x
  2. Because it estimates ZθZ_\theta by Monte Carlo along the way
  3. Because it only applies to Gaussian models, where ZθZ_\theta is known
  4. Because it maximizes the likelihood, in which ZθZ_\theta cancels
Show the answer

A. Because ∇xlog⁡(p~θ/Zθ)=∇xlog⁡p~θ\nabla_{\mathbf x}\log(\tilde p_\theta/Z_\theta)=\nabla_{\mathbf x}\log\tilde p_\theta: the constant disappears under the gradient in x\mathbf x

log⁡Zθ\log Z_\theta depends on θ\theta but not on x\mathbf x, 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).