PaperlayerView exact revision on arXiv

Source-linked AI summary

Riemannian Adaptive Optimization Methods

Gary Bécigneul, Octavian-Eugen Ganea

arXiv:1810.00760v2cs.LGstat.ML

TL;DR

The paper addresses the difficulty of generalizing adaptive optimization schemes intrinsically to general Riemannian manifolds. It proposes adaptive algorithms with convergence analysis for Cartesian products of Riemannian manifolds, and reports that they outperform non-adaptive methods on hyperbolic word-taxonomy embedding.

  • Problem

    Adaptive methods such as ADAM, AMSGRAD, and ADAGRAD remained to be generalized to Riemannian manifolds, while intrinsic coordinate-free formulations are unclear in the general setting.

  • Method

    The paper generalizes adaptive optimization tools to Cartesian products of Riemannian manifolds, implementing adaptivity across manifold components and analyzing convergence for geodesically convex objectives.

  • Results

    Riemannian adaptive methods outperform non-adaptive methods such as RSGD on hyperbolic word-taxonomy embedding, with RADAM achieving the lowest training loss in the reported experiments.

  • Takeaways & Limitations

    The proposed product-manifold generalization provides Riemannian adaptive algorithms whose convergence rates are similar to corresponding Euclidean models and supports competitive hyperbolic embedding optimization.

  • Takeaways & Limitations

    In a general Riemannian manifold, path-dependent parallel transport and curvature can break gradient sparsity and undermine the coordinate-based interpretation of adaptivity.

Abstract

from arXiv · show

Several first order stochastic optimization methods commonly used in the Euclidean domain such as stochastic gradient descent (SGD), accelerated gradient descent or variance reduced methods have already been adapted to certain Riemannian settings. However, some of the most popular of these optimization tools - namely Adam , Adagrad and the more recent Amsgrad - remain to be generalized to Riemannian manifolds. We discuss the difficulty of generalizing such adaptive schemes to the most agnostic Riemannian setting, and then provide algorithms and convergence proofs for geodesically convex objectives in the particular case of a product of Riemannian manifolds, in which adaptivity is implemented across manifolds in the cartesian product. Our generalization is tight in the sense that choosing the Euclidean space as Riemannian manifold yields the same algorithms and regret bounds as those that were already known for the standard algorithms. Experimentally, we show faster convergence and to a lower train loss value for Riemannian adaptive methods over their corresponding baselines on the realistic task of embedding the WordNet taxonomy in the Poincare ball.

1 INTRODUCTION

The paper addresses the absence of intrinsic Riemannian counterparts for successful adaptive optimizers such as ADAGRAD, ADAM, and AMSGRAD. It explains the general obstacle, proposes product-manifold generalizations, and evaluates them on hyperbolic taxonomy embedding.

  • First-order stochastic optimization is important for high-dimensional applications including deep neural networks and large-vocabulary embeddings.
  • Adaptive methods such as ADAGRAD, ADAM, and AMSGRAD were developed for parameters in Euclidean space R^n.
  • Riemannian stochastic methods exist, but adaptive methods and their convergence analyses had not yet found corresponding Riemannian counterparts.
  • Generalizing coordinate-wise adaptivity intrinsically is difficult because Riemannian manifolds generally lack canonical coordinates.
  • The paper proposes adaptive algorithms and convergence analyses for products of Riemannian manifolds, treating each manifold component as an adaptive “coordinate.”It also empirically studies hyperbolic taxonomy embedding.
  • The motivating application is symbolic embedding in non-Euclidean spaces, where adaptive optimization may help address differing sampling frequencies.

2 PRELIMINARIES AND NOTATIONS

The preliminaries introduce Riemannian geometry and explain how stochastic optimization updates move on manifolds. They then review ADAGRAD, ADAM, and AMSGRAD as Euclidean adaptive methods.

  • Differential geometry: A manifold is locally approximated by Euclidean space, while tangent spaces provide local vector spaces and Riemannian metrics define local geometry.
  • Differential geometry: A Riemannian metric induces distances and geodesics, with geodesics locally minimizing path length.
  • Differential geometry: Exponential maps move tangent vectors onto the manifold along shortest-path directions, while logarithmic maps can provide inverses when defined.
  • Differential geometry: Parallel transport moves tangent vectors along geodesics, and in curved manifolds the result depends on the chosen path.
  • Riemannian optimization: Riemannian SGD replaces Euclidean addition with an exponential-map update using the Riemannian gradient and a positive step-size.
  • Riemannian optimization: Retraction maps provide first-order approximations to exponential maps when the latter are unavailable in closed form.
  • Adaptive methods: ADAGRAD rescales updates coordinate-wise using accumulated squared gradients, whereas ADAM uses momentum and an exponentially averaged adaptivity term.ADAGRAD’s accumulation can slow learning; ADAM’s exponential averaging forgets past gradients over time.
  • Adaptive methods: AMSGRAD modifies ADAM after a convergence-proof error was identified, while ADAMNC instead uses an increasing, time-dependent β2 schedule.

