### Q10 2018

Hey,
how can the bound for the L_i=\norm(a_i)^2 be obtained? I tried to apply triangle inequality...
Thank you.

Top comment

Triangle inequality is the right thing to do here :
$$f(x + \gamma e_i) = \frac{1}{2} ||Ax-b + \gamma a_i||^2 \leq \frac{1}{2} ||Ax-b||^2 + \frac{||a_i||^2}{2} \gamma^2$$
where we found $$a_i$$ thanks to $$a_i = Ae_i$$.
By identification (equation 10.5 page 183 of the notes) : $$L_i = ||a_i||^2$$

Thank you very much, "anonymous" for helping to answer questions! Much appreciated.

When applying the triangle inequality, we only have two terms. However, equation 10.5 has three terms, where one of them is a gradient. How can we affirm the coordinate-wise smoothness is ||a_i||^2 if we're missing this gradient in our inequality?

And my bad, it wasn't clear! :)

It is indeed not complete. Sorry for that! You can use
$$f(x+\gamma e_i) = \frac{1}{2} ||Ax - b + \gamma a_i||^2 = \frac{1}{2} ||Ax-b||^2 + 2\gamma a_i^T(Ax-b) + \frac{||a_i||^2}{2}\gamma^2$$

Page 1 of 1