= Solution
With varying positive step sizes, the same one-step inequality is
$$
2\eta_s\,\mathbb E[f(\beta_s)-f(\widehat\beta)]
\leq\mathbb E\lVert\beta_s-\widehat\beta\rVert_2^2
-\mathbb E\lVert\beta_{s+1}-\widehat\beta\rVert_2^2
+\eta_s^2\frac{M^2}{\{\log2\}^2}.
$$
Sum from $s=1$ to $k$, use $\lVert\beta_1-\widehat\beta\rVert_2\leq2R$, and divide by $2A_1$. The <Jensen inequality> for the weighted average $\widetilde\beta=A_1^{-1}\sum_s\eta_s\beta_s$ gives
$$
\boxed{
\mathbb E f(\widetilde\beta)-f(\widehat\beta)
\leq\frac{A_2M^2}{2A_1\{\log(2)\}^2}+\frac{2R^2}{A_1}},
$$
where $A_1=\sum_s\eta_s$ and $A_2=\sum_s\eta_s^2$.
Back to article page
