Source-linked AI summary
Cheap Orthogonal Constraints in Neural Networks: A Simple Parametrization of the Orthogonal and Unitary Group
Mario Lezcano-Casado, David Martínez-Rubio
TL;DR
The paper addresses difficult and costly optimization under orthogonal or unitary constraints, including gradient instability in RNNs. It uses an exponential-map parametrization to convert constrained optimization into Euclidean optimization and reports empirical evidence of superior performance, while noting scope and method limitations.
Problem
Orthogonality-constrained optimization can be difficult and computationally expensive, while RNNs face exploding or vanishing gradients across time steps.
Method
The paper parametrizes orthogonal and unitary matrices through the Lie-group exponential map, enabling unconstrained optimization with general-purpose methods.
Results
The paper reports empirical evidence of superior performance for its approach and smoother, fully convergent expRNN training on the more difficult L = 2000 copying-memory task.
Takeaways & Limitations
The exponential parametrization provides a practical approach to optimization over compact Lie groups, with an implementation trick that enables arbitrary parametrizations at negligible runtime cost.
Takeaways & Limitations
The exponential parametrization is not a retraction for SO(n) when n > 2 or U(n) when n > 1, and one experiment’s comparison implementations mishandled variable-length sequences.
Abstract
from arXiv · showhide
We introduce a novel approach to perform first-order optimization with orthogonal and unitary constraints. This approach is based on a parametrization stemming from Lie group theory through the exponential map. The parametrization transforms the constrained optimization problem into an unconstrained one over a Euclidean space, for which common first-order optimization methods can be used. The theoretical results presented are general enough to cover the special orthogonal group, the unitary group and, in general, any connected compact Lie group. We discuss how this and other parametrizations can be computed efficiently through an implementation trick, making numerically complex parametrizations usable at a negligible runtime cost in neural networks. In particular, we apply our results to RNNs with orthogonal recurrent weights, yielding a new architecture called expRNN. We demonstrate how our method constitutes a more robust approach to optimization with orthogonal constraints, showing faster, accurate, and more stable convergence in several tasks designed to test RNNs.
1. Introduction
The paper targets costly and difficult optimization under orthogonal or unitary constraints, especially the gradient instability affecting RNNs. It introduces an exponential-map parametrization with theoretical and practical advantages for neural-network optimization.
- Motivation: RNN gradients can explode or vanish exponentially across time steps when recurrent kernels lack unitary eigenvalues.This produces very slow convergence or a lack of convergence.
- Motivation: Orthogonal constraints can benefit generalization through implicit regularization, but practical optimization has been neither simple nor computationally cheap.The paper aims to address this gap in constrained optimization.
- Approach: The proposed parametrization uses Lie group theory and theoretical guarantees to handle orthogonality or unitary constraints.The approach is designed for groups including SO(n) and U(n).
- Advantages: The parametrization supports general-purpose optimizers without creating additional minima or saddle points in its main region.Its local representation is unique in the relevant neighborhood.
- Advantages: A structured initializer can exploit the eigenvalue structure of the orthogonal matrix, while implementation overhead remains negligible because the parametrization is batch-size independent.The paper also emphasizes that hard orthogonality constraints need not be enforced directly.
- Approach: The matrix exponential maps skew-symmetric matrices to orthogonal matrices, converting constrained optimization into unconstrained optimization in Euclidean space.Padé approximants and scale-squaring compute the exponential and its gradient.
2. Related Work
Prior work developed manifold optimization, unitary RNN parametrizations, and orthogonality-constrained methods, but these approaches differ in coverage, expressiveness, and computational practicality.
- Riemannian optimization: Riemannian optimization research has adapted classical convergence results to manifolds, while adapting popular optimizers such as RMSPROP and ADAM remains an active topic.The related work distinguishes established Riemannian gradient methods from ongoing optimizer adaptations.
- Orthogonal and unitary groups: Orthogonal-constraint optimization spans Stiefel and Grassmannian manifolds and includes conjugate-gradient and Newton formulations.This line of work has been central in the optimization community.
- Orthogonal and unitary groups: Complex-valued unitary optimization methods generally use approaches similar to those used in the real case.The cited related-work passage places these methods within the broader orthogonal-optimization literature.
- Unitary RNNs: Unitary RNN parametrizations based on FFT-like approaches are memory efficient but do not span the whole unitary group, reducing model expressiveness.Iterated butterfly operations were introduced to address this representation issue.
3. Parametrization of Compact Lie Groups
The paper parametrizes SO(n) and U(n) through matrix exponentials, converting constrained optimization into Euclidean optimization while preserving a complete group representation. The parametrization supports general-purpose optimizers, has favorable local geometry, and introduces a specific retraction limitation.
- Group parametrization: Skew-symmetric and skew-Hermitian matrices form Lie algebras isomorphic to Euclidean vector spaces, supplying unconstrained optimization coordinates.The Lie exponential maps these algebra elements into SO(n) or U(n).
- Group parametrization: SO(n) and U(n) are compact and connected, so matrix exponentials provide a complete parametrization of both groups.The exponential map is surjective on connected compact Lie groups.
- Euclidean optimization: The exponential parametrization pulls optimization on G back to Euclidean space, enabling standard optimizers such as ADAM and ADAGRAD.A minimizer in the Euclidean problem maps to a minimizer on the group through the exponential map.
- Local geometry: On a bounded neighborhood V, the exponential map is analytic and invertible with an analytic inverse, and exp(V) is dense in the group.Within V, the representation is unique and the diffeomorphic parametrization does not create spurious minima or saddle points.
- Local geometry: The parametrization induces a new metric on the group, making its optimization equivalent to Riemannian gradient descent under the pushforward metric.Empirically, initialization in V keeps the optimization path inside V throughout training.
- Retraction limitation: The induced step-update map is not a retraction for SO(n) when n > 2 or U(n) when n > 1.This limits its equivalence to standard retraction-based Riemannian updates outside the stated low-dimensional cases.
4. Numerical Implementation
The paper implements orthogonal recurrent networks through an exponential parametrization, using efficient approximations and separately computed machine-precision gradients. This approach avoids direct orthogonality drift while adding negligible batch-size-dependent overhead.
- Exponential RNN Architecture: EXPRNN models an orthogonal recurrent neural network by parametrizing its recurrent matrix with a skew-symmetric matrix exponential.The complex unitary variant replaces skew-symmetric matrices with skew-Hermitian matrices; experiments use the real case.
- Exponential RNN Architecture: The parametrization allows common unconstrained first-order optimization over skew-symmetric matrices while representing the recurrent matrix as orthogonal.Orthogonality is implicit in the exponential representation rather than enforced by directly storing and updating an orthogonal matrix.
- Approximating the exponential of matrices: Padé approximants combined with scale-squaring efficiently approximate the matrix exponential, reducing approximation error for matrices with norm greater than 1.A degree n Padé approximant matches the exponential's Taylor expansion through degree 2n, while scale-squaring reduces error after scaling the matrix.
- Approximating the exponential of matrices: The exponential parametrization avoids the Cayley transform's divergence when an optimum has −1 as an eigenvalue and preserves local uniqueness with a differentiable inverse.The related learned-diagonal variant mitigates divergence but loses local unicity, whereas the exponential parametrization retains both local uniqueness and differentiability.
- Approximating the exponential of matrices: Padé scale-squaring also maps skew-symmetric matrices to special orthogonal matrices, providing a more precise retraction than the Cayley map at almost no extra computational cost.The observation can improve the precision of methods that optimize orthogonality through retractions.
- Gradient and implementation details: Machine-precision gradients are computed separately, and the parametrization's value and gradient do not depend on batch size, yielding negligible runtime overhead.The stochastic gradient with respect to the orthogonal matrix is computed first, after which the parametrization gradient is applied.
5. Experiments
The experiments evaluate orthogonal RNN parametrizations on copying memory, pixel-by-pixel MNIST, P-MNIST, and TIMIT speech prediction. EXPRNN converges more smoothly and outperforms competing parametrizations across the reported tasks.
- Experimental setup: The evaluation uses copying memory, pixel-permuted MNIST, and TIMIT speech prediction to test long-term dependency handling.The experiments compare EXPRNN with LSTM, URNN, EURNN, SCORNN, and RGD.
- Experimental setup: A learning rate 10 times larger for orthogonal parameters than non-orthogonal parameters yielded good empirical performance.
- Copying memory: The copying task requires recalling K initial characters after a delay of L time-steps and uses cross entropy for evaluation.The standard baseline outputs blanks followed by random symbols, with cross entropy K log(N)/(L + 2K).
- Copying memory: In the harder copying problem with L = 2000, EXPRNN was the only architecture that fully converged to the correct answer.SCORNN training was unstable, whereas EXPRNN showed smoother convergence.
- MNIST and P-MNIST: EXPRNN saturated the orthogonal RNN model's capacity on MNIST and P-MNIST faster than other parametrizations.The reported comparison is summarized by best test accuracy in Table 1.
- TIMIT speech prediction: On TIMIT, the exponential parametrization beat other orthogonal-group parametrizations and LSTM by a large margin in reported test MSE.The comparison uses test MSE at the epoch with the lowest validation loss.
- TIMIT speech prediction: The TIMIT comparisons require caution because some competing implementations mishandled variable-length sequences and one reported lower-than-correct batch MSE.Even under this unfavorable scenario, the parametrization obtained results twice as good as those from the other architectures.
6. Conclusion and Future Work
The paper concludes with three contributions: Lie-group parametrization, efficient implementation, and improvements to Riemannian-gradient methods. Future work includes coupling the approach with LSTM or extending it to settings such as the Stiefel manifold.
- Contributions: The paper presents a Lie-group approach for optimization over compact groups including SO(n) and U(n), with theoretical and empirical support.
- Contributions: An implementation trick enables arbitrary parametrizations at negligible runtime cost.
- Contributions: The paper sketches improvements to existing Lie-group optimization methods using Riemannian gradient descent.
- Future work: Coupling the ideas with the LSTM architecture to improve performance is left for future work.
- Future work: Formalizing how orthogonal constraints help deep feed-forward networks would require generalizing the results to homogeneous Riemannian manifolds such as the Stiefel manifold.
A. Riemannian Geometry and Lie Groups
This appendix reviews the classical Riemannian geometry and Lie group theory used to support the paper's proofs. It points readers to standard references for both areas.
- Purpose: The section supplies background in classical Riemannian geometry for the proofs in later sections.
- Purpose: It also introduces Lie group theory as a second mathematical foundation for the paper's theoretical development.
- References: The authors cite do Carmo for Riemannian geometry and Hall for an elementary, matrix-focused introduction to Lie groups.
A.1. Riemannian geometry
The section defines the geometric and Lie-group concepts underlying the paper, including metrics, connections, geodesics, exponential maps, and group structure. It also identifies canonical bi-invariant metrics for SO(n) and the unitary group.
- Riemannian geometry: A Riemannian manifold is a smooth manifold equipped with a smoothly varying positive-definite inner product on each tangent space.
- Riemannian geometry: The metric defines curve length and induces distance as the infimum of lengths of piecewise-smooth connecting curves.
- Connections: An affine connection differentiates vector fields, enabling parallel transport and the Levi-Civita connection when metric compatibility and zero torsion hold.
- Geodesics and exponential maps: Geodesics have covariantly constant tangent vectors, and the exponential map sends an initial tangent vector to the geodesic's endpoint at time one.
- Lie groups: A Lie group is a smooth manifold with smooth multiplication and inversion; its tangent space at the identity is the Lie algebra.For matrix Lie groups, the adjoint action is gXg^-1 and the Lie bracket is XY − YX.
- Metrics on Lie groups: Every compact Lie group admits a bi-invariant metric, with tr(X^⊺Y) for SO(n) and tr(X∗Y) in the unitary case.
B. Retractions
Retractions provide first-order approximations to the Riemannian exponential map and support manifold optimization. For embedded manifolds, differentiable projections yield concrete retractions, including normalization on spheres and projection onto SO(n).
- A retraction is a first-order approximation of the Riemannian exponential map.The exponential map itself is a retraction.
- For an embedded submanifold, a differentiable surjective projection produces a retraction through the projection-based construction.The projection is idempotent, and the tangent space is identified with a subspace of the ambient Euclidean space.
- Sphere: On the sphere, retraction maps a tangent perturbation v to the normalized point (x + v) / ∥x + v∥.
- Special orthogonal group: For SO(n), the projection of X = UΣV^⊺ is UV^⊺, which is the ambient orthogonal projection onto SO(n) under the canonical metric.
- The SO(n) and sphere constructions are orthogonal projections, whereas the general projection-based proposition does not require orthogonality.
C. Comparing Riemannian gradient descent and the exponential parametrization
The paper compares Riemannian gradient descent on SO(n) with gradient descent after exponential parametrization. Although both follow geodesic flows locally, they generally induce different metrics and agree only under specific conditions.
- SO(n) example: The SO(n) example represents B as e^A for skew-symmetric A and compares manifold optimization with optimization over the matrix Lie algebra.The manifold uses the canonical metric inherited from the ambient matrix space.
- Riemannian gradient descent: Riemannian gradient descent follows the geodesic generated by the negative manifold gradient, using the Riemannian exponential map for its update.
- Riemannian gradient descent: The tangent space and its canonical-metric projection determine the manifold gradient used in the SO(n) update.
- Riemannian gradient descent: Multiplication by an orthogonal matrix is an isometry, allowing the Riemannian exponential to be computed by transporting to the identity, exponentiating, and transporting back.
- Exponential parametrization: The exponential-parametrization update is ordinary gradient descent applied after composing the objective with the exponential map.
- Comparison: Both updates follow geodesic flows locally, but the two methods generally produce different metrics and coincide only under necessary and sufficient conditions.
C.1. Optimization on Lie Groups with Bi-invariant Metrics
For compact Lie groups, bi-invariant metrics connect Lie-group geometry with matrix algebra and make exponential parametrization amenable to Euclidean first-order optimization. The paper develops the geometric identities needed to compute gradients through the exponential map.
- Bi-invariant metrics: Every compact Lie group admits a bi-invariant metric, which is invariant under both left and right translations.
- Bi-invariant metrics: A bi-invariant metric lets many Riemannian computations reduce to matrix algebra rather than differential-equation systems.
- Exponential maps: With a bi-invariant metric, the Riemannian exponential at the identity agrees with the Lie exponential, which also agrees with the matrix exponential for matrix Lie groups.
- Exponential parametrization: The Lie exponential is surjective for connected Lie groups equipped with a bi-invariant metric, allowing optimization to be mapped to the Lie algebra.
- Exponential parametrization: Because the Lie algebra is a vector space, classical Euclidean first-order methods can optimize the pulled-back objective using its gradient.
- Gradient computation: The differential of the exponential map is required to define and compute the gradient of the objective composed with the exponential.
D. Maximal Normal Neighborhood of the Identity
The exponential map has a maximal bounded neighborhood around the identity where it is analytically invertible. Its differential becomes singular when eigenvalue differences reach nonzero multiples of 2πi, while the boundary has measure zero for the compact cases studied.
- The maximal normal neighborhood is characterized by studying where the exponential ceases to be an immersion or where its differential loses invertibility.
- For a compact connected matrix Lie group, the exponential is analytic and has an analytic inverse on a bounded open neighborhood of the origin.
- The exponential differential is singular when two eigenvalues of A differ by a nonzero integer multiple of 2πi.
- On compact matrix Lie groups, the exponential is injective on the domain where every eigenvalue has imaginary part strictly between −π and π.
- SO(n): For SO(n), skew-symmetric matrices have purely imaginary conjugate-paired eigenvalues, placing singularities on the boundary of the specified domain.
- SO(n) and U(n): The exponential map is surjective on SO(n) and U(n), and the boundary of the normal-neighborhood domain has measure zero.
E. Hyperparameters for the Experiments
The experiments use fixed training settings and reproducibility controls, with hyperparameters reported in Table 3.
- Batch size was 128 across all experiments.
- Orthogonal parameters used learning rates 10 times lower than non-orthogonal parameters.
- Numpy and Pytorch seeds were fixed to 5544 for reproducibility, matching the seed used by Helfrich et al. (2018).
- Table 3 reports the hyperparameters used for the experiments in Section 5.