1
$\begingroup$

I'm reading a book about Gradient methods right now, where the author is using a Taylor series to explain/derive an equation.

$$ \mathbf x_a = \mathbf x - \alpha \mathbf{ \nabla f } (\mathbf x ) $$

Now he says the first order expansion of the Taylor series around x would look like this:

$$ \mathbf{ f } (\mathbf x_a ) = \mathbf{ f } (\mathbf x ) + \mathbf{ \nabla f } (\mathbf x )'( \mathbf x_a - \mathbf x ) + \mathbf o ( || \mathbf x_a - \mathbf x || )$$

and the simplifies it to:

$$ \mathbf{ f } (\mathbf x_a ) = \mathbf{ f } (\mathbf x ) + \alpha || \mathbf{ \nabla f } (\mathbf x )||^2 + \mathbf o (\alpha)$$

Now I don't get this part $ \mathbf o ( || \mathbf x_a - \mathbf x || ) $. As far as I know it's not part of the Taylor Series. Furthermore since I don't know what $ \mathbf o () $ is I can't understand how he can simplify it to $ \mathbf o ( \alpha ) $.

$\endgroup$
  • $\begingroup$ can you put a link to the article where you found the proof? $\endgroup$ – souparno majumder Jan 20 '18 at 20:43
  • $\begingroup$ I'm sorry, but I can not provide the original source. It's been too long and I found better literature for my purposes. $\endgroup$ – Nima Mousavi Jan 23 '18 at 11:33
1
$\begingroup$

$o()$ refers to the Landau notation.

$$ f ( x_\alpha ) = f ( x ) + { \nabla f } ( x )'( x_a - x ) + o ( || x_a - x || )$$

Plugin the definition of $x_a$

$$= f ( x ) + \nabla f ( x )'( x - \alpha \nabla f ( x ) - x ) + o ( || x - \alpha { \nabla f } ( x ) - x || ) $$

$$ = f ( x ) + \nabla f ( x )'( - \alpha \nabla f ( x ) ) + o ( ||- \alpha { \nabla f } ( x ) || ) \qquad \qquad \quad$$

And by definition of $o$ and $||\cdot||$

$$ = f ( x ) -\alpha \underbrace{ \nabla f ( x )' \nabla f ( x )}_{||\nabla f(x)||^2} + \underbrace{o ( \alpha || { \nabla f } ( x ) || )}_{o(\alpha)} \qquad \qquad \qquad \quad \: \: \:$$

$\endgroup$
  • $\begingroup$ Why is the part with the Landau Notation included to the Taylor Series? $\endgroup$ – Nima Mousavi Aug 29 '14 at 10:30
  • $\begingroup$ $o(g)$ means (roughly) that there are more therms which converge to zero faster than $g$. So here we just consider the first few terms of the taylor series. $\endgroup$ – flawr Aug 29 '14 at 10:32
  • $\begingroup$ @Nimi Note that the Taylor expansion has an infinite number of terms. Also, as a side note: some methods in fact use more than just the first two terms (e.g. BFGS constructs the local Hessian). $\endgroup$ – lemon Aug 29 '14 at 10:34
  • $\begingroup$ Could you pls explains why it is allowed to ignore $ || \nabla f(x) || $ in o()? $\endgroup$ – Nima Mousavi Aug 29 '14 at 11:02
  • $\begingroup$ Because constants do change the behaivour of growth, you can look up the definition of $o()$ here: en.wikipedia.org/wiki/Big_O_notation#Little-o_notation and there is a nice comparitions of the different 'o's in the table right below there. Further down you find a lot more examples. You have to understand $o(g)$ represents a whole class of functions. $\endgroup$ – flawr Aug 29 '14 at 15:54
0
$\begingroup$

The equation \begin{equation*} f(x_a) = f(x) + \nabla f(x)^T (x_a - x) + o(\|x_a - x \|) \end{equation*} is a short way of saying that if $r(x_a)$ is defined by the equation \begin{equation*} f(x_a) = f(x) + \nabla f(x)^T (x_a - x) + r(x_a), \end{equation*} then $r(x_a)$ is small even when compared with $\| x_a - x\|$.

More precisely, \begin{equation*} \lim_{x_a \to x} \frac{|r(x_a)|}{\|x_a - x\|} = 0. \end{equation*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.