This bugzilla service is closed. All entries have been migrated to https://gitlab.com/libeigen/eigen
Bug 733 - CG: Documentation proposes degeneration to Gradient Descent
Summary: CG: Documentation proposes degeneration to Gradient Descent
Status: RESOLVED FIXED
Alias: None
Product: Eigen
Classification: Unclassified
Component: Sparse (show other bugs)
Version: 3.2
Hardware: All All
: Normal minor
Assignee: Nobody
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-01-30 16:08 UTC by waechter.mi
Modified: 2019-12-04 12:58 UTC (History)
2 users (show)



Attachments

Description waechter.mi 2014-01-30 16:08:11 UTC
The documentation of ConjugateGradient gives an example of how CG can be run step by step:

"Here is a step by step execution example starting with a random guess and printing the evolution of the estimated error:
* x = VectorXd::Random(n);
* cg.setMaxIterations(1);
* int i = 0;
* do {
*   x = cg.solveWithGuess(b,x);
*   std::cout << i << " : " << cg.error() << std::endl;
*   ++i;
* } while (cg.info()!=Success && i<100);
Note that such a step by step excution is slightly slower."


With this my optimization problem took ~1400 iterations and later I found out that it only takes ~180 if not done step wise.

As I see it, every time solveWithGuess is called CG is restarted. CG's first iteration is identical to gradient descent and thus the whole optimization effectively degenerates to gradient descent. The note "that such a step by step excution is slightly slower." does not really capture it. Also the evolution of the estimated errors that are being printed to std::cout are not the true CG errors because real CG would converge quicker.

Maybe the documentation can be changed such that it
1. suggests to use much more than 1 iteration in each solveWithGuess step.
2. mentions that too small maxIteration numbers make CG degenerate?
Comment 1 Gael Guennebaud 2015-02-10 22:30:49 UTC
https://bitbucket.org/eigen/eigen/commits/a482ead8ccbf/
https://bitbucket.org/eigen/eigen/commits/e77df591e0b9/
User:        blechta
Summary:     Fix bug 733: step by step solving is not a good example for solveWithGuess
Comment 2 Nobody 2019-12-04 12:58:04 UTC
-- GitLab Migration Automatic Message --

This bug has been migrated to gitlab.com's GitLab instance and has been closed from further activity.

You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.com/libeigen/eigen/issues/733.

Note You need to log in before you can comment on or make changes to this bug.