How does the second derivative inform an update step in Gradient Descent?

Question

I was reading the deep learning book by Begnio, Goodfellow and Courville and there was one section where they explain the second derivative that I don't understand (section 4.31):

The second derivative tells us how the first derivative will change as we vary the input. This is important because it tells us whether a gradient step will cause as much of an improvement as we would expect based on the gradient alone.

the part in bold is what does not make sense to me.

I think I do understand what the second derivative means. The second derivative simply measures how much the gradient/tangent slope $f'(x)$ changes as we make small changes in $x$. i.e. how small changes in $x$ changes the gradient $f'(x)$. So for example, if we had a large second derivative a we made a tiny move, then the tangent line should change a lot. Thus it makes sense it measures the speed at which a tangent line becomes steep and thus why its sometimes referred as a measure of the curvature. That makes sense.

What does NOT make sense to me is that part in bold. How does it inform us at all about if a gradient step would make as much of an improvement as we would expect based on the gradient alone? I don't think I even understand what that means in english as a sentence. The main reason that it seems confusing to me is that a gradient step is independent of the second derivative, so a gradient step will change the target function whatever amount it has to. In fact the second derivative is the rate of change of the derivative and doesn't seem to hold direct info on the target function we are trying to optimize so I don't know what it means with:

gradient step will cause as much as an improvement as we would expect based on the gradient alone.

can someone explain me what this means?

Answer 1

I agree with your distaste for the writing. It seems as though you have an understanding of what is going on, but I will attempt to clarify why the second derivative is important. Consider a two-dimensional orthogonal system. Since they are orthogonal we can look at them independently, and together. This need not be the case, but I use the orthogonal system to avoid the linear algebra which may muddy the intuition .

In the $x_1$ dimension, the objective, f, varies roughly as $f=x_1^2$. In the $x_2$ dimension, the objective varies as $f = .00001x_2^2$. The minima is f(0,0) = 0.

This is the gradient descent update in each dimension:

• $x_{1,k+1} = x_{1,k} - 2\alpha x_{1,k} $

• $x_{2,k+1} = x_{2,k} - .00002\alpha x_{2,k} $

Where $\alpha$ is the learning rate. That is, According to a gradient descent update, if you start at about (1,1) then after a few iterations you will be at $\approx (0,1)$ because the gradient in the $x_2$ direction is already very near zero. True, we may have predicted this based on the fact that the gradient at every point in the $x_2$ direction is near zero, but it is still undesirable -- I think that is the point they were trying to make in the bolded sentence.

Now we note that $\frac{\partial^2 f}{\partial x_2^2} = .00002$. $\frac{\partial^2 f}{\partial x_1^2} = 2$. Dividing by this amounts to accounting for the curvature (or lack thereof) in that dimension. Now let's solve these two 1-d functions using second order information. Recall that the form is $x_{k+1} = x_k - \alpha \frac{\partial^2 f}{\partial x_k^2}^{-1} \frac{\partial f}{\partial x_k}$:

• $x_{1,k+1} = x_{1,k} - \alpha x_{1,k} $

• $x_{2,k+1} = x_{2,k} - \alpha x_{2,k} $

That is, they are converging at the same rate, exactly as we would hope they would!

Answer 2

Deviation from an approximation by linear function

An estimate of the improvement after a gradient step approximates the value $f(x_{n+1})$ in the point $x_{n+1}$ by assuming that the slope of the function is constant. It approximates the function with a linear function

Your expectation might be that for a small change of the coordinates from $s= x_{n+1} - x_n$ the change of the function is approximately linear $$f(x_{n+1}) \approx f(x_n) + \nabla f(x) (x_{n+1}-x_{n}) $$

Whether the improvement will be as much of an improvement as the one based on such linear approximation depends on the second derivative and how much the function is not constant.

If the second directional derivative (along the direction of change $s$) is positive then you will get effectively a smaller change in the function.

E.g. in one dimensional quadratic function $f(x)=ax^2 + bx +c$ you have

$$f(x_{n+1}) = f(x_{n}) + f^\prime(x_n) (x_{n+1}-x_{n}) + \frac{f^{\prime\prime}(x_n)}{2}(x_{n+1}-x_{n})^2$$

---

More generally, instead of just the second order term you have a Taylor expansion

$$f(x_{n+1}) = f(x_{n}) + \sum_{k=1}^\infty \frac{f^{(k)}(x_n)}{k!} (x_{n+1}-x_{n})^k $$

although in many practical cases for small changes $(x_{n+1}-x_{n}) \ll 1$ the higher order terms are sufficiently small or even vanish (e.g. polynomial functions).

---

Expression of the error

We can quantify the limits of the error that is can be made by using a constant slope

$$x_{n+1} \approx x_{n} + f'(x_n) (x_{n+1}-x_{n})$$

instead of a varying slope

$$x_{n+1} = x_{n} + \int_{x_{n}}^{x_{n+1}} f'(s) ds$$

The error that we can make by taking a constant slope can not be larger than the difference between the situation between the steepest slopes (up/down).

$$ \int_{x_n}^{x_{n+1}} f^\prime_{min} ds \leq \int_{x_n}^{x_{n+1}} f^\prime(s) ds \leq \int_{x_n}^{x_{n+1}} f^\prime_{max} ds $$

or

$$ f^\prime_{min} (x_{n+1}-x_{n}) \leq \int_{x_n}^{x_{n+1}} f^\prime(s) ds \leq f^\prime_{max}(x_{n+1}-x_{n})$$

When the second derivative $\vert f^{\prime \prime} \vert$ is small between $x_{n}$ and $x_{n+1}$, then the minimum of the $f^\prime$ and maximum $f^\prime$ values won't differ much.

You can also express the limits of the error of the approximation in terms of minimum and maximum values of second-order derivative.

You can view the error $\epsilon = [ f(x_n) + f'(x_n) (x_{n+1}-x_{n})) ] - f(x_{n+1})$ based on the highest and lowest possible second derivative $f''$. We assumed $f''=0$, and the error that we make can be based on the worst cases when $f''$ is either constantly at it's maximum or minimum.

$$f''_{min} 0.5(x_{n+1}-x_n)^2 \leq \epsilon \leq f''_{max} 0.5(x_{n+1}-x_n)^2$$

Often the value of $f''$ is positive near the optimum (both upper/maximum and lower/minimum bounds, because the cost function is convex near the optimum and slope flattens), which means that the error is always positive and we often make smaller steps than expected.

That is probably why the expression is using the term 'as much', because commonly the improvement after a gradient step will be less. (but this is not always true, it is just the common situation)

whether a gradient step will cause as much of an improvement as we would expect based on the gradient alone.

Answer 3

Second derivatives are used to understand the rate of change of derivatives. Considering the huge number of hyper-parameters involved in building the trained model, it is always necessary to detect early the accuracy rate of the model being trained. Many of us, spend a considerable time in training the models with different set of hyper-parameters to reach an optimal solution. Thus, early detection of the learning trend helps in saving resources. Second derivatives are one of the easiest ways to help us in early detection of the learning trends and provides the model designer a feedback to intervene and refine the hyper-parameters at a much early stage, thus saving precious time and other resources.