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

T. Tony CaiRong Ma

article2022JMLR261 citations

Establishes a rigorous theoretical foundation for t-SNE by linking its early exaggeration phase to Laplacian spectral clustering and analyzing its map kinematics to provide principled guidelines for hyperparameter selection.

Listen

Data visualization and nonlinear dimension reduction are fundamental tools for discovering patterns, trends, and clusters in complex, high-dimensional datasets. The t-distributed stochastic neighbor embedding (t-SNE) algorithm is one of the most widely used methods across scientific disciplines such as genetics and computer vision. Despite its empirical success, the algorithm has long lacked a solid theoretical foundation, leaving practitioners unsure of how to properly interpret its visual outputs, how to systematically select tuning parameters, or how to avoid common artifacts.

The article establishes a rigorous theoretical foundation for t-SNE applied to clustered data. It evaluates and explains the computational mechanics and asymptotic properties of both the early exaggeration stage and the subsequent embedding stage of the algorithm.

The authors analyze t-SNE through discrete-time iterations and continuous-time gradient flows, framing the optimization process in terms of graph Laplacians and mechanical kinematic forces. They validate their theoretical findings using mathematical proofs, simulations on synthetic benchmarks (Gaussian mixture and noisy nested sphere models), and empirical evaluations on real-world image data from the MNIST handwritten digit dataset.

The investigation yields four central findings. First, the early exaggeration stage is mathematically equivalent to power iterations on a graph Laplacian, acting as an implicit spectral clustering mechanism that groups data without requiring the user to specify the number of clusters in advance. Second, early stopping during this initial stage provides implicit regularization; without stopping early, iterations over weakly clustered data cause "overshooting" and converge to trivial averages or false clusters. Third, the embedding stage consists of an amplification phase driven by intercluster repulsion and map expansion, followed by a stabilization phase that refines local structures. Fourth, while random initialization reliably uncovers cluster membership, the final relative spatial positions and neighboring relationships between clusters are arbitrary artifacts of initialization rather than true geometric properties of the original data.

These findings provide essential practical guidance for organizations and researchers relying on t-SNE for exploratory data analysis, quality control, or downstream decision-making. Analysts can avoid misleading interpretations of cluster geometry and reduce the risk of false discoveries. Furthermore, the theory provides explicit formulas for setting learning rates, iteration counts, and exaggeration parameters in a data-adaptive manner.

Practitioners should implement early stopping during the early exaggeration stage (such as setting the number of exaggeration iterations proportional to the square of the logarithm of sample size) to prevent overshooting on weakly clustered data. Analysts must interpret cluster groupings for membership only, avoiding conclusions based on the spatial distance between distinct clusters. Because random initialization can occasionally induce false clusters via intercluster repulsion, users should run t-SNE across multiple random initializations or use spectral initialization based on the leading Laplacian eigenvectors for strongly clustered datasets.

While the analytical conclusions are supported with high mathematical confidence under standard clustering assumptions, the theoretical separation requirements between clusters remain somewhat conservative relative to empirical performance limits. Future research is needed to determine the exact information-theoretic separation boundaries, explore data-driven bandwidth selection, and analyze the late-stage stabilization dynamics.

Stanford University University of Pennsylvania data visualization regularization spectral clustering t-SNE high-dimensional clustered data nonlinear dimension reduction

arXiv: 2105.07536

Paper: Stochastic Neighbor Embedding, Geoffrey E. Hinton et al. (2002). Introduces the original Stochastic Neighbor Embedding algorithm, providing the foundational probabilistic neighborhood objective that t-SNE modifies and the source theoretically analyzes.
Paper: Accelerating t-SNE using tree-based algorithms, Laurens van der Maaten (2014). Presents standard algorithmic formulations of t-SNE optimization, early exaggeration, and kinematic repulsive-attractive force mechanics analyzed in the theoretical study.
Paper: A tutorial on spectral clustering, Ulrike von Luxburg (2007). Provides the mathematical background on graph Laplacians and spectral clustering needed to understand the source's proof connecting early exaggeration iterations to power methods on Laplacians.
Paper: Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering, Mikhail Belkin et al. (2001). Establishes spectral embedding via graph Laplacians for dimensionality reduction, which serves as the theoretical and practical initialization baseline in the source.
Paper: On Spectral Clustering: Analysis and an algorithm, Andrew Y. Ng et al. (2001). Offers essential analytical tools and perturbation theory for normalized graph Laplacians, directly underlying the source's analysis of cluster separation and spectral dynamics.
Paper: UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction, Leland McInnes et al. (2018). Develops a neighboring graph-based nonlinear dimensionality reduction framework that relies on spectral initialization and force optimization comparable to t-SNE.
Paper: Think Globally, Fit Locally: Unsupervised Learning of Low Dimensional Manifold, L. Saul et al. (2003). Introduces foundational concepts of local neighborhood graph preservation for nonlinear manifold learning prior to probabilistic embedding models.

