# EX 1: Hoeffding Inequality

Laplace transform of random var $X$, function $f$ s.t.

$f(s) ≝ 𝔼(\exp(sX))$

Goal of exercise: Prove the

Hoeffding Inequality:
$ℙ(S_n - 𝔼(S_n) ≥ t) ≤ \exp\left(-2 \frac{t^2}{\sum\limits_{ i } (b_i - a_i)^2}\right)$

where

• $S_n ≝ \sum\limits_{ i } X_i$
• $X_i$ independent
• $a_i ≤ X_i ≤ b_i$

NB: For the proof, we need a lemma:

Lemma: if $X$ s.t. $𝔼(X)=0$ and $a ≤ X ≤ b$, then its Laplace transform $f$ is such that $f(s) ≤ \exp\left(\frac{s^2 (b-a)^2}{8}\right) \quad ∀s>0$

## 1.

Use Chernoff’s method (Markov inequality + exp) to bound $ℙ(S_n - 𝔼(S_n)≥ t)$ by a quantity that depends on the Laplace transform $f(s)$ of $Z_n ≝ S_n - 𝔼(S_n)$.

Then, optimize the bound over $S$ to get Hoeffding’s result.

Reminder:

Markov inequality for $X ≥ 0$:
$ℙ(X ≥ a) ≤ \frac{𝔼(X)}{a}$

\begin{align*} ℙ(Z_n ≥ t) &= ℙ(\exp(s Z_n) ≥ \exp(st)) \\ & ≤ \frac{\overbrace{𝔼(\exp(s Z_n))}^{\text{Laplace transform}}}{\exp(st)} \text{ (Markov)}\\ & ≤ \frac{\exp\left(\frac{s^2 (\sum\limits_{ i } b_i - a_i)^2}{8}\right)}{\exp(st)} \\ \end{align*}

But:

$Z_n = \sum\limits_{i} X_i - 𝔼(\sum\limits_{ i } X_i \\ = \sum\limits_{i} \underbrace{(X_i - 𝔼(X_i))}_{\text{ noted } Y_i}$

and the $Y_i$ are independent due to the $X_i$ being independent.

So

\begin{align*} f_{Z_n}(s) &= 𝔼(\exp{s Z_n}) \\ &= 𝔼(\exp{s \sum\limits_{ i } Y_i }) \\ &= 𝔼(\prod_i \exp{s Y_i }) \\ &= \prod_i \underbrace{𝔼(\exp{s Y_i })}_{≝ \; f_{Y_i}(s)} &&\text{(independence)} \end{align*}

Therefore:

\begin{align*} ℙ(Z_n ≥ t) &≤ \prod_i \frac{𝔼(\exp{s Y_i })}{\exp(st)} \\ & ≤ \prod_i \frac{\exp\left(\frac{s^2 (b_i - a_i)^2}{8}\right)}{\exp(st)} \\ &=\exp\left(\frac{s^2 \sum\limits_{ i } (b_i - a_i)^2}{8} -st\right) \\ \end{align*}

This bound is true for all $s>0$: to get the tightest bound possible, we minimize over $s$.

Since $\exp$ is non-decreasing, we just need to minimize

$φ(s) ≝ \frac{s^2 \sum\limits_{ i } (b_i - a_i)^2}{8} -st$

⟹ $s^\ast ≝ \frac{4t}{\sum\limits_{ i } (b_i - a_i)^2}$

Hence:

$ℙ(S_n - 𝔼(S_n) ≥ t) ≤ \exp\left(-2 \frac{t^2}{\sum\limits_{ i } (b_i - a_i)^2}\right)$

Corollary:

Chernoff: If $X_i ⇝ Ber(p)$,

$ℙ\left(\sum\limits_{ i } X_i - p ≥ t\right) ≤ \exp(-2t^2)$

because $0 ≤ X_i ≤ 1$

# EX 2: Regularized VS Constrained problems

Consider the regression problem:

$f(x) = w^T x$

over the sample $(x_1, y_1), ⋯, (x_n, y_n)$

To avoid overfitting, we can

• either regularize with the norm of $w$ (Ridge regression): $\min_w \underbrace{l}_{\text{loss}}(w^T x - y) + λ \Vert w \Vert_2^2 \qquad (ℛ_λ)$

• or contrain the norm $\Vert w \Vert_2^2$: $\min_w l(w^T x - y) \quad \text{ s.t. } \Vert w \Vert_2^2 ≤ R^2 \qquad (𝒞_R)$

Actually, if the loss $l$ is convex, both problems are equivalent, i.e.:

• $∀R, ∃λ_R$
• $∀λ, ∃R_λ$

such that both problems have the same solutions.

So: $\begin{cases} ℛ_λ &= 𝒞_{R_λ}\\ 𝒞_R &= ℛ_{λ_R} \end{cases}$

## 1.

Show that: $∀λ ≥ 0$, the problem $ℛ_λ$ with solution $w_λ$ corresponds to the problem $𝒞_R$ with a certain $R$ (meaning that $w_λ$ is also a solution to $𝒞_R$)

Indication: $R^2_λ ≝ \Vert w_λ \Vert_2^2$

Show that $w_λ$ is a solution of

$\min_w l(w^T x - y) \quad \text{ s.t. } \Vert w \Vert_2^2 ≤ R_λ^2 ≝ \Vert w_λ \Vert_2^2 \qquad (𝒞_R)$

Assume $w’$ is a solution of $(𝒞_R)$ s.t. $w’≠ w_λ$:

• either: $\Vert w’ \Vert = \Vert w_λ \Vert$: then $w’$ is also a solution of $ℛ_λ$ (because it minimizes the loss function and $λ \Vert w’ \Vert = λ \Vert w_λ \Vert$)

• or: $\Vert w’ \Vert < \Vert w_λ \Vert$: then as $λ \Vert w’ \Vert < λ \Vert w_λ \Vert$ and $l(w’^T x - y) = l(w_λ^T x - y)$, it contradicts $w_λ$ minimizing $ℛ_λ$ (since $w’$ is a better minimizer thereof)

Reciproqual:

Consider $g(R) ≝ \min_{\Vert w \Vert_2^2 = R^2} \sum\limits_{i} l(w^T x_i - y_i)$$$f(R) ≝ \min_{\Vert w \Vert_2^2 ≤ R^2} \sum\limits_{ i } l(w^T x_i - y_i)$ Show that$f$is a decreasing function. Let$R’ > R$. •$f(R’)$solution of$\min_{\Vert w \Vert_2^2 ≤ R’^2} \sum\limits_{ i } l(w^T x_i - y_i)$•$f(R)$solution of$\min_{\Vert w \Vert_2^2 ≤ R^2} \sum\limits_{ i } l(w^T x_i - y_i)$Since $\lbrace w \mid \Vert w \Vert_2^2 ≤ R'^2 \rbrace \supset \lbrace w \mid \Vert w \Vert_2^2 ≤ R^2 \rbrace$ the minimization set for$R’$is larger than the one for$R$, so that$f(R’) ≤ f(R)\$

So $f(R) = \inf_{R'≤ R} g(R')$

Tags:

Updated: