Theoretical Foundations of t-SNE for Visualizing High-Dimensional Clustered Data

T. Tony Cai; Rong Ma

Source-linked AI summary

Theoretical Foundations of t-SNE for Visualizing High-Dimensional Clustered Data

T. Tony Cai, Rong Ma

arXiv:2105.07536v4May 16, 2021stat.MLcs.LGmath.ST

TL;DR

t-SNE is widely used to reveal structure in high-dimensional data, but its underlying mechanisms, limiting behavior, and tuning-parameter sensitivity require theoretical explanation. This paper develops a gradient-descent framework showing power-iteration behavior during early exaggeration and amplification followed by stabilization during embedding.

Problem
The paper addresses limited theoretical understanding of t-SNE’s mechanisms, low-dimensional-map behavior, and sensitivity to tuning parameters.
Method
The paper analyzes t-SNE through a novel theoretical framework based on gradient descent, covering its early exaggeration and embedding stages.
Results
Early exaggeration is asymptotically equivalent to power iterations, while embedding exhibits amplification with intercluster repulsion and expansion followed by stabilization.
Takeaways & Limitations
The theory connects early exaggeration to implicit regularization and indicates early stopping for noisy or approximately clustered data to avoid overshooting.
Takeaways & Limitations
The early-exaggeration analysis relies on the Davis–Kahan matrix perturbation inequality, whose conditions may be relaxable using more advanced random-matrix results.

Abstract

from arXiv · show

This paper investigates the theoretical foundations of the t-distributed stochastic neighbor embedding (t-SNE) algorithm, a popular nonlinear dimension reduction and data visualization method. A novel theoretical framework for the analysis of t-SNE based on the gradient descent approach is presented. For the early exaggeration stage of t-SNE, we show its asymptotic equivalence to power iterations based on the underlying graph Laplacian, characterize its limiting behavior, and uncover its deep connection to Laplacian spectral clustering, and fundamental principles including early stopping as implicit regularization. The results explain the intrinsic mechanism and the empirical benefits of such a computational strategy. For the embedding stage of t-SNE, we characterize the kinematics of the low-dimensional map throughout the iterations, and identify an amplification phase, featuring the intercluster repulsion and the expansive behavior of the low-dimensional map, and a stabilization phase. The general theory explains the fast convergence rate and the exceptional empirical performance of t-SNE for visualizing clustered data, brings forth interpretations of the t-SNE visualizations, and provides theoretical guidance for applying t-SNE and selecting its tuning parameters in various applications.

1. Introduction

The paper develops a theoretical framework for t-SNE that explains its behavior on clustered data, including early exaggeration, embedding dynamics, and practical interpretation. Its analysis connects early exaggeration to spectral clustering and identifies mechanisms underlying cluster separation and stabilization.

1. Introduction: t-SNE maps high-dimensional data into a low-dimensional space using nonlinear dimension reduction to reveal intrinsic structures.The method is widely used for visualizing trends, patterns, and outliers in scientific applications.
1.2 Main Results and Our Contribution: During embedding, an amplification phase produces intercluster repulsion and expansion, followed by stabilization that locally refines the map.Repulsive forces from other clusters increase spaces between existing clusters, while the map’s diameter may increase across iterations.
1.2 Main Results and Our Contribution: Early exaggeration is asymptotically equivalent to power iterations based on the graph Laplacian and exhibits an implicit spectral-clustering mechanism.For approximately clustered data, the low-dimensional coordinates converge toward the Laplacian null space, producing embeddings aligned with cluster membership.
1.2 Main Results and Our Contribution: Early stopping acts as implicit regularization for weakly clustered or noisy data, because continuing too long can cause overshooting and false clustering.The paper gives K0 = ⌊(log n)2⌋ as an example early-stopping choice for weakly clustered data.
1.2 Main Results and Our Contribution: The theory provides guidance for initialization, tuning parameters, and interpretation, including repeated runs because random initialization can create misleading relative positions or false clusters.Cluster membership may be reliable while relative cluster positions are not, and spectral initialization can replace early exaggeration for strongly clustered data.
1. Introduction: The paper addresses limited theoretical understanding of t-SNE’s mechanisms, limiting behavior, parameter sensitivity, and visualization artifacts.The scope is clustered data, where interpretation and commonly observed phenomena remain insufficiently explained.

2. Analysis of the Early Exaggeration Stage

The early exaggeration stage is asymptotically equivalent to Laplacian-based power iterations, revealing implicit spectral clustering and iteration-dependent regularization. The analysis explains localization, cluster formation, and why weakly clustered data require early stopping to avoid overshooting.

