An Analysis of the t-SNE Algorithm for Data Visualization

Sanjeev Arora; Wei Hu; Pravesh K. Kothari

Source-linked AI summary

An Analysis of the t-SNE Algorithm for Data Visualization

Sanjeev Arora, Wei Hu, Pravesh K. Kothari

arXiv:1803.01768v2Mar 5, 2018cs.LG

TL;DR

The paper asks how to make clusters in high-dimensional data visually identifiable in two dimensions, where standard linear reduction can fail. It formalizes visualization and analyzes t-SNE under deterministic cluster conditions, proving guarantees for broad mixture models and partial recovery beyond those conditions.

Problem
High-dimensional data lack a rigorous 2D visualization framework that makes cluster structure visually identifiable, while standard linear reductions can merge distinct clusters.
Method
The paper defines visible clusters and analyzes t-SNE’s nonconvex similarity-matching optimization under a deterministic condition on ground-truth clusters.
Results
The analysis gives the first provable t-SNE guarantees for full visualizations of spherical, well-separated data and specified mixture models, plus partial visualization when those conditions fail.
Takeaways & Limitations
t-SNE provably succeeds in natural parameter regimes for clusterable generative models where standard linear dimensionality reduction techniques fail.
Takeaways & Limitations
The visualization formalization is a first cut and does not capture all psychological and perceptual aspects of what humans see as a good visualization.

Abstract

from arXiv · show

A first line of attack in exploratory data analysis is data visualization, i.e., generating a 2-dimensional representation of data that makes clusters of similar points visually identifiable. Standard Johnson-Lindenstrauss dimensionality reduction does not produce data visualizations. The t-SNE heuristic of van der Maaten and Hinton, which is based on non-convex optimization, has become the de facto standard for visualization in a wide range of applications. This work gives a formal framework for the problem of data visualization - finding a 2-dimensional embedding of clusterable data that correctly separates individual clusters to make them visually identifiable. We then give a rigorous analysis of the performance of t-SNE under a natural, deterministic condition on the "ground-truth" clusters (similar to conditions assumed in earlier analyses of clustering) in the underlying data. These are the first provable guarantees on t-SNE for constructing good data visualizations. We show that our deterministic condition is satisfied by considerably general probabilistic generative models for clusterable data such as mixtures of well-separated log-concave distributions. Finally, we give theoretical evidence that t-SNE provably succeeds in partially recovering cluster structure even when the above deterministic condition is not met.

1 Introduction

The paper formalizes 2D data visualization as making ground-truth clusters visually identifiable and rigorously analyzes t-SNE under deterministic cluster conditions. It proves full or partial visualization guarantees for several clusterable-data models.

Motivation: High-dimensional data are difficult to reduce to two dimensions without merging distinct clusters, whereas t-SNE targets visually identifiable cluster structure.The paper contrasts t-SNE with linear methods such as JL and PCA, which can produce uniform-looking point clouds.
Algorithm and analysis: t-SNE minimizes KL divergence between high-dimensional and embedded pairwise similarities using nonconvex gradient descent with random initialization and early exaggeration.The analysis aims to understand this optimization procedure under structured data assumptions.
Formalization: A visualization is a 2D embedding in which points from each ground-truth cluster are well-separated from the rest.The paper formalizes visibility for individual clusters and defines a visualization by requiring every cluster to be visualized.
Main guarantees: Under a natural deterministic condition for spherical, well-separated clusterable data, t-SNE with early exaggeration outputs a full visualization with high probability.The condition concerns concentrated within-cluster distances, larger between-cluster distances, and sufficiently large clusters.
Mixture models: For mixtures of isotropic Gaussians and isotropic log-concave distributions, the required mean separations are ˜Ω(d1/4) and ˜Ω(d5/12), respectively.These guarantees apply to well-separated mixture models and yield full visualizations with high probability.
Partial visualization: Even without mean separation, t-SNE partially visualizes mixtures of two concentric spherical Gaussians whose variances differ by a constant factor.For variance ratio 1.5 ≤ σ2/σ1 ≤ 10, one cluster is (1 − d−Ω(1))-visible in the resulting partial visualization.

