Answers.Body: <p>Stochastic Gradient Descent empirically has shown to lead better results than classic Gradient Descent since its formulation, and today we're getting close to understand that it's not just luck, but the results of better mathematical qualities as well. SO the answer to your question is no, the theoretical results also show that SGD is better than classic GD.</p>
  <p>Check these papers offer different explanations about why SGD tend to perform better that classic GD:</p>
  <ol>
  <li><a href="https://arxiv.org/abs/1509.01240" rel="nofollow noreferrer">Train faster, generalize better: Stability of stochastic gradient descent</a></li>
  <li><a href="https://proceedings.mlr.press/v40/Ge15.pdf" rel="nofollow noreferrer">Escaping From Saddle Points –
  Online Stochastic Gradient for Tensor Decomposition</a></li>
  <li><a href="https://arxiv.org/abs/1802.06175" rel="nofollow noreferrer">An Alternative View: When Does SGD Escape Local Minima?</a></li>
  </ol>
  <p>Quick summaries:</p>
  <ol>
  <li>SGD works better cause it's less prone to generalization error, or to put it the other way around, a more stable learner compare to GD, i.e. the solutions learned with SGD are less affected by small perturbations in the training data.</li>
  <li>SGD works better cause its randomness makes it less prone to get stuck in saddle points.</li>
  <li>SGD works better cause it's literally GD but applied to a smoother version (convolved with noise) of the objective function we want to minimize, so again, less risk to get stuck not only in saddle points, but bad local minima as well (see image below).</li>
  </ol>
  <p><a href="https://i.sstatic.net/Y4Ikc.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Y4Ikc.png" alt="enter image description here" /></a></p>
  <p>Extra note:
  it's not hard to understand conceptually how SGD can help escaping saddle points and local minima. When computing a single step using all gradients of all training instances like GD does, we don't leave much room for exploration of the loss function surface. So if our training instances point to a local minima that will be the solution found by GD. On the other hand, SGD compute gradients only on a batch of instances, and therefore each update is a suboptimal step toward the negative direction of the gradients. Being suboptmal, each step leave room for exploration, i.e. if an update step points to a local minima it might be that the next step point in a different direction, something that can't happen in GD since we perform a single update. Same conclusion, but different conceptualization comes from the interpretation of the last paper. They prove that SGD can be seen as GD (so again, single update step) performed on a loss function convolved with noise. Noise convolution has the effect of smoothing out the function (think as a metaphor to combine random frequencies, they are more likely to cancel each other out than boosting each other). Smoothing the loss function means precisely removing small local minima, as you can see in the last picture. The consequence is the same as in the first explanation, i.e. less chance of getting stuck in a local minima.</p>
  <p><a href="https://i.sstatic.net/FwOAk.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/FwOAk.png" alt="enter image description here" /></a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-15T14:55:47.003Z
