103 Learning Theory — Hoeffding

103.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\).

103.2 Declarations

Lemma 103.1 \(x(1-x) \le 1/4\)

✓

For any \(x \in [0,1]\), the product \(x(1-x) \le \tfrac {1}{4}\).

Theorem 103.2 Convexity bound for the exponential

✓

For any \(\eta , x \in \mathbb {R}\) with \(x \in [0,1]\), convexity of \(\exp \) gives

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

Theorem 103.3 Weighted exponential sum vs. affine upper bound

✓

Let \(p : \mathrm{Fin}\, n \to \mathbb {R}\) be a probability vector (\(p_i \ge 0\), \(\sum _i p_i = 1\)) and let \(\ell : \mathrm{Fin}\, n \to \mathbb {R}\) satisfy \(0 \le \ell _i \le 1\) for all \(i\). For any \(\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 103.4 \(\ln (1+u) \le u\)

✓

For any \(u \gt -1\), \(\ln (1+u) \le u\).

Theorem 103.5 \(\eta - 1 + e^{-\eta } \le \eta ^2/2\)

✓

For any \(\eta \ge 0\),

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

Theorem 103.6 Weak Hoeffding log-MGF bound

✓

Let \(p\) be a probability vector on \(\mathrm{Fin}\, n\) and let \(\ell _i \in [0,1]\) for all \(i\). For \(\eta \gt 0\), setting \(L = \sum _i p_i \ell _i\),

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

Theorem 103.7 Bernoulli MGF bound (Hoeffding’s lemma)

✓

For \(L \in [0,1]\) and any \(\eta \in \mathbb {R}\),

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

The bound is established by showing that the function \(\varphi (\eta ) = -L\eta + \eta ^2/8 - \ln (1-L+Le^{-\eta })\) is convex with \(\varphi (0) = 0\) and \(\varphi '(0) = 0\).

Theorem 103.8 Tight Hoeffding log-MGF bound

✓

Under the same hypotheses as hoeffding_log_mgf_weak, the tighter bound holds:

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

This follows by first applying weighted_exp_le_affine and then bernoulli_mgf_bound.