Same recipe as before: upper-bound Φ, lower-bound Φ, compare, take logs 50:30 50:48.

Upper bound

Starting from Φ(t+1) = Σᵢ wᵢ(t+1) and plugging in the update 51:11 51:38:

  1. Φ(t+1) = Σᵢ wᵢ(t)·(1 − ε·mᵢ(t)) (after distributing) 51:38
  2. = Φ(t) − ε·Σᵢ wᵢ(t)·mᵢ(t) 52:10
  3. Substituting wᵢ(t) = pᵢ(t)·Φ(t) 52:10: = Φ(t)·(1 − ε·⟨m(t), p(t)⟩) 53:09
  4. The favourite trick 1 − x ≤ e^{−x} again: ≤ Φ(t)·e^{−ε⟨m(t),p(t)⟩} 53:09
  5. By induction from Φ(1) = n: Φ(T+1) ≤ n · e^{−ε·Σ_t ⟨m(t), p(t)⟩} 54:06

Lower bound

  • Again Φ(T+1) ≥ wᵢ(T) for any fixed expert i 54:50.

  • Unrolling the update: wᵢ(T) = Π_{t=1}^{T} (1 − ε)^{mᵢ(t)} 56:11.

  • Splitting by sign of mᵢ(t) gives 57:39 1:00:28:

    wᵢ(T) ≥ (1 − ε)^{Σ_{mᵢ(t) ≥ 0} mᵢ(t)} · (1 + ε)^{−Σ_{mᵢ(t) < 0} mᵢ(t)}

The two calculus claims

Stated as "calculus claims" and used without full derivation 58:23 59:15:

ClaimRange
(1 − ε)^x ≤ 1 − εxx ∈ [0, 1]
(1 + ε)^{−x} ≤ 1 − εxx ∈ [−1, 0]
  • Cleaner proof than Taylor: f(x) = (1 − ε)^x is convex (check the second derivative is positive), so f((1−x)·0 + x·1) ≤ (1−x)·f(0) + x·f(1) — which is exactly the claim. The lecturer notes his earlier Taylor's-theorem route was "a little clumsy" 59:15 59:42 1:00:02.

Combining

Chaining both bounds 1:01:06 1:01:24:

(1 − ε)^{Σ_{≥0} mᵢ(t)} · (1 + ε)^{Σ_{<0} mᵢ(t)}  ≤  n · e^{−ε·Σ_t ⟨m(t), p(t)⟩}

Take logs and rearrange — the theorem follows, with no further ideas involved. The lecturer skips the algebra and points to the paper/notes 1:01:53.