100 Learning Theory — Hoeffding

100.1 Overview

This module develops the analytic lemmas underlying Hoeffding’s lemma for the Hedge (multiplicative-weights) algorithm. Starting from the convexity of the exponential function, it derives a chain of bounds culminating in two log-MGF inequalities: a weak bound with constant \(\eta ^2/2\) and a tight bound with constant \(\eta ^2/8\).

100.2 Declarations

Lemma 100.1 Product of a fraction and its complement

✓

For every real number \(x\) with \(0 \le x \le 1\), the product \(x(1-x)\) is at most \(\tfrac {1}{4}\).

Theorem 100.2 Convexity bound for the exponential

✓

Let \(\eta \) be a real number and let \(x \in [0,1]\). Then

\[ e^{-\eta x} \; \le \; 1 - x + x\, e^{-\eta }. \]

Theorem 100.3 Weighted exponential sum versus affine upper bound

✓

Let \(p_1,\dots ,p_n\) be a probability vector, that is \(p_i \ge 0\) for every \(i\) and \(\sum _{i} p_i = 1\), and let \(\ell _1,\dots ,\ell _n \in \mathbb {R}\) satisfy \(0 \le \ell _i \le 1\) for every \(i\). Then for every \(\eta \in \mathbb {R}\),

\[ \sum _{i} p_i\, e^{-\eta \, \ell _i} \; \le \; 1 - \bigl(1 - e^{-\eta }\bigr)\sum _{i} p_i\, \ell _i. \]

Theorem 100.4 The logarithmic inequality \(\ln (1+u)\le u\)

✓

For every real number \(u \gt -1\), the natural logarithm satisfies \(\ln (1+u) \le u\).

Theorem 100.5 A quadratic upper bound for \(\eta - 1 + e^{-\eta }\)

✓

For every real number \(\eta \ge 0\), the quantity \(\eta - 1 + e^{-\eta }\) satisfies the bound

\[ \eta - 1 + e^{-\eta } \; \le \; \frac{\eta ^2}{2}. \]

Theorem 100.6 Weak Hoeffding log-MGF bound

✓

Let \(n \ge 1\) and let \(p = (p_1, \dots , p_n)\) be a probability vector, so that \(p_i \ge 0\) for every \(i\) and \(\sum _{i} p_i = 1\). Let \(\ell _1, \dots , \ell _n \in [0,1]\), and let \(\eta \gt 0\). Writing \(L = \sum _{i} p_i \ell _i\) for the average loss, one has

\[ \log \! \Bigl(\sum _{i} p_i\, e^{-\eta \, \ell _i}\Bigr) \; \le \; -\eta L + \frac{\eta ^2}{2}. \]

Theorem 100.7 Bernoulli MGF bound (Hoeffding’s lemma)

✓

Let \(L \in [0,1]\) and let \(\eta \) be a real number. Then the moment generating function of the shifted Bernoulli weight \(1 - L + L\, e^{-\eta }\) satisfies

\[ \ln \! \bigl(1 - L + L\, e^{-\eta }\bigr) \; \le \; -L\eta + \frac{\eta ^2}{8}. \]

Theorem 100.8 Tight Hoeffding bound on the exponential loss

✓

Let \(p_1,\dots ,p_n\) be a probability distribution, so \(p_i \ge 0\) for every \(i\) and \(\sum _{i=1}^n p_i = 1\), and let \(\ell _1,\dots ,\ell _n \in [0,1]\) be losses. Write \(L = \sum _{i=1}^n p_i\, \ell _i\) for the expected loss. Then for every \(\eta \gt 0\),

\[ \log \! \Bigl(\sum _{i=1}^n p_i\, e^{-\eta \, \ell _i}\Bigr) \; \le \; -\eta \, L + \frac{\eta ^2}{8}. \]

100.3 Additional declarations

Lemma 100.9 First derivative of the Hoeffding auxiliary function

✓

Let \(L, x \in \mathbb {R}\) and suppose \(1 - L + L\, e^{-x} \gt 0\). Then the auxiliary function

\[ \varphi (x) \; =\; -L x + \frac{x^2}{8} - \ln \! \bigl(1 - L + L\, e^{-x}\bigr) \]

is differentiable at \(x\) with derivative

\[ \varphi '(x) \; =\; -L + \frac{x}{4} + \frac{L\, e^{-x}}{1 - L + L\, e^{-x}}. \]

This is the \(\varphi '\) computation used in the proof of bernoulli_mgf_bound.

Lemma 100.10 Second derivative of the Hoeffding auxiliary function

✓

Let \(L, x \in \mathbb {R}\) and suppose \(1 - L + L\, e^{-x} \gt 0\). Then the function

\[ \varphi '(x) \; =\; -L + \frac{x}{4} + \frac{L\, e^{-x}}{1 - L + L\, e^{-x}} \]

(the derivative from bernoulli_mgf_bound_step1) is differentiable at \(x\) with derivative

\[ \varphi ''(x) \; =\; \frac{1}{4} - \frac{L\, (1 - L)\, e^{-x}}{\bigl(1 - L + L\, e^{-x}\bigr)^2}. \]

This is the \(\varphi ''\) computation used in the proof of bernoulli_mgf_bound.