8
$\begingroup$

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 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 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, 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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ There seems to be a paper on this topic. cs.stanford.edu/~acoates/papers/LeNgiCoaLahProNg11.pdf $\endgroup$
    – DKDK
    Commented Nov 17, 2021 at 2:09
  • $\begingroup$ @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? $\endgroup$
    – Recessive
    Commented Nov 17, 2021 at 4:15
  • $\begingroup$ 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). $\endgroup$
    – DKDK
    Commented Nov 17, 2021 at 4:26
  • $\begingroup$ 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 $\endgroup$
    – DKDK
    Commented Nov 17, 2021 at 4:28

2 Answers 2

Reset to default
9
$\begingroup$

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 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.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ 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? $\endgroup$
    – nbro
    Commented Nov 17, 2021 at 12:10
  • $\begingroup$ 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. $\endgroup$
    – Taw
    Commented Nov 17, 2021 at 18:43
  • $\begingroup$ maybe you think the answer is more clear now $\endgroup$
    – Taw
    Commented Nov 17, 2021 at 19:05
  • $\begingroup$ 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"? $\endgroup$
    – nbro
    Commented Nov 17, 2021 at 21:21
  • 1
    $\begingroup$ 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 $\endgroup$
    – Recessive
    Commented Nov 18, 2021 at 0:56
4
$\begingroup$

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 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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .