COMPX270 — Chapter 12 Supplement
Mathematical Foundations: Learning from Experts
Potential function arguments, geometric weight decay, logarithmic bounds, the \(\beta\) trade-off, and the key inequality \(1 - x \leq -\ln x\).
Potential Functions
A potential function \(\Phi_t\) is a non-negative quantity that we track over time. The proof strategy is:
- Upper bound: Show \(\Phi\) decreases significantly with each mistake.
- Lower bound: Show \(\Phi\) can never drop below some positive value.
- Combine: The gap between initial and final values limits the number of mistakes.
\(\Phi_t = |S_t|\) (number of surviving experts).
- \(\Phi_1 = n\) (all experts alive).
- Each mistake: \(\Phi_{t+1} \leq \Phi_t - 1\).
- \(\Phi_t \geq 1\) always (perfect expert survives).
Mistakes \(\leq n - 1\). \(\checkmark\)
\(\Phi_t = |S_t|\). Each mistake: \(\Phi_{t+1} \leq \Phi_t / 2\). After \(k\) mistakes: \(\Phi \leq n/2^k \geq 1\). So \(k \leq \log_2 n\). \(\checkmark\)
\(\Phi_t = W_t = \sum_i w_{i,t}\) (total weight).
- \(\Phi_1 = n\).
- Each mistake: \(\Phi_{t+1} \leq \frac{1+\beta}{2} \Phi_t\).
- \(\Phi_{T+1} \geq \beta^{C^*}\) (weight of best expert).
Combining: \(\beta^{C^*} \leq n \cdot \left(\frac{1+\beta}{2}\right)^{C(T)}\). \(\checkmark\)
Logarithmic Bounds
If a quantity \(\Phi\) starts at \(\Phi_0\), decreases by a constant factor \(\alpha < 1\) per mistake, and has a lower bound \(L\):
\[\Phi_0 \cdot \alpha^k \geq L \implies k \leq \frac{\log(\Phi_0/L)}{\log(1/\alpha)}\]This is the universal pattern behind all bounds in this chapter.
| Algorithm | \(\Phi_0\) | Decay \(\alpha\) | Lower \(L\) | Bound |
|---|---|---|---|---|
| Consistent | \(n\) | \(\frac{n-1}{n}\) | \(1\) | \(n-1\) |
| Halving | \(n\) | \(1/2\) | \(1\) | \(\log_2 n\) |
| MWU(\(\beta\)) | \(n\) | \(\frac{1+\beta}{2}\) | \(\beta^{C^*}\) | \(\frac{C^*\log(1/\beta)+\log n}{\log(2/(1+\beta))}\) |
Geometric Weight Decay
Each expert \(A_i\) starts with weight \(w_{i,1} = 1\). After \(T\) rounds:
\[w_{i,T+1} = \beta^{C_i(T)}\]where \(C_i(T)\) is the number of mistakes expert \(A_i\) made. The weight decays geometrically with each mistake.
When we make a mistake, the wrong side has weight \(> W_t/2\) (deterministic MWU). After penalising by \(\beta\):
\[W_{t+1} = W_t - (1 - \beta) \cdot (\text{wrong weight}) \leq W_t - (1-\beta) \cdot \frac{W_t}{2} = \frac{1+\beta}{2} W_t\]After \(m\) mistakes from rounds 1 to \(T\): \(W_{T+1} \leq n \cdot \left(\frac{1+\beta}{2}\right)^m\).
For any expert \(A_{i^*}\) (in particular the best one with \(C_{i^*} = C^*\)):
\[W_{T+1} = \sum_i w_{i,T+1} \geq w_{i^*,T+1} = \beta^{C^*}\]The \(\beta\) Trade-off
The MWU(\(\beta\)) bound is:
\[C(T) \leq \underbrace{\frac{\log(1/\beta)}{\log(2/(1+\beta))}}_{\text{multiplicative factor}} \cdot C^* + \underbrace{\frac{\log n}{\log(2/(1+\beta))}}_{\text{additive term}}\]As \(\beta \to 0\): \(\log(1/\beta) \to \infty\) but \(\log(2/(1+\beta)) \to \log 2\). The multiplicative factor \(\to \infty\), but additive term \(\to \log_2 n\). This recovers Halving-like behaviour (great additive, terrible multiplicative).
As \(\beta \to 1\): Both \(\log(1/\beta)\) and \(\log(2/(1+\beta))\) approach 0, but their ratio \(\to 1\). The multiplicative factor \(\to 1\) (perfect!), but the additive term \(\to \infty\) (bad for small \(C^*\)).
Setting \(\beta = 1 - \varepsilon\) with \(\varepsilon = \sqrt{\log n / C^*}\) (assuming \(C^*\) is known or estimated):
\[C(T) \leq 2C^* + O\!\left(\sqrt{C^* \log n}\right)\]This is nearly optimal: the multiplicative factor is 2 (matching Fact 56.3 for deterministic) and the additive term is sub-linear in both \(C^*\) and \(\log n\).
Telescoping & the ln Inequality
For all \(x > 0\):
\[1 - x \leq -\ln x\]Equivalently, \(1 - x \leq \ln(1/x)\). Equality holds at \(x = 1\). This is the crucial inequality in the Randomised MWU proof.
In the randomised analysis, \(\mathbb{E}[\text{cost at } t] = F_t/W_t\), where \(F_t = (W_t - W_{t+1})/(1-\beta)\). So:
\[\mathbb{E}[C(T)] = \frac{1}{1-\beta} \sum_{t=1}^{T} \frac{W_t - W_{t+1}}{W_t} = \frac{1}{1-\beta} \sum_{t=1}^{T} \left(1 - \frac{W_{t+1}}{W_t}\right)\]Applying \(1 - x \leq -\ln x\) with \(x = W_{t+1}/W_t\):
\[\leq \frac{1}{1-\beta} \sum_{t=1}^{T} \ln\frac{W_t}{W_{t+1}} = \frac{1}{1-\beta} \ln\frac{W_1}{W_{T+1}}\]The sum telescopes! Using \(W_1 = n\) and \(W_{T+1} \geq \beta^{C^*}\) gives the bound.
Deterministic MWU only uses \(W_{t+1} \leq \frac{1+\beta}{2}W_t\) when a mistake occurs. This wastes information on non-mistake rounds.
Randomised MWU accounts for every round via \(F_t/W_t\), and the telescoping sum captures the total weight decrease without the factor-2 loss from the weighted majority threshold.
Deterministic vs Randomised Gap
| Deterministic MWU(\(\beta\)) | Randomised MWU(\(\beta\)) | |
|---|---|---|
| Bound | \(\displaystyle\frac{C^*\log(1/\beta)+\log n}{\log(2/(1+\beta))}\) | \(\displaystyle\frac{C^*\ln(1/\beta)+\ln n}{1-\beta}\) |
| Type | Worst-case | Expected |
| \(\beta \to 1\) | \(\approx 2C^* + \frac{2\log n}{\varepsilon}\) | \(\approx C^* + \frac{\ln n}{\varepsilon}\) |
The factor of 2 difference: deterministic pays \(2C^*\), randomised pays \(C^*\). This matches the lower bound of Fact 56.3.
In deterministic MWU, we charge a mistake only when our prediction differs from truth. But the weighted majority threshold causes us to err only when the wrong side has weight \(> W/2\). The penalty affects at most \(W/2\) of the weight, yielding the factor \(\frac{1+\beta}{2}\).
In randomised MWU, we charge \(F_t/W_t\) fractionally, and \(F_t\) can be any fraction of \(W_t\). The inequality \(1 - x \leq -\ln x\) absorbs the loss elegantly without the factor-2 gap.
Math quiz
Chapter math quizzes are in the Quiz Hub. Filter by this chapter and choose Study / Math / All.