0.25
0.5
0.75
1.25
1.5
1.75
2
Regret to the Best vs. Regret to the Average
Published on Feb 25, 20073159 Views
We study regret minimization algorithms, focusing not only on their regret to the best expert, but also on their regret to the average of all experts and to the worst expert. We show that any algori
Chapter list
Regret to the Best vs. Regret to the Average00:00
The No-Regret Setting00:05
This Work01:39
Our Results03:27
Oscillations: The Cost of an Update05:31
A Bad Sequence07:33
A Simple Trade-off: The ?(T) Barrier08:42
Exponential Weights [F94]11:06
So far…12:35
An Unrestricted Lower Bound12:52
A Simple Additive Algorithm13:52
Breaking the ?(T) Barrier15:01
Staying in the Loop16:02
Exiting the Loop18:03
Obliterating the ?(T) Barrier19:58