2
$\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$
3
  • $\begingroup$ can you put a link to the article where you found the proof? $\endgroup$
    – isnvi23h4
    Commented Jan 20, 2018 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$ Commented Jan 23, 2018 at 11:33
  • $\begingroup$ How is this logic? $\endgroup$
    – ABIM
    Commented Sep 15, 2020 at 8:17

2 Answers 2

2
$\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$
5
  • $\begingroup$ Why is the part with the Landau Notation included to the Taylor Series? $\endgroup$ Commented Aug 29, 2014 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
    Commented Aug 29, 2014 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
    Commented Aug 29, 2014 at 10:34
  • $\begingroup$ Could you pls explains why it is allowed to ignore $ || \nabla f(x) || $ in o()? $\endgroup$ Commented Aug 29, 2014 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
    Commented Aug 29, 2014 at 15:54
1
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .