PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Abundance of Critical Points of the t-SNE Energy

Nakul Haridas, Ryan Murray

arXiv:2609.04379v1cs.LGmath.APmath.STstat.TH

TL;DR

Because t-SNE’s non-convex energy lacks solution formulas, its landscape is difficult to analyze rigorously. The paper uses symmetry-preserving gradient dynamics to construct critical points, proving infinitely many strongly distinct ones for radial inputs in Euclidean space. The numerical examples leave unresolved whether the symmetry solutions are stable critical points or saddles.

  • Problem

    t-SNE’s non-convex energy has no solution formulas, making rigorous analysis difficult while embeddings are found by gradient descent.

    Source: §1 · p. 1

  • Method

    The paper studies symmetry-invariant couplings and a well-posed gradient flow that preserves symmetry, using compactness to obtain invariant critical points.

    Source: §2.3 · p. 7

  • Results

    For radial input data in Euclidean space, the paper proves infinitely many critical points that remain distinct even after isometries of the input or output spaces.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The construction uses broader discrete symmetries to quantify critical-point richness beyond prior symmetry-based analysis of embedding instability.

    Source: §1.1 · p. 3

    The numerical examples do not resolve whether the symmetry solutions are stable critical points or saddles.

    Source: §4.3 · p. 19

Abstract

from arXiv · show

This paper considers the energy landscape of the t-SNE algorithm. While this algorithm has enjoyed broad adoption, the non-convexity of the associated energy has made it difficult to rigorously understand what the algorithm captures in many settings. In particular, a number of well-known numerical examples, several of which are reproduced in this article, suggest a complicated energy landscape with many local minimizers that do not respect the topology or clustering structure of the underlying data. This work seeks to provide first steps towards a rigorous explanation of these phenomena. Specifically, for a general family of energies, which include both the original t-SNE algorithm and recently identified large data limits, and for densities in feature space which obey a continuous symmetry, we construct infinite families of distinct critical points. These critical points are based upon identifying pairs of discrete symmetries, one in the original feature space and the other in the target embedding space, which are preserved under gradient dynamics. These critical configurations exhibit many characteristics, such as topology breaking and spurious clustering, which are often observed empirically. Finally, numerical and analytical examples are given throughout as a means of illustrating the approach.

1 Introduction

The introduction frames t-SNE as widely used but difficult to analyze because its non-convex energy lacks solution formulas. It presents symmetry-preserving dynamics as a route to proving abundant critical points, including infinitely many strongly distinct Euclidean critical points for radial inputs.

1 Introduction

  • t-SNE is widely adopted, but its non-convex energy has no solution formulas, so embeddings must be found by gradient descent.The introduction places this challenge within the broader use of optimization-based dimension-reduction methods.Source: §1 · p. 1
  • The paper develops a general t-SNE energy formulation and symmetry-invariant couplings, then uses well-posed, symmetry-preserving gradient flow and compactness to obtain invariant critical points for each symmetry pair.The formulation includes variants from prior work; numerical examples illustrate the construction on various manifolds.Source: §1 · p. 2
  • For radial input data in Euclidean space, the paper proves infinitely many critical points, with distinctness excluding isometries in either space.It also proves that the constant embedding is not a local minimum and notes that, for a wide class of symmetry pairs, it is the only map satisfying multiple symmetries simultaneously.Source: §1 · p. 2

1.1 Related Literature

  • Prior work studies early-exaggeration guarantees and continuum limits, with the latter yielding well-posed equilibria over plans in one regime and asymptotic ill-posedness over maps in another.The cited map regime assumes perplexity growing faster than log n but slower than n.Source: §1.1 · p. 2
  • Empirical studies report t-SNE cluster-visualization failures beyond specific separation conditions, including cases where a lower objective value accompanies a worse visualization.Other cited work discusses pathological behavior and sensitivity to initialization.Source: §1.1 · pp. 2–3
  • For large samples from a hypersphere, prior work finds that a global minimizer concentrates most mass in a small embedded ball when the inputs are approximately equidistant.The cited analysis attributes the uniform input distribution to permutation symmetry of equidistant points.Source: §1.1 · p. 3
  • Unlike prior scale-and-translation symmetry work that argues for embedding instability, this paper uses broader discrete symmetries to quantify the richness of the critical-point family.The prior work transforms critical embeddings toward an n-simplex configuration that remains critical in an appropriate sense.Source: §1.1 · p. 3

2 Energetic models

