Solutions for Problem Set 8

[vincenzobaz]

I cannot find the solutions for problem set 8 in the lecture notes (Frank-Wolfe is only covered in the slides, not in the lecture notes). Could we have them? Thanks in advance

[martinjaggi]

the solution to problem set 8, ex 1 is the following. all other available solutions, notes and slides, are posted on the webpage already.

By induction. Considering $t\ge1$, we have [ \begin{array}{rl} h_{t+1} \le& (1- \gamma_t) h_t + {\gamma_t}^2 C \[2pt] =& \big(1-\frac2{t+2}\big) h_t + \big(\frac2{t+2}\big)^2 C \[2pt] \le& \big(1-\frac2{t+2}\big) \frac{4C}{t+2} + \big(\frac2{t+2}\big)^2 C \ , \end{array} ] where in the last inequality we have used the induction hypothesis for $ht$. Simply rearranging the terms gives [ \begin{array}{rl} h{t+1} \le& \frac{4C}{t+2} \big(1-\frac{1}{t+2}\big) ~=~ \frac{4C}{t+2} \frac{t+2-1}{t+2} \[3pt] \le& \frac{4C}{t+2} \frac{t+2}{t+3} ~=~ \frac{4C}{t+3} \ , \end{array} ] which is our claimed bound for $t\ge 1$.

[vincenzobaz]

Thanks!