2 Preliminaries and Notation

The paper defines notation for clustered high-dimensional data and describes t-SNE as an optimization procedure that maps it into a 2-dimensional visualization.

Data and notation: The dataset X consists of points in R^d with a ground-truth partition into k clusters, and n is assumed polynomial in d.The mapping π identifies each point’s cluster, while i ∼ j denotes membership in the same cluster.
t-SNE algorithm: t-SNE maps the input dataset to a 2-dimensional dataset Y suitable for visualization.The analysis focuses on R^2, although the stated results also hold in any constant dimension.
Similarity construction: For each pair of distinct input points, t-SNE computes a joint probability p_ij using Gaussian bandwidths τ_i.The bandwidth parameter controls the Gaussian kernel around each input point.
Optimization: For the embedding, t-SNE defines pairwise affinities q_ij and minimizes the KL divergence between the input similarities p and embedding similarities q.The objective is minimized by gradient descent using the gradient of the objective function.
Optimization: The algorithm takes Gaussian bandwidths, an exaggeration parameter α, a step size h, and a round count T as inputs.Initialization samples each y_i independently and uniformly from [-0.01, 0.01]^2; early exaggeration multiplies all p_ij by α > 1.

3 Full Visualization via t-SNE

Under deterministic spherical and well-separated cluster conditions, t-SNE with early exaggeration produces a 2-dimensional embedding that fully visualizes the ground-truth clusters with high probability. The analysis extends to several probabilistic mixture models and connects the guarantee to power-method iterations.

Main theorem: With probability at least 0.99, t-SNE outputs a full visualization for γ-spherical, γ-well-separated data with sufficiently large clusters and k ≪ n^1/5.The theorem uses specified choices of τ, h, α, and T, with T determined asymptotically by the analysis.
Probabilistic models: For mixtures of isotropic Gaussians, mean separation of ˜Ω(d^1/4) suffices for full visualization with high probability.The result applies to Gaussian samples with identity covariance and pairwise-separated means.
Proof strategy: The proof combines affinity conditions with iterative cluster shrinkage and centroid separation to make within-cluster distances smaller than between-cluster distances.Lemma 3.3 identifies sufficient affinity conditions, while the proof tracks shrinking clusters and separated centroids.
Probabilistic models: The guarantee extends to certain non-isotropic log-concave mixtures under covariance-dependent radius and mean-separation conditions.The stated condition requires R/σℓ > d^η and mean separation much larger than Rd^-η/6 log^2/3 n.
Connection to power methods: Ignoring the low-dimensional repulsion terms, t-SNE updates correspond to noiseless power-method iterations on the matrix of pairwise affinities.This correspondence gives t-SNE the same full-visualization guarantee as the power method for the stated well-separated data.

4 Partial Visualization via t-SNE

The paper examines whether t-SNE can partially visualize cluster structure when its usual separation condition fails, using mixtures of concentric Gaussians as an example. It proves that t-SNE still makes one cluster highly visible under this difficult setting.

Motivation: The section investigates partial visualization when the separation condition for full visualization fails drastically.Partial visualization means correctly visualizing at least one cluster.
Example setting: The example uses two concentric Gaussians with identical means and variance ratio σ2/σ1 = 1.5, so their means have zero separation.Despite identical means, concentration properties imply cross-component points can be closer than points within the larger-variance component.
Implication: The result contrasts with the fact that most Gaussian-mixture learning algorithms fail in this setting, except distance-based methods.The comparison is stated for the same zero-mean, unequal-variance Gaussian situation.
Guarantee: Under the theorem’s assumptions, t-SNE runs for T = Θ(log d) iterations and, with high probability over initialization, produces a (1 − d^-Ω(1))-partial visualization.The visible cluster is C1, which is itself (1 − d^-Ω(1))-visible.
Proof strategy: The proof establishes general conditions for partial visualization and verifies them for mixtures of two concentric Gaussians.The theorem is obtained by checking those conditions for the specified mixture model.

5 Conclusion

