An Analysis of the t-SNE Algorithm for Data Visualization

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.Source: §1 · p. 1

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.Source: §1 · p. 2

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.Source: §1 · pp. 2–3

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.Source: §1.1 · p. 4

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.Source: §1.1 · p. 5

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.Source: §1.1 · p. 5

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.Source: §2 · p. 6

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.Source: §2 · p. 6

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.Source: §2 · p. 6

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.Source: §2 · p. 6
• 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.Source: §2 · p. 7

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.Source: §3 · p. 7

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.Source: §3 · p. 8

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.Source: §3 · p. 8, §3.1 · p. 9

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.Source: §3.2 · p. 12

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.Source: §3.3 · p. 13

Motivation

• The section investigates partial visualization when the separation condition for full visualization fails drastically.Partial visualization means correctly visualizing at least one cluster.Source: §4 · p. 14

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.Source: §4 · p. 14

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.Source: §4 · p. 14

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.Source: §4 · p. 14

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.Source: §4 · p. 14

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.Source: §5 · p. 14

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.Source: §5 · p. 14

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.Source: §A.1 · p. 18

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.Source: §A.1 · p. 18

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.Source: §A.1 · p. 19
• 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.Source: §A.1 · p. 19

Conclusion

• After these checks, the proof concludes Lemma 3.4.The conclusion follows from verifying the required conditions.Source: §A.1 · p. 19

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.Source: §A.2 · pp. 19–20

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.Source: §A.2 · pp. 19–20

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.Source: §A.2 · p. 20
• 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.Source: §A.2 · p. 20

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.Source: §A.2 · p. 22

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 − µ∥.Source: §A.3 · p. 22
• 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.Source: §A.3 · p. 23

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.Source: §A.3 · p. 23

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.Source: §A.3 · p. 23

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.Source: §A.4 · pp. 23–24
• 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ℓ.Source: §A.4 · p. 24
• 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.Source: §A.4 · p. 24

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.Source: §A.4 · p. 24

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.Source: B Proofs for Section 4 · pp. 24–25
• γ-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.Source: B Proofs for Section 4 · p. 24

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.Source: B Proofs for Section 4 · p. 25
• 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.Source: B Proofs for Section 4 · p. 25
• 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.Source: B Proofs for Section 4 · p. 25

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.Source: §B.1 · pp. 25–26

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 βℓ.Source: §B.1 · p. 27

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.Source: §B.1 · pp. 29–30

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.Source: §B.1 · p. 29

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.Source: §B.1 · pp. 30–31

• 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.Source: §B.2 · p. 31
• 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.Source: §B.2 · p. 31
• X is O(d^-η)-regular with high probability for any constant η < 1/2.Source: §B.2 · p. 31
• 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.Source: §B.2 · pp. 31–32
• 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.Source: §B.2 · pp. 31–32