Efficient Riemannian Optimization on the Stiefel Manifold via the Cayley Transform

Jun Li, Fuxin Li, Sinisa Todorovic

TL;DR

Enforcing orthonormality in neural network weights improves stability and performance, but standard methods are computationally prohibitive. This paper introduces Cayley SGD and Cayley ADAM, which utilize a novel iterative approximation of the Cayley transform and an implicit vector transport mechanism. These innovations allow for manifold optimization with significantly lower overhead, making strict orthonormality constraints practical for large-scale deep learning.

The Challenge of Orthonormal Constraints

In deep learning, constraining weight matrices to be orthonormal (i.e., $W^T W = I$) offers significant benefits. It stabilizes neural activations, prevents gradients from vanishing or exploding—especially in Recurrent Neural Networks (RNNs)—and can improve overall generalization.

Mathematically, the set of all orthonormal matrices forms a Stiefel manifold. Optimizing over this manifold requires specialized "Riemannian" techniques. The standard approach involves an "exponential map" or a "Cayley transform" to ensure that weights remain on the manifold after every update. However, these operations typically require matrix inversions or Singular Value Decompositions (SVD). These operations scale poorly ($O(n^3)$) and are far too slow for the massive parameter matrices found in modern Convolutional Neural Networks (CNNs).

Proposed Methods

The authors propose two primary innovations to make Stiefel manifold optimization efficient and scalable:

  1. Iterative Cayley Transform: Instead of computing the exact, closed-form Cayley transform (which requires a costly matrix inverse), the authors propose a fixed-point iteration: $$Y(\alpha) = X + \frac{\alpha}{2}W(X + Y(\alpha))$$ This approach only requires a few matrix multiplications. The authors prove that this iteration converges rapidly to the true transform. In practice, just two iterations ($s=2$) are sufficient to maintain near-perfect orthonormality.

  2. Implicit Vector Transport: To use momentum on a manifold, vectors from different time steps cannot simply be added together because they belong to different "tangent spaces." Usually, this requires a complex operation called "parallel transport." The authors show that because the Cayley transform implicitly projects vectors onto the tangent space, they can perform linear combinations of momentum and gradients in Euclidean space and let the transform handle the manifold projection automatically.

These contributions are integrated into two new algorithms: Cayley SGD with momentum and Cayley ADAM.

Key Insights

  • Efficiency through Iteration: The core breakthrough is realizing that an exact matrix inverse is unnecessary to stay on the manifold. A fast iterative approximation is computationally cheaper and actually more numerically stable than the closed-form version in deep learning frameworks.
  • Bypassing Differential Geometry: By treating the Stiefel manifold as a submanifold of Euclidean space, the authors simplify the "vector transport" problem. This allows them to adapt popular optimizers like ADAM to manifolds without the heavy mathematical machinery usually required.
  • Orthonormality as a Speedup: While each iteration of Cayley SGD is slightly slower than vanilla SGD, the network often converges in fewer epochs. The orthonormality constraint acts as a powerful regularizer that smooths the optimization landscape.

Key Results

The authors evaluated their algorithms on standard image classification (CIFAR-10/100) and sequence modeling benchmarks (Pixel-by-pixel MNIST).

Training curves on CIFAR-10 and CIFAR-100 comparing Cayley optimizers against baselines.
  • Computational Speed: On a Wide ResNet (WRN-28-10), Cayley SGD took approximately 218 seconds per epoch, compared to 943 seconds for other state-of-the-art manifold methods (like OMDSM) and 1071 seconds for the closed-form Cayley transform.
  • Accuracy Gains: Cayley ADAM achieved a top error rate of 3.57% on CIFAR-10 and 18.10% on CIFAR-100, outperforming standard ADAM (3.86% and 18.45% respectively).
  • RNN Performance: For unitary RNNs (uRNNs), the proposed methods reduced training time per iteration by about 35% while maintaining or slightly improving accuracy on the pixel-by-pixel MNIST task.
  • Numerical Precision: The iterative method with $s=2$ actually produced a lower unitariness error ($7.38 \times 10^{-6}$) than the closed-form version ($8.27 \times 10^{-5}$), likely due to avoiding the accumulation of rounding errors during matrix inversion.

Limitations and Future Work

  • Overhead vs. Vanilla: Although much faster than previous manifold methods, Cayley SGD/ADAM is still roughly 2x slower per iteration than standard Euclidean SGD/ADAM. The trade-off is only beneficial if the accuracy gain or faster epoch-wise convergence justifies the per-step cost.
  • Hyperparameters: The method introduces new hyperparameters, such as the number of iterations ($s$) and a manifold-specific learning rate ($l_{st}$), which may require tuning.
  • Scope: The paper primarily focuses on $p \le n$ (non-square matrices). While this covers most CNN layers, further exploration into very high-dimensional or specifically structured matrices could be beneficial.

Summary updated

Abstract

Strictly enforcing orthonormality constraints on parameter matrices has been shown advantageous in deep learning. This amounts to Riemannian optimization on the Stiefel manifold, which, however, is computationally expensive. To address this challenge, we present two main contributions: (1) A new efficient retraction map based on an iterative Cayley transform for optimization updates, and (2) An implicit vector transport mechanism based on the combination of a projection of the momentum and the Cayley transform on the Stiefel manifold. We specify two new optimization algorithms: Cayley SGD with momentum, and Cayley ADAM on the Stiefel manifold. Convergence of Cayley SGD is theoretically analyzed. Our experiments for CNN training demonstrate that both algorithms: (a) Use less running time per iteration relative to existing approaches that enforce orthonormality of CNN parameters; and (b) Achieve faster convergence rates than the baseline SGD and ADAM algorithms without compromising the performance of the CNN. Cayley SGD and Cayley ADAM are also shown to reduce the training time for optimizing the unitary transition matrices in RNNs.
BibTeX
@inproceedings{li2020efficient,
  author = {Jun Li and Fuxin Li and Sinisa Todorovic},
  title = {{Efficient Riemannian Optimization on the Stiefel Manifold via the Cayley Transform}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=u6vAnWlupt1},
}
Figure