New user self-registration is currently disabled. Please email eigen-core-team @ lists.tuxfamily.org if you need an account.
Bug 733 - CG: Documentation proposes degeneration to Gradient Descent
CG: Documentation proposes degeneration to Gradient Descent
Status: RESOLVED FIXED
Product: Eigen
Classification: Unclassified
Component: Sparse
3.2
All All
: Normal minor
Assigned To: Nobody
:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2014-01-30 16:08 UTC by waechter.mi
Modified: 2015-02-10 22:30 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

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