Abstract: Optimization on Riemannian manifolds, particularly for Symmetric Positive Definite (SPD) matrices, is a cornerstone of second-order optimization and probabilistic modeling in machine learning. However, standard Riemannian methods often suffer from high computational costs and mathematical intractability on complex submanifolds. This paper introduces Generalized Normal Coordinates (GNCs), a framework that "flattens" curved manifolds into local Euclidean spaces. By leveraging GNCs, standard momentum-based gradient descent can be applied to complex submanifolds without solving expensive differential equations. The resulting optimizers are matrix-inverse-free and demonstrate superior performance and stability in large-scale deep learning tasks.
Introduction
Presented at ICML 2023, this work addresses a significant challenge in deep learning: optimizing parameters that live on curved Riemannian manifolds. A prime example is the space of Symmetric Positive Definite (SPD) matrices, which are essential for second-order optimization techniques like KFAC. Traditional Riemannian optimization is often computationally prohibitive due to two main factors: the $O(k^3)$ complexity of operations like the exponential map and parallel transport, and the difficulty of enforcing submanifold constraints (e.g., sparsity or specific structural patterns) which often require solving complex ordinary differential equations (ODEs). This paper introduces a framework that simplifies these manifold operations into efficient, Euclidean-like updates.
Generalized Normal Coordinates (GNCs)
The core innovation is the Generalized Normal Coordinate (GNC). Instead of working in a global coordinate system where the space is curved, the authors generate a new local coordinate system at every iteration. In this local "bubble," the metric is orthonormalized, making it appear as a flat Euclidean space. This allows researchers to perform standard Euclidean Gradient Descent with momentum, which automatically accounts for the manifold's curvature when mapped back.
As illustrated in the figure above, the coordinate system moves with the optimization point, bypassing the need for global geodesic ODEs. For structured SPD matrices, the framework exploits Lie algebra to represent the manifold as a Lie subgroup, ensuring that updates naturally stay on the desired submanifold.
Inverse-Free Optimization and Efficiency
To overcome the computational bottleneck of matrix inversions, the authors develop an "inverse-free" optimizer. By using approximations of the matrix exponential—such as linear ($I + N$) or quadratic truncations—they create updates that rely solely on matrix multiplications. This approach is not only faster but also more numerically stable than traditional methods like KFAC, particularly in low-precision floating-point environments where matrix inversions can lead to numerical instability.
The technical summary in the table above highlights the flexibility of GNCs compared to Standard Normal Coordinates (SNC). While SNCs require zero Christoffel symbols at the current point, GNCs allow them to be non-zero, providing a more general framework for submanifold optimization while maintaining a simplified metric.
Experimental Validation
The authors validated their approach on synthetic benchmarks and large-scale deep learning tasks, including image classification on CIFAR-100 and ImageNet-100. They tested a wide range of architectures, such as VGG-16, RegNetX, and ConvMixer.
Key results include:
- Superior Accuracy: On ImageNet-100 with ConvMixer, the GNC-based inverse-free update achieved an 18.8% test error, outperforming KFAC's 20.7%.
- Robustness: The method proved more stable than KFAC in various settings, avoiding the "exploding" values often associated with matrix inversion.
- Efficiency: The proposed updates maintain running times similar to KFAC but offer better optimization performance per second, as evidenced by error-vs-time metrics.
Conclusion and Future Directions
The introduction of Generalized Normal Coordinates provides a powerful tool for simplifying Riemannian optimization. By transforming complex manifold updates into local Euclidean steps, this framework enables the use of momentum and structured constraints without the typical computational overhead. While currently focused on SPD manifolds with Lie group structures, the authors suggest that this "moving frame" approach could be extended to other non-SPD manifolds, such as Stiefel or Grassmann manifolds, potentially offering a unified framework for manifold optimization in deep learning.
Summary updated