Localization: The embedding remains globally localized and non-expansive during the analyzed iterations, with average row distance from the origin bounded by the initialization.The result can remain valid for more iterations when the step-wise deviation diminishes under the stated tuning conditions.
Asymptotic graphical interpretation: The early exaggeration updates become asymptotically equivalent to power iterations driven by the Laplacian of a fixed weighted graph.The graph adjacency is the scaled and shifted similarity matrix αP−H_n.
Asymptotic power iterations and spectral clustering: The resulting power method targets leading eigenvector directions, with the limiting subspace determined by the Laplacian null space.For strongly clustered data, this null space encodes connected components through cluster-wise constant coordinates.
Early stopping: For weakly clustered data, iterations must be sufficiently long to move toward an informative subspace but stopped early to avoid convergence to a superficial, non-informative Laplacian null space.The paper reports that failing to stop early can lead to false clustering, especially when the data are more weakly clustered.
Implicit regularization: Early iterations impose implicit regularization by retaining all eigenvector components while progressively suppressing components associated with larger Laplacian eigenvalues.Stopping early preserves a mixture that can better retain informative structure before less informative components decay exponentially.

3. Analysis of the Embedding Stage

The embedding stage first amplifies and refines clusters inherited from early exaggeration, then enters stabilization as expansion slows. Intercluster repulsion drives cluster separation and the expanding low-dimensional map during amplification.

Embedding-stage overview: The embedding stage transitions from concentrated early-exaggeration outputs to amplification and refinement of existing cluster structures.It then aims at a proper embedding of the original data.
Amplification phase: The low-dimensional map’s diameter increases through amplification, making clusters more distinct and separated.This expansion continues until the small-diameter condition no longer holds.
Amplification phase: Proposition 12 shows that during amplification, entries of S(k) depend on the magnitude of the corresponding similarities in P.For n^2pij tending to zero, S(k)ij = −1 + O(η(k)); when n^2pij remains bounded below, |S(k)ij| is of order pij.
Amplification phase: During amplification, repulsive forces from other clusters determine each point’s movement direction and distance.The movement depends on current cluster positions and the cluster structure inherited from early exaggeration.
Stabilization phase: After expansion reaches roughly constant diameter, the dynamics enter stabilization, where the diameter grows only very slowly.The theory identifies this phase after the fast expansive iterations of amplification.

4. Application I: Visualizing Model-Based Clustered Data

The theory is applied to Gaussian-mixture and noisy-nested-sphere models, yielding conditions and tuning choices under which the predicted visualization properties hold. The Gaussian-mixture analysis also covers both low- and high-dimensional regimes, while experiments illustrate robustness to some separation violations.

Applications: The paper applies its general t-SNE theory to Gaussian-mixture and noisy nested-sphere models.The examples are used to determine tuning parameters and assess the predicted visualization properties.
Gaussian Mixture Model: For Gaussian mixtures, the theory supplies efficient tuning choices such as K0 = floor((log n)^2), h = h′ = n^δ, and α = n^(1−δ).These choices apply when ρ^2 ≳ log n · max{p, log n}.
Gaussian Mixture Model: Under the Gaussian-mixture conditions, the theoretical conclusions hold in both p = o(n) and p ≳ n settings.The conditions include covariance regularity and a separation requirement stated in (C2).
Empirical demonstrations: In the Gaussian-mixture experiment, t-SNE visualizations confirmed the theoretical predictions for n = 1500 samples using theory-guided parameters.The experiment used p = 100, six clusters, and perplexity 30.
Noisy Nested Sphere Model: For the noisy nested-sphere model, suitable parameter choices yield the desired visualization properties with high probability under the stated radial-separation conditions.The sufficient conditions use both ratios and differences between neighboring sphere radii.

5. Application II: Visualizing Real-World Clustered Data

The MNIST application demonstrates the practical effects of theory-guided tuning, early stopping, and random initialization. The results show visible cluster patterns across parameter choices, while initialization can alter relative cluster positions and sometimes create false clusters.

Experimental setup: The MNIST experiment embeds 1600 handwritten-digit images from four classes as 784-dimensional vectors using theory-guided parameters.The selected parameters include δ = 2/3, perplexity 30, and K0 = floor((log n)^2).
Early stopping: Stopping early during early exaggeration helps avoid overshooting, whereas excessive iterations may produce false clustering.The compared values are K0 = 54, 137, and 253 under identical initializations and tuning parameters.
Random initialization: Random initialization changes the relative positions of clusters, so visual neighbors need not be neighbors in the original data.The paper reports this comparison across three runs with identical tuning parameters.
Random initialization: False clustering can arise from random initialization and intercluster repulsion, motivating multiple t-SNE runs.The paper presents this as a practical way to assess initialization effects.
Parameter robustness: Cluster patterns remained visible and similar for n = 2400 across δ ∈ {1/3, 1/2, 2/3}.These visualizations used identical random initialization and the tuning-parameter family in (39).

