Is gradient descent slower for finite differences? In gradient descent, we updated each parameter $\theta_i$ in the direction which minimizes a function $f(\theta_1,\theta_2,\dots,\theta_N)$ by doing $$\theta_1 \leftarrow \theta_1 - \alpha \frac{\partial f}{\partial \theta_1}(\theta_1,\theta_2,\dots,\theta_N)$$
$$\theta_2 \leftarrow \theta_2 - \alpha \frac{\partial f}{\partial \theta_2}(\theta_1,\theta_2,\dots,\theta_N)$$
$$\vdots$$
$$\theta_N \leftarrow \theta_N - \alpha \frac{\partial f}{\partial \theta_N}(\theta_1,\theta_2,\dots,\theta_N).$$

If we have $N$ parameters, then it will involve $N$ evaluations.

If possible, obviously, we want to use this analytical form of the gradient.

But we could, of course, approximate it using finite differences,
$$\theta_1 \leftarrow \theta_1 - \alpha \frac{f(\theta_1+\varepsilon,\theta_2,\dots,\theta_N)-f(\theta_1,\theta_2,\dots,\theta_N)}{\varepsilon}$$
$$\theta_2 \leftarrow \theta_2 - \alpha \frac{f(\theta_1,\theta_2+\varepsilon,\dots,\theta_N)-f(\theta_1,\theta_2,\dots,\theta_N)}{\varepsilon}$$
$$\vdots$$
$$\theta_N \leftarrow \theta_N - \alpha \frac{f(\theta_1,\theta_2,\dots,\theta_N+\varepsilon)-f(\theta_1,\theta_2,\dots,\theta_N)}{\varepsilon}$$

This involves $N+1$ evaluations, which is negligible if $N$ is large, as is the case with deep neural networks.

Obviously, the analytical gradient is preferable since it is more accurate, and it avoids numerical problems due to $\varepsilon$ being too large or too small.

My question is: I have heard people claim that using gradient descent with the analytical derivative is faster than approximating the derivatives. Is this true? To me, it sounds like it only avoids one extra evaluation.



EDIT: Practical example:

Let's say we have
$$y=\sigma(ax)$$

$$z=by$$
where $a$ and $b$ are the parameters we want to optimize.

Gradients

Using the gradients, we would have $\nabla=\left(\frac{\partial z}{\partial a},\frac{\partial z}{\partial b} \right) = \left(bx\sigma(ax)(1-\sigma(ax)), \sigma(ax)\right)$

(I hope I didn't make a mistake there. $\frac{\partial z}{\partial a}=\frac{\partial z}{\partial y}\frac{\partial y}{\partial a}=bx\sigma'(ax)=bx\sigma(ax)(1-a\sigma(ax))$.)

For each back-propagation, we would need two evaluations for $a$ and for $b$: $\nabla(a,b)$, so that we can do...

These are the computations required:

$a \leftarrow a-\alpha bx\sigma(ax)(1-\sigma(ax))$

$b \leftarrow b-\alpha \sigma(ax)$

Finite differences

We have the differences $$\Delta=\left((z(a+\varepsilon,b)-z(a,b))/\varepsilon, (z(a,b+\varepsilon)-z(a,b))/\varepsilon \right)$$

$z(a,b)=\color{blue}{b\sigma(ax)}$

$z(a+\varepsilon,b) = \color{blue}{b\sigma(ax)} + b\sigma(\epsilon x)$

$z(a,b+\varepsilon) = \color{blue}{b\sigma(ax)} + \varepsilon\sigma(ax)$

These are the computations required:

$a \leftarrow a-\alpha b\sigma(\varepsilon x)/\varepsilon$

$b \leftarrow b-\alpha \sigma(ax)$

The terms in blue disppear in the graph because they are subtracted by themselves.
(In response to the comments)

Consider logistic regression with labels +1/-1, where the function is $f(x) = \sum log(1 + \exp(-y * (x \theta)))$ . Taking finite differences requires computing $\sum log(1 + \exp(-y * (x (\theta + \epsilon_n))))$ (where $\epsilon_n$ is a small value for only one variable) for each variable (in each evaluation, you require plugging in the current values of all other variables too). The analytical solution is $\sum residual \theta$ - you only require plugging in the current values twice. You can keep a sum of $\theta x$ to save calculations (still more calculations with the differences approach), but as your function gets more non-linear, there’s less that you can precompute between variables – e.g. if you have 3 hidden units, changing the first unit will not let you reuse computations for the others.

In terms of big-oh notation, if you are looking at number of evaluations and you consider the gradient evaluation as $O(n)$ (keep in mind vectorization makes a difference though), I guess you won’t see much difference, but if you look at others aspects you’ll see that the analytical solution requires fewer calculations.

In addition, optimization techniques such as L-BFGS will not work if you don’t use precise gradients.