0
$\begingroup$

I am reading a paper on the Information Bottleneck Method. In this paper authors give a short review of rate distortion theory. In rate distortion theory we are interested in the rate distortion function $R(D)$, which is defined as $$R(D) = \min_{p(\tilde x | x)} I(X, \tilde{X}) \qquad\text{such that}\quad \mathbb{E}_{p(x,\tilde x)}[d(x, \tilde x)] \leq D$$ where:

  • $X$ is our source random variable. It is discrete and finite.
  • $\tilde X$ is quantization of $X$ (this quantization is stochastic, i.e. we have a stochastic mapping $p(\tilde x | x)$)
  • $d(x, \tilde x)$ is our distortion function, which measures the quality of quantization (in practice, it can be something like MSE error or Hamming distance)
  • $\beta$ is the Lagrange multiplier

Authors say, that we do it by minimizing a Lagrangian:

$$\mathcal{F}(p(\tilde x | x)) = I(X, \tilde{X}) + \beta \mathbb{E}_{p(x,\tilde x)}[d(x, \tilde x)]$$

There are two moments that I do not understand:

  • Why second term in Lagrangian does not contain $D$? Wikipedia says, that inequality constraints "$g(x) \leq C$" should give second term of the kind "$\beta(g(x) - C)$", not "$\beta g(x)$". We somehow imply that $C = 0$ here?

  • Why do authors say, that we find a whole function $R(D)$? It looks like we are finding just a single value of this function, evaluated at the point $D$, not the whole form of it.

$\endgroup$
1
$\begingroup$

This is quite common in this kind of max/minimization problems.

In general, supose you want to find an extremum of $f(x)$ subject to $g(x)\le D$. The method of Lagrange multiplier does not adapt to this constraint. But, if if you have reasons to assume (we often have) that the constraint $g(x)\le D$ is "relevant / pessimistic", that is, that we wish $D$ to be bigger to get better extrema of $f(x)$, this implies that the extremum of $f(x)$ subject to $g(x)\le D$ will occur in the limit of the region, i.e., where $g(x)=D$ or $g(x)-D=0$. Then, we are justified in replacing the inequality by an equality.

Then, Lagrange multiplier tells us to find the extremum of the Lagrangian

$$J_1(x) = f(x) + \beta (g(x)-D) \tag1$$ together with $g(x)-D=0$. But, because $D$ is constant, this is equivalent to find the extremum of the alternative Lagrangian

$$ J_2(x) =f(x) + \beta' g(x) \tag2$$

But to find the extremum of $(2)$ is not the same as assuming $D=0$, because the additional equation $g(x)-D=0$ remains as is. Different values of $D$ will give different multipliers ($\beta \ne \beta'$) and hence different extrema.

Namely, if the extrema corresponds to a critical point, both $(1)$ and $(2)$ will lead to the same system of equations:

\begin{cases} f'(x)+ \beta g'(x)&=0\\ g(x) -D &= 0 \tag3 \end{cases}

The solution, of course, depends on $D$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! That makes things much more clear. So just to be sure: the solution to this optimization procedure does not give us the whole $R(D)$ function, but just its evaluation at a particular choice of $D$, right? $\endgroup$ – Wunsch Punsch Feb 20 '19 at 20:57
  • $\begingroup$ The solution of $(3)$ gives an extremum of $f$ (let's call it $f_0$) that depends on the value of $D$, hence it's a function of it: $f_0(D)$. To get "the whole $R(D)$ function" and to get "the evaluation of $R$ a each value of $D$" are the same thing to me. $\endgroup$ – leonbloy Feb 20 '19 at 21:11
  • $\begingroup$ Thanks! Btw, in equation $(2)$ do we assume that $\beta'$ is fixed (i.e. $\beta' = 3$) before starting the optimization procedure? Because otherwise, if our $J_2(x)$ depends on $\beta'$ and we optimize for it too, then it is the same thing as assuming $D = 0$, isn't it? $\endgroup$ – Wunsch Punsch Feb 21 '19 at 8:05
  • $\begingroup$ No. $\beta$ is indeterminated. You should regard $(3)$ as a system of two equations with two unknowns: $x$ and $\beta$. $\endgroup$ – leonbloy Feb 21 '19 at 15:18
  • $\begingroup$ BTW, my other comment above is wrong , it should read "The solution of (3) gives the value of $x$ which attain the extremum (let's call it $x_0$); that depends on the value of $D$, hence it's a function of it: $x_0(D)$. $\endgroup$ – leonbloy Feb 21 '19 at 15:19

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.