6. Discussion

The discussion presents the framework as a foundation for interpreting t-SNE and extending the analysis to related visualization methods. It also identifies unresolved questions about stabilization, local structure, iteration counts, adaptive bandwidths, and fundamental visualization limits.

Limitations and future work: The current early-exaggeration analysis relies on the Davis–Kahan matrix perturbation inequality, and stronger random-matrix tools may relax some conditions.The authors specifically mention results by Benaych-Georges and Nadakuditi and by Bao et al.
Open questions: The limiting behavior of the low-dimensional map after transition to stabilization remains unresolved.This is identified as an open question for future analysis.
Open questions: The paper leaves open how to interpret within-cluster local structure, determine embedding-stage iteration counts, and choose bandwidths adaptively.These questions concern the later embedding dynamics and data-driven parameter selection.
Extensions: The framework may generalize to related methods that begin with similarity matrices, including multidimensional scaling, kernel PCA, and Laplacian eigenmaps.The paper presents this as a possible direction for applying the theoretical framework beyond t-SNE.
Open questions: Fundamental limits remain open concerning when low-dimensional metric embeddings exist and whether t-SNE sacrifices global structure for local fidelity.These questions are left for future investigation.

A.2 Proof of Proposition 3

The proposition establishes that bounded iterates remain controlled under the stated conditions, with bounds propagated across iterations while k r_n remains O(1).

Under boundedness of η(k) and the coordinate sup norms, relation (42) also bounds η(k+1) and the next iterate’s coordinate sup norms.
Iterating relation (42) preserves boundedness for all k ≥ 1 when the initial coordinates are O(1) and η(0) satisfies the stated bound.
When k r_n = O(1), the resulting iterate norms remain controlled by the proposition’s propagated bounds.

A.3 Proof of Theorem 4

The proof derives Theorem 4 from earlier results by reducing its assumptions to the theorem’s conditions and controlling the perturbed Laplacian iteration under explicit step-size and iteration constraints.

Theorem 4’s conclusions follow from Theorem 2 and Proposition 3, while its remaining claim is established through an auxiliary proposition.
If ∥hL(αP)∥ < 2, then the perturbed Laplacian operator satisfies 1 ≤ ∥I − hL(αP − H_n)∥ ≤ 1 + h/(n−1).
For k h ζ = O(1), a universal constant controls the relevant iterates uniformly in n, while k h/n = O(1) bounds the associated growth factor.
The proof reduces bounds on α, h, k, and the initial coordinates to conditions (I1), (I2), and (T1.D).
The final contraction follows from 1 + h/(n−1) − hλ_{R+1} < 1 − κ/2 < 1 under the stated spectral condition.

A.5 Proof of Proposition 6

The proof identifies the Laplacian null space with the graph’s connected-component structure and shows that the limiting low-dimensional representation takes at most one value per component.

Because the graph has R connected components, the zero eigenvalue of L(P) has multiplicity R and its eigenspace is spanned by the component indicator vectors.
Under the stated conditions on h, k, and ζ, the proposition’s limiting representation is obtained from the null-space projection of the Laplacian.
The matrix U U^⊤ h has at most R distinct rows, with identical rows for vertices in the same graph component.
The algorithm is the Euler scheme for the associated differential equation, so standard differential-equation theory supplies its global approximation error.
The shifted and unshifted Laplacians share eigenvectors because their difference consists of identity and all-ones terms.

B.3 Proof of Theorem 10

The proof decomposes the dynamics into Laplacian eigenspaces, bounds perturbation effects through spectral separation, and controls convergence toward the population null-space representation.

The matrix U spans the smallest R eigenvalues of L(P), while U_0 spans the null space of L(P*); Davis–Kahan bounds their subspace deviation.
The population trajectory decomposes into components along U and U_⊥, with exponential factors determined by the corresponding Laplacian eigenvalues.
The approximation error is bounded by a perturbation term proportional to ∥L(E)∥/λ_{R+1}(L(P*)) plus a decaying spectral term.
A second bound combines eigenspace deviation, perturbation size, and the decay of the nonleading spectral component.
Weyl’s inequality transfers eigenvalue control from L(P*) to L(P), supporting the theorem’s conditions under the stated assumptions.

