A worst-case complexity analysis for riemannian non-monotone line-search methods

In this paper, the non-monotone line-search methods are presented and analyzed for minimizing an objective function on a smooth manifold. Particularly, we study the number of iterations necessary for this class of schemes to obtain ϵ-approximated stationary points. We prove that under a regularity Lipschitz-type condition on the pullbacks of the cost function to the tangent spaces of the manifold and other mild assumptions, the Riemannian non-monotone line-search methods generate points with Riemannian gradient norm smaller than ϵ in O(ϵ-2) iterations. Our worst-case complexity includes a wide variety of known non-monotone strategies existing in the literature. Additionally, we establish the global convergence for this family of methods. The bounds obtained in our analysis agree with the bounds known for line-search methods in the field of unconstrained nonlinear optimization and hence generalize previous work.