PaperlayerView exact revision on arXiv

Source-linked AI summary

Trivializations for Gradient-Based Optimization on Manifolds

Mario Lezcano-Casado

arXiv:1909.09501v2cs.LGstat.ML

TL;DR

Manifold constraints can make gradient-based optimization difficult, especially for matrix-valued objects and for adaptive optimizers designed for Euclidean spaces. The paper formalizes trivializations and introduces dynamic basis changes to address problematic regions of fixed parametrizations. Dynamic trivializations combine the strengths of parametrization methods and Riemannian gradient descent, with reported convergence improvements in neural-network optimization.

  • Problem

    Matrix-manifold constraints are challenging, while widely used adaptive optimizers are designed for Euclidean spaces and are not clearly generalizable to most manifolds.

  • Method

    The paper studies Euclidean parametrizations of manifolds and dynamically changes the tangent-space basis while applying standard Euclidean optimizers to local trivializations.

  • Results

    Dynamic trivializations combine classic trivializations and Riemannian gradient descent as limit cases and improve convergence in the reported neural-network optimization setting.

  • Takeaways & Limitations

    Dynamic trivializations provide a manifold optimization family that combines parametrization methods with Riemannian gradient descent and generalizes Euclidean optimizers to manifolds.

  • Takeaways & Limitations

    Riemannian and Lie exponential parametrizations may create saddle points or local minima near certain manifold regions, and trivializations can yield zero transformed gradients when their derivative vanishes.

Abstract

from arXiv · show

We introduce a framework to study the transformation of problems with manifold constraints into unconstrained problems through parametrizations in terms of a Euclidean space. We call these parametrizations "trivializations". We prove conditions under which a trivialization is sound in the context of gradient-based optimization and we show how two large families of trivializations have overall favorable properties, but also suffer from a performance issue. We then introduce "dynamic trivializations", which solve this problem, and we show how these form a family of optimization methods that lie between trivializations and Riemannian gradient descent, and combine the benefits of both of them. We then show how to implement these two families of trivializations in practice for different matrix manifolds. To this end, we prove a formula for the gradient of the exponential of matrices, which can be of practical interest on its own. Finally, we show how dynamic trivializations improve the performance of existing methods on standard tasks designed to test long-term memory within neural networks.

1 Introduction

The paper frames manifold-constrained optimization as a challenge for matrix-valued objects and develops trivializations that convert constrained problems into unconstrained ones. It introduces dynamic trivializations to address problematic regions of fixed parametrizations while combining properties of parametrization methods and Riemannian gradient descent.

  • Motivation: Matrix constraints are harder to handle than simple element-wise vector constraints used in gating-based neural architectures.The paper motivates a framework for optimization on matrix manifolds in machine learning and neural networks.
  • Aim: The paper targets a theoretically sound and efficiently implementable framework for gradient-based optimization on matrix manifolds.
  • Trivializations: Trivialization transforms a constrained optimization problem on a manifold into an unconstrained problem through a parametrization φ: R^n → M.For sufficiently regular parametrizations, gradient descent on the transformed problem is equivalent to Riemannian gradient descent under a changed metric.
  • Fixed-parametrization issue: Riemannian and Lie exponential parametrizations can create saddle points or local minima near certain manifold regions.
  • Dynamic trivializations: Dynamic trivializations repeatedly lift optimization to the current tangent space and move the manifold basis when the current parametrization becomes problematic.The method optimizes f ◦ φ_xi with Euclidean optimizers, then sets x_i+1 := φ_xi(y_k) and restarts in T_xi+1M.
  • Consequences and implementation: Dynamic trivializations have Riemannian gradient descent and classic trivializations as limit cases, combining strengths of both and generalizing Euclidean optimizers to manifolds.The paper also derives matrix-exponential gradient formulas and reports improved performance for orthogonally constrained neural-network optimization.

2 Related Work

Related work covers Riemannian optimization, parametrization-based optimization, and Lie-group trivialization. The paper positions its framework as an extension of existing exponential and Cayley-map methods with negligible execution cost and improved practical convergence.

  • Riemannian optimization: Riemannian optimization developed manifold versions of methods including conjugate gradient and Newton algorithms, with convergence results for several first- and second-order settings.
  • Trivialization: Lie-group parametrization through the Lie exponential is commonly called trivialization in differential-equation research, a term adopted here because the general ideas are similar.
  • Parametrization-based optimization: Parametrizing manifolds through Euclidean spaces has been used for symmetric positive definite matrices, compact Lie groups, SO(n), and unitary groups.
  • Relation to prior methods: The framework extends Lie-exponential and Cayley-map methods for optimization on SO(n) and can be implemented on top of them at negligible execution cost.
  • Relation to prior methods: The paper reports that its theoretical improvement translates into better convergence in practice.

