Variational Optimization on Lie Groups, with Examples of Leading (Generalized) Eigenvalue Problems

Abstract

The article considers smooth optimization of functions on Lie groups. By generalizing NAG variational principle in vector space (Wibisono et al., 2016) to Lie groups, continuous Lie-NAG dynamics which are guaranteed to converge to local optimum are obtained. They correspond to momentum versions of gradient flow on Lie groups. A particular case of $\mathsf{SO}(n)$ is then studied in details, with objective functions corresponding to leading Generalized EigenValue problems: the Lie-NAG dynamics are first made explicit in coordinates, and then discretized in structure preserving fashions, resulting in optimization algorithms with faithful energy behavior (due to conformal symplecticity) and exactly remaining on the Lie group. Stochastic gradient versions are also investigated. Numerical experiments on both synthetic data and practical problem (LDA for MNIST) demonstrate the effectiveness of the proposed methods as optimization algorithms ($not$ as a classification method).

arXiv commentAccepted by AISTATS 2020; never submitted elsewhere

References in corpus (10)

• An overview of gradient descent optimization algorithms
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Global rates of convergence for nonconvex optimization on manifolds
• Explicit symplectic approximation of nonseparable Hamiltonians: algorithm and long time performance
• Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• Is There an Analog of Nesterov Acceleration for MCMC?
• Towards Riemannian Accelerated Gradient Methods
• Stochastic Approximation for Canonical Correlation Analysis