Accelerated Algorithms for Convex and Non-Convex Optimization on Manifolds
This work addresses the challenge of verifying complexity in manifold optimization, providing a unified accelerated method for researchers in optimization and machine learning, though it appears incremental as it builds on existing Euclidean insights.
The paper tackles optimization on manifolds by proposing a scheme that convexifies the objective function using squared retraction distance, enabling accelerated convergence for convex problems and convergence to stationary points for non-convex ones, with demonstrations on tasks like Fréchet mean estimation and low-rank matrix factorization.
We propose a general scheme for solving convex and non-convex optimization problems on manifolds. The central idea is that, by adding a multiple of the squared retraction distance to the objective function in question, we "convexify" the objective function and solve a series of convex sub-problems in the optimization procedure. One of the key challenges for optimization on manifolds is the difficulty of verifying the complexity of the objective function, e.g., whether the objective function is convex or non-convex, and the degree of non-convexity. Our proposed algorithm adapts to the level of complexity in the objective function. We show that when the objective function is convex, the algorithm provably converges to the optimum and leads to accelerated convergence. When the objective function is non-convex, the algorithm will converge to a stationary point. Our proposed method unifies insights from Nesterov's original idea for accelerating gradient descent algorithms with recent developments in optimization algorithms in Euclidean space. We demonstrate the utility of our algorithms on several manifold optimization tasks such as estimating intrinsic and extrinsic Fréchet means on spheres and low-rank matrix factorization with Grassmann manifolds applied to the Netflix rating data set.