PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalization Error Bound for Hyperbolic Ordinal Embedding

Atsushi Suzuki, Atsushi Nitanda, Jing Wang, Linchuan Xu, Marc Cavazza, Kenji Yamanishi

arXiv:2105.10475v1cs.LG

TL;DR

HOE’s generalization in noisy settings lacked theoretical guarantees, despite its use of hyperbolic space for hierarchical representations. The paper derives a bound through a decomposed Lorentz-Gramian characterization; the bound is at most exponential in radius and has entity-count and ordinal-data-size dependencies matching EOE up to constants.

  • Problem

    HOE’s generalization performance in noisy settings had not been theoretically guaranteed, despite hyperbolic space’s exponential representation ability.

    Source: §1 · p. 1

  • Method

    The paper characterizes HOE using decomposed Lorentz Gramian matrices to derive its generalization bound.

    Source: §4 · p. 7

  • Results

    HOE’s generalization-error bound is at most exponential in radius, with entity-count and ordinal-data-size dependencies matching EOE up to constant factors.

    Source: §1 · p. 2, §5 · p. 9

  • Takeaways & Limitations

    The authors characterize the exponential radius dependence as a reasonable cost for HOE’s exponential representation ability.

    Source: §5 · p. 9

    The bounds do not directly depend on embedding dimension D, leaving that dimension dependence less well characterized.

    Source: §3.5 · p. 7

Abstract

from arXiv · show

Hyperbolic ordinal embedding (HOE) represents entities as points in hyperbolic space so that they agree as well as possible with given constraints in the form of entity i is more similar to entity j than to entity k. It has been experimentally shown that HOE can obtain representations of hierarchical data such as a knowledge base and a citation network effectively, owing to hyperbolic space's exponential growth property. However, its theoretical analysis has been limited to ideal noiseless settings, and its generalization error in compensation for hyperbolic space's exponential representation ability has not been guaranteed. The difficulty is that existing generalization error bound derivations for ordinal embedding based on the Gramian matrix do not work in HOE, since hyperbolic space is not inner-product space. In this paper, through our novel characterization of HOE with decomposed Lorentz Gramian matrices, we provide a generalization error bound of HOE for the first time, which is at most exponential with respect to the embedding space's radius. Our comparison between the bounds of HOE and Euclidean ordinal embedding shows that HOE's generalization error is reasonable as a cost for its exponential representation ability.

1. Introduction

Hyperbolic ordinal embedding can represent hierarchical data using hyperbolic space’s exponential growth, but its generalization in noisy settings lacked theoretical guarantees. The paper derives a bound using a new Lorentz-Gramian characterization and compares its radius dependence with Euclidean ordinal embedding.

1. Introduction

  • Hyperbolic space’s exponential growth supports hierarchical data, but HOE’s generalization performance in noisy settings lacked theoretical guarantees.The introduction contrasts hyperbolic space’s exponential growth with Euclidean space’s polynomial growth for representing hierarchical structures.Source: §1 · pp. 1–2

1.1. Our Contributions

  • HOE’s generalization-error bound grows at most exponentially with radius, while its entity-count and ordinal-data-size dependencies match EOE up to constant factors.Compared with EOE, the bound replaces a linear radius term with an exponential one, which the authors describe as a reasonable cost for hyperbolic representation ability.Source: §1 · p. 2, §1.1 · p. 2

1. Introduction

  • A decomposed Lorentz-Gramian characterization reformulates HOE as linear prediction, enabling a Rademacher-complexity calculation and a generalization bound.The standard Gramian approach does not work because hyperbolic space is not an inner-product space and that Gramian does not reflect its metric structure.Source: §1 · p. 2

1.2. Related Work

  • Prior analyses discussed hyperbolic tree-embedding properties under noiseless conditions, while noisy-setting generalization for hyperbolic machine-learning models had not been analyzed.The introduction also situates HOE among work applying hyperbolic embeddings across machine-learning areas.Source: §1.2 · p. 2
  • Prior work calculated Rademacher complexity for EOE, while this paper evaluates HOE’s Rademacher complexity for the first time.The paper combines that calculation with standard statistical learning theory to derive the HOE bound.Source: §1 · p. 2, §1.2 · p. 3

2. Preliminaries

The preliminaries define ordinal embedding through triplet comparisons and introduce hyperbolic space in the hyperboloid model. They then specify HOE and EOE and frame the analysis through risk functions.