3 ADAPTIVE SCHEMES IN RIEMANNIAN MANIFOLDS

Coordinate-wise adaptive updates are generally not intrinsic on Riemannian manifolds because coordinate systems are noncanonical and path-dependent transport can disrupt their meaning. The paper restores adaptivity across components of product manifolds.

  • 3.1 THE DIFFICULTY OF DESIGNING ADAPTIVE SCHEMES IN THE GENERAL SETTING: A chart-dependent quantity is intrinsic only if its definition does not depend on the chosen local coordinate system.
  • 3.1 THE DIFFICULTY OF DESIGNING ADAPTIVE SCHEMES IN THE GENERAL SETTING: RSGD is intrinsic because it uses the exponential map and Riemannian gradient, whereas adaptive coordinate-wise operations are not clearly coordinate-free.
  • 3.1 THE DIFFICULTY OF DESIGNING ADAPTIVE SCHEMES IN THE GENERAL SETTING: Parallel-transporting a fixed tangent-space coordinate system makes transport path-dependent and can introduce curvature-induced rotation.
  • 3.1 THE DIFFICULTY OF DESIGNING ADAPTIVE SCHEMES IN THE GENERAL SETTING: Curvature-induced rotation can break gradient sparsity and make coordinate-wise adaptivity depend on the optimization path.
  • 3.2 ADAPTIVITY IS POSSIBLE ACROSS MANIFOLDS IN A PRODUCT: The proposed setting assumes a Cartesian product of Riemannian manifolds with an induced product metric.
  • 3.2 ADAPTIVITY IS POSSIBLE ACROSS MANIFOLDS IN A PRODUCT: In a product manifold, distances, tangent spaces, gradients, exponential maps, logarithmic maps, and parallel transport decompose across component manifolds.
  • 3.2 ADAPTIVITY IS POSSIBLE ACROSS MANIFOLDS IN A PRODUCT: The proposed Riemannian ADAGRAD treats each manifold component x_i ∈ M_i as one adaptive “coordinate.”
  • 3.2 ADAPTIVITY IS POSSIBLE ACROSS MANIFOLDS IN A PRODUCT: Adaptivity uses squared Riemannian norms of component gradients to rescale updates, matching the component update size in the Euclidean setting.

4 RAMSGRAD, RADAMNC: CONVERGENCE GUARANTEES

The paper formulates Riemannian adaptive methods on product manifolds, derives regret and convergence guarantees under geodesic-convexity assumptions, and recovers standard AMSGRAD in Euclidean space.

  • ADAM combines ADAGRAD-style accumulation with momentum, while AMSGRAD modifies ADAM to support its convergence proof.
  • The analysis assumes geodesically complete component manifolds, nonpositive lower curvature bounds, compact feasible factors, bounded diameter, and bounded component gradients.
  • Riemannian AMSGRAD applies adaptive updates across manifold factors, using component projections, exponential maps, logarithmic maps, and parallel transport.
  • When every component manifold is Euclidean, RAMSGRAD and AMSGRAD coincide, including their convergence guarantees.
  • The regret analysis replaces Euclidean convexity with geodesic convexity and introduces curvature-dependent factors through a Riemannian analogue of the cosine-law bound.
  • Adaptivity yields substantially improved bounds for sparse per-manifold gradients, such as when only a few word or graph-node embeddings are updated.

5 EXPERIMENTS

The experiments evaluate adaptive Riemannian methods on WordNet embeddings in the 5-dimensional Poincaré ball, comparing exponential-map and retraction updates using loss and MAP. RADAM performs best in the full Riemannian setting, while retraction methods are reported separately because they are not directly comparable.

  • Dataset & Model: WordNet’s 82,115 nouns and 743,241 hypernymy relations are embedded in a 5-dimensional Poincaré model, minimizing distances for edges and maximizing them otherwise.The evaluation uses reconstruction and link prediction settings, with a 2% validation edge sample for link prediction.
  • Optimization methods: Retraction updates unexpectedly reached lower loss values than exponential-map updates, possibly because they require fewer steps and smaller gradients to escape suboptimal boundary-collapse points.The paper treats this explanation as a possible account rather than an established mechanism.
  • Results: The experiments report training loss and MAP on train and validation sets for both exponential-map and retraction updates.Figures 2 and 3 use the same three left-to-right metrics for the two update schemes.
  • Results: RADAM consistently achieves the lowest training loss and outperforms other methods on MAP in the full Riemannian setting.This applies to both reconstruction and link prediction evaluations.
  • Results: In the retraction setting, RADAM reaches the lowest training loss and matches RSGD on MAP, while RAMSGRAD converges faster in MAP for link prediction.Retraction-based methods are presented separately because they are not directly comparable to fully Riemannian analogues.

