Claim
Assume that all losses are in [0,1], the regret of the Multiplicative Weight Algorithm run for T steps with a parameter 0<ϵ≤1/2 is:
In particular, if T>4lnn and we choose ϵ=Tlnn, we have
Outline
Define
to be the sum of the weights at time t, at the end of the execution of the algorithm:
- If WT+1 is small, then the offline optimum is large
- If the loss suffered by the algorithm is large, then WT+1 is small
Therefore
- If the algorithm suffers a large loss, then the offline optimum is also large, so regret is small
Call the offline optimum L∗:
and we can use Lt to denote the loss incurred by the algorithm at time t
Lemmas
Lemma 2
If WT+1 is small, then the offline optimum is large
Proof
Let j be any strategy, then
Now let i∗ be an offline optimal strateggy,
And observe that for i∗,
Lemma 3
If the loss suffered by the algorithm is large, then WT+1 is small
Proof
We know W1=n, so we can prove
Observe that
Proof
LEMMA 2: If WT+1 is small, then the offline optimum is large
LEMMA 3: If the loss suffered by the algorithm is large, then WT+1 is small
Putting them together
Note that because of tarylor series ln(1−z)=∑n=1∞−nzn, we have inequality
Then apply this inequality
Divide by ϵ and rearrange a bit,