4
$\begingroup$

I am looking at the following problem: $$ \min_q \underbrace{KL \left[ q(x) ~||~ p(x) \right]}_{=: A} + \underbrace{\mathbb{E}_{x \sim q} \left [ f(x) \right ]}_{=: B}. $$ For $A$, the solution is $q(x) = p(x)$. For $B$, the solution is a point mass/dirac/delta distribution putting all its mass at $arg,\min f(x)$. Further I know that $A$ should be strictly convex (accd to a comment in this question .)

My questions are the following:

Is there any hope of finding the minimizer in closed form, making use of the two respective solutions? Something like "the minimizer lies on a line between the two respective solutions." ?

$\endgroup$

2 Answers 2

6
$\begingroup$

There is also a way to derive the answer without calculus of variations. First, rewrite \begin{align} KL(q(X) \Vert p(X)) + \mathbb{E}_q[f(X)] &= \sum_x q(x) \ln \frac{q(x)}{p(x)} + \sum_x q(x) f(x) \\ & = \sum_x q(x) \ln \frac{q(x)}{p(x)e^{-f(x)}} \tag{1} \end{align}

Now define the probability distribution $w(x) := \frac{1}{Z} p(x)e^{-f(x)}$, where $Z=\sum_x p(x)e^{-f(x)}$ is the normalization constant. We can then rewrite $(1)$ as \begin{align} \sum_x q(x) \ln \frac{q(x)}{w(x)Z} = KL(q(X)\Vert w(X))-\ln Z\tag{2} \end{align} Note that $\ln Z$ is a constant that doesn't depend on $q$. Thus, Eq. $(2)$ is minimized by taking $q(x)=w(x)$, at which point it reaches its minimum value of $-\ln Z$.

$\endgroup$
5
$\begingroup$

This is a case of a variational problem with a subsidiary condition (constraint). The objective is to minimize the functional $$ J[q]\triangleq \int_x F(q) dx, $$

where $F(q) \triangleq q(x)\left(\log \frac{q(x)}{p(x)} + f(x)\right)$, under the condition $$ \tag{1} \int_x q(x)dx =1. $$

From calculus of variations, a necessary condition for the function $q(x)$ to be an extremal of $J[q]$ is

$$ \tag{2} \frac{\partial}{\partial q} F + \lambda =0, $$ for some constant $\lambda$. Solving the differential equation of (2) with respect to $q(x)$ gives

$$ q(x) = p(x) e^{-f(x) - \lambda -1}. $$

Plugging this into (1), shows that $\lambda= \log \mathbb{E}_{x\sim p}\left(e^{-f(x)}\right) - 1$, finally resulting in

$$ q(x) = \frac{1}{\mathbb{E}_{x\sim p}\left(e^{-f(x)}\right)} p(x) e^{-f(x)}. $$

edit1: corrected link.

edit 2: fixed algebraic error, identified by @Artemy.

$\endgroup$
5
  • $\begingroup$ Thanks! Can you recommend a resource to get into calculus of variations? $\endgroup$
    – bayer
    Aug 10, 2019 at 16:56
  • $\begingroup$ @bayer I am only familiar with this book, which is very good. But there is a huge literature out there, maybe an expert in the topic (I am not!) could suggest something better. $\endgroup$
    – Stelios
    Aug 10, 2019 at 17:03
  • $\begingroup$ Would you please explain the difference between equation (2) and the Euler-Langrange equation? $\endgroup$
    – robit
    Aug 10, 2019 at 18:17
  • 1
    $\begingroup$ @robit Check this reference (Theorem 1, page 43) $\endgroup$
    – Stelios
    Aug 10, 2019 at 18:41
  • $\begingroup$ I have a follow up question–I have been trying to find out if your answer also holds for the multivariate case where $\mathbf{x} \in \mathbb{R}^n$. The resource you pointed to does not go into that. Do you have an idea or a direction to look for this? $\endgroup$
    – bayer
    Jan 17, 2020 at 7:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .