Answers.Body: <p>That paragraph is incomplete and unclear indeed.
  Let's crack the difference with a concrete example: logistic regression.</p>
  <p>The objective we want to minimize is:</p>
  <p><span class="math-container">$J_{train}(\theta)=\frac{1}{2m}\sum_{i=1}^{m}(h_{\theta}(x^{i})-y^{i})^{2}$</span></p>
  <p>Notice how this loss formulation requires us to iterate trough all our data to sum the squared errors. Gradient descent does precisely that:</p>
  <p><span class="math-container">$\theta_{j} := \theta_{j} - \alpha\frac{1}{m}\sum_{i=1}^{m}(h_{\theta}(x^{i})-y^{i})x^{i}_{j}$</span></p>
  <p>Also here, to compute a single descent step we are iterating through to all our data, while keep summing the gradients. This is why normal gradient descent is so memory inefficient.</p>
  <p>One work around to this problem is to redefine our initial loss <span class="math-container">$J$</span> in order to allow us to perform a descent step without having to look at all our data. We usually call this new formulation <em>cost</em>:</p>
  <p><span class="math-container">$cost(\theta, (x^{i}, y^{i})) = \frac{1}{2}(h_{\theta}(x^{i})-y^{i})^{2}$</span></p>
  <p>This allows us to rewrite also our descent step in a way that doesn't require to look at all our data.</p>
  <p><span class="math-container">$\theta_{j} := \theta_{j} - \alpha\frac{1}{2}(h_{\theta}(x^{i})-y^{i})x^{i}_{j}$</span></p>
  <p>Since the sum now it's gone it means that we don't need to sum gradients or keep in memory extra stuff, so this is much more efficient. And this is basically Stochastic gradient descent.</p>
  <p>Problem is that because we're updating on a fraction of our data at the time, order becomes relevant. If our data are ordered in some strange fashion, we'll risk to introduce biases in our parameters do to biases in the subset we selected to perform the update. And even if other subsets of data would normally account for that, now it's not the case anymore, cause we already performed an update step, and when applying our model to the new subset the parameters are therefore already biased. The only strategy we have to prevent this is precisely randomizing the order of our data.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-07T07:20:54.757Z
Answers.Text: thank you for taking the time and explaining your answer.
Answers.UserDisplayName: JammingThebBits
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-06T19:34:18.277Z
Answers.LastActivityDate: 2022-02-06T19:34:18.277Z
Answers.UserDisplayName: Edoardo Guerriero
Body: <p>From wikipedia page it mentioned:</p>
  <blockquote>
  <p>To economize on the computational cost at every iteration, stochastic
  gradient descent samples a subset of summand functions at every step.
  This is very effective in the case of large-scale machine learning
  problems</p>
  </blockquote>
  <p>And later on it demonstrates the pseudo code with shuffle, and not sub-setting the samples.
  I don't get it how come applying shuffle improves the Gradient descent:
  <a href="https://i.sstatic.net/nRWey.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/nRWey.png" alt="enter image description here" /></a></p>
  <p>Can somebody shed some light on this issue?</p>
  
Tags: <gradient-descent><stochastic-gradient-descent>
Title: Unclear fact about difference between Gradient Descent to Stochastic Gradient Decent in wikipedia
UserDisplayName: JammingThebBits
ThreadText: # Unclear fact about difference between Gradient Descent to Stochastic Gradient Decent in wikipedia
  
  (Asked by: username_0 on 2022-02-06)
  
  From wikipedia page it mentioned:
  
  > To economize on the computational cost at every iteration, stochastic
  > gradient descent samples a subset of summand functions at every step.
  > This is very effective in the case of large-scale machine learning
  > problems
  
  And later on it demonstrates the pseudo code with shuffle, and not sub-setting the samples.
  I don't get it how come applying shuffle improves the Gradient descent:
  [![enter image description here](https://i.sstatic.net/nRWey.png)](https://i.sstatic.net/nRWey.png)
  
  Can somebody shed some light on this issue?
  
  **Tags:** gradient-descent, stochastic-gradient-descent
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-02-06. Score: 1 | Accepted answer
  
  That paragraph is incomplete and unclear indeed.
  Let's crack the difference with a concrete example: logistic regression.
  
  The objective we want to minimize is:
  
  $J\_{train}(\theta)=\frac{1}{2m}\sum\_{i=1}^{m}(h\_{\theta}(x^{i})-y^{i})^{2}$
  
  Notice how this loss formulation requires us to iterate trough all our data to sum the squared errors. Gradient descent does precisely that:
  
  $\theta\_{j} := \theta\_{j} - \alpha\frac{1}{m}\sum\_{i=1}^{m}(h\_{\theta}(x^{i})-y^{i})x^{i}\_{j}$
  
  Also here, to compute a single descent step we are iterating through to all our data, while keep summing the gradients. This is why normal gradient descent is so memory inefficient.
  
  One work around to this problem is to redefine our initial loss $J$ in order to allow us to perform a descent step without having to look at all our data. We usually call this new formulation *cost*:
  
  $cost(\theta, (x^{i}, y^{i})) = \frac{1}{2}(h\_{\theta}(x^{i})-y^{i})^{2}$
  
  This allows us to rewrite also our descent step in a way that doesn't require to look at all our data.
  
  $\theta\_{j} := \theta\_{j} - \alpha\frac{1}{2}(h\_{\theta}(x^{i})-y^{i})x^{i}\_{j}$
  
  Since the sum now it's gone it means that we don't need to sum gradients or keep in memory extra stuff, so this is much more efficient. And this is basically Stochastic gradient descent.
  
  Problem is that because we're updating on a fraction of our data at the time, order becomes relevant. If our data are ordered in some strange fashion, we'll risk to introduce biases in our parameters do to biases in the subset we selected to perform the update. And even if other subsets of data would normally account for that, now it's not the case anymore, cause we already performed an update step, and when applying our model to the new subset the parameters are therefore already biased. The only strategy we have to prevent this is precisely randomizing the order of our data.
  
  > **Comments:**
  > **username_0**: thank you for taking the time and explaining your answer.  
  
  ---
  
  