Computation complexity of trustregions method with manifolds.

[sarvendranath R]

Hi,

Is there any standard result for the computational complexity of trustregions method in general.

I mean if the number of optimization variables is N. Is there any result which says computational complexity N^{x}.

Also, will the complexity depend on manifold used?

[Nicolas Boumal]

Hello,

The computational complexity depends on the target.

If you are just interested in the cost of one iteration, then this isn't too hard to track, and yes, it depends on f and on the manifold since you will be using gradient / Hessians of f, projections, retractions, etc. Ultimately, it depends on the subproblem solver you use. Check out the tCG.m file in Manopt to see how much work this involves.

If you wish to compute approximate critical points (gradient close to zero) or approximate second-order critical points (Hessian also almost positive semidefinite), you can check out this paper:

Global rates of convergence for nonconvex optimization on manifolds
Nicolas Boumal, P.-A. Absil, Coralia Cartis

https://arxiv.org/abs/1605.08101

https://academic.oup.com/imajna/article/39/1/1/4836777

If you wish to compute local (or even global) optima, then this is unfortunately too hard in general. It turns out that in practice RTR often does a good job, but there exists no satisfactory bounds (they would be exponential because there exist "bad" problems).

Best,

Nicolas