21
$\begingroup$

If $f$ is a convex function then Jensen's inequality states that $f(\textbf{E}[x]) \le \textbf{E}[f(x)]$, and mutatis mutandis when $f$ is concave. Clearly in the worst case you cannot upper bound $\textbf{E}[f(x)]$ in terms of $f(\textbf{E}[x])$ for a convex $f$, but is there a bound that goes in this direction if $f$ is convex but "not too convex"? Is there some standard bound that gives conditions on a convex function $f$ (and possibly the distribution as well, if necessary) that would allow you to conclude that $\textbf{E}[f(x)] \le \varphi(f)f(\textbf{E}[x])$, where $\varphi(f)$ is some function of the curvature/degree of convexity of $f$? Something akin to a Lipschitz condition, perhaps?

$\endgroup$
  • $\begingroup$ Voting to close as off-topic. math.stackexchange.com maybe? $\endgroup$ – Aryabhata Aug 27 '10 at 19:00
  • 7
    $\begingroup$ I think that this question should stay open; this is the sort of inequality that many working theorists would find useful on a regular basis. $\endgroup$ – Aaron Roth Aug 27 '10 at 19:12
  • 10
    $\begingroup$ I know that this is closer to pure math than most of the questions posted so far, but I would argue that this is on-topic since this kind of thing comes up frequently in the analysis of randomized algorithms (which is the application I have in mind). I think that math that is heavily used in computer science should be considered fair game for questions. $\endgroup$ – Ian Aug 27 '10 at 19:13
  • 6
    $\begingroup$ vote to keep open. definitely on topic $\endgroup$ – Suresh Venkat Aug 27 '10 at 19:32
  • 1
    $\begingroup$ I also vote to keep open. $\endgroup$ – Jeffε Aug 29 '10 at 11:05
21
$\begingroup$

EDIT: original version missed an absolute value. sorry!!

Hi Ian. I will briefly outline two sample inequalities, one using a Lipschitz bound, the other using a bound on the second derivative, and then discuss some difficulties in this problem. Although I'm being redundant, since an approach using one derivative explains what happens with more derivatives (via Taylor), it turns out that the second derivative version is quite nice.

First, with a Lipschitz bound: simply re-work the standard Jensen inequality. The same trick applies: compute the Taylor expansion at the expected value.

Specifically, Let $X$ have corresponding measure $\mu$, and set $m := \textrm E(x)$. If $f$ has Lipschitz constant $L$, then by Taylor's theorem

$$ f(x) = f(m) + f'(z)(x-m) \leq f(m) + L|x-m|, $$

where $z \in [m, x]$ (note that $x\leq m$ and $x> m$ are possible). Using this and re-working the Jensen proof (I am paranoid and checked that the standard one is indeed on wikipedia),

\begin{align} \operatorname{E}(f(X)) & = \int f(x) \, d\mu(x) \leq f(m) \int d\mu(x) + L\int |x-m| \, d\mu(x) \\[6pt] & = f(\operatorname{E}(X)) + L \operatorname{E} (|X-\operatorname{E}(X)|). \end{align}

Now, suppose $|f''(x)| \leq \lambda$. In this case,

\begin{align} f(x) & = f(m) + f'(m)(x-m) + f''(z) \frac{(x-m)^2} 2 \\[6pt] & \leq f(m) + f'(m)(x-m) + \lambda \frac{(x-m)^2} 2, \end{align}

and so

\begin{align} \operatorname{E}(f(X)) & \leq f(m) + f'(m)(\operatorname{E}(X) - m) + \frac {\lambda \operatorname{E}((X-m)^2)}{2} \\[6pt] & = f(\operatorname{E}(X)) + \frac {\lambda \operatorname{Var}(X)}2. \end{align}

I'd like to briefly mention a few things. Sorry if they are obvious.

One is that, you can't merely say "wlog $\operatorname{E}(X) = 0$" by shifting the distribution, because you are changing the relationship between $f$ and $\mu$.

Next is that the bound must depend on the distribution in some way. To see this, imagine that $X \sim \textrm{Gaussian}(0, \sigma^2)$ and $f(x) = x^2$. Whatever the value of $\sigma$, you still get $f(\operatorname{E}(X)) = f(0) = 0$. On the other hand, $\operatorname{E}(f(X)) = \operatorname{E}(X^2) = \sigma^2$. Thus, by changing $\sigma$, you can make the gap between the two quantities arbitrary! Intuitively, more mass is pushed away from the mean, and thus, for any strictly convex function, $\operatorname{E} (f(X))$ will increase.

Lastly, I don't see how to get a multiplicative bound like you suggest. Everything I have used in this post is standard: Taylor's theorem and derivative bounds are bread&butter in statistics bounds, and they automatically give additive, not multiplicative errors.

I will think about it though, and post something. Vague intuition is it will need very strenous conditions on both the function and the distribution, and that the additive bound is actually at the heart of it.

$\endgroup$
  • $\begingroup$ Every time i edit, the answer gets bumped. So I'll point out: the second derivative bound is tight for the example I gave. $\endgroup$ – matus Aug 27 '10 at 21:58
  • $\begingroup$ I think you're right in that additive bounds are the best possible without much stronger conditions on the function. $\endgroup$ – Ian Aug 28 '10 at 18:08
  • $\begingroup$ Dear Ian, I thought about this problem quite a bit more, but the main difficulty in my mind is hinted at by the example I gave, where $f(\textrm E(X))= 0$, but $\textrm E (f(X)) > 0$. You can constrain both the function family (bounded, bounded derivatives, integrable) and the distribution (smooth, bounded, bounded momemts), and you still have these examples. It suffices to have a symmetric, nonnegative function equal to zero at the mean of the distribution. That said, everything depends on the constraints in your exact problem. In the general case, I think the additive nature is fundamental. $\endgroup$ – matus Aug 28 '10 at 19:44
  • $\begingroup$ @Ian: The proofs of the Chernoff and Azuma-Hoeffding inequalities use arguments reminiscent of this, so you may wish to read those for inspiration. See e.g. Mitzenmacher and Upfal's book on randomization in computing. $\endgroup$ – Warren Schudy Oct 4 '10 at 3:29
3
$\begingroup$

For insight, consider a distribution concentrated on two values; say, with equal probabilities of 1/2 that it equal 1 or 3, whence $\textbf{E}[x] = 2$. Take $N >> 0$ and $\epsilon > 0$. Consider functions $f$ for which $f(1) = f(3)= N\epsilon$ and $f(\textbf{E}[x]) = f(2) = \epsilon$. By making $\epsilon$ sufficiently small and connecting $f$ continuously among these three points we can make the curvature of $f$ as small as desired. Then

$\textbf{E}[f(x)] = N\epsilon$, yet

$N = N\epsilon / \epsilon = \textbf{E}[f(x)] / f(\textbf{E}[x]) \le \varphi(f)$.

This shows $\varphi(f)$ must be arbitrarily large.

$\endgroup$

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.