No sufficiently relevant recommendations were found.

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

Abstract

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 the interpretations of the t-SNE visualizations, and provides theoretical guidance for applying t-SNE and selecting its tuning parameters in various applications.

Topics

data visualization regularization spectral clustering stochastic visualization tools high dimensional data

Keywords

t-SNE high-dimensional clustered data nonlinear dimension reduction Noisy Nested Sphere Model multidimensional scaling spectral clustering shift-invariant similarities low-dimensional map package Rtsne

1. Introduction
1.1 Basic t-SNE Algorithm
1.2 Main Results and Our Contribution
1.3 Related Work
1.4 Notation and Organization
2. Analysis of the Early Exaggeration Stage
2.1 Asymptotic Graphical Interpretation and Localization
2.2 Asymptotic Power Iterations, Implicit Spectral Clustering and Early Stopping
2.3 Gradient Flow and Implicit Regularization
3. Analysis of the Embedding Stage
4. Application I: Visualizing Model-Based Clustered Data
4.1 Gaussian Mixture Model
4.2 Noisy Nested Sphere Model
5. Application II: Visualizing Real-World Clustered Data
6. Discussion
Acknowledgement
References
Appendix A. Discrete-Time Analysis of the Early Exaggeration Stage
A.1 Proof of Theorem 2
A.2 Proof of Proposition 3
A.3 Proof of Theorem 4
A.4 Proof of Theorem 5
A.5 Proof of Proposition 6
A.6 Proof of Theorem 7
Appendix B. Continuous-Time Analysis of the Early Exaggeration Stage
B.1 Proof of Proposition 8
B.2 Proof of Proposition 9
B.3 Proof of Theorem 10
Appendix C. Analysis of the Embedding Stage
C.1 Proof of Proposition 12
C.2 Proof of Theorem 13
C.3 Proof of Theorem 14
C.4 Proof of Theorem 15
Appendix D. Analysis of Two Examples
D.1 Proofs of the Gaussian Mixture Model
D.2 Proof of the Noisy Nested Sphere Model
Appendix E. Proof of Auxiliary Lemmas
E.1 Proof of Lemma 21
E.2 Proof of Lemma 23
E.3 Proof of Lemma 24
E.4 Proof of Lemma 25
E.5 Proof of Lemma 27
Appendix F. Supplementary Figures

Knowls

Knowl 1 — Two-Stage t-SNE Gradient Descent Framework with Early Exaggeration
model/method
Let $\{X_i\}_{i=1}^n \subset \mathbb{R}^p$ be high-dimensional data points. The pairwise similarity matrix in high dimension is $P = (p_{ij})_{1 \le i,j \le n} \in \mathbb{R}^{n \times n}$ , with $p_{ii} = 0$ and for $i \neq j$ : $p_{ij} = \frac{p_{i|j} + p_{j|i}}{2n}, \quad p_{j|i} = \frac{\exp(-\|X_i - X_j\|_2^2 / (2\tau_i^2))}{\sum_{\ell \neq i} \exp(-\|X_i - X_\ell\|_2^2 / (2\tau_i^2))},$ where $\tau_i > 0$ are bandwidth parameters. For a low-dimensional map $\{y_i\}_{i=1}^n \subset \mathbb{R}^2$ , the similarity matrix is $Q = (q_{ij})_{1 \le i,j \le n}$ , with $q_{ii} = 0$ and for $i \neq j$ : $q_{ij} = \frac{(1 + \|y_i - y_j\|_2^2)^{-1}}{\sum_{\ell \neq s} (1 + \|y_\ell - y_s\|_2^2)^{-1}}.$ The t-SNE objective minimizes the Kullback-Leibler divergence $D_{\mathrm{KL}}(P, Q) = \sum_{i \neq j} p_{ij} \log(p_{ij}/q_{ij})$ . The standard optimization is decomposed into two distinct stages:
1. Early Exaggeration Stage: For the first $K_0 > 0$ iterations, similarity entries are multiplied by an exaggeration parameter $\alpha > 0$ : $y_i^{(k+1)} = y_i^{(k)} + h \sum_{j \neq i} (y_j^{(k)} - y_i^{(k)}) S_{ij}^{(k)}(\alpha), \quad i=1,\dots,n,$ where $S_{ij}^{(k)}(\alpha) = \frac{\alpha p_{ij} - q_{ij}^{(k)}}{1 + \|y_i^{(k)} - y_j^{(k)}\|_2^2}$ and $h > 0$ is the step size.
2. Embedding Stage: For iterations $k \ge K_0$ , the exaggeration parameter is dropped (effectively $\alpha = 1$ ) with step size $h' > 0$ : $y_i^{(k+1)} = y_i^{(k)} + h' \sum_{j \neq i} (y_j^{(k)} - y_i^{(k)}) S_{ij}^{(k)}(1), \quad i=1,\dots,n.$
Knowl 2 — Asymptotic Graphical Interpretation of Early Exaggeration
theoretical result
For a symmetric matrix $A = (a_{ij}) \in \mathbb{R}^{n \times n}$ , define the degree operator $D(A) = \operatorname{diag}(\sum_{j=1}^n a_{1j}, \dots, \sum_{j=1}^n a_{nj})$ and Laplacian operator $L(A) = D(A) - A$ . In the early exaggeration stage of t-SNE, the update for each coordinate $\ell \in \{1, 2\}$ is: $y_\ell^{(k+1)} = [I_n - h L(S_\alpha^{(k)})] y_\ell^{(k)},$ where $S_\alpha^{(k)} \in \mathbb{R}^{n \times n}$ has off-diagonal entries $S_{ij}^{(k)}(\alpha) = (\alpha p_{ij} - q_{ij}^{(k)}) / (1 + \|y_i^{(k)} - y_j^{(k)}\|_2^2)$ and zero diagonal. Let $\eta^{(k)} = [\operatorname{diam}(\{y_i^{(k)}\}_{i=1}^n)]^2$ and $H_n = \frac{1}{n(n-1)}(1_n 1_n^\top - I_n)$ , where $1_n = (1, \dots, 1)^\top \in \mathbb{R}^n$ .

