3 ms·

I need to write something about conjugate gradients. The first thing we did in my optimisation class at CIMAT was gradient descent and showed how it was so slow

by jordigh 10y ago

I need to write something about conjugate gradients. The first thing we did in my optimisation class at CIMAT was gradient descent and showed how it was so slow compared to everything else. In practical applications, there's way too much magic in choosing the so-called "learning rate" (known as "step size" in numerical optimisation). Even choosing an optimal step size per iteration (by doing a line search), gradient descent is still slow. Conjugate gradients are a bit more difficult to understand, but they're not that hard to implement if you just blindly copy a few formulae, and they are a dramatic speedup. All of these blog posts about gradient descent feel like everyone keeps going on about what a great algorithm bubblesort is because it's so easy to understand and implement.

dharmon 10y ago
This was the "standard" text we used for new grad students to understand CG. It's not perfect but covers the ideas and algorithms pretty well: http://www.cs.cmu.edu/%7Equake-papers/painless-conjugate-gradient.pdf http://www.cs.cmu.edu/%7Equake-papers/painless-conjugate-gra...
eliben 10y ago
Claiming that gradient descent is a great algorithm certainly wasn't the goal of this article. But GD is the basis from which most other iterative algorithms stem, and it's worthwhile having a good understanding of its inner workings as a prerequisite for more advanced algorithms. Personally I found http://sebastianruder.com/optimizing-gradient-descent/ http://sebastianruder.com/optimizing-gradient-descent/ interesting - it goes into the advanced variants like nesterov, adadelta, etc
- jordigh 10y ago
  I realise, but since a lot more gets written about steepest descent than everything else, it also gets implemented and used a lot more often, even when other alternatives are readily available and already implemented. For example, the trainscg method of Matlab is relatively obscure thus unused and not frequently re-implemented. There's an implicit endorsement in these blog posts. People wouldn't be spilling all this ink nowadays on plain adalines, even if they're building blocks for backprop networks, right? So by writing so much about it, people get the impression that it has to be studied and implemented very carefully, to the exclusion of better methods.
  - maxerize 10y ago
    As the above poster said, if you can introduce people to a topic by explaining a simplified or 'naive' solution/algorithm, then that could be a good springboard to learn more about the topic. Which is why there should be more comments presenting improvements and alternatives, rather than criticising what is obviously meant as a primer on optimisation. From the intro: Gradient descent is a standard tool for optimizing complex functions iteratively within a computer program. Its goal is: given some arbitrary function, find a minima. For some small subset of functions - those that are convex - there's just a single minima which also happens to be global. For most realistic functions, there may be many minima, so most minima are local. Making sure the optimization finds the "best" minima and doesn't get stuck in sub-optimial minima is out of the scope of this article. Here we'll just be dealing with the core gradient descent algorithm for finding some minima from a given starting point.
    - theoh 10y ago
      The way the author uses the word "minima" as if it was both singular and plural is a really discouraging sign.
theoh 10y ago
Presumably you are aware of Jonathan Shewchuk's "An Introduction to the Conjugate Gradient Method Without the Agonizing Pain": https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf https://www.cs.cmu.edu/~quake-papers/painless-conjugate-grad...
- nkurz 10y ago
  Ilya Kuzovkin did nice companion article in the form of a Python Notebook to accompany Shewchuk's classic: "The Concept of Conjugate Gradient Descent in Python" http://ikuz.eu/2015/04/15/the-concept-of-conjugate-gradient-descent-in-python/ http://ikuz.eu/2015/04/15/the-concept-of-conjugate-gradient-... And for those with more math and less patience for explanation, Robert Gower also offers: "Conjugate Gradients: The short and painful explanation with oblique projections" http://www.maths.ed.ac.uk/~s1065527/pdf/GowerR_Painful_PCG_projections http://www.maths.ed.ac.uk/~s1065527/pdf/GowerR_Painful_PCG_p...

by jordigh 10y ago

dharmon 10y ago

This was the "standard" text we used for new grad students to understand CG. It's not perfect but covers the ideas and algorithms pretty well: http://www.cs.cmu.edu/%7Equake-papers/painless-conjugate-gradient.pdf http://www.cs.cmu.edu/%7Equake-papers/painless-conjugate-gra...

eliben 10y ago

Claiming that gradient descent is a great algorithm certainly wasn't the goal of this article. But GD is the basis from which most other iterative algorithms stem, and it's worthwhile having a good understanding of its inner workings as a prerequisite for more advanced algorithms. Personally I found http://sebastianruder.com/optimizing-gradient-descent/ http://sebastianruder.com/optimizing-gradient-descent/ interesting - it goes into the advanced variants like nesterov, adadelta, etc

jordigh 10y ago
I realise, but since a lot more gets written about steepest descent than everything else, it also gets implemented and used a lot more often, even when other alternatives are readily available and already implemented. For example, the trainscg method of Matlab is relatively obscure thus unused and not frequently re-implemented. There's an implicit endorsement in these blog posts. People wouldn't be spilling all this ink nowadays on plain adalines, even if they're building blocks for backprop networks, right? So by writing so much about it, people get the impression that it has to be studied and implemented very carefully, to the exclusion of better methods.
- maxerize 10y ago
  As the above poster said, if you can introduce people to a topic by explaining a simplified or 'naive' solution/algorithm, then that could be a good springboard to learn more about the topic. Which is why there should be more comments presenting improvements and alternatives, rather than criticising what is obviously meant as a primer on optimisation. From the intro: Gradient descent is a standard tool for optimizing complex functions iteratively within a computer program. Its goal is: given some arbitrary function, find a minima. For some small subset of functions - those that are convex - there's just a single minima which also happens to be global. For most realistic functions, there may be many minima, so most minima are local. Making sure the optimization finds the "best" minima and doesn't get stuck in sub-optimial minima is out of the scope of this article. Here we'll just be dealing with the core gradient descent algorithm for finding some minima from a given starting point.
  - theoh 10y ago
    The way the author uses the word "minima" as if it was both singular and plural is a really discouraging sign.

theoh 10y ago

Presumably you are aware of Jonathan Shewchuk's "An Introduction to the Conjugate Gradient Method Without the Agonizing Pain": https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf https://www.cs.cmu.edu/~quake-papers/painless-conjugate-grad...

nkurz 10y ago
Ilya Kuzovkin did nice companion article in the form of a Python Notebook to accompany Shewchuk's classic: "The Concept of Conjugate Gradient Descent in Python" http://ikuz.eu/2015/04/15/the-concept-of-conjugate-gradient-descent-in-python/ http://ikuz.eu/2015/04/15/the-concept-of-conjugate-gradient-... And for those with more math and less patience for explanation, Robert Gower also offers: "Conjugate Gradients: The short and painful explanation with oblique projections" http://www.maths.ed.ac.uk/~s1065527/pdf/GowerR_Painful_PCG_projections http://www.maths.ed.ac.uk/~s1065527/pdf/GowerR_Painful_PCG_p...