The paper develops a rigorous framework for visualization and analyzes t-SNE theoretically. Its analysis shows provable success for clusterable data from well-studied generative models, while acknowledging that the visualization formalization is only a first cut.

Contribution: The paper presents a rigorous framework for studying visualization and a theoretical analysis of the t-SNE algorithm.The framework formalizes the visualization problem, while the analysis targets a popular visualization heuristic.
Limitation: The visualization formalization is a first cut because a complete account of good visualizations would involve psychological and perceptual aspects.The authors identify further investigation of useful visualization notions and analytical tools as an open direction.

A.1 Proof of Lemma 3.4

This proof verifies the pairwise similarity bounds needed for the deterministic conditions underlying the t-SNE analysis. It then checks the corresponding conditions one by one.

Pairwise bounds: The proof first establishes constants c1 and c2 that bound pairwise quantities for distinct points.These bounds distinguish related and unrelated point pairs in the subsequent verification.
Assumptions: The γ-sphericalness and γ-well-separation assumptions relate each point’s nearest-neighbor distance to its cluster scale.The resulting inequalities provide the distance control used in the pairwise analysis.
Condition verification: The proof uses the established bounds to verify condition (i) of Lemma 3.3 through a lower bound on within-cluster similarity.The argument applies the bound to all points in the relevant neighborhood.
Condition verification: It verifies condition (iv) by upper-bounding the aggregate similarity to points not related to a given point.The bound is obtained by summing the relevant pairwise terms.
Conclusion: After these checks, the proof concludes Lemma 3.4.The conclusion follows from verifying the required conditions.

A.2 Proof of Lemma 3.5

This proof analyzes the t-SNE embedding dynamics by combining a shrinkage lemma with diameter bounds. It shows exponential contraction until a controlled scale, after which the diameter remains bounded.

Dynamic-system analysis: The proof rewrites cluster evolution as a dynamic system and applies a prior shrinkage lemma to analyze the updates.The dynamic-system formulation is used to control the motion of embedded points over time.
Geometric control: The convex hull of the evolving points satisfies Conv(t+1) ⊆ Conv(t) + B(0, ϵ′).This bounds how far the next-step embedding can extend beyond the current convex hull.
Diameter contraction: The diameter recurrence is D(t+1) ≤ (1 − mδ′η′/2)D(t) + 2ϵ′ under the conditions of Lemma A.2.The contraction term reduces the diameter while 2ϵ′ accounts for additive perturbation.
Diameter contraction: When D(t) exceeds 5ϵ′/(mδ′η′), the diameter contracts by a multiplicative factor; below that threshold, it remains bounded by the same scale.These are the two cases of Corollary A.3.
Proof completion: The proof verifies the required conditions and checks that the iteration count remains within the range where the intermediate claims apply.It then concludes Lemma 3.5.

A.3 Proof of Lemma 3.12

The proof uses thin-shell concentration and one-dimensional log-concave tail bounds to control norms and inner products, then applies a union bound over all point pairs.

Concentration tools: Thin-shell concentration controls the distance of log-concave samples from their mean.For x with covariance Σ and A = Σ^1/2, the proof invokes a concentration lemma for ∥x − µ∥.
Concentration tools: A one-dimensional projection of a log-concave distribution is itself log-concave and has variance ∥Ay∥^2.This follows by linear-transformation closure of log-concavity and covariance calculation.
Projection bound: For any δ ∈ (0, 1), the projection obeys |⟨x − µ, y⟩| ≤ (1 + ϵ)∥Ay∥ with probability at least 1 − δ.The proof sets ϵ = Θ(log 1/δ) through the one-dimensional concentration lemma.
Pairwise control: The lemma proof bounds sample norms and cross-cluster inner products, using independence through conditioning.The resulting bounds hold with probability at least 1 − n^-3, and a union bound over all pairs completes the argument.

A.4 Proof Sketch of Lemma 3.13

The proof sketch analyzes t-SNE dynamics within each cluster as a noisy power method, yielding cluster shrinkage while preserving a separation bound.