3 Problem Set-Up

The paper formulates optimization on a connected manifold equipped with Riemannian structure and reviews exponential-map and retraction-based gradient updates. It also identifies the practical difficulty of extending Euclidean adaptive optimizers to general manifolds.

  • Manifold structure: A Riemannian metric supplies the distance and steepest-descent structure that a differentiable manifold does not intrinsically possess.
  • Exponential-map descent: The Riemannian exponential maps tangent-space rays to geodesics, providing the update x_t+1 = exp_x_t(−η∇f(x_t)).This update follows the geodesic in the steepest-descent direction for η > 0.
  • Retractions: Retractions provide first-order approximations to the exponential map and yield the update x_t+1 = r_x_t(−η∇f(x_t)).In many cases, this update has the same convergence properties as exponential-map Riemannian gradient descent.
  • Practical motivation: Riemannian gradient descent is practically limited because adaptive Euclidean optimizers such as ADAM, ADAGRAD, and RMSPROP often outperform vanilla SGD.Although generalizations exist for product manifolds, extending these methods to most manifolds remains unclear.

4 Trivializations

Trivializations convert manifold-constrained optimization into unconstrained optimization, with diffeomorphic maps behaving as metric changes rather than introducing new critical points. Riemannian and Lie exponential trivializations have favorable local behavior but can create minima or saddle points near their non-diffeomorphic boundaries.

  • Trivializations: Trivializations transform constrained optimization on a manifold into unconstrained optimization by composing the objective with a surjective parametrization.The framework includes vector examples such as ReLU and sigmoid maps, as well as exponential maps for manifolds.
  • Trivializations: For a diffeomorphic trivialization, Euclidean gradient descent corresponds to Riemannian gradient descent under a metric induced by the parametrization.Such a map changes the metric without adding local minima or saddle points.
  • The Riemannian trivialization: The Riemannian exponential is a trivialization whose metric agrees to first order with the manifold metric near the base point, but it ceases to be diffeomorphic at the cut locus.On a connected, complete manifold, the exponential is a diffeomorphism on a maximal radially convex neighborhood whose image covers the manifold; its boundary corresponds to the cut locus.
  • The Riemannian trivialization: The cut locus can introduce minima or saddle points, although its problematic tangent-space preimage has Hausdorff dimension either 0 or n −1 and Lebesgue measure zero.The text nevertheless cautions that the cut locus can matter in practice and is generally not differentiable.
  • The Lie trivialization: The Lie exponential is diffeomorphic on matrices satisfying |Im(λ_i(A))| < π, but its boundary creates the same local-minima and saddle-point issue as the Riemannian exponential.For connected compact Lie groups it is surjective and coincides with a suitable Riemannian trivialization at the identity; otherwise it can be used on its image or extended through the paper’s construction.

5 Dynamic Trivializations

Dynamic trivializations periodically move the parametrization basis during Euclidean optimization on a manifold, addressing distortions that arise as optimization moves away from the initial point. The framework interpolates between fixed trivializations and Riemannian gradient descent while permitting standard Euclidean optimizers.

  • Dynamic trivialization: Dynamic trivializations change the parametrization basis after K optimization steps to reduce problems caused by moving away from the initial point.The new basis is the current manifold point reached after the preceding optimization block.
  • Algorithm: Given a retraction, the method performs K Euclidean optimization updates in a tangent space, then maps the result back to the manifold and resets the tangent-space origin.The Euclidean updates can use SGD, ADAM, ADAGRAD, or RMSPROP.
  • Limit cases: K = ∞ recovers a fixed trivialization, while K = 1 with regular SGD recovers stochastic Riemannian gradient descent using the retraction.These are the two limiting cases of the dynamic procedure.
  • Limit cases: With φ = expM, dynamic trivializations interpolate between exponential-trivialization optimization and stochastic Riemannian gradient descent.Using other Euclidean optimizers generalizes ADAM, ADAGRAD, and RMSPROP to manifolds.

6 Gradient Computations and Examples

