Answers.Body: <h2>Introduction</h2>
  
  <p>First of all, it's completely normal that you are confused because nobody really explains this well and accurately enough. Here's my partial attempt to do that. So, this answer doesn't <em>completely</em> answer the original question. In fact, I leave some unanswered questions at the end (that I will eventually answer).</p>
  
  <h2>The gradient is a linear operator</h2>
  
  <p>The gradient operator <span class="math-container">$\nabla$</span> is a linear operator, because, for some <span class="math-container">$f : \mathbb{R} \rightarrow \mathbb{R} $</span> and <span class="math-container">$g: \mathbb{R} \rightarrow \mathbb{R}$</span>, the following two conditions hold.</p>
  
  <ul>
  <li><span class="math-container">$\nabla(f + g)(x) = (\nabla f)(x) + (\nabla g)(x),\; \forall x \in \mathbb{R}$</span></li>
  <li><span class="math-container">$\nabla(kf)(x) = k(\nabla f)(x),\; \forall k, x \in \mathbb{R}$</span></li>
  </ul>
  
  <p><em>In other words, the restriction, in this case, is that the functions are evaluated at the same point <span class="math-container">$x$</span> in the domain. This is a very important restriction to understand the answer to your question below!</em></p>
  
  <p>The linearity of the gradient directly follows from the linearity of the derivative. See a <a href="https://www.youtube.com/watch?v=CfaaOc7dZIs" rel="noreferrer">simple proof here</a>. </p>
  
  <h3>Example</h3>
  
  <p>For example, let <span class="math-container">$f(x) = x^2$</span>, <span class="math-container">$g(x) = x^3$</span> and <span class="math-container">$h(x) = f(x) + g(x) = x^2 + x^3$</span>, then <span class="math-container">$\frac{dh}{dx} = \frac{d (x^2 + x^3)}{d x} = \frac{d x^2}{d x} + \frac{d x^3}{d x} = \frac{d f}{d x} + \frac{d g}{d x} = 2x + 3x$</span>. </p>
  
  <p>Note that both <span class="math-container">$f$</span> and <span class="math-container">$g$</span> are not linear functions (i.e. straight-lines), so the linearity of the gradients is not just applicable in the case of straight-lines.</p>
  
  <h2>Straight-lines are not necessarily linear maps</h2>
  
  <p>Before proceeding, I want to note that there are at least two notions of <em>linearity</em>. </p>
  
  <ol>
  <li><p>There's the notion of a <a href="https://en.wikipedia.org/wiki/Linear_map" rel="noreferrer">linear map</a> (or linear operator), i.e. which is the definition above (i.e. the gradient operator is a linear operator because it satisfies the two conditions, i.e. it preserves addition and scalar multiplication). </p></li>
  <li><p>There's the notion of a straight-line function: <span class="math-container">$f(x) = c*x + k$</span>. A function can be a straight-line and not be a linear map. For example, <span class="math-container">$f(x) = x+1$</span> is a straight-line but it doesn't satisfy the conditions above. More precisely, in general, <span class="math-container">$f(x+y) \neq f(x) + f(y)$</span>, and you can easily verify that this is the case if <span class="math-container">$x = 2$</span> and <span class="math-container">$y=3$</span> (i.e. <span class="math-container">$f(2+3) = 6$</span>, <span class="math-container">$f(2) = 3$</span>, <span class="math-container">$f(3) = 4$</span>, but <span class="math-container">$f(2) + f(3) = 7 \neq f(2+3)$</span>.</p></li>
  </ol>
  
  <h2>Neural networks</h2>
  
  <p>A neural network is a composition of (typically) non-linear functions (let's ignore the case of linear functions), which can thus be represented as <span class="math-container">$$y'_{\theta}= f^{L}_{\theta_L} \circ f^{L-1}_{\theta_{L-1}} \circ \dots \circ f_{\theta_1},$$</span> where </p>
  
  <ul>
  <li><span class="math-container">$f^{l}_{\theta_l}$</span> is the <span class="math-container">$i$</span>th layer of your neural network and it 
  computes a non-linear function</li>
  <li><span class="math-container">${\theta_l}$</span> is a vector of parameters associated with the <span class="math-container">$l$</span>th layer</li>
  <li><span class="math-container">$L$</span> is the number of layers, </li>
  <li><span class="math-container">$y'_{\theta}$</span> is your neural network, </li>
  <li><span class="math-container">$\theta$</span> is a vector containing all parameters of the neural network</li>
  <li><span class="math-container">$y'_{\theta}(x)$</span> is the output of your neural network</li>
  <li><span class="math-container">$\circ $</span> means the composition of functions</li>
  </ul>
  
  <p>Given that <span class="math-container">$f^l_{\theta}$</span> are non-linear, <span class="math-container">$y'_{\theta}$</span> is also a non-linear function of the input <span class="math-container">$x$</span>. This notion of linearity is the second one above (i.e. <span class="math-container">$y'_{\theta}$</span> is not a straight-line). In fact, neural networks are typically composed of sigmoids, ReLUs, and hyperbolic tangents, which are not straight-lines.</p>
  
  <h2>Sum of squared errors</h2>
  
  <p>Now, for simplicity, let's consider the sum of squared error (SSE) as the loss function of your neural network, which is defined as</p>
  
  <p><span class="math-container">$$
  \mathcal{L}_{\theta}(\mathbf{x}, \mathbf{y}) = \sum_{i=1}^N  \mathcal{S}_{\theta}(\mathbf{x}_i, \mathbf{y}_i) = \sum_{i=1}^N (\mathbf{y}_i - y'_{\theta}(\mathbf{x}_i))^2
  $$</span>
  where </p>
  
  <ul>
  <li><span class="math-container">$\mathbf{x} \in \mathbb{R}$</span> and <span class="math-container">$\mathbf{y} \in \mathbb{R}$</span> are vectors of inputs and labels, respectively</li>
  <li><span class="math-container">$\mathbf{y}_i$</span> is the label for the <span class="math-container">$i$</span>th input <span class="math-container">$\mathbf{x}_i$</span></li>
  <li><span class="math-container">$\mathcal{S}_{\theta}(\mathbf{x}_i, \mathbf{y}_i) = (\mathbf{y}_i - y'_{\theta}(\mathbf{x}_i))^2$</span></li>
  </ul>
  
  <h2>Sum of gradients vs gradient of a sum</h2>
  
  <p>Given the gradient is a linear operator, one could think that computing the sum of the gradients is equal to the gradient of the sums.</p>
  
  <p>However, in our case, we are summing <span class="math-container">$\mathcal{S}_{\theta}(\mathbf{x}_i, \mathbf{y}_i)$</span> and, in general, <span class="math-container">$\mathbf{x}_i \neq \mathbf{x}_j$</span>, for <span class="math-container">$i \neq j$</span>. So, essentially, the SSE is the sum of the same function, i.e. <span class="math-container">$S_{\theta}$</span>, evaluated at different points of the domain. However, the definition of a linear map applies when the functions are evaluated at the same point in the domain, as I said above.</p>
  
  <p>So, in general, in the case of neural networks with SSE, the gradient of the sum may not be equal to the sum of gradients, i.e. the definition of the linear operator for the gradient doesn't apply here because we are evaluating every squared error at different points of their domains.</p>
  
  <h2>Stochastic gradient descent</h2>
  
  <p>The idea of stochastic gradient descent is to approximate the <em>true gradient</em> (i.e. the gradient that would be computed with all training examples) with a <em>noisy gradient</em> (which is an approximation of the true gradient).</p>
  
  <h2>How does the noisy gradient approximate the true gradient?</h2>
  
  <p>In the case of mini-batch (<span class="math-container">$M \leq N$</span>, where <span class="math-container">$M$</span> is the size of the mini-batch and <span class="math-container">$N$</span> is the total number of training examples), this is actually a sum of the gradients, one for each example in the mini-batch. </p>
  
  <p>The papers <a href="https://www.ics.uci.edu/~welling/publications/papers/stoclangevin_v6.pdf" rel="noreferrer">Bayesian Learning via Stochastic Gradient Langevin Dynamics</a> (equation 1) or <a href="https://arxiv.org/pdf/1312.6114.pdf" rel="noreferrer">Auto-Encoding Variational Bayes</a> (in section 2.2) use this type of approximation. See also <a href="http://www.princeton.edu/~yc5/ele522_optimization/lectures/stochastic_gradient.pdf" rel="noreferrer">these slides</a>.</p>
  
  <h3>Why?</h3>
  
  <p>To give you some intuition of why we sum the gradients of the error of each input point <span class="math-container">$\mathbf{x}_i$</span>, let's consider the case <span class="math-container">$M=1$</span>, which is often referred to as the (actual) stochastic gradient descent algorithm. </p>
  
  <p>Let's assume we uniformly sample an arbitrary tuple <span class="math-container">$(\mathbf{x}_j, \mathbf{y}_j)$</span> from the dataset <span class="math-container">$\mathcal{D} = \{ (\mathbf{x}_i, \mathbf{y}_i) \}_{i=1}^N$</span>. </p>
  
  <p>Formally, we want to show that </p>
  
  <p><span class="math-container">\begin{align}
  \nabla_{\theta} \mathcal{L}_{\theta}(\mathbf{x}, \mathbf{y}) 
  &amp;=
  \mathbb{E}_{(\mathbf{x}_j, \mathbf{y}_j) \sim \mathbb{U}}\left[ \nabla_{\theta} \mathcal{S}_{\theta} \right] \label{1} \tag{1}
  \end{align}</span></p>
  
  <p>where </p>
  
  <ul>
  <li><p><span class="math-container">$\nabla_{\theta} \mathcal{S}_{\theta}$</span> is the gradient of <span class="math-container">$\mathcal{S}_{\theta}$</span> with respect to the parameters <span class="math-container">$\theta$</span></p></li>
  <li><p><span class="math-container">$\mathbb{E}_{(\mathbf{x}_j, \mathbf{y}_j) \sim \mathbb{U}}$</span> is the expectation with respect to the random variable associated with a sample <span class="math-container">$(\mathbf{x}_j, \mathbf{y}_j)$</span> from the uniform distribution <span class="math-container">$\mathbb{U}$</span></p></li>
  </ul>
  
  <p>Under some conditions (see <a href="https://math.stackexchange.com/q/217702/168764">this</a>), we can exchange the expectation and gradient operators, so \ref{1} becomes
  <span class="math-container">\begin{align}
  \nabla_{\theta} \mathcal{L}_{\theta}(\mathbf{x}, \mathbf{y}) 
  &amp;=
  \nabla_{\theta} \mathbb{E}_{(\mathbf{x}_j, \mathbf{y}_j) \sim \mathbb{U}}\left[  \mathcal{S}_{\theta} \right] 
  \label{2} \tag{2}
  \end{align}</span>
  Given that we uniformly sample, the probability of sampling an arbitrary <span class="math-container">$(\mathbf{x}_j, \mathbf{y}_j)$</span> is <span class="math-container">$\frac{1}{N}$</span>. So, equation \ref{2} becomes
  <span class="math-container">\begin{align}
  \nabla_{\theta} \mathcal{L}_{\theta} (\mathbf{x}, \mathbf{y}) 
  &amp;=
  \nabla_{\theta} \sum_{i=1}^N \frac{1}{N} \mathcal{S}_{\theta}(\mathbf{x}_i, \mathbf{y}_i) \\
  &amp;=
  \nabla_{\theta} \frac{1}{N}  \sum_{i=1}^N \mathcal{S}_{\theta}(\mathbf{x}_i, \mathbf{y}_i) 
  \end{align}</span></p>
  
  <p>Note that <span class="math-container">$\frac{1}{N}$</span> is a constant with respect to the summation variable <span class="math-container">$i$</span> and so it can be taken out of the summation.</p>
  
  <p>This shows that the gradient with respect to <span class="math-container">$\theta$</span> of the loss function <span class="math-container">$\mathcal{L}_{\theta}$</span> that includes all training examples is equivalent, in expectation, to the gradient of <span class="math-container">$\mathcal{S}_{\theta}$</span> (the loss function of one training example). </p>
  
  <h2>Questions</h2>
  
  <ol>
  <li><p>How can we extend the previous proof to the case <span class="math-container">$1 &lt; M \leq N$</span>?</p></li>
  <li><p>Which conditions need exactly to be satisfied so that we can exchange the gradient and the expectation operators? And are they satisfied in the case of typical loss functions, or sometimes they aren't (but in which cases)?</p></li>
  <li><p>What is the relationship between the proof above and the linearity of the gradient?</p>
  
  <ul>
  <li>In the proof above, we are dealing with expectations and probabilities!</li>
  </ul></li>
  <li><p>What would the gradient of a sum of errors represent? Can we still use it in place of the sum of gradients? </p></li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-18T23:10:06.870Z
Answers.LastActivityDate: 2020-05-01T23:12:31.317Z
Answers.LastEditDate: 2020-05-01T23:12:31.317Z
Answers.UserDisplayName: nbro
Answers.Body: <blockquote>
  <p>do I have to:</p>
  <ul>
  <li><p>forward propagate</p>
  </li>
  <li><p>calculate error</p>
  </li>
  <li><p>calculate all gradients</p>
  </li>
  <li><p>...repeatedly over all samples in the batch, and then average all gradients and apply the weight change?</p>
  </li>
  </ul>
  </blockquote>
  <p>Yes, that is correct. You can save a bit of memory by summing gradients as you go. Once you have calculated the gradients for one example for the weights of one layer, then you do not re-use the individual gradients again, so you can just keep a sum. Alternatively for speed, you can calculate a minibatch of gradients in parallel, as each example is independent - which is a major part of why GPU acceleration is so effective in neural network training.</p>
  <p>It is <em>critical</em> to getting correct results that you calculate the gradient of the loss function with respect to each example input/output pair separately. Once you have done that, you can average the gradients across a batch or mini-batch to estimate a true gradient for the dataset which can be used to take a gradient descent step.</p>
  <blockquote>
  <p>recently I have read somewhere that you basically only average the error of each example in the batch, and then calculate the gradients at the end of each batch.</p>
  </blockquote>
  <p>Without a reference it is hard to tell whether this is an error in the &quot;somewhere&quot;, or you have misunderstood, or there is a specific context.</p>
  <p>If by &quot;error&quot; you mean the literal difference <span class="math-container">$\hat{y}_i - y_i$</span>, where <span class="math-container">$\hat{y}_i$</span> is your estimate for data input <span class="math-container">$i$</span> and <span class="math-container">$y_i$</span> is the ground-truth training value, then that <em>is</em> the gradient for many loss functions and activation function pairs. For instance, it is the error gradient for mean square error and linear output. Some texts loosely refer to this as the &quot;error&quot;, and talk about backpropagating &quot;the error&quot;, but actually it is a gradient.</p>
  <p>In addition, if the article was referring to linear regression, logistic regression or softmax regression, everything else is linear - in those specific models then you can just &quot;average the error&quot; and use that as the gradient.</p>
  <p>In general, however, the statement is incorrect because a neural network with one or more hidden layers has many non-linearities that will give different results when calculating average first then backpropagating vs taking backpropagating first the averaging - that is <span class="math-container">$f'(\mu(Y))$</span> vs <span class="math-container">$\mu(f'(Y))$</span> where <span class="math-container">$f'$</span> is the derivative of the transfer function and <span class="math-container">$\mu$</span> is the mean for the batch (i.e. <span class="math-container">$\mu(Y) = \frac{1}{N}\sum_{i=1}^{N} y_i$</span> and <span class="math-container">$Y$</span> represents all the <span class="math-container">$y_i$</span> in a given batch of size <span class="math-container">$N$</span>)</p>
  <p>When <span class="math-container">$y_i = f(x_i) = ax_i +b$</span> i.e. the transfer function is linear, then <span class="math-container">$f'(\mu(Y)) = \mu(f'(Y)) = \frac{a}{N}\sum_{i=1}^N x_i$</span>, but almost all useful loss functions and all transfer functions except some output layers in neural networks are non-linear. For those, <span class="math-container">$f'(\mu(Y)) \neq \mu(f'(Y))$</span>.</p>
  <p>A simple example would show this, if we start a small minibatch back propagation with the loss function (as opposed to its gradient).</p>
  <p>Say you had the following data for regression:</p>
  <pre><code>  x    y
  
    1    2
    1    4
  </code></pre>
  <p>You want a model that can regress to least mean squared error <span class="math-container">$y$</span> when given an input <span class="math-container">$x = 1$</span>. The best model should predict <span class="math-container">$3$</span> in that case.</p>
  <p>If your model has converged, the average MSE of the dataset is <span class="math-container">$1$</span>. Using that would make your model move <em>away</em> from convergence and it will perform worse.</p>
  <p>If you first take the gradients, then average those, you will calculate <span class="math-container">$0$</span>. A simple gradient update step using that value will make no change, leaving the model in the optimal position.</p>
  <p>This issue occurs on every hidden layer in a neural network, so in general you cannot simply resolve the loss function gradient and start with the average error gradient at the output. You would still hit the inequality <span class="math-container">$f'(\mu(Y)) \neq \mu(f'(Y))$</span> on each nonlinearly.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T17:23:32.547Z
