Clustering with t-SNE, provably

George C. Linderman; Stefan Steinerberger

Source-linked AI summary

Clustering with t-SNE, provably

George C. Linderman, Stefan Steinerberger

arXiv:1706.02582v1Jun 8, 2017cs.LGstat.ML

TL;DR

The paper tackles the lack of mathematical understanding of t-SNE despite its widespread use. It rigorously analyzes the early exaggeration phase and derives parameter regimes under which clustered data converge exponentially, while relating the dynamics to spectral clustering. The results support interpreting separated embedded clusters as evidence about input clusters, but leave the behavior of classical parameter choices unresolved.

Problem
Despite t-SNE's widespread use for cluster visualization, its theoretical foundations and inner workings remain unclear.
Method
The paper rigorously analyzes early exaggeration using discrete dynamical systems and studies the exaggeration parameter α and step size h.
Results
Canonical parameters α ∼ n/10 and h ∼ 1 produce exponential convergence of embedded clusters to small balls, and the analyzed regime behaves like spectral clustering.
Takeaways & Limitations
For well-clustered data, suitably chosen parameters can justify using separated t-SNE clusters to infer structure in the original data.
Takeaways & Limitations
Whether classical early-exaggeration parameters α ∼ 12 and h ∼ 200 are qualitatively equivalent to the proposed choice remains an open problem.

Abstract

from arXiv · show

