Is gradient descent slower for finite differences?

Question

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.

Answer 1

(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.

Answer 2

If you have many variables, you'll have to calculate those finite differences for each one separately (meaning: evaluating the function with all the other variables), while you can usually compute the analytical gradients for all at once in a faster way.

Answer 3

Let us look at the neural network as a graph (calculation graph). Each calculation node, forwards or backwards, costs the same (correct me if I'm wrong on that point).

The neurons are the nodes, and the inputs/outputs to/from each neuron are the vertices.

Calculating f(theta) (or f(theta,… theta+epsilon,… theta)) takes a single pass over all the graph. O(v+e), using forward propagation.

Calculating backpropagation also takes a single pass over all the graph O(v+e).

Thus, calculating derivatives using backpropagation, will cost 2*O(v+e), one for forward and one for back propagation.

Also, thus, Calculating derivatives for each variable using the approximation will cost at least one pass over the graph (two for the two sided formula of the derivative), meaning O(v+e) per variable, costing a total of N*O(v+e) for all the variables.

When N is large, backpropagation becomes much faster.

Answer 4

The question of OP is: What is faster? Approximation of the derivative or analytical derivative in backpropagation algorithm? I will show on the example of original poster (OP) that the computational complexity of the approximation is higher than that of the analytical derivative in backpropagation.

OP example Here I use the example of original poster (OP) with the sigmoid activation function for the hidden layer.

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

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

Analytical derivatives

$\frac{\partial z}{\partial b} = y$

$\frac{\partial z}{\partial a} =\frac{\partial z}{\partial y}\frac{\partial y}{\partial a} =\frac{\partial z}{\partial y}\frac{\partial y}{\partial \sigma}\frac{\partial \sigma}{\partial t}\frac{\partial t}{\partial a} =b\cdot 1 \cdot \sigma(t) \cdot (1-\sigma(t)) \cdot x$

Taking into account that $z=b \cdot \sigma(t)$ and $y=\sigma(t)$ we get the following:

$\frac{\partial z}{\partial a} = z\cdot (1-y)\cdot x$

These are our derivatives:

For $a$: $z(1-y)x$

For $b$: $y$

Finite differences

$z(a,b)=z$

$z(a,b+\varepsilon) = (b+\varepsilon)\sigma(ax) = b\sigma(ax)+ \varepsilon\sigma(ax) = z + \varepsilon y$

$z(a+\varepsilon,b) = b\sigma((a+\varepsilon)x) =b\frac{1}{1+e^{-(a+\varepsilon)x}} =b\frac{1}{1+e^{-t-\varepsilon x}}$

We have previously calculated $e^{-t}$. Lets name $u=e^{-t}$

$z(a+\varepsilon,b) =b\frac{1}{1+ue^{-\varepsilon x}}$

Here $\sigma(a+b)$ is not equal to $\sigma(a)+\sigma(b)$ so you cannot easily write $z+...$ At least I did not find a way to take z value out.

$\frac{z(a,b+\varepsilon)-z(a,b)}{\varepsilon} = y$ This is the same as the derivative like in OP calculation.

$\frac{z(a+\varepsilon,b)-z(a,b)}{\varepsilon} = \frac{b\frac{1}{1+ue^{-\varepsilon x}} - z}{\varepsilon}$

these are our derivative approximations:

For $a$: $\frac{b\frac{1}{1+ue^{-\varepsilon x}} - z}{\varepsilon}$

For $b$: $y$

Comparison

In both cases you need to calculate the $z$ function at the point. Calculations for $b$ are the same. Derivative approximation for $a$ is significantly more complicated than an analytical derivative.

$\frac{b\frac{1}{1+ue^{-\varepsilon x}} - z}{\varepsilon}$ VS $z(1-y)x$