Cluster shrinkage: Within each cluster, embedded coordinates are shown to converge toward a common value as iterations grow.The same conclusion applies coordinatewise in R^2.
Cluster shrinkage: Restricting the update to one cluster gives z(t+1) = Bℓz(t) + ε(t), a noisy power-method recurrence.Here ε(t) collects the coordinatewise update noises within cluster Cℓ.
Cluster shrinkage: With a bounded-noise assumption and an eigengap, the cluster state converges to the scaled top eigenvector of Bℓ.The top eigenvector is the all-1 vector because it corresponds to the leading eigenvalue 1.
Separation: The proof combines within-cluster shrinkage with the separation bound from Lemma 3.6 to obtain Lemma 3.13.Thus the argument uses both contraction inside clusters and separation between them.

B Proofs for Section 4

This section develops a general theorem for balanced, regular datasets with gapped shrinkage parameters and applies it to the two-concentric-Gaussians example.

Applicability: The proof strategy establishes Theorem B.4 first and then verifies its conditions for the two-concentric-Gaussians example.The general result is therefore used as the route to Theorem 4.1.
Applicability: γ-regularity is stronger than γ-sphericalness but can hold for mixtures of non-isotropic log-concave distributions and spherical Gaussians.For the former class, the passage states γ = O(d^-η) for some η > 0.
General theorem: Theorem B.4 assumes balanced γ-regular data whose cluster shrinkage parameters are gapped.The largest βℓ must be at least 1.1 times larger than the second largest.
General theorem: After T = Θ(log d) iterations, t-SNE partially visualizes the dataset and makes the cluster with largest shrinkage parameter visible.The theorem gives high-probability guarantees over the random initialization.
General theorem: The guarantee is that C1 is (1 − d^-Ω(1))-visible in a (1 − d^-Ω(1))-partial visualization.The dataset size must satisfy n ≥ k^(1+ω)d^ω for a constant ω > 0.

B.1 Proof of Theorem B.4

The proof of Theorem B.4 controls the t-SNE iterates, establishes differential shrinkage across clusters, and uses this to show partial visualization of the leading cluster.

Iterate control: The initialization and update bounds keep every embedded point inside the small square [−0.01, 0.01]^2 throughout the iterations.The proof establishes this invariant by induction.
Shrinkage: Within cluster Cℓ, pairwise distances approximately shrink by a factor of 1 − αhβℓ/n at each iteration.This contraction motivates the term shrinkage parameter for βℓ.
Partial visualization: After T = C'' log d iterations, C1 becomes tightly concentrated while no other cluster contains a sufficiently large tightly concentrated subset.Lemma B.9 supplies both high-probability properties.
Shrinkage: Because β1 is separated from the other shrinkage parameters, C1 shrinks strictly faster than every other cluster.The proof compares contraction factors r1 and r2 and obtains 0 < r1 < r2 < 1.
Partial visualization: Combining the concentration of C1 with separation from most points outside C1 proves that C1 is visualized by itself.The final step applies Lemma B.9 to the definition of partial visualization.

B.2 Proof of Theorem 4.1

The proof verifies Theorem B.4's conditions for two balanced clusters, using Gaussian distance concentration to establish regularity and then checking the shrinkage-parameter inequality.

The proof applies Theorem B.4 with n > 4d, so the required sample-size condition holds with ω = 1, and |C1| = |C2| = n/2 gives balanced clusters.
The variance relation R^2_1,2 = R^2_2,1 = σ^2_1 + σ^2_2 and 1.5 ≤ σ2/σ1 ≤ 10 imply R1,1 < R1,2 < R2,2 ≤ 10R1,1.
X is O(d^-η)-regular with high probability for any constant η < 1/2.
Distance concentration for Gaussians yields within- and between-cluster squared-distance ratios accurate up to a multiplicative 1 ± O(d^-η) factor.The displayed relations cover pairs within C1, cross-cluster pairs, and pairs within C2.
Because β1 + β2 = 2, proving β1 ≥ 1.1β2 reduces to showing β1 ≥ 1.05 after computing β1 and β2.The proof defines β1 and β2 from the cluster-specific c-parameters before making this reduction.