Question about product manifold

[lineya...@gmail.com]

Hi,

I found an interesting thing these days. When I was using the product manifold (for multiple variables), I found the convergence rate becomes slower for trust region algorithm, which has a linear convergence rate (log(err)-iteration is a line). What's more, it's even slower than conjugate gradient algorithm. It confuses me and do you have any reasonable explanations? Thanks.

Kai

[Nicolas Boumal]

Hello Kai,

This kind of behavior is going to depend on a number of things (it's problem dependent). One thing that can happen in a product manifold is that conditioning may become poor, because the separate terms of the product manifold have different scale.

Did you check the Hessian with checkhessian(problem) to make sure it is accurate?

Best,

Nicolas

[lineya...@gmail.com]

Hi Nicolas,

Actually I checked gradient and Hessian and found no mistakes. The very strange phenomenon happens only when r = rank(X_i) = 1. I'' appreciate it very much if you can run the code and see the convergence figures. Thanks

Kai

[Nicolas Boumal]

Hello,
I do not see your code attached?
Best,
Nicolas

[Nicolas Boumal]

Ok, got your code by e-mail. I ran it, and indeed I can see how TR is slower than CG in some instances. That's not necessarily a bug: like I said, this may very well be an issue with conditioning, where for some reason CG handles it better than TR. Did you try running hessianspectrum(problem, X) where X is the "optimum" found by TR or CG?

[Nicolas Boumal]

Ok, I just did, and the condition number of the Hessian is great (around 20), so that's not the issue...

       E = hessianspectrum(problem, Xcg);

       max(E)/min(E) -> gives ~18

       stem(E);

On the other hand, I ran checkhessian(problem, Xcg), and it fails (I get a slope of 2 instead of 3) -- so that seems to be the issue. The Hessian needs to be fixed.

Best,

Nicolas

[lineya...@gmail.com]

Hi Nicolas,

I'm afraid not, maybe you neglect that for fixedrank2factors factory, it says that 

Notice that the checkhessian test fails: the slope is not right. This is because the retraction is not second-order compatible with the Riemannian exponential on this manifold, making thecheckhessian tool unusable. The Hessian is correct though. 

in https://manopt.org/manifold_documentation_fixedrank_2factors.html. 

Or we can just comments out the Hessian function, the result would remain the same. It's quite strange, ha? And as long as we set the r >1, the convergence rate becomes normal as expected.

Kai

[Nicolas Boumal]

Hello Kai,

Thanks for your message: you are right about the Hessian test failing here, I forgot about that. This is because the retraction R is only a first-order approximation of the exponential map.

So, f o R_x (the cost function f composed with the retraction R at x) has the same gradient as f itself, but they do not share the same Hessian. This means the gradient and Hessian of f only provide a first-order approximation of f o R_x, instead of a second order approximation. Perhaps this is why with or without the Hessian we do not see a qualitatively different result.

(Although, as we converge to a critical point, this distinction becomes moot: at a critical point x, the Hessian of f o R_x and the Hessian of f will coincide indeed, which is why we would still expect quadratic convergence "eventually" -- it's just very surprising that it seems not to occur before the numerical experiments are shut down.)

Again, this does not necessarily mean there is a bug, but if see more surprising behavior with this particular geometry, please do let us know about it.

Thanks,

Nicolas

[lineya...@gmail.com]

Hi Nicolas,

Actually we found that the computation of Hessian is wrong, but in this case chechhessian doesn't recognize this fact. And thanks to the help of BM we've corrected this issue. But I also find that in your factory  "symfixedrankYYcomplexfactory", you guys doesn't do the horizontal projection. But actually, your Hessian has been projected to the horizontal space. And I also find this wouldn't be catched by the checkgradient and checkhessian function. Nevertheless, I think for this quotient manifold horizontal projection is essential and this should be a bug. In the reference paper they also project the gradient to the hotizontal space. Am I right?

Kai Yang

[BM]

Hello Kai, 

Thanks for your queries.

We do project the Hessian. Below are the lines that are directly lifted from the factories symfixedrankYYfactory and symfixedrankYYcomplexfactory.

M.egrad2rgrad = @(Y, eta) eta;
M.ehess2rhess = @(Y, egrad, ehess, U) M.proj(Y, ehess);

We don't project the gradient as it already belongs to the horizontal space.

Am I missing something?

Regards,
BM

[Nicolas Boumal]

Thanks Bamdev! -- is this also true for the complex version of that factory?

[BM]

Hello Nicolas, 

Yes. 

Regards,

Bamdev

[lineya...@gmail.com]

Thanks BM and Nicolas!  I checked and found it does belong to the horizontal space! 

在 2017年6月29日星期四 UTC+8上午12:55:12，BM写道：