Optimization flows landing on the Stiefel manifold⋆

Bin Gao, Simon Vary, Pierre Ablin, P.-a. AbsilIFAC-PapersOnLine 2022 · DOI

TL;DR

This paper introduces a novel continuous-time "landing flow" for optimizing functions over the Stiefel manifold (the set of orthonormal matrices). Unlike traditional methods that strictly enforce the manifold constraint, this flow allows iterates to temporarily leave the manifold, simplifying computations. The authors demonstrate that this flow asymptotically converges to the Stiefel manifold and its critical points, offering a more robust and potentially faster optimization approach.

What Problem Does This Paper Address?

Many important problems in machine learning and scientific computing involve optimizing functions subject to orthogonality constraints. This is often formulated as minimizing a function $f(X)$ where $X$ is a matrix with orthonormal columns, i.e., $X^T X = I_p$. This set of matrices is known as the Stiefel manifold. Traditional optimization methods for these problems typically require complex "retraction" operations to ensure that each step of the optimization stays on the manifold. These retractions can be computationally expensive, especially for complex objective functions. The paper addresses the challenge of developing an optimization flow that bypasses the need for explicit retractions while still guaranteeing convergence to the correct solutions on the Stiefel manifold.

Methods

The core of the paper is the introduction of a "landing flow," a continuous-time dynamical system defined by a differential equation: $\dot{X}(t) = -\Lambda(X(t))$. The "landing field" $\Lambda(X)$ is composed of two parts:

  1. $\psi(X)X$: This term is shown to be the Riemannian gradient of $f$ on a generalized Stiefel manifold with a specific metric.
  2. $\lambda \nabla N(X)$: This term is related to the distance from the Stiefel manifold, where $N(X) = \frac{1}{2} \|X^T X - I_p\|^2$, and $\lambda > 0$ is a regularization parameter.

A key innovation is the introduction of a generalized Stiefel manifold $St_M(p,n) = \{Y \in \mathbb{R}^{n \times p} : Y^T Y = M\}$ for a symmetric positive-definite matrix $M$. This generalization allows for a geometric interpretation of the landing field as the sum of a Riemannian gradient on this generalized manifold and a vector in its normal space. The paper proves that this orthogonality between the two components of $\Lambda(X)$ is crucial for the flow's properties.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • "Landing" as a Feature, Not a Bug: The most significant idea is that allowing optimization iterates to temporarily leave the Stiefel manifold (i.e., $X^T X \neq I_p$) can simplify the dynamics and potentially accelerate convergence. The flow is designed to "land" back on the manifold asymptotically.
  • Geometric Interpretation via Generalized Manifolds: By introducing a generalized Stiefel manifold $St_M(p,n)$, the authors provide a clear geometric interpretation for the landing flow. The flow's vector field is decomposed into a Riemannian gradient on this generalized manifold and a normal vector, highlighting its structure.
  • Orthogonality is Key: The paper emphasizes the importance of the orthogonality between the Riemannian gradient term and the "manifold distance" term in the landing field. This orthogonality ensures the well-definedness of the flow and its convergence properties, even for $\lambda > 0$.
  • Global Convergence Guarantees: The authors prove that the landing flow globally converges to the set of critical points of $f$ on the Stiefel manifold. This is a strong theoretical guarantee, suggesting robustness across different starting points.
  • Asymptotic Stability of Minima: Local minima and isolated critical points of $f$ on the Stiefel manifold are shown to be asymptotically stable equilibria of the landing flow, meaning trajectories starting near them will converge to them.

Key Results

  • The proposed landing flow $\dot{X} = -\Lambda(X)$ is well-defined and has unique solutions for any $\lambda > 0$.
  • The flow asymptotically converges to the Stiefel manifold, meaning $\lim_{t \to \infty} X(t)^T X(t) = I_p$.
  • The flow globally converges to the set of critical points of $f$ on the Stiefel manifold.
  • Local minima and isolated critical points of $f$ on the Stiefel manifold are asymptotically stable equilibria of the landing flow.

Limitations and Future Work

  • Continuous-Time Focus: The paper focuses on a continuous-time dynamical system. A natural next step, which the authors mention, is to develop a discrete-time counterpart of this landing flow that retains its favorable convergence properties. This would be more directly applicable to practical numerical optimization.
  • Theoretical vs. Practical Speedup: While the flow offers theoretical advantages (simpler dynamics, guaranteed convergence), the paper doesn't provide extensive empirical results comparing its practical speedup against state-of-the-art discrete methods on benchmark problems.
  • Generalization of Objective Functions: The analysis assumes $f$ is continuously differentiable and its gradient is locally Lipschitz. Further exploration might involve extending the results to non-smooth or more complex objective functions.

Summary updated

Abstract

We study a continuous-time system that solves the optimization problem over the set of orthogonal matrices, which is also known as the Stiefel manifold. The resulting optimization flow follows a path that is not always on the manifold but eventually lands on the manifold. We introduce a generalized Stiefel manifold to which we extend the canonical metric of the Stiefel manifold. We show that the vector field of the proposed flow can be interpreted as the sum of a Riemannian gradient on a generalized Stiefel manifold and a normal vector. Moreover, we prove that the proposed flow globally converges to the set of critical points, and any local minimum and isolated critical point is asymptotically stable.
BibTeX
@inproceedings{gao2022optimization,
  author = {Bin Gao and Simon Vary and Pierre Ablin and P.-A. Absil},
  title = {{Optimization flows landing on the Stiefel manifold⋆}},
  booktitle = {IFAC-PapersOnLine},
  year = {2022},
  doi = {10.1016/j.ifacol.2022.11.023},
}
Figure