For any $i \neq j$ and iteration $k \ge 1$ with $\eta^{(k)} < 1$ , the entries satisfy: $\left| S_{ij}^{(k)}(\alpha) - \alpha p_{ij} + \frac{1}{n(n-1)} \right| \le \alpha p_{ij} \eta^{(k)} + \frac{2\eta^{(k)}}{n(n-1)(1 - \eta^{(k)})}.$ Consequently, if $\eta^{(k)} \ll \frac{\|P\|}{n \|P\|_\infty}$ and $\alpha \gg \frac{1}{n\|P\|}$ as $n \to \infty$ , then: $\lim_{n \to \infty} \frac{\|S_\alpha^{(k)} - (\alpha P - H_n)\|}{\|\alpha P - H_n\|} = 0.$ Thus, under small embedding diameter and sufficiently large exaggeration, $S_\alpha^{(k)}$ behaves asymptotically as a fixed matrix $\alpha P - H_n$ across iterations.
Knowl 3 — Localization and Asymptotic Equivalence to Power Iterations in Early Exaggeration
theoretical result
Consider the early exaggeration stage of t-SNE under the following conditions on initialization $\{y_i^{(0)}\}_{i=1}^n$ and parameters $(\alpha, h, k)$ as $n \to \infty$ :
- (I1) $\min_{\ell \in \{1,2\}} \|y_\ell^{(0)}\|_2 > 0$ and $\max_{\ell \in \{1,2\}} \|y_\ell^{(0)}\|_\infty = O(1)$ ;
- (I2) $\max_{\ell \in \{1,2\}} \|y_\ell^{(0)}\|_\infty^2 = o(\|P\| / (n \|P\|_\infty))$ ;
- (T1.D) $\alpha \gg (n \|P\|)^{-1}$ and $k(n h \alpha \|P\|_\infty + h/n) = o(1)$ .
Under these conditions:
1. Localization: The low-dimensional map remains bounded within the initial range throughout iterations: $\operatorname{diam}(\{y_i^{(k+1)}\}_{i=1}^n) \le C \max_{\ell \in \{1,2\}} \|y_\ell^{(0)}\|_\infty,$ for a universal constant $C > 0$ .
2. Asymptotic Power Iteration: The early exaggeration iterates are asymptotically equivalent to power iterations on the fixed Laplacian operator $I_n - hL(\alpha P - H_n)$ : $\lim_{n \to \infty} \frac{\|y_\ell^{(k)} - [I_n - hL(\alpha P - H_n)]^k y_\ell^{(0)}\|_2}{\|y_\ell^{(0)}\|_2} = 0, \quad \ell \in \{1, 2\}.$
Knowl 4 — Convergence of Power Iterations to the Graph Laplacian Null Space
theoretical result
Let $R \ge 1$ be the dimension of the null space of the Laplacian $L(P) \in \mathbb{R}^{n \times n}$ , and let $U \in \mathbb{R}^{n \times R}$ be a matrix with orthonormal columns forming a basis for this null space. Assume the step size and exaggeration satisfy the eigengap condition: $\kappa < h \lambda_{R+1}(L(\alpha P)) \le h \lambda_n(L(\alpha P)) < 1$ for a constant $\kappa \in (0, 1)$ , and $k h = o(n)$ . Then for any non-zero vector $y \in \mathbb{R}^n$ : $\lim_{k \to \infty} \frac{\|[I_n - hL(\alpha P - H_n)]^k y - U U^\top y\|_2}{\|y\|_2} = 0.$ Furthermore, when the symmetric adjacency matrix $A \in \mathbb{R}^{n \times n}$ corresponds to a graph with $R \ge 2$ disconnected components of sizes $n_1, \dots, n_R$ , the null space of $L(A)$ is spanned by $\{\theta_1, \dots, \theta_R\}$ where: $[\theta_r]_j = \begin{cases} 1/\sqrt{n_r} & \text{if node } j \text{ belongs to the } r\text{-th component} \\ 0 & \text{otherwise} \end{cases}$ Every vector $u$ in the null space of $L(A)$ takes at most $R$ distinct constant values across nodes, sharing identical values if and only if nodes belong to the same component.
Knowl 5 — Implicit Spectral Clustering and Early Stopping for Weakly Clustered Data
theoretical result
Let the original high-dimensional similarity $P$ be weakly clustered, in the sense that there exists a symmetric, well-conditioned matrix $P^* \in \mathbb{R}^{n \times n}$ with $R$ disconnected components of sizes $n_1, \dots, n_R$ such that $k h \alpha \|L(P^* - P)\| = o(1)$ (condition T2.D). Under conditions (I1), (I2), and (T1.D), there exists a permutation matrix $O \in \mathbb{R}^{n \times n}$ such that for coordinate $\ell \in \{1, 2\}$ : $\lim_{(k,n) \to \infty} \frac{\|y_\ell^{(k)} - O z_\ell\|_2}{\|y_\ell^{(0)}\|_2} = 0,$ where $z_\ell = (\underbrace{z_{\ell 1}, \dots, z_{\ell 1}}_{n_1}, \underbrace{z_{\ell 2}, \dots, z_{\ell 2}}_{n_2}, \dots, \underbrace{z_{\ell R}, \dots, z_{\ell R}}_{n_R})^\top \in \mathbb{R}^n, \quad z_{\ell r} = \frac{\theta_r^\top y_\ell^{(0)}}{\sqrt{n_r}} = \frac{1}{n_r}\sum_{i \in H_r} y_{i\ell}^{(0)}.$ This implies:
1. Intra-cluster contraction: Samples belonging to the same cluster contract toward a single 2D point $(z_{1r}, z_{2r})$ .
2. Dependence on initialization: Cluster centers in the embedding depend solely on the initial random coordinates $y^{(0)}$ rather than the true geometric distances between clusters.
3. Necessity of early stopping: The iteration count must obey $k \ll \frac{1}{h \alpha \|L(P^* - P)\|}$ . Running early exaggeration without stopping early causes overshooting, where the embedding converges to the uninformative trivial null eigenvector $n^{-1/2} 1_n$ of the connected graph Laplacian $L(P)$ .
Knowl 6 — Continuous-Time Gradient Flow and Implicit Regularization in Early Exaggeration
theoretical result
In the early exaggeration stage, the continuous-time limit of the power iteration sequence $\tilde{y}_\ell^{(k)} = [I_n - hL(\alpha P - H_n)]^k y_\ell^{(0)}$ as $h \to 0$ with $t = kh$ is the linear ordinary differential equation: $\dot{Y}_\ell(t) = -L(\alpha P - H_n) Y_\ell(t), \quad Y_\ell(0) = y_\ell^{(0)}, \quad \ell \in \{1, 2\}.$ If $k h^2 \|L(\alpha P - H_n)\|^2 \to 0$ as $n \to \infty$ , the step process $y_{\ell,h}(t) = \tilde{y}_\ell^{(k)}$ uniformly approximates $Y_\ell(t)$ on $[0, T]$ with: $\sup_{t \in [0, T]} \frac{\|y_{\ell,h}(t) - Y_\ell(t)\|_2}{\|Y_\ell(t)\|_2} \le T h \|L(\alpha P - H_n)\|^2.$ Given the eigendecomposition $L(P) = \sum_{i=1}^n \lambda_i u_i u_i^\top$ with $0 = \lambda_1 \le \lambda_2 \le \dots \le \lambda_n$ and $u_1 = n^{-1/2}1_n$ , the explicit solution path is: $Y_\ell(t) = (u_1^\top y_\ell^{(0)}) u_1 + \sum_{i=2}^n \exp\left(-t\left(\alpha \lambda_i - \frac{1}{n-1}\right)\right) (u_i^\top y_\ell^{(0)}) u_i.$ This imposes an implicit regularization effect: early in optimization, $y_\ell^{(k)}$ acts as a conical sum over all eigenvectors $u_i$ . Informative eigenvectors with small eigenvalues (where $\alpha \lambda_i < \frac{1}{n-1}$ ) are amplified over time, while uninformative eigenvectors with large eigenvalues (where $\alpha \lambda_i > \frac{1}{n-1}$ ) decay exponentially in $k$ .
Knowl 7 — Intercluster Repulsion in the Amplification Phase of the Embedding Stage
theoretical result
Let $[n] = \bigcup_{r=1}^R H_r$ be the true cluster partition with sizes $|H_r| = n_r$ . Assume initialization satisfies (I3), early exaggeration satisfies (T1.E), and the embedding stage step size $h'$ and iteration count $K_1$ satisfy (T3.E) such that $\operatorname{diam}(\{y_i^{(K_0+K_1)}\}_{i=1}^n) = o(1)$ (the amplification phase). For each iteration $K_0 \le k \le K_0 + K_1$ and any point $i \in H_{r_0}$ : $y_i^{(k+1)} = y_i^{(k)} + \sum_{r \in [R] \setminus \{r_0\}} f_{ir}^{(k)} + \epsilon_i^{(k)},$ where $\lim_{n \to \infty} \|\epsilon_i^{(k)}\|_2 / \|f_{ir}^{(k)}\|_2 = 0$ for all $r \neq r_0$ , and the repulsive force from cluster $r$ is: $f_{ir}^{(k)} = \frac{h' |H_r|}{n(n-1)} \left( y_i^{(k)} - \frac{1}{|H_r|} \sum_{j \in H_r} y_j^{(k)} \right) \in \mathbb{R}^2.$ Furthermore, the intra-cluster and inter-cluster distances satisfy: $\sup_{K_0 \le k \le K_0 + K_1} \max_{i \sim j} \|y_i^{(k)} - y_j^{(k)}\|_2 \ll n^{-1} (\|y_1^{(0)}\|_2 + \|y_2^{(0)}\|_2),$ $\inf_{K_0 \le k \le K_0 + K_1} \min_{i \not\sim j} \|y_i^{(k)} - y_j^{(k)}\|_2 \gtrsim n^{-1} (\|y_1^{(0)}\|_2 + \|y_2^{(0)}\|_2).$ Each point moves away from the centroids of all other clusters along the vector sum of repulsive forces, driving cluster separation.
Knowl 8 — Global Expansion and Transition to Stabilization Phase in the Embedding Stage
theoretical result
Under the intercluster repulsion conditions of the amplification phase with $\|P^*\|_\infty \lesssim n^{-2}$ , the global diameter of the embedding is strictly increasing after every iteration $k \in \{K_0, \dots, K_0 + K_1\}$ : $\operatorname{diam}(\{y_i^{(k+1)}\}_{i=1}^n) > \operatorname{diam}(\{y_i^{(k)}\}_{i=1}^n),$ with a strictly positive lower bound on expansion: $\operatorname{diam}(\{y_i^{(k+1)}\}_{i=1}^n) - \operatorname{diam}(\{y_i^{(k)}\}_{i=1}^n) \gtrsim \frac{h'}{n^2} \min_{\ell \in \{1,2\}} \|y_\ell^{(0)}\|_2.$

Stabilization Phase: Once $\operatorname{diam}(\{y_i^{(k)}\}_{i=1}^n)$ reaches constant order $O(1)$ , the amplification condition ceases to hold. The updates transition to the stabilization phase governed by: $y_i^{(k+1)} = y_i^{(k)} + h' \sum_{j \neq i} \frac{p_{ij} - q_{ij}^{(k)}}{1 + \|y_i^{(k)} - y_j^{(k)}\|_2^2} (y_j^{(k)} - y_i^{(k)}).$ In this phase, individual forces between $y_i$ and $y_j$ switch between attractive and repulsive based on the sign of $p_{ij} - q_{ij}^{(k)}$ : points attract when $p_{ij} > q_{ij}^{(k)}$ and repel when $p_{ij} < q_{ij}^{(k)}$ , performing fine local adjustments to reproduce high-dimensional pairwise similarities.
Knowl 9 — Theoretical Guarantees and Parameter Selection for Gaussian Mixture Models
theoretical result
Let data be generated from an $R$ -component Gaussian mixture model $X_i \mid z_i = r \sim \mathcal{N}(\mu_r, \Sigma)$ in $\mathbb{R}^p$ for $i \in [n]$ , with mixing proportions $\min_r \pi_r \ge c > 0$ , covariance satisfying $C^{-1} \le \lambda_1(\Sigma) \le \lambda_p(\Sigma) \le C$ and $\operatorname{tr}(\Sigma)/p \le C$ , and center separation $\rho^2 = \min_{j \neq k} \|\mu_j - \mu_k\|_2^2 \ge C' \max\{p, \log n\}$ . Let bandwidth $\tau_i^2 \asymp \max\{p, \log n\}$ .

If $\alpha \gg 1$ , $K_0 h = o(n)$ , $h\alpha \asymp n$ , $1 \ll K_0 \ll \exp\{\frac{\rho^2}{\max\{p, \log n\}}\}$ , and $K_0 h \alpha \sigma_n^2 \log n = o(n^2)$ , then implicit spectral clustering holds for early exaggeration. If in addition $\log n \ll K_0 \ll n^{-1} \exp\{\frac{\rho^2}{\max\{p, \log n\}}\}$ , $K_0 h \alpha \sigma_n^2 \log n = o(n)$ , and $K_1 h' = O(n)$ , then intercluster repulsion and map expansion hold during the embedding stage.

Theory-Guided Parameter Selection: When $\rho^2 \gtrsim \log n \cdot \max\{p, \log n\}$ , for any constant $\delta \in (0, 1)$ , choosing: $K_0 = \lfloor (\log n)^2 \rfloor, \quad \sigma_n = (\log n)^{-2}, \quad h = h' = n^\delta, \quad \alpha = n^{1-\delta}$ satisfies all requirements for both low-dimensional ( $p = o(n)$ ) and high-dimensional ( $p \gtrsim n$ ) settings.
Knowl 10 — Theoretical Guarantees and Parameter Selection for Noisy Nested Sphere Models
theoretical result
Consider data generated from nested spheres with radial noise: $X_i = \mu_i + \frac{\mu_i}{\|\mu_i\|_2} \xi_i$ , $\xi_i \overset{\mathrm{i.i.d.}}{\sim} \mathcal{N}(0, \sigma^2)$ , where $\mu_i \mid z_i = r$ is uniform on a sphere in $\mathbb{R}^p$ of radius $\rho_r$ , with $\rho_1 < \dots < \rho_R$ . Assume separation ratio $\max_{r \in [R-1]} \frac{\rho_r}{\rho_{r+1}} \le 1 - C \sqrt{\gamma \log \gamma}$ and radial gap $c \min_r |\rho_{r+1} - \rho_r| \ge \sigma \sqrt{\log n}$ , where $\max\{n^{-1}, \sigma^2 \rho_1^{-2}\} \log n \ll \gamma \ll 1$ . Set bandwidth $\tau_i^2 \asymp \gamma \rho_{z_i}^2$ .

When spheres are equally separated with $\rho_{r+1} - \rho_r = \Delta \ge c \rho_R$ and $\gamma = c(\log n)^{-1}$ , setting: $K_0 = \lfloor (\log n)^2 \rfloor, \quad \sigma_n = (\log n)^{-2}, \quad h = h' = n^\delta, \quad \alpha = \gamma n^{1-\delta}, \quad K_1 \le n^{1-\delta}/\log n$ for any constant $\delta \in (0, 1)$ guarantees that implicit spectral clustering holds in early exaggeration and intercluster repulsion holds in the embedding stage with high probability.
Knowl 11 — Empirical Verification of Early Stopping and Initialization Artifacts on MNIST
empirical result
Applying t-SNE to $n = 1600$ MNIST handwritten digits ('2', '4', '6', '8'; $N = 400$ per digit in 784 dimensions) with theory-guided parameters $\alpha = n^{1-\delta}$ , $h = h' = n^\delta$ (with $\delta = 2/3$ ) and default perplexity 30 demonstrates two key theoretical phenomena:
1. Early stopping prevents overshooting: When $K_0 = \lfloor (\log n)^2 \rfloor = 54$ , clear and separated cluster patterns emerge at both the end of early exaggeration and the final embedding ( $k = 1000$ ). When $K_0$ is increased beyond theoretical bounds to $K_0 = \lfloor n^{2/3} \rfloor = 137$ , cluster separation deteriorates; when $K_0 = \lfloor n^{3/4} \rfloor = 253$ , the early exaggeration embedding collapses onto a 1D curve, resulting in false clustering artifacts in the final visualization.
2. Random initialization determines relative cluster layout: Re-running t-SNE with identical parameters but different random initializations produces final 2D embeddings where relative cluster adjacencies change (e.g., digit clusters '2' and '8' are adjacent in one run but separated in another). Furthermore, accidental initial cluster overlaps combined with intercluster repulsion can occasionally split a true single cluster into apparent subclusters, confirming that relative 2D cluster positions do not reflect high-dimensional distances.

Coverage note — Deliberately omitted technical proofs in the appendices and minor secondary lemmas (e.g., Lemmas 21, 23, 24, 25, 27) that serve solely as intermediate proof steps for the main theorems.

References

1.Arash A Amini and Zahra S Razaee. Concentration of kernel matrices with application to kernel spectral clustering. The Annals of Statistics, 49(1):531–556, 2021.
2.Sanjeev Arora, Wei Hu, and Pravesh K Kothari. An analysis of the t-SNE algorithm for data visualization. In Conference on Learning Theory, pages 1455–1462. PMLR, 2018.
3.Sivaraman Balakrishnan, Min Xu, Akshay Krishnamurthy, and Aarti Singh. Noise thresholds for spectral clustering. In Advances in Neural Information Processing Systems, pages 954–962, 2011.
4.Zhigang Bao, Xiucai Ding, and Ke Wang. Singular vector and singular subspace distribution for the matrix denoising model. The Annals of Statistics, 49(1):370–392, 2021.
5.Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373–1396, 2003.
6.Florent Benaych-Georges and Raj Rao Nadakuditi. The singular values and vectors of low rank perturbations of large rectangular random matrices. Journal of Multivariate Analysis, 111:120–135, 2012.
7.John Charles Butcher. Numerical methods for ordinary differential equations. John Wiley & Sons, 2008.
8.T Tony Cai and Anru Zhang. Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics. The Annals of Statistics, 46(1):60–89, 2018.
9.Miguel A Carreira-Perpin'an. The elastic embedding algorithm for dimensionality reduction. In ICML, volume 10, pages 167–174, 2010.
10.Tara Chari, Joeyta Banerjee, and Lior Pachter. The specious art of single-cell genomics. BioRxiv, 2021.
11.Angelos Chatzimparmpas, Rafael M Martins, and Andreas Kerren. t-viSNE: Interactive assessment and interpretation of t-SNE projections. IEEE Transactions on Visualization and Computer Graphics, 26(8):2696–2714, 2020.
12.Jian Cheng, Haijun Liu, Feng Wang, Hongsheng Li, and Ce Zhu. Silhouette analysis for human action recognition based on supervised temporal t-SNE and incremental learning. IEEE Transactions on Image Processing, 24(10):3203–3217, 2015.
13.Adela DePavia and Stefan Steinerberger. Spectral clustering revisited: Information hidden in the fiedler vector. arXiv preprint arXiv:2003.09969, 2020.
14.Xiucai Ding and Rong Ma. Learning low-dimensional nonlinear structures from highdimensional noisy data: An integral operator approach. arXiv preprint arXiv:2203.00126, 2022.
15.David Donoho. 50 years of data science. Journal of Computational and Graphical Statistics, 26(4):745–766, 2017.
16.Andrej Gisbrecht, Alexander Schulz, and Barbara Hammer. Parametric nonlinear dimensionality reduction using kernel t-SNE. Neurocomputing, 147:71–82, 2015.
17.Geoffrey Hinton and Sam T Roweis. Stochastic neighbor embedding. In Advances in Neural Information Processing Systems, volume 15, pages 833–840, 2002.
18.Daniel Jiwoong Im, Nakul Verma, and Kristin Branson. Stochastic neighbor embedding under f-divergences. arXiv preprint arXiv:1811.01247, 2018.
19.Robert A Jacobs. Increased rates of convergence through learning rate adaptation. Neural Networks, 1(4):295–307, 1988.
20.Dmitry Kobak and Philipp Berens. The art of using t-SNE for single-cell transcriptomics. Nature Communications, 10(1):1–14, 2019.
21.Dmitry Kobak and George C Linderman. Initialization is critical for preserving global data structure in both t-SNE and UMAP. Nature Biotechnology, 39(2):156–157, 2021.
22.Joseph B Kruskal. Multidimensional Scaling. Number 11. Sage, 1978.
23.John A Lee and Michel Verleysen. Shift-invariant similarities circumvent distance concentration in stochastic neighbor embedding and variants. Procedia Computer Science, 4: 538–547, 2011.
24.John A Lee and Michel Verleysen. Two key properties of dimensionality reduction methods. In 2014 IEEE symposium on computational intelligence and data mining (CIDM), pages 163–170. IEEE, 2014.
25.George C Linderman and Stefan Steinerberger. Clustering with t-SNE, provably. SIAM Journal on Mathematics of Data Science, 1(2):313–332, 2019.
26.George C Linderman, Manas Rachh, Jeremy G Hoskins, Stefan Steinerberger, and Yuval Kluger. Fast interpolation-based t-SNE for improved visualization of single-cell RNA-seq data. Nature Methods, 16(3):243–245, 2019.
27.Anne Marsden. Eigenvalues of the laplacian and their relationship to the connectedness of a graph. University of Chicago, REU, 2013.
28.Luis Gustavo Nonato and Michael Aupetit. Multidimensional projection for visual analytics: Linking techniques with distortions, tasks, and layout enrichment. IEEE Transactions on Visualization and Computer Graphics, 25(8):2650–2673, 2018.
29.Florent Olivon, Nicolas Elie, Gwendal Grelier, Fanny Roussi, Marc Litaudon, and David Touboul. Metgem software for the generation of molecular networks based on the t-SNE algorithm. Analytical Chemistry, 90(23):13900–13908, 2018.
30.Nicola Pezzotti, Boudewijn PF Lelieveldt, Laurens Van Der Maaten, Thomas Ḧllt, Elmar Eisemann, and Anna Vilanova. Approximated and user steerable tSNE for progressive visual analytics. IEEE Transactions on Visualization and Computer Graphics, 23(7): 1739–1752, 2016.
31.Alexander Platzer. Visualization of snps with t-SNE. PloS One, 8(2):e56883, 2013.
32.Isaac Robinson and Emma Pierce-Hoffman. Tree-sne: Hierarchical clustering and visualization using t-sne. arXiv preprint arXiv:2002.05687, 2020.
33.Mark Rudelson and Roman Vershynin. Hanson-wright inequality and sub-gaussian concentration. Electronic Communications in Probability, 18, 2013.
34.Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. Kernel principal component analysis. In International Conference on Artificial Neural Networks, pages 583–588. Springer, 1997.
35.Uri Shaham and Stefan Steinerberger. Stochastic neighbor embedding separates wellseparated clusters. arXiv preprint arXiv:1702.02670, 2017.
36.Gregor Traven, Gal Matijevič, Tomaz Zwitter, M žerjal, Janez Kos, Martin Asplund, Joss Bland-Hawthorn, Andrew R Casey, Gayandhi De Silva, Kenneth Freeman, et al. The galah survey: classification and diagnostics with t-SNE reduction of spectral information. The Astrophysical Journal Supplement Series, 228(2):24, 2017.
37.Laurens van der Maaten. Accelerating t-SNE using tree-based algorithms. The Journal of Machine Learning Research, 15(1):3221–3245, 2014.
38.Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, 9(Nov):2579–2605, 2008.
39.Richard S Varga. Geršgorin and his circles, volume 36. Springer Science & Business Media, 2010.
40.Yingfan Wang, Haiyang Huang, Cynthia Rudin, and Yaron Shaposhnik. Understanding how dimension reduction tools work: An empirical approach to deciphering t-sne, umap, trimap, and pacmap for data visualization. Journal of Machine Learning Research, 22: 1–73, 2021.
41.Bo Xie, Yang Mu, Dacheng Tao, and Kaiqi Huang. m-SNE: Multiview stochastic neighbor embedding. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 41(4):1088–1096, 2011.
42.Zhirong Yang, Irwin King, Zenglin Xu, and Erkki Oja. Heavy-tailed symmetric stochastic neighbor embedding. In Advances in Neural Information Processing Systems, volume 22, pages 2169–2177, 2009.
43.Yulan Zhang and Stefan Steinerberger. t-SNE, forceful colorings and mean field limits. arXiv preprint arXiv:2102.13009, 2021.

Citation

MLA

Cai, T. T., and R. Ma. “Theoretical Foundations of t-SNE for Visualizing High-Dimensional Clustered Data”. Journal of Machine Learning Research, vol. 23, no. 301, 2022, pp. 1–4, https://www.jmlr.org/papers/v23/21-0524.html.

APA

Cai, T. T., & Ma, R. (2022). Theoretical Foundations of t-SNE for Visualizing High-Dimensional Clustered Data. Journal of Machine Learning Research, 23(301), 1–54. https://www.jmlr.org/papers/v23/21-0524.html

Chicago

Cai, T. T., and R. Ma. 2022. “Theoretical Foundations of t-SNE for Visualizing High-Dimensional Clustered Data”. Journal of Machine Learning Research 23 (301): 1–54. https://www.jmlr.org/papers/v23/21-0524.html.

Harvard

Cai, T.T. and Ma, R. (2022) “Theoretical Foundations of t-SNE for Visualizing High-Dimensional Clustered Data”, Journal of Machine Learning Research, 23(301), pp. 1–54. Available at: https://www.jmlr.org/papers/v23/21-0524.html.

Vancouver

1. Cai TT, Ma R (2022) Theoretical Foundations of t-SNE for Visualizing High-Dimensional Clustered Data. Journal of Machine Learning Research 23:1–54

BibTeX

@article{JMLR:v23:21-0524,
  author  = {T. Tony Cai and Rong Ma},
  title   = {Theoretical Foundations of t-SNE for Visualizing High-Dimensional Clustered Data},
  journal = {Journal of Machine Learning Research},
  year    = {2022},
  volume  = {23},
  number  = {301},
  pages   = {1--54},
  url     = {http://jmlr.org/papers/v23/21-0524.html}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

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

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Two-Stage t-SNE Gradient Descent Framework with Early Exaggeration

Knowl 2 — Asymptotic Graphical Interpretation of Early Exaggeration

Knowl 3 — Localization and Asymptotic Equivalence to Power Iterations in Early Exaggeration

Knowl 4 — Convergence of Power Iterations to the Graph Laplacian Null Space

Knowl 5 — Implicit Spectral Clustering and Early Stopping for Weakly Clustered Data

Knowl 6 — Continuous-Time Gradient Flow and Implicit Regularization in Early Exaggeration

Knowl 7 — Intercluster Repulsion in the Amplification Phase of the Embedding Stage

Knowl 8 — Global Expansion and Transition to Stabilization Phase in the Embedding Stage

Knowl 9 — Theoretical Guarantees and Parameter Selection for Gaussian Mixture Models

Knowl 10 — Theoretical Guarantees and Parameter Selection for Noisy Nested Sphere Models

Knowl 11 — Empirical Verification of Early Stopping and Initialization Artifacts on MNIST

References

Citation

BibTeX

Access the Paper