8.8 Polynomial weighted algorithm. The objective of this problem is to show how another regret minimization algorithm can be dened and studied. Let L be a loss function convex in its rst argument and taking values in [0;M].

We will assume N > e2 and then for any expert i 2 [N], we denote by rt;i the instantaneous regret of that expert at time t 2 [T], rt;i = L(byt; yt) ???? L(yt;i; yt),

and by Rt;i its cumulative regret up to time t: Rt;i = Pt s=1 rt;i. For convenience, we also dene R0;i = 0 for all i 2 [N]. For any x 2 R, (x)+ denotes max(x; 0), that is the positive part of x, and for x = (x1; : : : ; xN)> 2 RN, (x)+ = ((x1)+; : : : ; (xN)+)>.
Let > 2 and consider the algorithm that predicts at round t 2 [T] according to byt = Pn Pi=1 wt;iyt;i n i=1 wt;i , with the weight wt;i dened based on the th power of the regret up to time (t ???? 1): wt;i = (Rt????1;i)????1 + . The potential function we use to analyze the algorithm is based on the function  dened over RN by : x 7! k(x)+k2 = PN i=1(xi)
+
 2 .

(a) Show that  is twice dierentiable over RN????B, where B is dened as follows:
B = fu 2 RN : (u)+ = 0g:

(b) For any t 2 [T], let rt denote the vector of instantaneous regrets, rt = (rt;1; : : : ; rt;N )>, and similarly Rt = (Rt;1; : : : ;Rt;N )>. We dene the potential function as (Rt) = k(Rt)+k2 . Compute r(Rt????1) for Rt????1 62 B and show that r(Rt????1)
rt  0 (Hint: use the convexity of the loss with respect to the rst argument).

(c) Prove the inequality r>[r2(u)]r  2( ???? 1)krk2 valid for all r 2 RN and u 2 RN ????B (Hint: write the Hessian r2(u) as a sum of a diagonal matrix and a positive semidenite matrix multiplied by (2 ???? ). Also, use Holder's inequality generalizing Cauchy-Schwarz: for any p > 1 and q > 1 with 1 p + 1 q = 1 and u; v 2 RN, ju
vj  kukpkvkq).

(d) Using the answers to the two previous questions and Taylor's formula, show that for all t  1, (Rt)????(Rt????1)  (????1)krtk2 , if Rt????1+(1????
)Rt 62 B for all 2 [0; 1].

(e) Suppose there exists 2 [0; 1] such that (1????
)Rt????1 +
Rt 2 B. Show that (Rt)  ( ???? 1)krtk2 .

(f) Using the two previous questions, derive an upper bound on (RT ) expressed in terms of T, N, and M.
(g) Show that (RT ) admits as a lower bound the square of the regret RT of the algorithm.
(h) Using the two previous questions give an upper bound on the regret RT . For what value of is the bound the most favorable? Give a simple expression of the upper bound on the regret for a suitable approximation of that optimal value.