Answers.Text: Thank you for your answer! I would be very interested in understanding why the added randomness and smoothness make it less likely to get stuck in saddle points!
Answers.UserDisplayName: stats_noob
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-15T15:47:29.647Z
Answers.Text: I've updated the question
Answers.UserDisplayName: Edoardo Guerriero
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-15T15:56:26.180Z
Answers.Text: Thank you so much for your answer! If you have time, can you please take a look at this question? https://ai.stackexchange.com/questions/34389/are-bayesian-optimization-methods-better-suited-noisy-optimization-problems thank you so much for all your help!
Answers.UserDisplayName: stats_noob
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-15T10:08:54.070Z
Answers.LastActivityDate: 2022-02-15T15:56:42.323Z
Answers.LastEditDate: 2022-02-15T15:56:42.323Z
Answers.UserDisplayName: Edoardo Guerriero
Body: <p>On a very informal level, if we were to compare the (classical) <strong>Gradient Descent Algorithm to the Stochastic Gradient Descent Algorithm</strong>, the first thing that comes to mind is:</p>
  <ul>
  <li>Gradient Descent can be considered as a slower algorithm than Stochastic Gradient Descent, since it requires performing mathematical operations (e.g. derivatives, second derivatives) on the entire data set. On the other hand, Stochastic Gradient Descent can be considered as a faster algorithm, since it approximates the gradient using &quot;mini batches&quot; of observations from the data set. Logically, this makes sense : Stochastic Gradient Descent requires fewer calculations compared to Gradient Descent, therefore the same computer should take less time to perform fewer calculations compared to more calculations.</li>
  </ul>
  <p>However, (in the spirit of tradeoffs) the somewhat logical counter point to the above argument is that:</p>
  <ul>
  <li>Since Stochastic Gradient Descent approximates the gradient of the function whereas Gradient Descent evaluates the full gradient - one would imagine that perhaps Gradient Descent might have a better ability to find the true minimum of the function compared to Gradient Descent. <strong>However, I am not sure about this.</strong></li>
  </ul>
  <p><strong>My Question:</strong> In the past few years, a lot of research has been done about studying the behavior (e.g. theoretical convergence properties) of Stochastic Gradient Descent (e.g. <a href="https://arxiv.org/abs/2103.14350" rel="nofollow noreferrer">https://arxiv.org/abs/2103.14350</a> , <a href="https://raghumeka.github.io/CS289ML/gdnotes.pdf" rel="nofollow noreferrer">https://raghumeka.github.io/CS289ML/gdnotes.pdf</a>) which have demonstrated similar abilities of the Stochastic Gradient Descent Algorithm to converge as compared to Gradient Descent.</p>
  <p><strong>But are there any theoretical results which expose the above (speculated) tradeoff?</strong> At the end of the day, if Stochastic Gradient requires less computing power when compared to Gradient Descent - are there any theoretical results that suggest Gradient Descent has an inherent ability to better find the minimum of the function (e.g. perhaps less likely to get &quot;stuck&quot; in saddle points) since it is not relying on an approximation of the gradient? Or if Stochastic Gradient Descent is equal to Gradient Descent in this regard - could Stochastic Gradient Descent be then considered as superior to Gradient Descent?</p>
  <p>Can someone please comment on this?</p>
  <p>Thanks!</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-15T09:38:57.427Z
Comments.Text: Don't ask a question that will lead to opinions. Ask "Is X superior to Y?" will most likely lead to opinions. Rephrase your question so that it will lead to objective answers.
Comments.UserDisplayName: nbro
Tags: <neural-networks><gradient-descent>
Title: In general - is Stochastic Gradient Descent a "superior" algorithm compared to Gradient Descent?
UserDisplayName: stats_noob
ThreadText: # In general - is Stochastic Gradient Descent a "superior" algorithm compared to Gradient Descent?
  
  (Asked by: username_0 on 2022-02-15)
  
  On a very informal level, if we were to compare the (classical) **Gradient Descent Algorithm to the Stochastic Gradient Descent Algorithm**, the first thing that comes to mind is:
  
  * Gradient Descent can be considered as a slower algorithm than Stochastic Gradient Descent, since it requires performing mathematical operations (e.g. derivatives, second derivatives) on the entire data set. On the other hand, Stochastic Gradient Descent can be considered as a faster algorithm, since it approximates the gradient using "mini batches" of observations from the data set. Logically, this makes sense : Stochastic Gradient Descent requires fewer calculations compared to Gradient Descent, therefore the same computer should take less time to perform fewer calculations compared to more calculations.
  
  However, (in the spirit of tradeoffs) the somewhat logical counter point to the above argument is that:
  
  * Since Stochastic Gradient Descent approximates the gradient of the function whereas Gradient Descent evaluates the full gradient - one would imagine that perhaps Gradient Descent might have a better ability to find the true minimum of the function compared to Gradient Descent. **However, I am not sure about this.**
  
  **My Question:** In the past few years, a lot of research has been done about studying the behavior (e.g. theoretical convergence properties) of Stochastic Gradient Descent (e.g. <https://arxiv.org/abs/2103.14350> , <https://raghumeka.github.io/CS289ML/gdnotes.pdf>) which have demonstrated similar abilities of the Stochastic Gradient Descent Algorithm to converge as compared to Gradient Descent.
  
  **But are there any theoretical results which expose the above (speculated) tradeoff?** At the end of the day, if Stochastic Gradient requires less computing power when compared to Gradient Descent - are there any theoretical results that suggest Gradient Descent has an inherent ability to better find the minimum of the function (e.g. perhaps less likely to get "stuck" in saddle points) since it is not relying on an approximation of the gradient? Or if Stochastic Gradient Descent is equal to Gradient Descent in this regard - could Stochastic Gradient Descent be then considered as superior to Gradient Descent?
  
  Can someone please comment on this?
  
  Thanks!
  
  **Tags:** neural-networks, gradient-descent
  > **Comments:**
  > **username_1**: Don't ask a question that will lead to opinions. Ask "Is X superior to Y?" will most likely lead to opinions. Rephrase your question so that it will lead to objective answers.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2022-02-15. Score: 3 | Accepted answer
  
  Stochastic Gradient Descent empirically has shown to lead better results than classic Gradient Descent since its formulation, and today we're getting close to understand that it's not just luck, but the results of better mathematical qualities as well. SO the answer to your question is no, the theoretical results also show that SGD is better than classic GD.
  
  Check these papers offer different explanations about why SGD tend to perform better that classic GD:
  
  1. [Train faster, generalize better: Stability of stochastic gradient descent](https://arxiv.org/abs/1509.01240)
  2. [Escaping From Saddle Points –
     Online Stochastic Gradient for Tensor Decomposition](https://proceedings.mlr.press/v40/Ge15.pdf)
  3. [An Alternative View: When Does SGD Escape Local Minima?](https://arxiv.org/abs/1802.06175)
  
  Quick summaries:
  
  1. SGD works better cause it's less prone to generalization error, or to put it the other way around, a more stable learner compare to GD, i.e. the solutions learned with SGD are less affected by small perturbations in the training data.
  2. SGD works better cause its randomness makes it less prone to get stuck in saddle points.
  3. SGD works better cause it's literally GD but applied to a smoother version (convolved with noise) of the objective function we want to minimize, so again, less risk to get stuck not only in saddle points, but bad local minima as well (see image below).
  
  [![enter image description here](https://i.sstatic.net/Y4Ikc.png)](https://i.sstatic.net/Y4Ikc.png)
  
  Extra note:
  it's not hard to understand conceptually how SGD can help escaping saddle points and local minima. When computing a single step using all gradients of all training instances like GD does, we don't leave much room for exploration of the loss function surface. So if our training instances point to a local minima that will be the solution found by GD. On the other hand, SGD compute gradients only on a batch of instances, and therefore each update is a suboptimal step toward the negative direction of the gradients. Being suboptmal, each step leave room for exploration, i.e. if an update step points to a local minima it might be that the next step point in a different direction, something that can't happen in GD since we perform a single update. Same conclusion, but different conceptualization comes from the interpretation of the last paper. They prove that SGD can be seen as GD (so again, single update step) performed on a loss function convolved with noise. Noise convolution has the effect of smoothing out the function (think as a metaphor to combine random frequencies, they are more likely to cancel each other out than boosting each other). Smoothing the loss function means precisely removing small local minima, as you can see in the last picture. The consequence is the same as in the first explanation, i.e. less chance of getting stuck in a local minima.
  
  [![enter image description here](https://i.sstatic.net/FwOAk.png)](https://i.sstatic.net/FwOAk.png)
  
  > **Comments:**
  > **username_0**: Thank you for your answer! I would be very interested in understanding why the added randomness and smoothness make it less likely to get stuck in saddle points!  
  > **username_2**: I've updated the question  
  > **username_0**: Thank you so much for your answer! If you have time, can you please take a look at this question? https://ai.stackexchange.com/questions/34389/are-bayesian-optimization-methods-better-suited-noisy-optimization-problems thank you so much for all your help!  
  
  ---
  
  