3
$\begingroup$

Consider a PDF $\pi(x)$ for $x\in[0,1]$, and the following functional $$ F(\pi) = \mathbb{E}_\pi |x-y| $$ It is minimized by any point mass, so to avoid such degeneracy I'd like to lower-bound the entropy of $\pi$: $$ \mathbb{E}_\pi \left[ \ln \pi \right] \geq C $$

Is there an analytical solution to $\min_\pi F(\pi)$ subject to such an entropy constraint? In case of multiple solutions, I'd like the one(s) closest to some given $\pi_0$ (in the $L_p$ sense for a convenient $p$).

In the absence of analytical solutions, numerical methods would be useful. The entropy constraint can be addressed by a Lagrange multiplier, but perhaps there is some elegant way to deal with its non-linearity.

Now, the functional I'd really like to minimize over $L_1$ is $$ F_\alpha(\pi) = \mathbb{E_\pi} \left[ |x-y| \cdot (\pi^\alpha (x) + \pi(y)^\alpha) \right] $$ for $1 \leq \alpha \leq 2$. Perhaps, start with $\alpha=1$.

The entropy constraint isn't critical, but I will start with some $\pi_{init}$ and would like to prevent unnecessary entropy loss if possible.

$\endgroup$
8
  • $\begingroup$ It is worth noting that for $\alpha>1$ (at least), you have a positive unconstrained infimum of $F(\pi)$. Are you sure that you really care about that entropy condition in this case? It looks like just an extra headache. $\endgroup$
    – fedja
    Jun 10, 2018 at 23:02
  • $\begingroup$ Actually, there is a non-zero lower bound even for $\alpha=1$. $\endgroup$
    – fedja
    Jun 11, 2018 at 0:20
  • $\begingroup$ For $\alpha=1$ a rigorous lower bound is about $0.245$ and a numeric example gives about $0.276$. If you don't care too much about the $0.03$ discrepancy, I'll post the argument. If you need an exact minimum analytically, I'd rather opt out :-) $\endgroup$
    – fedja
    Jun 11, 2018 at 2:21
  • $\begingroup$ Sorry, double that (you have a sum in parentheses and I took one half of it when computing). $\endgroup$
    – fedja
    Jun 11, 2018 at 2:33
  • $\begingroup$ If $\pi$ is a point mass, then $F_\alpha(\pi)=0$ regardless of $\alpha$, since $\mathbb{E}_\pi$ integrates over $\pi (x)dx$. OTOH, small numerical differences aren't very important. $\endgroup$ Jun 11, 2018 at 4:22

1 Answer 1

2
$\begingroup$

Here is the lower bound of $0.49$ for all $\alpha\ge 1$. Note that $\min_\pi F(\pi)$ is a non-decreasing function of $\alpha$, so it is enough to consider $\alpha=1$. Also, the truth is about $0.55$ for $\alpha=1$ and $0.62$ for $\alpha=2$, so, if you care about entropy, the uniform distribution that gives $\frac 23$ for all $\alpha$ is not too far from the truth.

If you do it numerically and try just to consider functions constant on short intervals, then do not forget the self-action on each interval in the sum to be optimized. It looks small compared to the whole for spread distributions but without it everything will quickly converge to a singleton. I made this error when trying to optimize numerically and it took me some time to realize and fix it.

Now the bound. I'll just consider $G(\pi)=\frac{F(\pi)}{2}=\iint \pi(x)^2\pi(y)|x-y|\,dx\,dy$. Note that this expression is invariant with respect to the scaling $\pi\mapsto c\pi(c\cdot)$, so the support restriction is not important. What matters is only that $\int\pi=1$.

Write the Lebesgue decomposition $\pi(x)=\int_{t>0}\chi_{E_t}(x)\,dt$ where $E_t$ is a decreasing nested family of measurable sets. Then $$ G(\pi)=\iint_{s,t>0}2sQ(s,t)\,ds\,dt $$ where $$ Q(s,t)=\iint_{E_s\times E_t}|x-y|\,dx\,dy\,. $$ It is not hard to see that if $0<\ell<L$ are lengths of $E_s,E_t$ (not necessarily in this order), then the least value of $Q$ is given by 2 concentric intervals, in which case it is $$ \frac{\ell L^2}{4}+\frac{\ell^3}{12}\ge \frac{\ell L(\ell+L)}{6}\,. $$ The RHS is just made up to get a symmetric expression in $s,t$, which leads to a nice optimization problem but costs about $12\%$ in the precision of the bound. Also it is clear from here that the only real competitors are symmetric unimodal distributions.