The paper develops gradient computations needed to implement dynamic trivializations and applies them to matrix manifolds using exponential maps and retractions. A matrix-exponential gradient formula, combined with an existing derivative approximation, enables machine-precision implementation.

  • Gradient computations: The section supplies explicit gradients for the two trivialization families so dynamic trivializations can be implemented.The required gradients concern the Lie and Riemannian exponential families.
  • Matrix exponential: A proposition gives the gradient of the matrix exponential parametrization for matrix-valued functions.The matrix exponential is both a Lie trivialization and an ingredient in Riemannian exponentials for many matrix manifolds.
  • Matrix exponential: The gradient of the exponential can be approximated to machine precision by combining the proposition with an existing approximation algorithm for d exp.This makes the gradient usable in first-order optimization methods.
  • Other retractions: The framework also covers retractions, including Cayley maps and projection-based retractions for matrix manifolds.For SO(n), the projection uses the SVD B = UΣV^⊺ and maps B to UV^⊺ when defined.

7 Experiments

Experiments evaluate dynamic trivializations for orthogonal recurrent networks on long-term-memory tasks, comparing several established orthogonal parametrizations and Riemannian gradient descent. Dynamic variants generally improve stability and performance, with DTRIV100 and DTRIV∞ repeatedly strongest.

  • Experimental setup: The experiments test DTRIV with basis changes every K = 1, 100, or ∞ steps on orthogonal optimization.Comparisons include EXPRNN, SCORNN, SCURNN, RGD, and a vanilla LSTM.
  • Tasks: The architecture is a vanilla RNN with an orthogonal layer parametrized using the Lie trivialization, evaluated on pixel-by-pixel MNIST and TIMIT.The MNIST variants process sequences of 784 pixels, while TIMIT uses variable-length speech sequences.
  • MNIST: 0.4% out of the 1.3% possible in the largest size is gained by adding any dynamic trivialization to the Lie parametrization on the MNIST experiment.The passage reports that dynamic trivializations always improve the previous results in that experiment.
  • TIMIT: DTRIV100 and DTRIV∞ always improve the performance of their static counterparts with identity bases and of RGD on TIMIT.The TIMIT comparison uses test MSE selected at the epoch with the lowest validation MSE.
  • Evaluation caveat: The paper recomputes the SCURNN validation and test losses using the correct denominator because the reported MSE included padded zeros.The original calculation divided by the longest sequence length times batch size rather than the sum of sequence lengths.

8 Conclusion and Future Work

The paper concludes that dynamic trivializations combine parametrization-based optimization with Riemannian gradient descent and can improve neural-network convergence by moving the parametrization point. Extending the framework to additional manifolds remains open.

  • Conclusion: Dynamic trivializations combine the strengths of parametrizations and Riemannian gradient descent for manifold optimization.The paper presents this combination as its central optimization approach.
  • Future work: Applying dynamic trivializations to other interesting manifolds remains an open line of research.The paper gives some computations for common manifolds in an appendix as an initial step.

B Parametrizations on Manifolds

This section analyzes how parametrizations transform manifold optimization, showing when unconstrained gradient descent corresponds to Riemannian gradient descent and when it does not. It also characterizes the induced optimization step through retractions and local isometries.

  • Parametrizations on Manifolds: Parametrizations rewrite optimization on a manifold M as optimization of f ◦φ on another Riemannian manifold N.The framework assumes a diffeomorphism φ between the manifolds and computes gradients for the pulled-back objective.
  • Induced metrics: A parametrization induces a metric on M through the adjoint differential dφ∗, making φ a Riemannian submersion under the induced metric.The construction relies on the inverse function theorem when φ is a diffeomorphism.
  • Retractions: Gradient descent using the induced metric and a retraction can therefore define an optimization method fundamentally different from Riemannian gradient descent under the original metric.The distinction arises because the transformed map need not be a retraction with respect to the original metric.
  • Retractions: The retraction φ∗r is a valid retraction exactly when φ is a local isometry.This condition expresses whether the transformed update preserves the relevant gradient structure under the original metric.

C Proof of Theorem 4.7

This section proves that the Lie exponential is injective, and hence a diffeomorphism, on a bounded spectral domain of a matrix Lie algebra. The proof combines a commutation theorem with properties of nilpotent upper-triangular matrices.

  • Injectivity proof: If A and B lie in U and exp(A) = exp(B), Hille’s theorem implies that A and B commute, yielding exp(A −B) = I.The commutation relation permits combining the exponentials before analyzing A −B.
  • Theorem: For a closed subgroup G of GL(n, C), the Lie exponential is a diffeomorphism on U = {A ∈g | |Im(λi(A))| < π}.The domain is defined by bounding the imaginary parts of all eigenvalues of A.
  • Proof strategy: The differential of the exponential is surjective on U, so the proof reduces to establishing injectivity there.The argument uses a classic result for the differential and focuses on showing exp(A) = exp(B) implies A = B.
  • Injectivity proof: The spectral bound implies that A −B has only zero eigenvalues and can be treated as an upper-triangular nilpotent matrix.The proof then reduces to showing that such a matrix exponentiates to the identity only when it is zero.
  • Nilpotent matrices: For upper-triangular matrices with ones on the diagonal, B −I is nilpotent, so the logarithm series converges and the exponential is bijective on this set.This establishes the final nilpotent-matrix step used in the injectivity argument.

