Clustering with t-SNE, provably.

Area of Science:

• Computational statistics
• Machine learning
• Data visualization

Background:

• t-distributed Stochastic Neighborhood Embedding (t-SNE) is a widely adopted clustering and visualization technique in natural sciences.
• Despite its prevalence, t-SNE lacks rigorous mathematical foundations, and its internal mechanisms remain poorly understood.
• Existing research highlights the need for a deeper theoretical understanding of t-SNE's behavior and optimization.

Purpose of the Study:

• To provide a mathematical proof demonstrating t-SNE's capability to recover well-separated clusters.
• To rigorously analyze the 'early exaggeration' phase of t-SNE, a key optimization technique.
• To derive novel insights for setting the exaggeration parameter (α) and step size (h).

Main Methods:

• Mathematical proof of t-SNE's cluster recovery capabilities.
• Analysis of the 'early exaggeration' phase using theoretical frameworks.
• Numerical experiments to validate proposed parameter tuning rules.

Main Results:

• The study rigorously proves that t-SNE can effectively recover well-separated clusters.
• The analysis of the 'early exaggeration' phase provides a theoretical basis for its optimization.
• Novel rules for setting the exaggeration parameter (α) and step size (h) are proposed and validated.

Conclusions:

• The mathematical framework confirms t-SNE's effectiveness in preserving cluster structures.
• The proposed parameter tuning strategies enhance the quality of embeddings, especially for topological structures like the swiss roll.
• A connection between t-SNE and spectral clustering methods is explored, suggesting potential for hybrid approaches.