6 RELATED WORK

Related work has extended several stochastic optimization methods to Riemannian manifolds, but adaptive methods remain limited by coordinate dependence and missing convergence guarantees. The paper positions its approach as addressing adaptivity across manifold factors intrinsically.

  • Existing Riemannian methods: Riemannian stochastic, variance-reduced, accelerated, averaged, and Langevin-style first-order methods have been developed, including analyses for geodesically convex objectives.Examples include RSGD, Riemannian SVRG, Riemannian accelerated gradient descent, and averaged RSGD.
  • Adaptive methods: Prior Riemannian momentum and RMSprop work transports momentum by parallel translation but provides no convergence guarantee.Its adaptive squaring and division remain coordinate-wise in tangent spaces.
  • Adaptive methods: A prior Grassmann-manifold ADAM variant removes the adaptive component because its adaptivity term becomes scalar and does not discuss adaptivity across manifolds.It also provides no convergence analysis.

7 CONCLUSION

The paper generalizes ADAM, AMSGRAD, and ADAGRAD intrinsically to Cartesian products of Riemannian manifolds, derives Euclidean-like convergence rates, and reports empirical gains over RSGD on hyperbolic taxonomy embeddings.

  • 7 CONCLUSION: The proposed methods extend popular adaptive optimization tools to Cartesian products of Riemannian manifolds in a principled and intrinsic manner.The methods are motivated by learning non-Euclidean embeddings for symbolic data.
  • 7 CONCLUSION: The derived convergence rates are similar to those of the corresponding Euclidean models.
  • 7 CONCLUSION: The methods outperform popular non-adaptive methods such as RSGD on hyperbolic word taxonomy embedding.

A PROOF OF THEOREM 1

The proof derives a regret bound by transforming and bounding terms involving transported iterates, momentum, and adaptive variables. It combines intermediate inequalities, a lemma, and telescopic summation to obtain the theorem’s bound.

  • A PROOF OF THEOREM 1: The proof uses a geodesic-triangle construction and projection-related substitutions to transform terms in the regret analysis.
  • A PROOF OF THEOREM 1: The proof assumes each Xi is geodesically convex so that the logarithms used in the argument are well-defined.
  • A PROOF OF THEOREM 1: Intermediate terms are bounded using Cauchy–Schwarz, Young’s inequality, and stated lemmas.The proof explicitly applies these inequalities to the last term and then bounds every term of the main expression.
  • A PROOF OF THEOREM 1: The regret bound follows by combining earlier equations and Lemma 3, while monotonicity of ζ(κ, d) supports the final bound.
  • A PROOF OF THEOREM 1: RAMSGRAD’s regret is also bounded by O(G∞T), so its effective upper bound is the minimum of two stated bounds.The proof remarks that this follows from the proof of Lemma 4.

B PROOF OF THEOREM 2

The proof follows the structure of Theorem 1, reusing earlier bounds while introducing a new lemma for the remaining terms before combining them into the final result. It also identifies an n/α correction absent from earlier corollaries.

  • The proof reuses the techniques and bound for the first term from Theorem 1.
  • A new lemma is required to control the other terms in the proof.
  • Applying the resulting inequality across all time steps and combining it with Eq. (53) yields the final result.
  • The final bound contains an n/α term missing from Reddi et al.'s corollaries, but this term does not depend on T.

C AMSGRAD

This section states AMSGRAD's Euclidean convergence theorem under bounded domains and gradients, with its proof delegated to prior work.

  • Theorem 5 gives a regret bound for AMSGRAD applied to differentiable convex functions on R^n.
  • The theorem assumes bounded coordinate-domain diameters and uniformly bounded infinity-norm gradients.
  • The proof is cited directly from Theorem 4 of Reddi et al. (2018).

D USEFUL LEMMAS

The section collects geometric and algebraic lemmas used in convergence proofs, including a cosine inequality, an analogue of Cauchy–Schwarz, and a bound on nonnegative sequences.

  • Lemma 6 provides a cosine inequality for geodesic triangles in Alexandrov spaces with curvature lower bounded by κ.
  • Lemma 7 states an analogue of Cauchy–Schwarz for vectors and nonnegative weights.
  • The proof of Lemma 7 applies Cauchy–Schwarz twice.
  • The analogue of Lemma 7 is needed in the convergence proof, following its use in Reddi et al. (2018) for ADAMNC.
  • Lemma 8 gives a bound for any sequence of non-negative real numbers.
Loading 1810.00760v2…