machine learning theory

There are 5 important inequalities in Machine Learning Theory:

• Markov’s Inequality
• Chebyshev’s Inequality
• Chernoff-Hoeffding Bound
• Hoeffding’s Inequality
• McDiarmid’s Inequality

Markov’s Inequality

If $X$ is a nonnegative random variable and $epsilon>0$. Then

$$P[Xgeqepsilon]leqfrac{E(X)}{epsilon}$$

Proof for Markov’s Inequality

First of all, we define indicator function:

For an event $A$, let $I(A)$ be the indicator of the event:

$$% <![CDATA[ I(A) = left{ begin{array}{ll} 1 & textrm{if $A$ is true}\ 0 & textrm{else} end{array} right. %]]>$$

We have $Xgeqepsilon I(Xgeqepsilon)$. Taking expectation on both sides, we get

$$E(X)geqepsilon E(I(Xgeqepsilon))=epsilon P(Xgeqepsilon)$$

Chebyshev’s Inequality

Let $X$ be a random variable with finite expected value and finite non-zero variance. Then for any real number $epsilon>0$:

$$P[vert X-E(X)vertgeqepsilon]leqfrac{var(X)}{epsilon^2}$$

Proof for Chebyshev’s Inequality

From Markov’s inequality, we define

$$Y=vert X-E(X)vert^2$$

Then

$$P[Ygeq epsilon^2]leqfrac{E(Y)}{epsilon^2}=frac{var(X)}{epsilon^2}$$

The previous two inequalities are easy to understand compared with the following three inequalities.

Chernoff-Hoeffding Bound

The following theorem is a special case of chernoff bound

Let $x_1, cdots, x_m$ be i.i.d. Bernoulli random variables, where for every $i$:

$$P(x_i=1)=p_i, P(x_i=0)=1-p_i$$

Let

$$bar{X}=frac{1}{m}sum_{i=1}^mx_i, p=frac{1}{m}sum_{i=1}^mp_i$$

We have

$$P(vertbar{X}-pvert>epsilon)leq 2e^{-2epsilon^2m}$$

Moment-Generating Functions (MGFs)

MGF of a random variable $X$ is defined as

$$M_X(t)=E[e^{tX}], tinmathbb{R}$$

MGF has some important properties:

1. If $M_X(t)$ is defined for $tin(-t^ast,t^ast)$ for some $t^ast>0$, then
   • All the moments of $X$ exist, and $M_X(t)$ has derivatives of all orders at $t=0$ where $forall k, E[X^k]=frac{partial^kM}{partial t^k}vert_{t=0}$
   • $forall tin(-t^ast,t^ast)$, $M_X(t)$ has Taylor’s expansion $M_X(t)=sum_kfrac{E[X^k]}{k!}t^k$
2. If $x$ and $y$ are independent random variables, then the $M_{x+y}(t)=M_x(t)M_y(t)$
3. For any constants $a$ and $b$, $M_{ax+b}(t)=e^{bt}M_x(at)$

Jensen’s Inequality

Let $X$ be a random variable, and $f$ be a convex function. Then

$$f(E[X])leq E[f(X)]$$

Proof for Chernoff-Hoeffding Bound

Define $y_i=x_i-p_i$, $bar{y}=frac{1}{m}sum_{i=1}^my_i$. We need to show $P(vertbar{y}vert>epsilon)leq2e^{-2epsilon^2m}$

Conseder each of $P(bar{y}>epsilon)$ and $P(bar{y}<epsilon)$

For $t>0$, look at

$$P(bar{y}&gt;epsilon)=P(e^{tbar{y}}&gt;e^{tepsilon})leqfrac{E[e^{tbar{y}}]}{e^{tepsilon}}=frac{M_{bar{y}}(t)}{e^{tepsilon}}$$

Lemma 1: For all $t>0$, $M_{y_i}(t)leq e^{t^2/8}$

Proof: Recall $% &lt;![CDATA[ y_i = left{ begin{array}{ll} 1-p_i &amp; x_i=1\ -p_i &amp; x_i=0 end{array} right. %]]&amp;gt;$

$$M_{y_i}(t)=E[e^{ty_i}]$$
$$=p_ie^{t(1-p_i)}+(1-p_i)e^{-tp_i}$$
$$=e^{-tp_i}(p_ie^t+(1-p_i))$$
$$=exp(-tp_i+ln(p_ie^t+(1-p_i)))$$

Look at $g(t)=-tp_i+ln(p_ie^t+(1-p_i))$, for some $t^astin[0,t]$

$$g(t)=g(0)+g'(0)t+g^{primeprime}(t^ast)frac{t^2}{2}$$

We can show that $forall t^ast$, we can get $g^{primeprime}(t)leqfrac{1}{4}$.

Thus $g(t)leqfrac{t^2}{8}$

Using properties of MGFs, $M_{bar{y}}(t)=prod_{i=1}^mM_{y_i}(frac{t}{m})$

Using Lemma 1, $M_{bar{y}}(t)leqprod_{i=1}^mexp(frac{t^2}{8m^2})=exp(frac{t^2}{8m})$

$$P(bar{y}&gt;epsilon)leqfrac{M_{bar{y}}(t)}{e^{tepsilon}}$$
$$leqfrac{exp(frac{t^2}{8m})}{e^{tepsilon}}$$
$$=exp(-(tepsilon)-frac{t^2}{8m})$$

Pick $t$ that maximizes the $P(bar{y}>epsilon)$

$$t=4mepsilonRightarrow P(bar{y}&gt;epsilon)leq e^{-2mepsilon^2}$$

The other direction is the same.

Hoeffding’s Inequality

Let $x_1, cdots, x_m$ be independent random variables, where for every $i$:

$$a_ileq x_ileq b_i$$

Let

$$bar{X}=frac{1}{m}sum_{i=1}^mx_i$$

For any $epsilon>0$, we have

$$P(bar{X}-E[bar{X}]&gt;epsilon)leq exp(-frac{2epsilon^2m^2}{sum_i(a_i-b_i)^2})$$
$$% &lt;![CDATA[ P(bar{X}-E[bar{X}]&lt;-epsilon)leq exp(-frac{2epsilon^2m^2}{sum_i(a_i-b_i)^2}) %]]&amp;gt;$$

McDiarmid’s Inequality

Let $f:mathbb{R}^mrightarrowmathbb{R}$ be such that $forall i$, and all $x_1, cdots, x_i, cdots, x_m, X’_i$

$$vert f(x_1, cdots, x_i, cdots, x_m)-f(x_1, cdots, X'_i, cdots, x_m)vertleqDelta_i$$

Let $x_1, cdots, x_m$ be independent random variables, then

$$P[f(x_1, cdots, x_m)-E[f(x_1, cdots, x_m)]&gt;epsilon]leq exp(-frac{2epsilon^2}{sum_iDelta_i^2})$$
$$% &lt;![CDATA[ P[f(x_1, cdots, x_m)-E[f(x_1, cdots, x_m)]&lt;-epsilon]leq exp(-frac{2epsilon^2}{sum_iDelta_i^2}) %]]&amp;gt;$$

Note: Hoeffding’s inequality is a special case of McDiarmid’s inequality: just set

$$f(x_1, cdots, x_m)=sum_ix_i$$

Thanks

知

切比雪夫不等式到底是个什么概念? - 回答作者：姚岑卓