Open-Loop Riemannian Frank--Wolfe: Fast Rates under Error Bounds and Scaling Inequalities

Abstract

We explore fast convergence of the Riemannian Frank--Wolfe method for smooth geodesically convex optimization over compact feasible sets. Hadamard manifolds are the main setting. On general complete manifolds, the analysis accounts for all feasible minimizing geodesics. We consider the open loop step-size $\eta_k=a/(k+a)$, which only uses the iteration index. Under a local H\"olderian error bound and local length-normalized directional scaling, every $a>2$ gives the eventual rate $O(k^{-1/(1-\theta)})$ for $\theta\in(0,1/2]$. An interior-ball condition yields $O(k^{-2})$ for strongly geodesically convex objectives. Under an exact Riemannian scaling inequality and a uniform positive lower bound on the gradient norm, every $a\geq2$ gives $O(k^{-a})$ after an explicit threshold index. The same rate holds for the smallest Frank--Wolfe gap over the most recent half of the iterates. For geodesic balls of radius \(R<\pi/2\) in the unit sphere, we establish the scaling inequality with $\alpha_R=\tfrac12\cot R$, yielding $O(k^{-a})$ primal error and recent-window gap rates. We also analyze the standard gap-feedback short step under the local error-bound conditions, obtaining $O(k^{-1/(1-2\theta)})$ for $\theta<1/2$ and a linear rate for $\theta=1/2$. Numerical experiments illustrate the predicted rates and compare iteration-only and feedback-based step selection.