C.1 Proof of Proposition 12

The proof establishes concentration and spectral properties of the similarity matrix under the Gaussian mixture model, then verifies conditions controlling the early exaggeration and embedding stages.

Embedding-stage bounds: At k=K0, within-cluster contributions and between-cluster contributions are bounded separately to establish the desired embedding behavior.The argument extends these bounds to k>K0 through an iterative formula and sign-based coordinate analysis.
Condition verification: The proof verifies the assumptions needed for early exaggeration by bounding perturbation errors between the empirical and population similarity matrices.The resulting requirement includes K0ne−cρ2/max{p,log n}=o(1).
Gaussian mixture similarity structure: Concentration inequalities control within- and between-cluster kernel similarities with high probability.The argument combines Hanson–Wright and sub-Gaussian bounds after selecting t proportional to max{p, log n}.
Gaussian mixture similarity structure: The Gaussian-mixture similarity matrix is approximated by a block-wise constant matrix, with Laplacian spectral structure determined by cluster membership.The proof introduces P0 through conditional expectations and uses Weyl’s inequality to transfer spectral bounds to P∗.
Conclusion: The proof concludes by establishing the relevant proposition under the stated spectral and concentration conditions.Several intermediate lemmas provide high-probability bounds for the kernel and Laplacian quantities used in the conclusion.

D.2 Proof of the Noisy Nested Sphere Model

The noisy nested sphere analysis verifies the model-specific assumptions needed for the theory and derives bounds ensuring the prescribed t-SNE iteration conditions hold with high probability.

Similarity structure: The model’s similarity matrix is analyzed through a proposition concerning its structure under the noisy nested sphere model.The proof then reduces the required conditions to bounds on kernel similarities and separation between sphere components.
Separation conditions: Sufficient separation between sphere radii prevents cross-cluster points from becoming too similar.The stated condition is min_i≁j |ρzi−ρzj| ≥ Cσ√log n.
Condition verification: The proof checks the technical assumptions governing K0, h, α, P, P∗, and the initial embedding.These conditions control early exaggeration growth, perturbation size, spectral scaling, and initialization.
Conclusion: The required conditions hold with probability at least 1−n−c when K0≫log n.This yields the corollary for the noisy nested sphere model.
Spectral control: The shifted Laplacian retains controlled operator norm, giving the bound 1≤∥I−hL(αP−Hn)∥≤1+h/(n−1).The argument uses the eigenvalues of L(αP) and its positive semidefiniteness.

E.2 Proof of Lemma 23

The proof of Lemma 23 derives concentration bounds for Gaussian kernel quantities and uses them to control similarity-matrix entries and neighborhood sizes under the model assumptions.

Kernel concentration: Gaussian differences are decomposed into mean separation and covariance-driven noise to analyze pairwise kernel values.For equal means, the proof derives a closed-form expectation involving τ and the eigenvalues of Σ.
Kernel concentration: Choosing τ2≍max{p,log n} balances the kernel bounds obtained from upper and lower concentration estimates.This choice is used to combine the bounds and establish the lemma’s target relation.
Kernel concentration: The expected within-cluster kernel satisfies EKij≍1.This provides the scale needed for subsequent similarity-matrix estimates.
Similarity-matrix bounds: The proof bounds entries of the empirical and conditional similarity matrices by analyzing kernel ratios and applying union bounds.The comparison distinguishes pairs inside and outside selected clusters.
Neighborhood-size bounds: For approximately aligned mean directions, the neighborhood Si(γ) contains at least order nγ points with high probability when γ≳log n/n.The argument combines spherical area calculations with binomial concentration.

F. Supplementary Figures

The supplementary figures examine theory-guided parameter choices across synthetic and MNIST data, showing cluster visualizations, similarity structure, and robustness to tuning variation and weaker separation.

Figure 7: Figure 7 compares final t-SNE embeddings for model-generated samples under alternative tuning parameters with δ=1/2.The experiments use Gaussian-mixture and noisy nested-sphere settings described in Section 4.
Figure 8: Figure 8 shows Gaussian-mixture embeddings when the separation condition ρ2≫p is slightly violated.The reported visualizations indicate that clusters remain visible under the weaker separations ρ2=p^2/3 and ρ2=p^4/5.
Figure 9: Figure 9 displays the MNIST similarity matrix P for 1,600 samples from digits 2, 4, 6, and 8.The row and column color bars encode cluster labels, supporting the assumed approximate block structure.
Figure 10: Figure 10 compares 2,400 MNIST visualizations using identical random initialization but different δ values.Similar cluster patterns are reported across the theory-guided tuning choices.