Catalyst Acceleration for Non-Convex Optimization on Manifolds

• Activity Number: 452 - Geometric Statistical and Computational Methods in Imaging
• Type: Topic Contributed
• Date/Time: Wednesday, July 31, 2019 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistics in Imaging
• Author(s): Lizhen Lin and Bayan Saparbayeva* and Michael Minyi Zhang and David Dunson
• Companies: University of Notre Dame and University of Notre Dame and Princeton University and Duke University
• Keywords: Optimization on manifolds; weakly convex functions; acceleration algorithms

Abstract

In the following work, we propose an extension of a class of optimization algorithms to non-convex problems on manifold spaces. To accomplish this, we leverage ideas from recent work on the ``Catalyst'' algorithm for non convex optimization on Euclidean spaces H.Lin et al. (2017). This method is initially designed to accelerate existing optimization algorithms for convex objective functions but is also amenable to non-convex functions. We apply the Catalyst acceleration scheme to many existing optimization routines, such as gradient descent, Newtonian methods and algorithms that are designed for distributed parallel inference on manifolds such as Sarpabayeva et al. (2018). One can show that the algorithm generally converges to the stationary point, and in the case of strongly convex functions, it converges to the local minimum. We will provide convergence analysis of the algorithms and present applications for a large class of objective functions in various manifold spaces.