Title: Stochastic Primal-Dual Method on Riemannian Manifolds with Bounded Sectional Curvature,
Abstract: We study a stochastic primal-dual method for constrained optimization over
Riemannian manifolds with bounded sectional curvature. We prove non-asymptotic
convergence to the optimal objective value. More precisely, for the class of
hyperbolic manifolds, we establish a convergence rate that is related to the
sectional curvature lower bound. To prove a convergence rate in terms of
sectional curvature for the elliptic manifolds, we leverage Toponogov's
comparison theorem. In addition, we provide convergence analysis for the
asymptotically elliptic manifolds, where the sectional curvature at each given
point on manifold is locally bounded from below by the distance function. We
demonstrate the performance of the primal-dual algorithm on the sphere for the
non-negative principle component analysis (PCA). In particular, under the
non-negativity constraint on the principle component and for the symmetric
spiked covariance model, we empirically show that the primal-dual approach
outperforms the spectral method. We also examine the performance of the
primal-dual method for the anchored synchronization from partial noisy
measurements of relative rotations on the Lie group SO(3). Lastly, we show that
the primal-dual algorithm can be applied to the weighted MAX-CUT problem under
constraints on the admissible cut. Specifically, we propose different
approximation algorithms for the weighted MAX-CUT problem based on optimizing a
function on the manifold of direct products of the unit spheres as well as the
manifold of direct products of the rotation groups.