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

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

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

• Why is the part with the Landau Notation included to the Taylor Series? – Nima Mousavi Aug 29 '14 at 10:30
• $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. – flawr Aug 29 '14 at 10:32
• @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). – lemon Aug 29 '14 at 10:34
• Could you pls explains why it is allowed to ignore $|| \nabla f(x) ||$ in o()? – Nima Mousavi Aug 29 '14 at 11:02
• 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. – flawr Aug 29 '14 at 15:54

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*}