The section reviews t-SNE’s affinity-based attraction–repulsion objective, then places it in a continuum and generalized framework. The generalized model encompasses discrete and large-data energies, while its analysis uses variations of couplings in the embedding space under stated regularity assumptions.

2.1 Review of original t-SNE Formulation

  • t-SNE minimizes a KL divergence between input and embedding similarities, using locally adaptive affinities shaped by perplexity and heavy-tailed embedding similarities.The input affinities act like smoothed nearest-neighbor weights, while the energy can be expressed as attraction plus repulsion.Source: §2.1 · pp. 3–4

2.2 Continuum Model

  • Continuum models replace discrete sums and implicit bandwidths with integrals and explicit bandwidth functions, but this derivation does not establish limits of the original energy.The cited approaches use different perplexity regimes and embedding formulations; proving minimizer limits for realistic perplexities remains an open problem outside this work’s scope.Source: §2.2 · p. 5

2.3 Generalized Model

  • The generalized energy includes the original discrete objective and continuum variants, extends to manifold spaces, and can optimize over couplings rather than only maps.The formulation recovers the cited continuum energies under specified choices of coupling and bandwidth.Source: §2.3 · pp. 5–7

2.4 Assumptions

  • The framework assumes regularity and boundedness conditions on the distance-like functions, plus a continuous bandwidth bounded away from zero.In the Euclidean case with squared-norm metrics, assumptions (I) and (II) are naturally satisfied.Source: §2.3 · p. 6, §2.4 · p. 8

2.3 Generalized Model

  • Its first variation changes the coupling in the embedding variable; the resulting gradient flow follows the negative energy field and requires a well-posedness argument.The authors state that standard results do not immediately apply, and defer the proof to Proposition 7.Source: §2.3 · pp. 7–8

3 Energy Landscape for t-SNE

Numerical examples illustrate that t-SNE’s non-convex energy landscape can yield embeddings that break topology or split data into spurious groups. Outcomes vary with initialization, including on a line, a grid, and a Swiss Roll.

3.1 Numerical illustrations of complexity of energy landscape

  • For the 3-D line, embeddings vary across initializations and break the connected input into components; random initialization has slightly lower energy than PCA, which better preserves topology.The linear 2-D projection has much worse energy than the optimized runs.Source: §3.1 · p. 9, Figure 1 · p. 9, Table 1 · p. 9
  • On the square grid, two of nine random-initialization samples twist the grid into separated pieces, while every sample shows smaller-scale splitting.The example uses a 20 × 20 grid.Source: §3.1 · p. 10, Figure 2 · p. 10
  • On the Swiss Roll, t-SNE fails to unroll the manifold, instead producing disconnected clusters with additional local twisting.The reported example uses 2,000 points and perplexity 13.Source: §3.1 · p. 11, Figure 3 · p. 11
  • The examples exhibit complex local-minimizer behavior, including topology breaking, splitting, and twisting that may not reflect structure in the input data.The authors present these cases as motivation for rigorously explaining the energy landscapes behind such outcomes.Source: §3.1 · pp. 9–12

4 Symmetry invariant embeddings

The section develops symmetry-invariant embeddings as a framework for understanding how t-SNE can have many distinct critical points, defining paired finite isometries and showing that gradient descent preserves symmetry-invariant initial couplings under stated assumptions. Numerical examples illustrate that this preservation depends on the optimizer and can coexist with topology-distorting embeddings.

4.1 Finite isometry groups: definitions, examples and invariant mappings

  • Finite isometry groups on the feature and embedding spaces define symmetry-invariant couplings and maps, which are determined by their values on a fundamental domain.The framework assumes equivalent groups and pairs their actions; the fundamental domain represents the orbits of the feature-space group.Source: §4.1 · pp. 12, 14
  • If 0 < i < j < k/2, the two symmetry pairs are mutually exclusive; in two dimensions, the corresponding pairs are mutually exclusive up to constants.Source: §4.1 · p. 15
  • Unlike maps, couplings can be invariant under multiple symmetry pairs: the uniform measure on T × T is invariant under any pair of isometries.This limits conclusions about mutual exclusivity for maps from extending directly to correspondences.Source: §4.1 · p. 16

4.2 Gradient descent for symmetry invariant embeddings

  • Under Theorem 4’s assumptions, including σ-invariance and a locally bounded I^-1, gradient descent preserves any initial coupling’s symmetry invariance throughout its existence interval.The theorem also assumes finite isometry groups, a symmetry-invariant initial coupling, and conditions (I), (II), and (III).Source: §4.2 · p. 17
  • Gradient descent preserves symmetry-invariant embeddings for all times, enabling construction of large families of distinct critical points.The paper then investigates this route numerically and gives rigorous proofs under appropriate assumptions in Sections 5 and 6.Source: §4.2 · p. 18

4.3 Numerical Illustrations

  • The symmetry error measures the normalized mean discrepancy between T(gX(x)) and gY(T(x)); it vanishes exactly for symmetry-invariant embeddings.The examples use invariant maps rather than general correspondences.Source: §4.3 · p. 18
  • Two circle examples produce distinct symmetric embeddings, with symmetry errors 3.088 × 10−15 and 1.483 × 10−11, respectively.The second embedding is explicitly reported as a different map from the first.Source: §4.3 · pp. 19–20
  • Vanilla gradient descent preserves symmetric initialization (SE = 3.088 × 10−15), while every tested openTSNE run breaks exact symmetry and reaches lower total energy.The openTSNE runs used different Barnes–Hut θ and early-exaggeration settings; their symmetry defects were many orders of magnitude larger.Source: §4.3 · pp. 18–19, Table 2 · p. 20
  • On a 20 × 20 square grid, vanilla gradient descent yields symmetry error of order 10−15, versus order 10−2 for openTSNE, reproducing grid twisting like Wattenberg et al. (2016).The grid example pairs reflection across the x-axis in the input with rotation by π in the embedding.Source: §4.3 · p. 20
  • In the hyperbolic-space example, symmetry is relatively well preserved early in optimization but breaks later, probably because of the implementation’s different optimization method.The example uses 10,000 points on S2 and displays the embedding in the Poincaré disk model.Source: §4.3 · p. 21

5 Existence of descent paths and their limits

The section establishes well-posed gradient descent and identifies conditions under which its trajectories yield symmetry-invariant critical points. Compactness and moment bounds determine when descent paths have weak limits, while some Euclidean conclusions remain conditional on conjectures.

Well-posedness

  • A direct ODE-style argument establishes a unique weak solution to the descent equation and extends it to all finite times.The authors note that existing fibred-probability-measure theory does not directly apply because of the scaling of I^-1.Source: §5 · pp. 23–24

Limits of descent paths

  • If Y is compact or the first moment in Y stays bounded, descent paths have a weakly convergent subsequence.In Euclidean settings, the required moment bound is conjectural beyond specific established contexts.Source: §5 · pp. 24–25
  • Without sharper bounds on the embedding moment, the rescaled weak limit cannot be concluded to be a critical point of the zero homogeneous energy.The moment bound needed for tightness in Euclidean embedding spaces remains conjectural in general.Source: §5 · p. 25

Symmetry-invariant critical points

  • For each symmetry pair admitting an invariant initial coupling, a symmetry-invariant critical point exists when Y is compact or, for Y = R^m, Conjecture 9 holds.The proof uses energy dissipation, weak compactness, and continuity of the energy integrand.Source: §5 · p. 25

6 Non-minimality of trivial maps in Euclidean settings

The section shows that trivial embeddings are not local minima under specified Euclidean symmetry conditions, then uses symmetry pairs to obtain infinitely many distinct critical points for radially symmetric data, conditionally on two conjectures.

Symmetry-preserving descent

  • Gradient descent paths preserve the specified symmetries and approach symmetry-invariant critical points.This links invariant initial configurations to the critical-point construction.Source: §6 · p. 25

Non-minimality of trivial maps

  • The constant map is not a local minimum among invariant mappings when the finite isometry groups have prime order, a single fixed point in Y, and µX is supported on full-size orbits.The proof constructs a symmetry-preserving perturbation with negative second variation.Source: §6 · pp. 26–27
  • The non-minimality argument can extend beyond Euclidean targets, but Gaussian-kernel positive definiteness generally fails on Riemannian settings.The proof route remains available under the stated fixed-point and support condition on µX.Source: §6 · p. 27

Distinct critical points

  • For radially symmetric µX, infinitely many distinct critical points exist when assumptions (I)–(IV) and Conjectures 9 and 15 hold, with d > 1 and m ≥ 2.The construction uses infinitely many mutually exclusive rotoreflection symmetry pairs; non-minimality of the constant map distinguishes their critical points.Source: §6 · p. 28

Related papers

Loading 2609.04379v1…