2.1. Ordinal Embedding

  • Ordinal embedding seeks metric-space representations consistent with true dissimilarities, using labeled triplets to indicate which pair is closer; noisy comparisons are also considered.The formulation concerns consistency on new triplets that may be unseen in training.Source: §2.1 · p. 3

2.2. Hyperbolic Space

  • The paper works mainly with the hyperboloid model, a submanifold of Minkowski space, and uses hyperbolic space’s exponential growth property.The text notes that tree-generated ordinal constraints can all be satisfied when the data are noiseless.Source: §2.2 · pp. 3–4

2.3. HOE and EOE

  • HOE seeks ordinal consistency in hyperbolic space, whereas EOE seeks it in Euclidean space, each using its corresponding distance function.The hyperboloid model’s distance is the HOE distance used in this formulation.Source: §2.3 · p. 4, §2.2 · p. 4
  • The analysis uses empirical and expected risks with increasing loss and transformation functions, choosing cosh for HOE and squared distance for EOE.The text identifies excess risk as the generalization error of ordinal embedding.Source: §2.3 · p. 4

3. Finite Sample Generalization Bound for HOE

The section derives a finite-sample generalization bound for HOE under data-generation and embedding-radius restrictions. It compares the bound with EOE and identifies the lack of direct dimension dependence as a limitation.

3.1. Assumptions on Data Generation

  • Training triplets are assumed independently and identically distributed, uniformly over triplets, with labels conditioned on true dissimilarity differences through a fixed link function.The triplet-generation assumption is stated as uniform, and the label probability is given by the link function applied to the true dissimilarity difference.Source: §3.1 · p. 4

3.2. Restriction on Representation Domain

  • The analysis restricts representations to a bounded embedding domain based on radius, using B_R as a simple practical choice and noting that a smaller ρ restriction can lower the bound.The passages motivate bounded representations as necessary for a finite generalization bound.Source: §3.2 · pp. 4–5

3.3. Main Result: Generalization Error

  • The HOE bound has the same dependencies on entity count and ordinal-data size as EOE, with S = O(N ln N) indicated by the stated dependency.The analysis obtains the bound through an upper bound on HOE’s Rademacher complexity.Source: §3.3 · p. 5

3.4. Comparison between EOE and HOE

  • HOE’s bound replaces EOE’s R^2 dependence with (exp R)^2 up to a constant factor, reflecting the exponential growth of hyperbolic-space volume.The paper describes this larger bound as the cost of HOE’s exponential representation capacity.Source: §3.4 · p. 6
  • For weighted-tree graph distances, HOE can achieve lower expected loss than EOE when the radius is sufficiently large; for some trees, enough ordinal data lets its empirical minimizer outperform every EOE representation.The tree result assumes distinct distances between distinct unordered vertex pairs; the cited example includes trees with a node of degree at least 6.Source: §3.4 · pp. 6–7

3.5. Limitation

  • The bounds do not directly depend on embedding dimension D, and deriving a tighter dimension-dependent bound for general ordinal embedding is left as future work.The paper notes this absence does not match the intuition that lower-dimensional spaces should yield lower generalization error.Source: §3.5 · p. 7

4. Proof Techniques

The proof adapts Euclidean ordinal-embedding analysis by reformulating HOE with Lorentz Gramian matrices and characterizing radius constraints through their decompositions. This enables a Rademacher-complexity bound for HOE.

4.1. Difficulty in HOE and Our Solution

  • The Euclidean Gramian approach does not directly apply because hyperbolic space is not an inner-product space and its Gramian does not reflect the metric structure.The paper addresses this using a Lorentz Gramian reformulation and a characterization of radius restrictions.Source: §4.1 · p. 7

4.2. Reformulation of HOE Hypothesis Function by Lorentz Gramian Matrix

  • The Lorentz Gramian reformulation expresses HOE’s hypothesis function as a linear function of that matrix.The risk is then reformulated as a function of the Lorentz Gramian.Source: §4.2 · pp. 7–8

4.3. Decomposition of the Lorentz Gramian Matrix

  • Decomposed Lorentz Gramian matrices characterize embedding-radius restrictions through conditions including their max and nuclear norms.This characterization enables techniques similar to those used for Euclidean ordinal embedding.Source: §4.3 · p. 8

