1
$\begingroup$

I have seen it stated that, as a rule of thumb, a backward pass in a neural network should take about twice as long as the forward pass. Examples:

measures the flops of the forward pass of a module and the flops of the backward pass is estimated as 2 times of that of the forward pass

in which it is claimed that the backward pass requires twice the number of matrix-multiplies needed in the forward pass, for a vanilla neural network

.

I unfortunately don't understand the argument made in Kaplan (not sure where the "two" in the "two matrix multiplications per layer he refers to" comes from).

In particular, any such rule would also seem to be very implementation-dependent, depending on whether local gradients are computed and cached during the forward pass, for instance. But I guess there is a standard implementation of backprop that makes this unambiguous.

If anyone can expand on the logic behind this lore or point me towards other references, I would be grateful.

$\endgroup$

2 Answers 2

1
$\begingroup$

This is a general fact of automatic/algorithmic differentiation. In the forward transport of tangents as well as any backward transport of gradients, each multiplication node splits in two on the derivative level \begin{array}{kcc} \text{node}&:&v=u·w,\\ \text{forward}&:&\dot v = \dot u·w+u·\dot w,\\ \text{backward}&:&\bar u = \bar v·w,~~~\bar w =\bar v·u, \end{array} where $\bar u=\frac{\partial L}{\partial u}$ etc. The evaluation of scalar nodes gives an equally complex operation for the node derivative and an additional scalar multiplication for the forward or backward sweep, \begin{array}{kcc} \text{node}&:&v=\phi(u)\\ \text{forward}&:&\dot v = \phi'(u)·\dot u\\ \text{backward}&:&\bar u = \bar v·\phi'(u), \end{array} which in combination is also a factor of about 2.

The structure of a layered neural network does not change the occurrence of these operations, it only reduces the organizational overhead. Overhead in general will possibly make the backward sweep slower than the forward sweep, as a tape (of some kind) of operations and values has to be constructed and read backwards. In NN this again is greatly simplified, reducing the difference, due to the layered structure already incorporating the tape.

$\endgroup$
0
$\begingroup$

The "two" in the "two matrix multiplications per layer" has nothing to do with any cached value computed in the previous feedforward pass (in fact forward pass doesn’t need any local gradient) where it only needs "one" matrix multiplication per layer denoting the term $Wx$ as shown in the standard input/output vectorial equation $a=\phi(Wx+b)$ in each layer. Thus it may be easier now to understand that for backprop applying automatic differentiation starting from the last layer to calculate derivatives of loss function w.r.t. each weight parameter in the current layer, it needs two matrix multiplication as shown in equation (1.4.6) in your second reference. The first multiplication denotes $\phi’ \times \phi$ where the former is a column vector and the latter is a row vector and its result is a matrix. And the second matrix multiplication occurs inside the calculation of $\phi’$ which is essentially an error factor vector of the input activation vector from its previous hidden layer obtained via output target error vector multiplied with a diagonal matrix of the last layer’s activation function’s derivatives at each node’s respective net input value during the forward pass if you go through the details of backprop.

$\endgroup$
4
  • $\begingroup$ Ohhh, I think I see: the point is that in terms of computational expense, the $\phi' \times \phi$ outer-product is just as expensive as a $W x$ matrix-multiply, which is the factor of two? Both O(N **2), assuming all dimensions are of size N? I was reading Kaplan as saying that there literally two canonical $W x$-type matrix-multiplies appearing somewhere, which was what I was searching for. $\endgroup$
    – user26866
    Nov 30, 2022 at 18:45
  • $\begingroup$ Still confused though. If my layers are of the form $z^\ell = W^\ell \phi(z^{\ell - 1})$ and I know the derivative $\frac{\partial L}{\partial z^\ell}$ from the preceding layer of backprop, then to get $\frac{\partial L}{\partial W^{\ell-1}}$ I would seem to need to compute $\frac{\partial z^\ell}{\partial z^{\ell-1}}$ (O(N ** 2)), matrix-multiply this into $\frac{\partial L}{\partial z^\ell}$ (another O(N ** 2)), and then also multiply this into a final $\frac{\partial z^{\ell - 1}}{\partial W^{\ell-1}}$ which would seem to be a third O(N ** 2) operation. $\endgroup$
    – user26866
    Nov 30, 2022 at 20:27
  • $\begingroup$ Generally no need to compute partial derivatives of current layer's net input $z$ wrt last layer's net input for any node in backprop algo detail. And Kaplan's notation doesn't use the usual loss function $L$ but direct final output $y$ which is a bit confusing here. But anyway the general idea here is per layer there're two matrix multiplications needed as I located above per layer. Strictly if you don't count a row error vector times a diagonal matrix, then in the starting layer there's only 1 multiplication (inside $\phi'$ no multiplication). $\endgroup$
    – cinch
    Dec 1, 2022 at 5:02
  • $\begingroup$ I didn't understand your claim about "And the second matrix multiplication occurs inside the calculation of 𝜙′". The argument of $\phi'$ was already computed in the forward pass and hence should be cached, no? $\endgroup$
    – user26866
    Dec 2, 2022 at 17:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .