Answers.Body: <p>When dealing with optimization problems, a fundamental distinction is whether the objective is a (deterministic) function, or an expectation of some function. I will refer to these cases as the deterministic and stochastic setting respectively.</p>
  <p>Almost always machine learning problems are in the stochastic setting. Gradient descent is not used here (and indeed, it performs poorly, which is why it is not used); rather it is <em>stochastic gradient descent</em>, or more specifically, mini-batch stochastic gradient descent (SGD) that is the &quot;vanilla&quot; algorithm. In practice however, methods such as ADAM (or related methods such as AdaGrad or RMSprop) or SGD with momentum are preferred over SGD.</p>
  <p>The deterministic case should be thought of separately, as the algorithms used there are completely different. It's interesting to note that the deterministic algorithms are much more complicated than their stochastic counterparts. Conjugate gradient is definitely going to be better on average than gradient descent, however it is quasi-Newton methods, such as BFGS (and its variants such as l-BFGS-b) or a truncated method that are currently considered state of the art.</p>
  <p><a href="https://proceedings.neurips.cc/paper/2000/file/059fdcd96baeb75112f09fa1dcc740cc-Paper.pdf" rel="noreferrer">Here's a NIPs paper</a> that says CG doesn't generalize well. There are similar results for quasi-Newton methods. If you want something better than SGD, you should look into a method like ADAM, which was designed for the stochastic setting. CG and ADAM both use information from past gradient directions to improve the current search direction. CG is formulated assuming that the past gradients are the exact gradient. ADAM is formulated assuming that the past gradients are gradient estimates, which is the case in the stochastic setting.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-17T12:10:51.187Z
Answers.Text: Saying that "Gradient descent is not used" in the context of deep learning is probably very wrong. People certainly tried to train neural networks with all data at some point (I think I already did it too). Maybe you should reformulate that sentence as "GD may not be widely used, but, instead, mini-batch GD seems to be more widely used in practice". In any case, after having read your answer, I don't understand why conjugate gradient is not used for training neural networks. What prevents exactly CG from being used?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-17T18:43:58.507Z
Answers.Text: gradient descent means using all examples to compute the search direction. stochastic gradient descent uses 1 training example to compute the search direction. mini-batch stochastic gradient descent (SGD) uses a batch of training examples to compute the search direction. I have never seen a code which uses only 1 training example or every training example.
Answers.UserDisplayName: Taw
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-17T19:05:50.580Z
Answers.Text: maybe you think the answer is more clear now
Answers.UserDisplayName: Taw
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-17T21:21:30.120Z
Answers.Text: Hello. Thanks for trying to clarify. I know the difference between GD, mini-batch, and stochastic gradient descent. My question was not about that. It was about why isn't the CG not "better" than SG for training neural networks. I think you clarify this in your last edit by saying that CG assumes that you use the "true" gradient of the objective function. However, if we use the full dataset (at each iteration, like in full-batch GD), wouldn't that lead to the "true gradient"?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-17T21:21:32.850Z
Answers.Text: And couldn't we use the CG with mini-batches (like we start doing with GD) as some kind of stochastic approximation? You provide a paper that claims that CG doesn't generalise well. I didn't read the paper, but I suspect that this paper provides these results for the neural network context. It may be a good idea to describe their setting. How are they using the CG exactly?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-18T00:56:13.350Z
Answers.Text: The paper indicates "[CG] overfits significantly" - however the paper also indicates "CG results in lower training error". Given the training sets were chosen "so that overfitting was possible", it would seem CG might still have a place if regularized properly to outperform Gradient Descent. Intuitively, your answer describing how SGD would outperform CG makes sense, as as you said, an optimizer like ADAM behaves very similarly to CG however it assumes (correctly) a stochastic environment whereas CG assumes deterministic. However it doesn't seem there is concrete results to back this
Answers.UserDisplayName: Recessive
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-24T22:14:00.117Z
Answers.Text: @Taw Maybe it's worth mentioning that CG can be used under certain conditions to have good outcome.
Answers.UserDisplayName: Green Falcon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-17T10:26:39.910Z
Answers.LastActivityDate: 2021-11-17T19:04:58.360Z
Answers.LastEditDate: 2021-11-17T19:04:58.360Z
Answers.UserDisplayName: Taw
Answers.Body: <p>The fundamental issue is that one doesn't really want to find an optimum of one's optimization problem. We are really interested in <em>generalization</em> - not optimality. And we still poorly understand how and why neural models generalize so well.</p>
  <p>Now, it looks like the generalization properties of neural models have something to do with the structure of their optimization landscape and some particular properties of their well-generalizing minima. Empirically, the SGD class of optimizers is better at finding such generalizing minima.</p>
  <p><a href="https://arxiv.org/abs/1803.05407" rel="nofollow noreferrer">This</a> paper illustrates these ideas by talking about &quot;wide flat&quot; minima and showing how one can use SGD with stochastic weight averaging to improve generalization and convergence.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-29T10:23:16.117Z
Answers.LastActivityDate: 2021-11-29T10:23:16.117Z
Answers.UserDisplayName: Kostya
Body: <p>Based on some preliminary research, the conjugate gradient method is almost exactly the same as gradient descent, except the search direction must be orthogonal to the previous step.</p>
  <p>From what I've read, the idea tends to be that the conjugate gradient method is <em><a href="https://scicomp.stackexchange.com/q/7819">better</a></em> than regular gradient descent, so if that's the case, why is regular gradient descent used?</p>
  <p>Additionally, I know algorithms such as the <a href="https://en.wikipedia.org/wiki/Powell%27s_method" rel="noreferrer">Powell method</a> use the conjugate gradient method for finding minima, but I also know the Powell method is computationally expensive in finding parameter updates as it can be run on any arbitrary function without the need to find partial derivatives of the computational graph. More specifically, when gradient descent is run on a neural network, the gradient with respect to every single parameter is calculated in the backward pass, whereas the Powell method just calculates the gradient of the overall function at this step from what I understand. (See <a href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html" rel="noreferrer">scipy's minimize</a>, you could technically pass an entire neural network into this function and it would optimize it, but there's no world where this is faster than backpropagation)</p>
  <p>However, given how similar gradient descent is to the conjugate gradient method, could we not replace the gradient updates for each parameter with one that is orthogonal to its last update? Would that not be faster?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-11-17T02:09:37.397Z
Comments.Text: There seems to be a paper on this topic. 
  https://cs.stanford.edu/~acoates/papers/LeNgiCoaLahProNg11.pdf
Comments.UserDisplayName: DKDK
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-11-17T04:15:56.373Z
Comments.Text: @DKDK Thanks for the link! An interesting read, however this only adds to my question. The paper indicates the conjugate gradient method is good enough to get an (at the time) SOTA result on MNIST. So why, 10 years after that paper is published, does nobody use it?
Comments.UserDisplayName: Recessive
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-11-17T04:26:02.840Z
Comments.Text: I can’t really think of a reason why people don’t use conjugate gradient. My guess is that the initial success of gd based optimizers led to research mostly focused on its variants and applicable tricks (like momentum and adaptive learning rates).
Comments.UserDisplayName: DKDK
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-11-17T04:28:51.180Z
Comments.Text: A new optimizer with conjugate gradient seems like a viable research topic and I would love to see a sota conjugate gradient optimizer in the near future
Comments.UserDisplayName: DKDK
Tags: <machine-learning><optimization><gradient-descent>
Title: Why is gradient descent used over the conjugate gradient method?
UserDisplayName: Recessive
ThreadText: # Why is gradient descent used over the conjugate gradient method?
  
  (Asked by: username_0 on 2021-11-17)
  
  Based on some preliminary research, the conjugate gradient method is almost exactly the same as gradient descent, except the search direction must be orthogonal to the previous step.
  
  From what I've read, the idea tends to be that the conjugate gradient method is *[better](https://scicomp.stackexchange.com/q/7819)* than regular gradient descent, so if that's the case, why is regular gradient descent used?
  
  Additionally, I know algorithms such as the [Powell method](https://en.wikipedia.org/wiki/Powell%27s_method) use the conjugate gradient method for finding minima, but I also know the Powell method is computationally expensive in finding parameter updates as it can be run on any arbitrary function without the need to find partial derivatives of the computational graph. More specifically, when gradient descent is run on a neural network, the gradient with respect to every single parameter is calculated in the backward pass, whereas the Powell method just calculates the gradient of the overall function at this step from what I understand. (See [scipy's minimize](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html), you could technically pass an entire neural network into this function and it would optimize it, but there's no world where this is faster than backpropagation)
  
  However, given how similar gradient descent is to the conjugate gradient method, could we not replace the gradient updates for each parameter with one that is orthogonal to its last update? Would that not be faster?
  
  **Tags:** machine-learning, optimization, gradient-descent
  
  > **Comments:**
  > **username_1**: There seems to be a paper on this topic.  https://cs.stanford.edu/~acoates/papers/LeNgiCoaLahProNg11.pdf  
  > **username_0**: @username_1 Thanks for the link! An interesting read, however this only adds to my question. The paper indicates the conjugate gradient method is good enough to get an (at the time) SOTA result on MNIST. So why, 10 years after that paper is published, does nobody use it?  
  > **username_1**: I can’t really think of a reason why people don’t use conjugate gradient. My guess is that the initial success of gd based optimizers led to research mostly focused on its variants and applicable tricks (like momentum and adaptive learning rates).  
  > **username_1**: A new optimizer with conjugate gradient seems like a viable research topic and I would love to see a sota conjugate gradient optimizer in the near future  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2021-11-17. Score: 9
  
  When dealing with optimization problems, a fundamental distinction is whether the objective is a (deterministic) function, or an expectation of some function. I will refer to these cases as the deterministic and stochastic setting respectively.
  
  Almost always machine learning problems are in the stochastic setting. Gradient descent is not used here (and indeed, it performs poorly, which is why it is not used); rather it is *stochastic gradient descent*, or more specifically, mini-batch stochastic gradient descent (SGD) that is the "vanilla" algorithm. In practice however, methods such as ADAM (or related methods such as AdaGrad or RMSprop) or SGD with momentum are preferred over SGD.
  
  The deterministic case should be thought of separately, as the algorithms used there are completely different. It's interesting to note that the deterministic algorithms are much more complicated than their stochastic counterparts. Conjugate gradient is definitely going to be better on average than gradient descent, however it is quasi-Newton methods, such as BFGS (and its variants such as l-BFGS-b) or a truncated method that are currently considered state of the art.
  
  [Here's a NIPs paper](https://proceedings.neurips.cc/paper/2000/file/059fdcd96baeb75112f09fa1dcc740cc-Paper.pdf) that says CG doesn't generalize well. There are similar results for quasi-Newton methods. If you want something better than SGD, you should look into a method like ADAM, which was designed for the stochastic setting. CG and ADAM both use information from past gradient directions to improve the current search direction. CG is formulated assuming that the past gradients are the exact gradient. ADAM is formulated assuming that the past gradients are gradient estimates, which is the case in the stochastic setting.
  
  > **Comments:**
  > **username_3**: Saying that "Gradient descent is not used" in the context of deep learning is probably very wrong. People certainly tried to train neural networks with all data at some point (I think I already did it too). Maybe you should reformulate that sentence as "GD may not be widely used, but, instead, mini-batch GD seems to be more widely used in practice". In any case, after having read your answer, I don't understand why conjugate gradient is not used for training neural networks. What prevents exactly CG from being used?  
  > **username_2**: gradient descent means using all examples to compute the search direction. stochastic gradient descent uses 1 training example to compute the search direction. mini-batch stochastic gradient descent (SGD) uses a batch of training examples to compute the search direction. I have never seen a code which uses only 1 training example or every training example.  
  > **username_2**: maybe you think the answer is more clear now  
  > **username_3**: Hello. Thanks for trying to clarify. I know the difference between GD, mini-batch, and stochastic gradient descent. My question was not about that. It was about why isn't the CG not "better" than SG for training neural networks. I think you clarify this in your last edit by saying that CG assumes that you use the "true" gradient of the objective function. However, if we use the full dataset (at each iteration, like in full-batch GD), wouldn't that lead to the "true gradient"?  
  > **username_3**: And couldn't we use the CG with mini-batches (like we start doing with GD) as some kind of stochastic approximation? You provide a paper that claims that CG doesn't generalise well. I didn't read the paper, but I suspect that this paper provides these results for the neural network context. It may be a good idea to describe their setting. How are they using the CG exactly?  
  > **username_0**: The paper indicates "[CG] overfits significantly" - however the paper also indicates "CG results in lower training error". Given the training sets were chosen "so that overfitting was possible", it would seem CG might still have a place if regularized properly to outperform Gradient Descent. Intuitively, your answer describing how SGD would outperform CG makes sense, as as you said, an optimizer like ADAM behaves very similarly to CG however it assumes (correctly) a stochastic environment whereas CG assumes deterministic. However it doesn't seem there is concrete results to back this  
  > **username_4**: @username_2 Maybe it's worth mentioning that CG can be used under certain conditions to have good outcome.  
  
  ---
  
  ### Answer by username_5 on 2021-11-29. Score: 4
  
  The fundamental issue is that one doesn't really want to find an optimum of one's optimization problem. We are really interested in *generalization* - not optimality. And we still poorly understand how and why neural models generalize so well.
  
  Now, it looks like the generalization properties of neural models have something to do with the structure of their optimization landscape and some particular properties of their well-generalizing minima. Empirically, the SGD class of optimizers is better at finding such generalizing minima.
  
  [This](https://arxiv.org/abs/1803.05407) paper illustrates these ideas by talking about "wide flat" minima and showing how one can use SGD with stochastic weight averaging to improve generalization and convergence.
  
  
  ---
  
  