D Gradient of the Matrix Exponential

This section derives gradient formulas for matrix functions, especially the matrix exponential, and connects them to practical implementations of trivializations. The results extend beyond the exponential to other analytic matrix functions and several inner products.

  • Matrix exponential: The section gives a formula for the gradient of the pullback of a function by the matrix exponential.The implementation of these formulas on different manifolds is discussed separately.
  • General matrix functions: The stronger result also applies to functions such as cos(X), sin(X), and related matrix functions.The paper notes that the result is useful across functional and numerical analysis, although a version appears in prior literature without proof.
  • General matrix functions: Theorem D.1 computes the adjoint differential for matrix functions induced by real analytic scalar functions under the canonical inner product.The derivation reduces matrix-function terms to adjoints of left and right multiplication operators.
  • Lie trivializations: The matrix-exponential gradient formula yields gradients for static and dynamic Lie trivializations on matrix Lie groups.The same formulas apply to GL(n) and analogous real matrix Lie groups, with an analogous complex case.
  • Noncanonical metrics: For left-translated inner products, the gradient becomes ∇(f ◦exp)(A) = B(d exp)A⊺(B−1∇f(eA)).This formula follows because left translations are isometries for these metrics.

E.1 Compact matrix Lie groups

This section describes exponential and retraction-based trivializations for compact matrix Lie groups and several matrix manifolds. It identifies useful formulas, computational costs, and cases where dynamic trivializations extend the available parametrizations.

  • Compact matrix Lie groups: Tangent spaces of a matrix Lie group are identified through left multiplication as T_BG = {BA | A ∈g}.Thus, the Lie algebra at the identity parametrizes every tangent space of the group.
  • Compact matrix Lie groups: For compact Lie groups with a bi-invariant metric, the Lie and Riemannian exponentials agree as expG,B(Ã) = B exp(B−1Ã).Under these assumptions, the Riemannian exponential is surjective.
  • Compact matrix Lie groups: For real and complex tori, the exponential is a Riemannian covering map and therefore a local isometry that creates neither local minima nor saddle points.Static trivializations are consequently sufficient for these manifolds.
  • Noncompact matrix groups: On GL(n) and SL(n), the Lie and Riemannian exponentials differ, and the Lie exponential is not surjective in the relevant real cases.Dynamic trivializations can nevertheless use parametrizations that static trivializations could not use.
  • Stiefel manifold: The Stiefel-manifold exponential requires a thin-QR factorization of an n × k matrix and a 2k × 2k skew-symmetric matrix exponential.These operations dominate the computational cost of computing its geodesics.
  • Retractions: Dynamic trivializations can use any retraction, provided the gradient of the objective precomposed with that retraction can be computed.For Sym+(n), matrix exponentiation gives a diffeomorphic but potentially expensive retraction-based parametrization.

F Detailed Experiment Set-Up and Hyperparameters

The experiments specify the recurrent architecture, initialization schemes, reproducibility settings, and hyperparameter tables used to evaluate dynamic trivializations. The copying experiment is omitted because both exponential and dynamic trivializations converge to the exact solution.

  • Experimental protocol: All experiments use batch size 128 and seed 5544 for both NumPy and PyTorch to support reproducibility.
  • Model architecture: The sequence model processes inputs x_t ∈ R^d with hidden size p using parameters A ∈ Skew(p) and T ∈ R^(p×d), with modReLU nonlinearity.
  • Initialization: Henaff initialization samples diagonal-block elements of skew-symmetric matrices from U(−π, π).
  • Initialization: Cayley initialization samples u from U(0, π/2) and uses the associated diagonal transformation described in the setup.
  • Experiment scope: The copying experiment is omitted because exponential and dynamic trivializations converge to the exact solution even when based at the identity.
  • Hyperparameters: Tables 3–5 report hyperparameters for DTRIV1, DTRIV100, and DTRIV∞, respectively.
Loading 1909.09501v2…