Answers.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/106917/discussion-on-answer-by-neil-slater-what-exactly-is-averaged-when-doing-batch-gr).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T12:44:32.483Z
Answers.LastActivityDate: 2020-04-19T17:48:37.530Z
Answers.LastEditDate: 2020-06-17T09:57:20.710Z
Answers.UserDisplayName: Neil Slater
Body: <p>I have a question about how the averaging works when doing mini-batch gradient descent.</p>
  
  <p>I think I now understood the general gradient descent algorithm, but only for online learning. When doing mini-batch gradient descent, do I have to:</p>
  
  <ul>
  <li><p>forward propagate</p></li>
  <li><p>calculate error</p></li>
  <li><p>calculate all gradients</p></li>
  </ul>
  
  <p>...repeatedly over all samples in the batch, and then average all gradients and apply the weight change? </p>
  
  <p>I thought it would work that way, but recently I have read somewhere that you basically only average the error of each example in the batch, and then calculate the gradients at the end of each batch. That left me wondering though, because, the activations of which sample in the mini-batch am I supposed to use to calculate the gradients at the end of every batch?</p>
  
  <p>It would be nice if somebody could explain what exactly happens during mini-batch gradient descent, and what actually gets calculated and averaged.</p>
  
Tags: <backpropagation><gradient-descent><feedforward-neural-networks><stochastic-gradient-descent><mini-batch-gradient-descent>
Title: What exactly is averaged when doing batch gradient descent?
UserDisplayName: Ben
ThreadText: # What exactly is averaged when doing batch gradient descent?
  
  (Asked by: username_0 on 2020-04-18)
  
  I have a question about how the averaging works when doing mini-batch gradient descent.
  
  I think I now understood the general gradient descent algorithm, but only for online learning. When doing mini-batch gradient descent, do I have to:
  
  * forward propagate
  * calculate error
  * calculate all gradients
  
  ...repeatedly over all samples in the batch, and then average all gradients and apply the weight change?
  
  I thought it would work that way, but recently I have read somewhere that you basically only average the error of each example in the batch, and then calculate the gradients at the end of each batch. That left me wondering though, because, the activations of which sample in the mini-batch am I supposed to use to calculate the gradients at the end of every batch?
  
  It would be nice if somebody could explain what exactly happens during mini-batch gradient descent, and what actually gets calculated and averaged.
  
  **Tags:** backpropagation, gradient-descent, feedforward-neural-networks, stochastic-gradient-descent, mini-batch-gradient-descent
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-04-18. Score: 13
  
  ## Introduction
  
  First of all, it's completely normal that you are confused because nobody really explains this well and accurately enough. Here's my partial attempt to do that. So, this answer doesn't *completely* answer the original question. In fact, I leave some unanswered questions at the end (that I will eventually answer).
  
  ## The gradient is a linear operator
  
  The gradient operator $\nabla$ is a linear operator, because, for some $f : \mathbb{R} \rightarrow \mathbb{R} $ and $g: \mathbb{R} \rightarrow \mathbb{R}$, the following two conditions hold.
  
  * $\nabla(f + g)(x) = (\nabla f)(x) + (\nabla g)(x),\; \forall x \in \mathbb{R}$
  * $\nabla(kf)(x) = k(\nabla f)(x),\; \forall k, x \in \mathbb{R}$
  
  *In other words, the restriction, in this case, is that the functions are evaluated at the same point $x$ in the domain. This is a very important restriction to understand the answer to your question below!*
  
  The linearity of the gradient directly follows from the linearity of the derivative. See a [simple proof here](https://www.youtube.com/watch?v=CfaaOc7dZIs).
  
  ### Example
  
  For example, let $f(x) = x^2$, $g(x) = x^3$ and $h(x) = f(x) + g(x) = x^2 + x^3$, then $\frac{dh}{dx} = \frac{d (x^2 + x^3)}{d x} = \frac{d x^2}{d x} + \frac{d x^3}{d x} = \frac{d f}{d x} + \frac{d g}{d x} = 2x + 3x$.
  
  Note that both $f$ and $g$ are not linear functions (i.e. straight-lines), so the linearity of the gradients is not just applicable in the case of straight-lines.
  
  ## Straight-lines are not necessarily linear maps
  
  Before proceeding, I want to note that there are at least two notions of *linearity*.
  
  1. There's the notion of a [linear map](https://en.wikipedia.org/wiki/Linear_map) (or linear operator), i.e. which is the definition above (i.e. the gradient operator is a linear operator because it satisfies the two conditions, i.e. it preserves addition and scalar multiplication).
  2. There's the notion of a straight-line function: $f(x) = c\*x + k$. A function can be a straight-line and not be a linear map. For example, $f(x) = x+1$ is a straight-line but it doesn't satisfy the conditions above. More precisely, in general, $f(x+y) \neq f(x) + f(y)$, and you can easily verify that this is the case if $x = 2$ and $y=3$ (i.e. $f(2+3) = 6$, $f(2) = 3$, $f(3) = 4$, but $f(2) + f(3) = 7 \neq f(2+3)$.
  
  ## Neural networks
  
  A neural network is a composition of (typically) non-linear functions (let's ignore the case of linear functions), which can thus be represented as $$y'\_{\theta}= f^{L}\_{\theta\_L} \circ f^{L-1}\_{\theta\_{L-1}} \circ \dots \circ f\_{\theta\_1},$$ where
  
  * $f^{l}\_{\theta\_l}$ is the $i$th layer of your neural network and it
    computes a non-linear function
  * ${\theta\_l}$ is a vector of parameters associated with the $l$th layer
  * $L$ is the number of layers,
  * $y'\_{\theta}$ is your neural network,
  * $\theta$ is a vector containing all parameters of the neural network
  * $y'\_{\theta}(x)$ is the output of your neural network
  * $\circ $ means the composition of functions
  
  Given that $f^l\_{\theta}$ are non-linear, $y'\_{\theta}$ is also a non-linear function of the input $x$. This notion of linearity is the second one above (i.e. $y'\_{\theta}$ is not a straight-line). In fact, neural networks are typically composed of sigmoids, ReLUs, and hyperbolic tangents, which are not straight-lines.
  
  ## Sum of squared errors
  
  Now, for simplicity, let's consider the sum of squared error (SSE) as the loss function of your neural network, which is defined as
  
  $$
  \mathcal{L}\_{\theta}(\mathbf{x}, \mathbf{y}) = \sum\_{i=1}^N \mathcal{S}\_{\theta}(\mathbf{x}\_i, \mathbf{y}\_i) = \sum\_{i=1}^N (\mathbf{y}\_i - y'\_{\theta}(\mathbf{x}\_i))^2
  $$
  where
  
  * $\mathbf{x} \in \mathbb{R}$ and $\mathbf{y} \in \mathbb{R}$ are vectors of inputs and labels, respectively
  * $\mathbf{y}\_i$ is the label for the $i$th input $\mathbf{x}\_i$
  * $\mathcal{S}\_{\theta}(\mathbf{x}\_i, \mathbf{y}\_i) = (\mathbf{y}\_i - y'\_{\theta}(\mathbf{x}\_i))^2$
  
  ## Sum of gradients vs gradient of a sum
  
  Given the gradient is a linear operator, one could think that computing the sum of the gradients is equal to the gradient of the sums.
  
  However, in our case, we are summing $\mathcal{S}\_{\theta}(\mathbf{x}\_i, \mathbf{y}\_i)$ and, in general, $\mathbf{x}\_i \neq \mathbf{x}\_j$, for $i \neq j$. So, essentially, the SSE is the sum of the same function, i.e. $S\_{\theta}$, evaluated at different points of the domain. However, the definition of a linear map applies when the functions are evaluated at the same point in the domain, as I said above.
  
  So, in general, in the case of neural networks with SSE, the gradient of the sum may not be equal to the sum of gradients, i.e. the definition of the linear operator for the gradient doesn't apply here because we are evaluating every squared error at different points of their domains.
  
  ## Stochastic gradient descent
  
  The idea of stochastic gradient descent is to approximate the *true gradient* (i.e. the gradient that would be computed with all training examples) with a *noisy gradient* (which is an approximation of the true gradient).
  
  ## How does the noisy gradient approximate the true gradient?
  
  In the case of mini-batch ($M \leq N$, where $M$ is the size of the mini-batch and $N$ is the total number of training examples), this is actually a sum of the gradients, one for each example in the mini-batch.
  
  The papers [Bayesian Learning via Stochastic Gradient Langevin Dynamics](https://www.ics.uci.edu/~welling/publications/papers/stoclangevin_v6.pdf) (equation 1) or [Auto-Encoding Variational Bayes](https://arxiv.org/pdf/1312.6114.pdf) (in section 2.2) use this type of approximation. See also [these slides](http://www.princeton.edu/~yc5/ele522_optimization/lectures/stochastic_gradient.pdf).
  
  ### Why?
  
  To give you some intuition of why we sum the gradients of the error of each input point $\mathbf{x}\_i$, let's consider the case $M=1$, which is often referred to as the (actual) stochastic gradient descent algorithm.
  
  Let's assume we uniformly sample an arbitrary tuple $(\mathbf{x}\_j, \mathbf{y}\_j)$ from the dataset $\mathcal{D} = \{ (\mathbf{x}\_i, \mathbf{y}\_i) \}\_{i=1}^N$.
  
  Formally, we want to show that
  
  \begin{align}
  \nabla\_{\theta} \mathcal{L}\_{\theta}(\mathbf{x}, \mathbf{y})
  &=
  \mathbb{E}\_{(\mathbf{x}\_j, \mathbf{y}\_j) \sim \mathbb{U}}\left[ \nabla\_{\theta} \mathcal{S}\_{\theta} \right] \label{1} \tag{1}
  \end{align}
  
  where
  
  * $\nabla\_{\theta} \mathcal{S}\_{\theta}$ is the gradient of $\mathcal{S}\_{\theta}$ with respect to the parameters $\theta$
  * $\mathbb{E}\_{(\mathbf{x}\_j, \mathbf{y}\_j) \sim \mathbb{U}}$ is the expectation with respect to the random variable associated with a sample $(\mathbf{x}\_j, \mathbf{y}\_j)$ from the uniform distribution $\mathbb{U}$
  
  Under some conditions (see [this](https://math.stackexchange.com/q/217702/168764)), we can exchange the expectation and gradient operators, so \ref{1} becomes
  \begin{align}
  \nabla\_{\theta} \mathcal{L}\_{\theta}(\mathbf{x}, \mathbf{y})
  &=
  \nabla\_{\theta} \mathbb{E}\_{(\mathbf{x}\_j, \mathbf{y}\_j) \sim \mathbb{U}}\left[ \mathcal{S}\_{\theta} \right]
  \label{2} \tag{2}
  \end{align}
  Given that we uniformly sample, the probability of sampling an arbitrary $(\mathbf{x}\_j, \mathbf{y}\_j)$ is $\frac{1}{N}$. So, equation \ref{2} becomes
  \begin{align}
  \nabla\_{\theta} \mathcal{L}\_{\theta} (\mathbf{x}, \mathbf{y})
  &=
  \nabla\_{\theta} \sum\_{i=1}^N \frac{1}{N} \mathcal{S}\_{\theta}(\mathbf{x}\_i, \mathbf{y}\_i) \\
  &=
  \nabla\_{\theta} \frac{1}{N} \sum\_{i=1}^N \mathcal{S}\_{\theta}(\mathbf{x}\_i, \mathbf{y}\_i)
  \end{align}
  
  Note that $\frac{1}{N}$ is a constant with respect to the summation variable $i$ and so it can be taken out of the summation.
  
  This shows that the gradient with respect to $\theta$ of the loss function $\mathcal{L}\_{\theta}$ that includes all training examples is equivalent, in expectation, to the gradient of $\mathcal{S}\_{\theta}$ (the loss function of one training example).
  
  ## Questions
  
  1. How can we extend the previous proof to the case $1 < M \leq N$?
  2. Which conditions need exactly to be satisfied so that we can exchange the gradient and the expectation operators? And are they satisfied in the case of typical loss functions, or sometimes they aren't (but in which cases)?
  3. What is the relationship between the proof above and the linearity of the gradient?
  
     * In the proof above, we are dealing with expectations and probabilities!
  4. What would the gradient of a sum of errors represent? Can we still use it in place of the sum of gradients?
  
  
  ---
  
  ### Answer by username_2 on 2020-04-19. Score: 4
  
  do I have to:
  
  forward propagate
  
  calculate error
  
  calculate all gradients
  
  ...repeatedly over all samples in the batch, and then average all gradients and apply the weight change?
  
  
  
  Yes, that is correct. You can save a bit of memory by summing gradients as you go. Once you have calculated the gradients for one example for the weights of one layer, then you do not re-use the individual gradients again, so you can just keep a sum. Alternatively for speed, you can calculate a minibatch of gradients in parallel, as each example is independent - which is a major part of why GPU acceleration is so effective in neural network training.
  It is critical to getting correct results that you calculate the gradient of the loss function with respect to each example input/output pair separately. Once you have done that, you can average the gradients across a batch or mini-batch to estimate a true gradient for the dataset which can be used to take a gradient descent step.
  
  recently I have read somewhere that you basically only average the error of each example in the batch, and then calculate the gradients at the end of each batch.
  
  Without a reference it is hard to tell whether this is an error in the "somewhere", or you have misunderstood, or there is a specific context.
  If by "error" you mean the literal difference $\hat{y}_i - y_i$, where $\hat{y}_i$ is your estimate for data input $i$ and $y_i$ is the ground-truth training value, then that is the gradient for many loss functions and activation function pairs. For instance, it is the error gradient for mean square error and linear output. Some texts loosely refer to this as the "error", and talk about backpropagating "the error", but actually it is a gradient.
  In addition, if the article was referring to linear regression, logistic regression or softmax regression, everything else is linear - in those specific models then you can just "average the error" and use that as the gradient.
  In general, however, the statement is incorrect because a neural network with one or more hidden layers has many non-linearities that will give different results when calculating average first then backpropagating vs taking backpropagating first the averaging - that is $f'(\mu(Y))$ vs $\mu(f'(Y))$ where $f'$ is the derivative of the transfer function and $\mu$ is the mean for the batch (i.e. $\mu(Y) = \frac{1}{N}\sum_{i=1}^{N} y_i$ and $Y$ represents all the $y_i$ in a given batch of size $N$)
  When $y_i = f(x_i) = ax_i +b$ i.e. the transfer function is linear, then $f'(\mu(Y)) = \mu(f'(Y)) = \frac{a}{N}\sum_{i=1}^N x_i$, but almost all useful loss functions and all transfer functions except some output layers in neural networks are non-linear. For those, $f'(\mu(Y)) \neq \mu(f'(Y))$.
  A simple example would show this, if we start a small minibatch back propagation with the loss function (as opposed to its gradient).
  Say you had the following data for regression:
    x    y
  
    1    2
    1    4
  
  You want a model that can regress to least mean squared error $y$ when given an input $x = 1$. The best model should predict $3$ in that case.
  If your model has converged, the average MSE of the dataset is $1$. Using that would make your model move away from convergence and it will perform worse.
  If you first take the gradients, then average those, you will calculate $0$. A simple gradient update step using that value will make no change, leaving the model in the optimal position.
  This issue occurs on every hidden layer in a neural network, so in general you cannot simply resolve the loss function gradient and start with the average error gradient at the output. You would still hit the inequality $f'(\mu(Y)) \neq \mu(f'(Y))$ on each nonlinearly.
  
  > **Comments:**
  > **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/106917/discussion-on-answer-by-neil-slater-what-exactly-is-averaged-when-doing-batch-gr).  
  
  ---
  
  