109 Learning Theory — Weighted Majority
109.1 Overview
This module formalizes the mistake-bound analysis of the Weighted Majority algorithm. Starting from \(n\) experts each assigned unit weight, the algorithm multiplies the weight of every mistaken expert by a penalty factor \(\beta \in (0,1)\) after each round. The key results bound the total number of algorithm mistakes \(M_{\mathrm{WM}}\) in terms of the best expert’s mistake count \(M^*\) and \(n\), and a factor-2 lower bound shows the analysis is essentially tight for deterministic learners.
109.2 Declarations
Let \(\beta \in (0,1)\), let \(W : \mathbb {N}\to \mathbb {R}\) be a sequence of positive reals, and let \(M\) be a natural number such that \(W(k+1) \le W(k) \cdot \tfrac {1+\beta }{2}\) for every \(k \lt M\). Then
Fix an integer \(n \ge 1\) and a real number \(\beta \) with \(0 \lt \beta \lt 1\), and let \(W \colon \mathbb {N}\to \mathbb {R}\) be a sequence of strictly positive reals with \(W(0) = n\). Suppose that for every \(k \lt M\) the sequence shrinks by at least the factor \((1+\beta )/2\) at each step, in the sense that
Then
Let \(\beta \in (0,1)\) and let \(n \ge 1\) be an integer, and let \(M^\ast , M_{\mathrm{WM}}\) be nonnegative integers satisfying
Then
where \(\log \) denotes the natural logarithm.
Let \(n \ge 2\) be an integer and let \(\beta \in (0,1)\). Suppose \(M^*\) and \(M_{\mathrm{WM}}\) are nonnegative integers satisfying
Then