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.

Aren't we missing the gradient though?

So sorry I don't understand your question..

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$$

Oh I see! Thank you very much!

Page 1 of 1