Im trying to follow a minimization of mutual information using Lagrange multipliers in a highly cited paper called The Information Bottleneck Method (1999), page 4:

$$R(D) = \min_{p(\tilde{x}|x): E[d(x,\tilde{x})]\leq D} I(X,\tilde{X})$$

Where $X$ is a given random variable and $\tilde{X}$ is a compressed representation of it. The constraint is just an expectation of a distortion function $d(\cdot,\cdot)$, that gives the difference between two realizations of the r.v.s. The mutual information is defined as $I(X;\tilde{X}) =\sum_{x\in X}\sum_{\tilde{x}\in\tilde{X}} p(x,\tilde{x})\log\frac{p(\tilde{x}|x)}{p(\tilde{x})}$ and $E[d(x,\tilde{x})] = \sum_x\sum_\tilde{x} p(x,\tilde{x})d(x,\tilde{x})$

The functional to minimize is written as: $$\mathcal{F}[p(\tilde{x}|x)]=I(X;\tilde{X}) +\beta E[d(x,\tilde{x})]$$ Where $\beta$ is a Lagrange multiplier.

The paper continues with the derivative $\frac{\partial \mathcal{F}}{\partial p(\tilde{x}|x)}=0$ and thats the step I don't understand how to follow. It says: $$\frac{\partial \mathcal{F}}{\partial p(\tilde{x}|x)}=p(x)\left[\log\frac{p(\tilde{x}|x)}{p(\tilde{x})}+1-\frac{1}{p(\tilde{x})}\sum_{x^\prime}p(x^\prime)p(\tilde{x}|x^\prime) + \beta d(x,\tilde{x})+\frac{\lambda(x)}{p(x)}\right]$$

It says "$\lambda(x)$ are the normalization Lagrange multipliers for each $x$".

Questions: what are a normalization Lagrange multiplier? I dont know where that sum comes from, it only says after "since the marginal distribution satisfies $p(\tilde{x})=\sum_{x^\prime}p(x^\prime)p(\tilde{x}|x^\prime)$" (which is a condition that appeared before, but I dont know why is doing here).

PS: I tried to follow the process in this presentation, slide 19-20, but again, I dont understand how to derive the expression...

Thanks a lot beforehand.

  • $\begingroup$ I interpret it as the marginal distribution of your required conditional distribution $p(\tilde{x}|x)$ must be induced by the original distribution $p(x)$. This may sound like a stupid redundant constraint, but in fact there ARE possible solutions whose marginals are NOT directly induced by $p(x)$ in this manner. This would be undesirable, and may possibly even make the solution set non-unique. $\endgroup$ Jan 21, 2016 at 7:38

1 Answer 1


I found the answer in a PhD thesis which is from Prof Tishby's student. lamba(x) is for normalization constraint ∑x p(x̃|x)=1 for each x. You can check the thesis for more detail: http://www.cs.huji.ac.il/labs/learning/Theses/Slonim_PhD.pdf

  • $\begingroup$ Welcome to MSE. This should be a comment, not a answer. $\endgroup$ Mar 13, 2018 at 10:02
  • $\begingroup$ Moreover, for the third term in ∂f/∂p(x̃|x), it's complicated to derive it. However, if you assume that x includes x1, x2 and x̃ includes x̃1 and x̃2, once you write down all the elements in F, you will find the third term is correct! $\endgroup$
    – Zhang Lin
    Mar 13, 2018 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.