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 \)

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?

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 \)

## 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.

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 \)

## 5

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

## 2

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 \)

## 1

Oh I see! Thank you very much!

## Add comment