Hedge:Algorithm Hedge:replacing the'max'operation in FTL by 'softmax'. At each round t=1,2,... (I)compute p:∈△v such that p,&xexp(-nLt-l,i)fori∈[Ny (2)the player submits p,suffers loss (p,)and observes loss eRN (3)update Lt=Lt-1+et FTL update Hedge update arg max(p,-Lt-1》 pi,i exp(-nLt-1,i),ViE [N] PEAN Advanced Optimization(Fall 2023) Lecture 6.Prediction with Expert Advice 11
Advanced Optimization (Fall 2023) Lecture 6. Prediction with Expert Advice 11 Hedge: Algorithm • Hedge: replacing the ‘max’ operation in FTL by ‘softmax’. FTL update Hedge update
Lazy and Greedy Updates ·Hedge algorithm lazy update Pi+1.i exp (-nLt.i),Vi E [N] Li=∑4 ViE [N] s=1 Another equivalent update(when the learning raten is fixed) greedy update Pi+1,i pt,i exp (-nt),ViE[N] where we set the uniform initialization as po.=1/N,ViE [N]. But the two updates can be significantly different when learning rate is changing. Advanced Optimization(Fall 2023) Lecture 6.Prediction with Expert Advice 12
Advanced Optimization (Fall 2023) Lecture 6. Prediction with Expert Advice 12 Lazy and Greedy Updates • Hedge algorithm • Another equivalent update (when the learning rate is fixed) lazy update greedy update But the two updates can be significantly different when learning rate is changing
Hedge:Regret Bound Theorem1.Suppose that∀t∈T]andi∈[N],0≤et,i≤l,then Hedge with learning rate n guarantees Ragat7sW+ +=(TIOgN), where the last equality is by setting noptimally asN)/T. Proof.We present a 'potential-based'proof here,where the potential is defined as Advanced Optimization(Fall 2023) Lecture 6.Prediction with Expert Advice 13
Advanced Optimization (Fall 2023) Lecture 6. Prediction with Expert Advice 13 Hedge: Regret Bound
Proof of Hedge Regret Bound Proof.. ( (即 (%刃 ∑mep(-d (update step of p) ∑：0-a+呢)》 x≥0，e-x≤1-x+x2) 1-n,)+∑P4， Advanced Optimization(Fall 2023) Lecture 6.Prediction with Expert Advice 14
Advanced Optimization (Fall 2023) Lecture 6. Prediction with Expert Advice 14 Proof of Hedge Regret Bound Proof