Does anybody know how could i prove this inequality?
Consider a sequence of vectors $v_1,v_2...v_T$ and an update equation of the form $w^{t+1}= w^t - \eta \cdot v_t$ with $w^1=0$. Show that:
$$\sum_{t=1}^T \langle w^t - w^*,v_t\rangle \le {||w^*||^2 \over 2\eta} + {\eta\over2}\sum_{t=1}^T||v_t||^2$$
where $w^*$ is any vector, $\eta$ is the learning rate and the $\langle \cdots \rangle$ is the dot product.
I am really having problems in proving this inequality. Do you have any suggestions? Thank you
Here is (I think) the standard proof: for any $t\geq 1$, notice that \begin{align} \|w_{t+1}-w^*\|^2&=\|w_t-\eta v_t-w^*\|^2\\ &=\|w_t-w^*\|^2+\eta^2\|v_t\|^2-2\eta\langle w_t-w^*,v_t\rangle. \end{align} Rearranging gives \begin{equation} \langle w_t-w^*,v_t\rangle = \frac{\|w_t-w^*\|^2}{2\eta}+\frac{\eta\|v_t\|^2}{2}-\frac{\|w_{t+1}-w^*\|^2}{2\eta}. \end{equation} Summing from $t=1$ to $T$, we obtain by telescoping that \begin{equation} \sum_{t=1}^T\langle w_t-w^*,v_t\rangle=\frac{\|w_1-w^*\|^2}{2\eta}+\frac{\eta\sum_{t=1}^T\|v_t\|^2}{2}-\frac{\|w_{T+1}-w^*\|^2}{2\eta}. \end{equation} As $w_1=0$ and the last term is nonpositive, we deduce \begin{equation} \sum_{t=1}^T\langle w_t-w^*,v_t\rangle\leq \frac{\|w^*\|^2}{2\eta}+\frac{\eta\sum_{t=1}^T\|v_t\|^2}{2}, \end{equation} as desired.