t-distributed Stochastic Neighborhood Embedding (t-SNE), a clustering and visualization method proposed by van der Maaten & Hinton in 2008, has rapidly become a standard tool in a number of natural sciences. Despite its overwhelming success, there is a distinct lack of mathematical foundations and the inner workings of the algorithm are not well understood. The purpose of this paper is to prove that t-SNE is able to recover well-separated clusters; more precisely, we prove that t-SNE in the `early exaggeration' phase, an optimization technique proposed by van der Maaten & Hinton (2008) and van der Maaten (2014), can be rigorously analyzed. As a byproduct, the proof suggests novel ways for setting the exaggeration parameter $α$ and step size $h$. Numerical examples illustrate the effectiveness of these rules: in particular, the quality of embedding of topological structures (e.g. the swiss roll) improves. We also discuss a connection to spectral clustering methods.

1. Introduction and main result

This paper addresses the unclear theory behind t-SNE by analyzing its early exaggeration phase and deriving parameter choices that provably produce rapid cluster convergence. It also connects this regime to spectral clustering and discusses implications for interpreting embeddings.

Motivation: t-SNE is widely used for dimensionality reduction and cluster visualization, but its theoretical foundations and inner workings remain unclear.It is especially common in unsupervised analysis, including single-cell RNA sequencing.
Early exaggeration: Early exaggeration accelerates optimization by multiplying the high-dimensional affinities p_ij during the initial iterations.The standard implementation uses an exaggeration factor and large step size, while the paper analyzes α and h directly.
Main result: The paper proves that canonical parameters α ∼ n/10 and h ∼ 1 yield exponential convergence of clustered data without momentum.Embedded clusters converge to small balls whose diameter depends on the quality of clustering in the input.
Spectral connection: In the analyzed regime, t-SNE behaves like an explicitly representable spectral clustering method, enabling alternative analysis and faster early-exaggeration implementations.The paper leaves open whether classical parameters α ∼ 12 and h ∼ 200 behave qualitatively equivalently.
Cluster recovery: With well-clustered input and suitable parameters, the number of disjoint embedded clusters provides a lower bound on the number of input clusters, and generically the numbers coincide.Increasing α while decreasing h can make embedded clusters smaller when αh ∼ n/10.

2. Numerical examples

The numerical examples show that classical random initialization can produce topological interlocking, while proposed parameter choices recover simpler structure and perform most clustering during early exaggeration.

2.1. Lines and Swiss roll.: Classical t-SNE fails to successfully embed the swiss roll, and random initialization can also cause difficulty on a simple line in R3.Figure 2 illustrates the classical embeddings of both structures.
2.1. Lines and Swiss roll.: Random initialization creates topological interlocking after initial contraction, producing knots in the swiss roll that t-SNE cannot later untie.The interlocking remains unresolved during subsequent optimization.
2.1. Lines and Swiss roll.: The proposed parameter selection recovers the line from random initial data and contracts the swiss roll to a correctly ordered line.The swiss roll would then expand during the algorithm’s second phase.
2.1. Lines and Swiss roll.: The line and swiss roll examples use early-exaggeration settings α = 20n, h = 0.05 and α = n, h = 1, respectively.These settings correspond to Figures 3 and 4.
2.1. Lines and Swiss roll.: With optimal α and h, the successful embeddings are consistent with early exaggeration acting like a spectral method.The paper connects this behavior to spectral methods that also correctly embed many such manifolds.
2.2. Real-life data.: On 10000 MNIST digits, early exaggeration with α ∼ n/10, h ∼ 1 performs essentially all clustering, while the second phase rearranges the result.Figure 5 compares classical t-SNE, the post-early-exaggeration embedding, and the final output.

3. t-SNE: Notation and the Main result

The paper formulates t-SNE through high- and low-dimensional affinities and analyzes gradient descent under explicit assumptions on clustered affinities and parameter choices. Its main result is stated for general mutual affinities rather than only standard t-SNE normalizations.

3.1. t-SNE.: t-SNE maps a d-dimensional dataset X to an s-dimensional embedding Y, with s much smaller than d and commonly equal to 2 or 3.The input points are x_i and the embedded points are y_i.
3.1. t-SNE.: The method computes joint input affinities p_ij and minimizes the Kullback-Leibler divergence between input and embedding distributions.The embedding distribution uses low-dimensional similarities between embedded points.
3.1. t-SNE.: The analysis treats p_ij as given and assumes they correspond to a well-clustered dataset, without requiring Gaussian-kernel construction or standard t-SNE normalizations.This provides a general affinity-level formulation.
3.1. t-SNE.: The points are randomly initialized, and the cost is minimized using gradient descent whose gradient separates attractive and repulsive forces.Early exaggeration multiplies the attractive-affinity contribution by α > 1.
3.1. t-SNE.: The main result assumes clustered affinities, including within-cluster lower bounds on p_ij, together with conditions on α and h.The clustered-data definition uses a cluster assignment map π and cluster sizes.

2. Parameter choice.

The analysis identifies parameter conditions that guarantee convergence and motivates practical choices for the exaggeration factor α and step size h. The admissible regime includes α ∼ n/10, h ∼ 1, while other scalings can also work.

Clusters satisfying the stated inequality are covered by the main convergence result.
The upper bound is necessary for early exaggeration to work, while α ∼ n/10 and h ∼ 1 is admissible.The analysis also permits choices such as α ∼ 10n, h ∼ 1/100.
For roughly n ≲ 24000 points, standard parameters α ∼ 12 and h ∼ 200 satisfy the derived bounds.For larger datasets, the lower bound is violated and convergence slows as the exponential factor κ approaches 1.
The proof suggests choosing parameters to optimize the convergence rate for an individual cluster or ensure convergence across all clusters.
The initialization lies in [−0.01, 0.01]^2, and smaller initial scales may improve constants.

3. Localized initialization.

The theorem gives localized convergence: an embedded cluster contracts exponentially until reaching a radius controlled by the clustering quality. This guarantee can apply to one cluster even when others fail to contract.

The diameter of the embedded cluster decays exponentially at a universal rate until it reaches a data-dependent bound.
The theorem can apply to a single cluster, so some clusters may contract while others do not.
The bound is nontrivial only under an additional separation condition involving the within-cluster affinity sum.
For well-clustered data, the relevant affinity sum is expected to be close to zero, yielding a leading error term of ch/n.
The constant c is estimated at roughly 10 for well-clustered data and increases for worse clustering properties.For classical parameters, it may slowly increase with n; the authors regard this estimate as conservative.

4. A Connection to Spectral Clustering

In the limit α → ∞ and h → 0 with αh fixed, t-SNE reduces to a spectral-clustering-like Markov process. The paper uses this connection to analyze convergence and visualize spectral iterations in R2, while leaving equivalence with classical parameters open.

4.1. Approximating spectral clustering: With α → ∞ and h → 0 while αh remains constant, the limiting method becomes a simple spectral clustering method.
4.1. Approximating spectral clustering: Absorbing the αh scaling into the affinities and taking h → 0 removes the repulsion term from the limiting dynamics.
4.1. Approximating spectral clustering: The limiting dynamics can be interpreted as a Markov chain, whose convergence depends on eigenvalues near 1 and the spectral gap.
4.2. Visualizing spectral clustering: Applying matrix powers to random initial vectors produces t-SNE-style R2 visualizations of spectral-method iterations.
4.1. Approximating spectral clustering: For perfectly separated clusters, exactly k eigenvalues equal 1, and the initialization converges according to this spectral structure.
4.2. Visualizing spectral clustering: On 40000 highly clustered points, t-SNE took roughly 7 minutes versus 1 minute for spectral decomposition, after which iterations are constant-time.
4.2. Visualizing spectral clustering: Whether classical parameters α ∼ 12, h ∼ 200 behave qualitatively like the analyzed spectral regime remains an open problem.

5. Ingredients for the Proof: Discretized Dynamical Systems

The paper studies a discrete dynamical system on points in R^s, establishing stability and contraction properties that support the t-SNE analysis. Under coefficient and error assumptions, point sets remain controlled and their diameter contracts toward an error-dependent scale.

Dynamical-system framework: The dynamical system uses points in R^s and analyzes their asymptotic behavior through a self-contained argument potentially interpretable as robust spectral-method analysis.The proof was guided by the maximum principle for parabolic partial differential equations.
Assumptions: The analysis assumes uniform lower and upper bounds on interaction coefficients and a uniform upper bound on the error term.These are stated as three conditions governing the coefficients and perturbations over time.
Stability: The convex hull remains stable up to an additive ball of radius ε after each iteration.Specifically, the next convex hull is contained in the current convex hull plus B(0, ε).
Contraction: The diameter shrinks exponentially at rate (1 − nδ/20)^t until reaching size ∼ε/(nδ).The scale ∼ε/(nδ) is optimal even for two points in R.
Contraction proof: The contraction proof projects the points onto arbitrary lines, proves exponential contraction of each one-dimensional projection, and then transfers the result to the original diameter.The argument partitions a projection interval into regions and uses the resulting point counts to obtain contraction, while accounting for ε.
Scope of estimates: The estimates can be improved by refining the error-norm treatment or weakening the δ condition, but such changes alter the constants and decay bounds.The paper notes that reducing the constant in the cluster estimate inevitably decreases the provable exponential decay rate.

6. Proof of the Main Result

The main proof rewrites early-exaggeration t-SNE on a small embedded cluster as a discrete dynamical system with an error term. It controls inter-cluster interactions, verifies the dynamical-system assumptions, and checks that contraction occurs within the regime where the initialization remains localized.

Proof setup: The proof initializes all embedded points in [−0.01, 0.01]^2 and represents gradient descent on one cluster as a dynamical system with an error term.The error term includes q_ij, which depend on distances between points from different clusters.
Error control: The proof bounds the error norm using the triangle inequality and analyzes its constituent terms separately.The q_ij-dependent inter-cluster contributions are the main source of difficulty when points are far apart.
Cluster dynamics: The analysis restricts attention to a small embedded cluster and separates the gradient update into a main contribution plus two error terms.This decomposition enables application of the previously established dynamical-system estimates.
Assumption verification: The coefficient conditions are verified from the gradient update, with the lower-bound condition admissible whenever αh ∼ n.The proof separately checks the required upper bound on the coefficients.
Time-scale consistency: At least ℓ ≥ 0.01/ε iterations remain within the small-region assumption, while contraction reduces the cluster during that interval.The time-scale comparison verifies that the dynamical-system estimate applies before the embedding leaves the localized region.
Proof flexibility: The proof leaves room for improved constants through smaller initialization regions, finer tuning, and less crude error estimates.The authors explicitly avoid optimizing constants to keep the argument simpler.