2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $\sigma(a+b)$ is not equal to $\sigma(a)+\sigma(b)$. So your first finite difference is wrong. $\endgroup$ – keiv.fly Oct 14 '18 at 14:36
1
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ I agree, some loss functions, like cross-entropy, are designed for differentiation because the loss becomes much simpler after you differentiate it. I think the real answer involves precomputations as you mentioned. Finite differences can be used together with techniques like memoization to avoid many intermedia computations (from dynamic programming), but even then maybe it cannot reuse as much computations. It would be cool if we could come up with a pratical example where e.g. the number of multiplications is lower when using $\partial f$ than $\Delta f$. But you are closest answer. $\endgroup$ – Ricardo Cruz Oct 14 '18 at 10:33
  • $\begingroup$ I added a pratical example to my post... Can you see where I got it wrong? $\endgroup$ – Ricardo Cruz Oct 14 '18 at 11:07
  • $\begingroup$ In your example, assuming that we are still talking about some statistical model rather than some function not based on data, if you divide the target variable by $b$, then you are back to logistic regression. Again, in that specific case, if you store computations that repeat between calculations, you won’t see a difference in terms of big-oh, but you’ll see it in terms of actual calculations. $\endgroup$ – anymous.asker Oct 14 '18 at 14:22
  • $\begingroup$ Now, if it were something like $z = \sigma(y)$, you’ll see that you cannot store everything you need for all variables, and as the function becomes more complex, the less memoization you can do and you get closer to having to evaluate the function for each variable separately (i.e. plugging in the values of all other variables too, for each evaluation with one variable changed). $\endgroup$ – anymous.asker Oct 14 '18 at 14:23
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ We have the gradient: $\nabla=\left(\frac{\partial f}{\partial\theta_1}, \frac{\partial f}{\partial\theta_2}, \dots, \frac{\partial f}{\partial\theta_N}\right)$. You have to compute each one of those functions once for each variable. Therefore you have $N$ computations. Using fininite differentes, you have $N+1$ computations. $\endgroup$ – Ricardo Cruz Oct 13 '18 at 22:14
  • $\begingroup$ When I say "computations", I mean "evaluations" if that makes it clearer. You have $N$ derivatives and you need to evaluate each one of those for each parameter. You need $N$ evaluations. For finite differentes, you need $N+1$ evaluations because you need to evaluate f(a,b,c,...) and then f(a+epsilon,b,c,...), f(a,b+epsilon,c,...), and so on. $\endgroup$ – Ricardo Cruz Oct 13 '18 at 22:40
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Maybe it's easier to start with a simple model like a logistic regression first. For such a simple model, when trained using gradient descent, you don't think there is a speed penalty for using finite differences over the derivatives? $\endgroup$ – Ricardo Cruz Oct 14 '18 at 10:25
  • $\begingroup$ If the number of inputs to logistic regression is N, my analysis is still the same, isn't it? It would take a single back propagation pass to calculate all derivatives, but O(N) passes of forward propagation $\endgroup$ – Gulzar Oct 14 '18 at 11:15
0
$\begingroup$

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$

| improve this answer | |
$\endgroup$
  • $\begingroup$ Obviously, I am talking about backprop. In your example, you have two derivatives (for each backprop) that you need to evaluate: $\frac{dy}{da}(x)$ and $\frac{dz}{dy}(x)$ because you have only $N=2$ variables. Using finite differences you would have 3 evaluations in your example. $\endgroup$ – Ricardo Cruz Oct 14 '18 at 10:15
  • $\begingroup$ I added your example to my post. I added a non-linearity to make it more realistic. $\endgroup$ – Ricardo Cruz Oct 14 '18 at 11:08
  • $\begingroup$ I changed the answer according to the example. $\endgroup$ – keiv.fly Oct 14 '18 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.