# Gradient Descent: Guaranteeing Cost Function Decreases

I'm reading this and am a bit confused starting around equation (9).

Suppose we have a real-valued function of many variables, $$v = v_1, v_2, ...$$

Let the gradient of our cost function, C, be: $$\nabla C = \left(\frac{\partial C}{\partial v_1}, \frac{\partial C}{\partial v_2}, ...\right) ^T$$

Then:

$$\Delta C \approx \nabla C \bullet \Delta V$$

Suppose we choose:

$$\Delta v = -n \nabla C,$$ where $n$ is a small, positive parameter.

Then we have:

$$\Delta C \approx -n \nabla C \bullet \nabla C = -n |\nabla C|^2$$

Since $$|\nabla C|^2 \geq 0,$$ this means that $$\Delta C \leq 0,$$ aka that C will always decrease, never increase, if we change $v$ as described above.

What's wrong with the above argument? I could easily imagine a non-parabolic function where I choose changes in $v$ that lead to increases in $C$...

• When you walk down a hill into a valley, do you expect your path to get steeper or less steep? – whuber Aug 12 '15 at 12:02

When a function is differentiable it is locally linear, and the error in the linear approximation is negligible in a sufficiently small neighborhood. If you take a small enough step, you are inside that neighborhood and therefore walking downhill on a nearly constant slope.

To find that small-enough step, many gradient descent methods contain a backtracking line search along the direction of steepest descent $-\nabla C$: one tries a certain step size $n$, and if it does not give a decrease in $C$, one cuts the step size in half until it does.

Assuming $C$ is a linear funciton of $v$, you'll always experience a reduction of $C$ in the direction of the negative gradient.

If $C$ is e.g. a higher-order polinomial of $v$, then you might have an increase of $C$ in the direction of the negative gradient, depending on the step-size parameter $n$. Given appropriate regularity conditions there is always a small enough $n$, which results in decrease of $C$ though. This is why in most gradient algorithms $n \to 0$.

Basically the problem with your argument is the first approximation which is unquantified. You need to use the Taylor series with remainder theorem. Then by bounding your second derivative matrix, you can guarantee to drop for a given step size.

Indeed you can make changes to $v$ so as to increase $C$.

But in the gradient descent algorithm, you want to decrease $C$ between each epoch so as to ultimately reach a local minima.

That's why $v$ is updated in this way.

• but the change in $v$ seems to say "decrease the $v_i$ component of $v$ by a certain amount. But I can imagine non-parabolic graphs where this would mean actually increasing C. I understand we want to move in the direction that decreases C. But isn't what I suggest possible when we have more than 2 components to $v$? – bclayman Aug 12 '15 at 12:50
• $\nabla C$ components can be negative so the change in $v$ does not necessarily mean decreasing the $v_i$ component. – Cloud Skywalker Aug 12 '15 at 13:03
• Ah ok, so you adjust $v_i$ by a certain amount (negative or positive), but doesn't what I've written above show that the change in $C$ will always be negative? That is, I can imagine surfaces where the change in C is positive but where the above algebra still holds. Clearly I'm missing something... – bclayman Aug 12 '15 at 13:15
• Maybe what you miss is that the above algebra does not hold for the surface you imagine. Or else I am the one that is missing something. – Cloud Skywalker Aug 12 '15 at 13:28