Now, putting $f(t)=|E_t|$, we see that we need to estimate $$ \frac 16\iint 2s f(s)f(t)[f(s)+f(t)]\,ds\,dt=\frac 13\iint (s+t) f(s)^2f(t)\,ds\,dt\\ =\frac 13\int (s+a)f(s)^2\,ds $$ from below under the conditions $\int f(s)\,ds=1,\int sf(s)\,ds=a>0$.

This is an almost pure Hilbert space question except for the positivity constraint. We'll just define $g_b(s)=\frac {(1-bs)_+}{a+s}$ for $b>0$ and use Cauchy-Schwarz: $$ \left[\int (s+a)f(s)^2\,ds\right]\left[\int (s+a)g_b(s)^2\,ds\right]\ge \left[\int (s+a)f(s)g_b(s)\,ds\right]^2 $$ The integral on the right is $$ \int f(s)(1-bs)_+\ge \int f(s)(1-bs)=1-ab\,, $$ so we get the bound $$ \int (s+a)f(s)^2\,ds\ge (1-ab)^2\left[\int (s+a)g_b(s)^2\,ds\right]^{-1} $$ as long as $ab<1$. Choosing $ab=\frac 14$, we get the right hand side independent of $a$ and equal approximately $0.735$ (the best choice is the solution of some transcendental equation, but we have lost $12\%$ already, so who cares now) giving $G(\pi)\ge 0.245$, as promised.

Simple functions that give values of $F(\pi)$ close to the true minimum (on $[-0.5,0.5]$ instead of $[0,1]$) are (properly normalized) $(1-2x)^2$ and $1-x$ for $\alpha=1$ and $\alpha=2$ respectively. Those are not exact optimizers but you may find it hard to beat them when doing numeric optimization.

$\endgroup$
5
  • $\begingroup$ This is very useful in several ways. Can you also interpolate minimizers for $1< \alpha < 2$? $\endgroup$ Jun 13, 2018 at 8:15
  • $\begingroup$ @IgorMarkov I improved my code a bit (though it is still a version of the naive gradient descent: it just works with piecewise linear even functions on 16 to 64 equally spaced nodes in $[0,\frac 12]$). Of course, I can share it, if you want :-). However, the main message is that all minimizers (I hope, they are minimizers) it outputs are very close to functions of the form $\frac{1-bx^2}{1+cx^2}$ with some $b=b(p)\in\mathbb R, c=c(p)>0$. The best fit has slightly negative $b$ around $p=3$ and the dependence of $b,c$ on $p$ is a bit mysterious. $\endgroup$
    – fedja
    Jun 17, 2018 at 2:54
  • $\begingroup$ That's interesting (by $p$, do you mean $\alpha$?). In the meantime, I think I have "elementary" proofs for some of the claims you mentioned. 1. Minimal densities are symmetric. Take any nonsymmetric density and symmetrize it. That decreases the $F()$ value (strict convexity of $f(t)=t^a$ for $a>1$). 2. Minimal densities decrease away from their maximum in the middle (say, $x=0$). Assume $0<x<y$ and $\pi(x)<\pi(y)$, then moving "a small amount of density" from $y$ to $x$ decreases $F()$ if $\pi$ was symmetric. This is seen by tracking "contributions" to $F$ by each $(y,z)$ and $(y,-z)$. $\endgroup$ Jun 18, 2018 at 1:43
  • $\begingroup$ @IgorMarkov 1 Be careful! $t\mapsto t^\alpha$ is convex but $t,s\mapsto t^{1+\alpha}s$ is not, so I don't quite understand how you can use the convexity of $t^\alpha$ directly. Perhaps I'm just dumb ;-) 2 My $p$ is your $\alpha+1$. 3. You can, probably, go all the way to the Euler-Lagrange equation, but it is not solvable explicitly anyway. Where exactly would you like to stop in lieu of an "explicit solution"? $\endgroup$
    – fedja
    Jun 18, 2018 at 2:49
  • $\begingroup$ Fair enough, I am a little sloppy, but still hope for a simpler line of reasoning to describe minimizers, justify apt numerical methods, and maybe, just maybe, prove tighter bounds. $\endgroup$ Jun 18, 2018 at 4:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.