4.4. Proof Sketch of Theorem 1

  • The proof sketch decomposes HOE’s Rademacher complexity into two terms using norm constraints on L+ and L−.The two terms are evaluated with techniques similar to those in Jain et al. (2016).Source: §4.4 · p. 8

5. Conclusion

The paper derives HOE’s first generalization error bound in noisy settings and finds that its radius dependence is at most exponential. The bound’s dependence on the number of entities and ordinal data size matches EOE’s up to constant factors.

5. Conclusion

  • HOE’s generalization error is at most exponential in embedding radius, while its dependence on entity count and ordinal-data size matches EOE’s up to constant factors.The authors characterize this as a cost for HOE’s exponential representation ability.Source: §5 · p. 9
  • For tree-structured data, the authors report that HOE’s generalization-performance cost is worth paying, while recommending EOE when it represents the true dissimilarity well.The conclusion connects this guidance to the paper’s tree example and noisy-setting analysis.Source: §5 · p. 9
  • The analysis assumes a simple uniform distribution on ordinal data and is presented as guidance for embedding-space selection in real applications.Source: §5 · p. 9

A. Proof of Lemma 4

The proof relates properties of the Euclidean Gramian matrix to the embedding representations’ distances from the origin.

A. Proof of Lemma 4

B. Proof of Lemma 7

The proof of Lemma 7 uses weighted-tree conditions and a distortion algorithm to obtain representations while preserving ordinal distance comparisons.

B. Proof of Lemma 7

  • The proof considers distinct ordered pairs of vertices when comparing weighted-tree distances.Source: B. Proof of Lemma 7 · p. 11
  • It assumes positive μ and ξ and defines constants using the weighted graph.Source: B. Proof of Lemma 7 · p. 11
  • A (1+ε)-distortion algorithm supplies representations, and the proof uses the condition that a larger true distance remains larger in the comparison.Source: B. Proof of Lemma 7 · p. 11

C. Proof of Lemma 11

The proof constructs Lorentz Gramian representations from a positive and a negative component, then verifies their validity and radius constraints. It also addresses a sign issue in the construction by forcing each time coordinate to be positive.

C. Proof of Lemma 11

  • The proof checks the decomposition conditions using positive semidefiniteness, rank properties, and inequalities derived from Cauchy–Schwarz.These checks establish the stated conditions for representations in the hyperbolic space.Source: C. Proof of Lemma 11 · p. 12
  • The Lorentz Gramian is represented as L = L+ − L−, with L+ positive semidefinite of rank at most D and L− positive semidefinite of rank 1.The construction uses the decomposition to obtain points in the hyperbolic space.Source: C. Proof of Lemma 11 · pp. 12–13
  • The proof verifies that the constructed points lie within radius R by showing cosh2 ∆LD(z0, zn) ≤ cosh2 R.The stated inequality is equivalent to ∆LD(z0, zn) ≤ R.Source: C. Proof of Lemma 11 · p. 13
  • The construction forces z0,n to be positive, resolving the case where the decomposition would otherwise yield representations in −LD rather than LD.The remark contrasts this construction with the proof of Proposition 1 in (Tabaghi & Dokmanic, 2020).Source: C. Proof of Lemma 11 · p. 13

D. Rademacher Complexity and Proof of Theorem 1

The paper uses Rademacher complexity to bound the HOE hypothesis class and applies a risk-bound corollary to prove Theorem 1. The resulting argument also yields an excess-risk bound for the empirical risk minimizer.

D. Rademacher Complexity and Proof of Theorem 1

  • The Rademacher complexity is defined using independent, equally likely ±1 signs and sampled data points from an unknown fixed distribution.The definition specifies mutual independence between signs and data.Source: D. Rademacher Complexity and Proof of… · p. 14
  • The Rademacher complexity of the HOE hypothesis class h(·; Bρ) is bounded in Lemma 11.The paper identifies Rademacher complexity as the key tool for obtaining HOE’s generalization error bound.Source: D. Rademacher Complexity and Proof of… · p. 14
  • The proof of Theorem 1 applies Corollary 10 to Lemma 11.Corollary 10 bounds excess risk using empirical and expected risks, with the proof evaluating terms via a risk bound and Hoeffding’s inequality.Source: D. Rademacher Complexity and Proof of… · pp. 14, 16
Loading 2105.10475v1…