Answers.Body: <p>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
  <span class="math-container">\begin{array}{kcc}
  \text{node}&amp;:&amp;v=u·w,\\
  \text{forward}&amp;:&amp;\dot v = \dot u·w+u·\dot w,\\
  \text{backward}&amp;:&amp;\bar u = \bar v·w,~~~\bar w =\bar v·u,
  \end{array}</span>
  where <span class="math-container">$\bar u=\frac{\partial L}{\partial u}$</span> 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,
  <span class="math-container">\begin{array}{kcc}
  \text{node}&amp;:&amp;v=\phi(u)\\
  \text{forward}&amp;:&amp;\dot v = \phi'(u)·\dot u\\
  \text{backward}&amp;:&amp;\bar u = \bar v·\phi'(u),
  \end{array}</span>
  which in combination is also a factor of about 2.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-12-01T08:30:19.603Z
Answers.LastActivityDate: 2022-12-01T08:30:19.603Z
Answers.UserDisplayName: Lutz Lehmann
Answers.Body: <p>The reason is more intuitive than you would think. Assume that most of the cost of a NN's forward backward pass comes from Linear or Convolution layers, that effectively do:</p>
  <pre><code>y = W @ x
  </code></pre>
  <p>Where <code>W</code> is a trainable parameter.</p>
  <p>The forward pass makes 1 matrix multiply (<code>W @ x</code>).</p>
  <p>During the backward pass, the incoming gradients from <code>dy</code> need to be propagated to both the weights as <code>dW</code>, as well as input tensor (<code>x</code>) as <code>dx</code>. To do this, you need to calculate the gradients <code>dW</code> and <code>dx</code> using a single matrix multiply each. Hence, the cost of the backward pass for a matrix multiply is twice the cost of a matrix multiply for the forward pass.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-25T04:25:35.427Z
Answers.LastActivityDate: 2024-12-25T04:25:35.427Z
Answers.UserDisplayName: dhruvbird
Answers.Body: <p>The &quot;two&quot; in the &quot;two matrix multiplications per layer&quot; 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 &quot;one&quot; matrix multiplication per layer denoting the term <span class="math-container">$Wx$</span> as shown in the standard input/output vectorial equation <span class="math-container">$a=\phi(Wx+b)$</span> 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 <span class="math-container">$\phi’ \times \phi$</span> 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 <span class="math-container">$\phi’$</span> 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-30T18:45:22.860Z
Answers.Text: 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.
Answers.UserDisplayName: user26866
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-30T20:27:23.423Z
Answers.Text: 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.
Answers.UserDisplayName: user26866
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-12-01T05:02:16.633Z
Answers.Text: 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](https://en.wikipedia.org/wiki/Backpropagation) 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).
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-12-02T17:19:53.353Z
Answers.Text: 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?
Answers.UserDisplayName: user26866
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-30T08:54:18.227Z
Answers.LastActivityDate: 2022-11-30T09:00:10.277Z
Answers.LastEditDate: 2022-11-30T09:00:10.277Z
Answers.UserDisplayName: cinch
Body: <p>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:</p>
  <ul>
  <li>From <a href="https://www.deepspeed.ai/tutorials/flops-profiler/#flops-measurement" rel="nofollow noreferrer">DeepSpeed's Flops Profiler</a> docs, the profiler:</li>
  </ul>
  <blockquote>
  <p>measures the flops of the forward pass of a module and the flops of
  the backward pass is estimated as <code>2</code> times of that of the forward
  pass</p>
  </blockquote>
  <ul>
  <li>Page 7 of Jared Kaplan's <a href="https://sites.krieger.jhu.edu/jared-kaplan/files/2019/04/ContemporaryMLforPhysicists.pdf" rel="nofollow noreferrer">Machine Learning notes</a>:</li>
  </ul>
  <blockquote>
  <p>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</p>
  </blockquote>
  <p>.</p>
  <p>I unfortunately don't understand the argument made in Kaplan (not sure where the &quot;<em>two</em>&quot; in the &quot;<em>two matrix multiplications per layer he refers to</em>&quot; comes from).</p>
  <p>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.</p>
  <p>If anyone can expand on the logic behind this lore or point me towards other references, I would be grateful.</p>
  
Tags: <neural-networks><backpropagation><deep-neural-networks><time-complexity>
Title: Why should one expect the backward pass to take twice as long as the forward pass?
UserDisplayName: user26866
ThreadText: # Why should one expect the backward pass to take twice as long as the forward pass?
  
  (Asked by: username_0 on 2022-11-30)
  
  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:
  
  * From [DeepSpeed's Flops Profiler](https://www.deepspeed.ai/tutorials/flops-profiler/#flops-measurement) docs, the profiler:
  
  > 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
  
  * Page 7 of Jared Kaplan's [Machine Learning notes](https://sites.krieger.jhu.edu/jared-kaplan/files/2019/04/ContemporaryMLforPhysicists.pdf):
  
  > 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.
  
  **Tags:** neural-networks, backpropagation, deep-neural-networks, time-complexity
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2022-12-01. Score: 2
  
  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.
  
  
  ---
  
  ### Answer by username_2 on 2024-12-25. Score: 1
  
  The reason is more intuitive than you would think. Assume that most of the cost of a NN's forward backward pass comes from Linear or Convolution layers, that effectively do:
  y = W @ x
  
  Where W is a trainable parameter.
  The forward pass makes 1 matrix multiply (W @ x).
  During the backward pass, the incoming gradients from dy need to be propagated to both the weights as dW, as well as input tensor (x) as dx. To do this, you need to calculate the gradients dW and dx using a single matrix multiply each. Hence, the cost of the backward pass for a matrix multiply is twice the cost of a matrix multiply for the forward pass.
  
  
  ---
  
  ### Answer by username_3 on 2022-11-30. Score: 0
  
  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.
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_0**: 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.  
  > **username_3**: 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](https://en.wikipedia.org/wiki/Backpropagation) 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).  
  > **username_0**: 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?  
  
  ---
  
  