# Density estimation as an optimization problem

Density estimation is the estimation of a probability density function from observed data. Can some of the common approaches to density estimation, such as kernel density estimation, be formulated as infinite-dimensional optimization problems? That is, can we formulate them as the problem of optimizing some functional of the resulting PDF, subject to some constraints?

In particular, I'm interested in the result of the following procedure: Suppose we have some samples $$x_i \in \mathbb{R}^n$$ from some unknown PDF with support in $$\Omega \subseteq \mathbb{R}^n$$. What PDF $$f$$ with support in $$\Omega$$ solves the following optimization problem?

Maximize the likelihood of the samples, i.e.

$$L(f) = \prod_i f(x_i)$$

subject to the constraint that the differential entropy of $$f$$

$$H(f) = -\int_\Omega f(x) \log f(x) \;\mathrm{d}x$$

is equal to some number $$h$$. If I understand correctly, this gets rid of the trivial maximum-likelihood solution of putting deltas at each sample, since deltas have differential entropies of $$-\infty$$. One might further impose a condition such as smoothness.

• Something vaguely related that might be of interest: given some complicated posterior distribution, this paper and its predecessors view Langevin MCMC as a deterministic optimization in the space of probability distributions. Oct 15 '19 at 20:07
• @user76284 where have you seen this optimization problem before? Sep 6 '20 at 20:36
• @develarist Maximum likelihood under constrained entropy? Just something I came up with that I thought might be related to density estimation. Sep 6 '20 at 20:42

(I'll answer the second question, about the results of your maximum likelihood with fixed differential entropy procedure; I don't know the answer to the first, about whether KDE can be phrased as optimizing some objective functional.)

Without additional constraints such as bounds on the derivatives, the problem is ill-posed: you can achieve any finite likelihood with fixed differential entropy.

Let $$f_0$$ be any density over $$\Omega$$ with differential entropy $$h$$. If $$\log \lvert \Omega \rvert < h$$, this is impossible and the problem is unsatisfiable; otherwise, take it to be e.g. uniform over some subset of $$\Omega$$ with appropriate volume. Then define $$f(x) = \begin{cases} q & \text{if } x = x_i \text{ for some } i \\ f_0(x) & \text{otherwise} \end{cases}$$ for any finite $$q$$. This has likelihood $$q^m$$, where $$m$$ is the number of points $$x_i$$; since we've only modified $$f_0$$ on a set of measure zero, $$f$$ still has integral 1 and differential entropy $$h$$. So you can make the likelihood as high as you want.

Of course, changing the density function on a set of measure zero is in some ways "not fair"; the distribution itself won't be altered, for example. But we can achieve essentially the same thing with continuous, or even $$C^\infty$$ density functions; just make a very narrow bump at each $$x_i$$. The next section shows formally that we can do that, but it's just this intuition in equations.

Let $$f_0$$ be a continuous (or $$C^\infty$$) density of differential entropy $$Q$$ whose support does not include any of the $$x_i$$ (or a ball around them). This makes the calculations much easier, as we don't have to worry about interactions between $$f_0$$ and the bumps we'll put at each $$x_i$$, but is not fundamental to the approach.

Let $$\ell < \min_{i,j} \lvert x_i - x_j \rvert$$ and also smaller than the distance from any $$x_i$$ to the support of $$f_0$$. Define $$f_i(x) = \frac1\ell g\left( \frac{x - x_i}{\ell} \right),$$ where $$g$$ is the pdf of a mean-zero distribution with continuous (or $$C^\infty$$) density and support on a subset of the unit ball. Many kernel functions would work, for example. Let $$g(0) = g_0$$ so that $$f_i(x_i) = \frac1\ell g_0$$, and let $$H[g] = \int g(x) \log g(x) \,\mathrm d x = \eta$$ so that $$H[f_i] = \eta - \log \ell$$.

We'll take a mixture between $$f_0$$ and the $$f_i$$, for some $$\alpha \in (0, 1)$$ to be determined later: $$f(x) = (1-\alpha) f_0(x) + \frac{\alpha}{m} \sum_{i=1}^m f_i(x) .$$ Then we have $$\int f(x) \,\mathrm d x = (1 - \alpha) \int f_0(x) \,\mathrm d x + \frac{\alpha}{m} \sum_{i=1}^m \int f_i(x) \,\mathrm d x = 1 ,$$ and $$L(f) = \left( \frac{\alpha}{m \ell} g_0 \right)^m = \left( \frac{g_0}{m} \right)^m \left( \frac{\alpha}{\ell} \right)^m .$$ The first term is constant; we want to choose $$\alpha$$, $$\ell$$ so as to maximize $$\alpha / \ell$$ and hence $$L(f)$$.

Our constraint on $$\alpha$$ and $$\ell$$ is determined by \begin{align} \int f(x) \log f(x) \,\mathrm{d}x &= \int (1-\alpha) f_0(x) \log\left( (1-\alpha) f_0(x) \right) \,\mathrm{d}x + \sum_{i=1}^m \int \frac{\alpha}{m} f_i(x) \log\left( \frac{\alpha}{m} f_i(x) \right) \mathrm d x \\&= (1-\alpha) H[f_0] + (1-\alpha) \log(1 - \alpha) + \frac\alpha m \sum_{i=1}^m H[f_i] + \frac\alpha m \sum_{i=1}^m \log \frac\alpha m \\&= (1-\alpha) Q + \alpha \eta - \alpha \log \ell + (1-\alpha) \log(1 - \alpha) + \alpha \log \alpha - \alpha \log m .\end{align} Setting this equal to $$h$$, dividing both sides by $$\alpha$$, and moving some terms, we get $$\frac{Q - h}{\alpha} + \frac{1-\alpha}{\alpha} \log(1 - \alpha) + \log \frac\alpha\ell = Q - \eta + \log m .$$

We could directly solve this for $$\ell$$, but the expression is little messy and we don't care about the particular value of $$\ell$$. It's sufficient to note that as we drive $$\ell \to 0$$, we'll have $$\alpha \to 0$$ as well; we care about the relative rate. We can use $$\log(1-\alpha) = - \alpha - \mathcal O(\alpha^2)$$ so that $$\frac{1-\alpha}{\alpha} \log(1-\alpha) = - 1 + \alpha - \mathcal O(\alpha) = -1 \pm \mathcal O(\alpha) .$$ Thus $$\frac{Q - h}{\alpha} \pm \mathcal O(\alpha) + \log \frac\alpha\ell = 1 + Q + \log m - \eta$$ and so $$\frac\alpha\ell = \underbrace{\exp\left( 1 + Q + \log m - \eta \right)}_\text{constant} \exp\left( \frac{h - Q}{\alpha} \pm \mathcal{O}(\alpha) \right) .$$ As long as $$Q < h$$, we have $$\frac\alpha\ell \to \infty$$ as $$\alpha \to 0$$, so $$L(h) \to \infty$$ as $$\alpha \to 0$$.

In the limit $$\ell \to 0$$, this converges to $$f_0$$ plus delta functions at each of the $$x_i$$ (as before). But for any finite $$\ell$$, we know we can balance the entropy of each nearly-a-delta-function spike with the entropy of $$f_0$$ appropriately so that the total is $$h$$. Thus, as before, for any finite target likelihood we can find a distribution with that likelihood and differential entropy $$h$$.

A constraint such as a Lipschitz density would correspond in this setting to a constraint on $$\ell$$, preventing us from driving the density to infinity.

It might be possible to derive the maximum-likelihood estimator among $$L$$-Lipschitz densities with differential entropy $$h$$. This might look something like:

• Put peaks as high as possible at each $$x_i$$.
• Decrease away from each peak uniformly with slope $$L$$.
• Stop decreasing at some base level uniform over $$\Omega$$.

This likely would not actually be the MLE in this family, but you might be able to get a linear program or something that gives a solution kind of like this.

• Thank you for your comprehensive answer! I wonder what other constraints on this optimization problem might yield interesting behaviour. Oct 18 '19 at 1:58
• Do you think constraining the total variation of the density would yield something similar? Oct 20 '19 at 17:59
• @user76284 That might work; not sure. Oct 21 '19 at 0:23