t-SNE and UMAP

A neighbor-embedding method takes points $x_1, \dots, x_n \in \mathbb{R}^D$ and produces points $y_1, \dots, y_n \in \mathbb{R}^d$ with $d \ll D$ (typically $d=2$), such that points that are close neighbors in the original space remain close in the embedding, and points that are far apart tend to stay far apart locally. This is fundamentally different from Manifold Learning and Nonlinear Dimensionality Reduction methods like Isomap or classical MDS, which try to preserve exact geodesic or Euclidean distances globally. Neighbor embedding instead preserves a probability distribution over neighbor relationships — a softer, more local, and more robust notion of structure that tolerates the fact that distances in high dimensions are often noisy or meaningless beyond the nearest few neighbors. The key technical device in both methods is a two-stage similarity comparison. First, define a similarity measure $p_{ij}$ between every pair of points in the original high-dimensional space, typically derived from a kernel over distances (Gaussian for t-SNE, a smooth approximation to a k-NN graph for UMAP). Second, define an analogous similarity measure $q_{ij}$ between the corresponding low-dimensional embedding points $y_i, y_j$, using a different, heavier-tailed kernel. Third, optimize the low-dimensional coordinates $y_i$ to make $q_{ij}$ match $p_{ij}$ as closely as possible, measured by a divergence (KL divergence for t-SNE, fuzzy-set cross-entropy for UMAP). This is an instance of the broader The Unsupervised Learning Problem: there is no label to fit, only internal consistency between two representations of the same data. The reason the low-dimensional kernel must have heavier tails than the high-dimensional one is called the crowding problem. In high dimensions, a point can have many equidistant moderate-distance neighbors (the volume of a shell at radius $r$ grows like $r^{D-1}$), but in 2D there simply is not enough "room" to place all of them at moderate distance while also giving close neighbors very small distances — everything gets squashed toward the center. Using a heavy-tailed distribution (Student-t with one degree of freedom, i.e., a Cauchy distribution, in t-SNE) means that moderate $q_{ij}$ values correspond to much larger actual distances than under a Gaussian, giving points room to spread out in the 2D map without distorting the representation of true close neighbors.

t-SNE: probabilistic similarities and KL minimization

Step 1 — high-dimensional similarities. For each point $x_i$, define a conditional probability that $x_j$ would be picked as a neighbor of $x_i$ under a Gaussian centered at $x_i$:

The bandwidth $\sigma_i$ is chosen per point, via binary search, so that the perplexity of the distribution $P_i$ equals a user-chosen constant (typically 5–50):

Perplexity is interpreted as "the effective number of neighbors" — larger perplexity means a wider Gaussian and more points considered locally similar. Symmetrize to get a joint distribution:

Symmetrizing this way (rather than just averaging the two conditionals without dividing by $n$) guarantees $\sum_j p_{ij} > (1/2n)$ for every point, so no point contributes a vanishing gradient, which stabilizes optimization for outliers.

Step 2 — low-dimensional similarities. In the embedding space, define joint probabilities using a Student-t distribution with one degree of freedom (equivalent to a Cauchy distribution), which has much heavier tails than a Gaussian:

Step 3 — objective and gradient. Minimize the KL divergence from $Q$ to $P$:

This is asymmetric: large $p_{ij}$ with small $q_{ij}$ is penalized heavily (true neighbors must stay together), while small $p_{ij}$ with larger $q_{ij}$ is penalized only mildly (non-neighbors can end up at any large distance without much cost). This asymmetry is why t-SNE plots show tight, well-separated clusters — the loss actively prioritizes local fidelity over global fidelity. The gradient with respect to a single embedded point works out to a clean physically-interpretable form (attraction and repulsion between all pairs):

This is optimized with gradient descent plus momentum, and an "early exaggeration" trick: multiply all $p_{ij}$ by a constant (e.g. 4–12) for the first few hundred iterations, which forces natural clusters to form tight, well-separated blobs early, from which the optimization refines fine structure afterward. ``` function T_SNE(X, d, perplexity, T, eta, alpha): n = number of rows in X

# --- Step 1: high-dimensional affinities --- for i in 1..n: sigma_i = binary_search_bandwidth(X, i, perplexity) for j in 1..n: p_cond[i][j] = gaussian_affinity(X[i], X[j], sigma_i) for i,j in 1..n: P[i][j] = (p_cond[i][j] + p_cond[j][i]) / (2*n) P[i][j] = max(P[i][j], 1e-12) # avoid log(0)

# --- Step 2: initialize embedding --- Y = random_normal(n, d, scale=1e-4) velocity = zeros(n, d)

# --- Step 3: gradient descent with early exaggeration --- for t in 1..T: P_used = (t <= 250) ? P 12.0 : P # early exaggeration Q, dist_inv = student_t_affinities(Y) # dist_inv[i][j] = (1+||y_i-y_j||^2)^-1 grad = zeros(n, d) for i in 1..n: for j in 1..n where j != i: coeff = 4 (P_used[i][j] - Q[i][j]) dist_inv[i][j] grad[i] += coeff (Y[i] - Y[j]) momentum = (t < 250) ? 0.5 : 0.8 velocity = momentum velocity - eta grad Y = Y + velocity return Y ```

UMAP: fuzzy simplicial sets and cross-entropy

UMAP replaces the Gaussian-kernel-and-KL-divergence machinery with a construction grounded in algebraic topology, but the resulting computational recipe is structurally parallel.

Step 1 — local fuzzy simplicial sets. For each point $x_i$, find its $k$ nearest neighbors (a hyperparameter analogous to perplexity, called `n_neighbors`). Define, for each neighbor $x_j$ of $x_i$:

where $\sigma_i$ is again calibrated (via binary search) so that $\sum_j w_{j|i} = \log_2(k)$. Subtracting $\rho_i$ ensures every point is connected to its nearest neighbor with weight exactly 1, which is what makes UMAP treat the manifold as locally uniform — a core modeling assumption (data is assumed locally uniformly distributed after adjusting for local density via $\rho_i$). Symmetrize using the fuzzy set union (probabilistic OR), not a simple average:

This produces a weighted graph on the data — the fuzzy topological representation of the high-dimensional manifold.

Step 2 — low-dimensional layout. In the embedding, define similarity with a smooth, heavy-tailed curve fit to approximate:

where $a, b>0$ are found by curve-fitting to a reference bump function (defaults chosen so this closely tracks $\exp(-\|y_i-y_j\|^2)$ near the origin, with a heavy tail beyond a target `min_dist`).

Step 3 — objective and optimization. UMAP minimizes a fuzzy-set cross entropy:

Unlike t-SNE's normalized joint distribution (which requires an $O(n^2)$ normalizing constant recomputed every iteration), each term here depends only on the pair $(i,j)$ — no global normalization is needed. This is what allows an efficient stochastic gradient descent with negative sampling: for each edge $(i,j)$ in the (sparse) k-NN graph, take an attractive gradient step, and pair it with a small number of repulsive steps against randomly sampled non-neighbors, rather than summing over all $n^2$ pairs every iteration. ``` function UMAP(X, d, n_neighbors, min_dist, T, n_negative): n = number of rows in X

# --- Step 1: fuzzy simplicial set (sparse k-NN graph) --- knn_idx, knn_dist = approximate_k_nearest_neighbors(X, n_neighbors) # e.g. via NN-descent for i in 1..n: rho_i = knn_dist[i][0] sigma_i = binary_search_bandwidth(knn_dist[i], n_neighbors, rho_i) for each (j, dist) in (knn_idx[i], knn_dist[i]): w_cond[i][j] = exp(-max(0, dist - rho_i) / sigma_i) W = sparse_matrix(n, n) for each stored edge (i,j): wij = w_cond[i][j] + w_cond[j][i] - w_cond[i][j] * w_cond[j][i] W[i][j] = W[j][i] = wij # fuzzy union, symmetric sparse graph a, b = fit_ab_curve(min_dist) # curve fit to target low-dim kernel shape

# --- Step 2: initialize embedding (e.g. spectral layout of graph W) --- Y = spectral_layout(W, d)

# --- Step 3: SGD with negative sampling over epochs --- edges = nonzero_entries(W) # list of (i, j, w_ij) for epoch in 1..T: shuffle(edges) for (i, j, w_ij) in edges: if random() > w_ij: continue # sample edges proportional to weight dist2 = squared_distance(Y[i], Y[j]) attract = (-2ab*dist2^(b-1)) / (1 + adist2^b) Y[i] += eta attract (Y[i]-Y[j]) Y[j] -= eta attract (Y[i]-Y[j]) for neg in 1..n_negative: k = random_point_index(n) if k == i: continue dist2_neg = squared_distance(Y[i], Y[k]) repel = 2b / ((0.001 + dist2_neg) (1 + adist2_neg^b)) Y[i] += eta repel (Y[i]-Y[k]) eta = eta * (1 - epoch/T) # linearly decay learning rate return Y ```

t-SNE complexity. Computing all pairwise affinities $p_{ij}$ and doing the binary search for $\sigma_i$ per point costs $O(n^2 D)$ for the naive dense version (distance computations dominate). Each gradient-descent iteration recomputes all $q_{ij}$ and the gradient sum, which is $O(n^2)$ per iteration, giving $O(Tn^2)$ total for $T$ iterations — quadratic in $n$, which becomes prohibitive beyond tens of thousands of points. The standard acceleration, Barnes-Hut t-SNE, exploits that only near neighbors need exact $p_{ij}$ (others are truncated to zero after building an approximate k-NN via a vantage-point tree, $O(n\log n)$), and approximates the repulsive force sum using a quadtree/octree, treating clusters of distant points as a single aggregate — analogous to the Barnes-Hut algorithm for n-body simulation. This reduces the per-iteration cost to $O(n\log n)$, giving overall $O(Tn\log n)$. FFT-accelerated variants (interpolation-based t-SNE) push this toward near-linear time in practice.

UMAP complexity. Nearest-neighbor search uses approximate methods (NN-descent or randomized projection trees), costing roughly $O(n^{1.14})$ to $O(n\log n)$ empirically depending on implementation and data distribution. The fuzzy-set construction is $O(nk)$ for $k$ = `n_neighbors`. The optimization phase is genuinely sparse: each epoch touches only the $O(nk)$ edges in the k-NN graph (plus a constant number of negative samples per edge), giving $O(nk)$ per epoch and $O(Tnk)$ total — no dense $n^2$ term ever appears, because the cross-entropy objective is a sum over actual graph edges plus a sampled estimate of the repulsive term, not an exact normalized joint distribution. This asymptotic advantage — avoiding the global normalizing constant that t-SNE's $Q$ requires — is the single biggest reason UMAP scales to millions of points where classical t-SNE cannot.

Space complexity. Dense t-SNE needs $O(n^2)$ memory for the affinity matrices; Barnes-Hut t-SNE needs only $O(n)$ for point storage plus $O(n)$ for the sparse truncated $P$ matrix and $O(n)$ for the tree. UMAP needs $O(nk)$ for its sparse graph — smaller when $k \ll n$, which is the typical regime.

Correctness reasoning. Neither algorithm has a "correctness proof" in the sense of an exact-answer algorithm; both are non-convex optimizations solving a well-posed but heuristic objective. The relevant correctness argument is does the objective actually encode "preserve local neighborhoods", and the derivation above shows it does by construction: $p_{ij}$ (or $w_{ij}$) is large exactly when $x_i, x_j$ are close in the original space, and the gradient of KL divergence (or cross-entropy) drives $q_{ij}$ (or $\psi_{ij}$) toward matching values, with an asymmetric penalty structure that strongly punishes separating true neighbors while only weakly punishing spurious closeness among non-neighbors being avoided. A useful invariant to note: in t-SNE, $\sum_{ij} p_{ij} = 1$ is fixed and does not change during optimization — only $Q$ changes — so the algorithm is literally projecting a fixed target distribution onto the family of distributions reachable by placing $n$ points in $\mathbb{R}^d$ under the Student-t kernel; convergence (to a local optimum) follows from standard gradient descent guarantees on a smooth, bounded-below objective, though global optimality is not guaranteed and initialization/random seed materially affects the resulting layout.

Tradeoffs to be honest about. Both methods discard global structure by design: inter-cluster distances and relative cluster sizes in the output are not reliable measures of true separation or density, since the objectives never directly penalize getting global geometry wrong — they only penalize local neighborhood mismatch (this is elaborated in the pitfalls section). t-SNE has no natural out-of-sample extension (a new point requires re-running or an approximate insertion heuristic); UMAP's optimization is more directly compatible with a `transform` step for new points because the fuzzy-set/embedding relationship can be reused, though this remains an approximation. UMAP's theoretical grounding in fuzzy simplicial sets provides an elegant motivation but does not, by itself, prove the final layout is a faithful topological invariant of the data — in practice both methods are best understood as sophisticated, well-motivated heuristics validated empirically rather than by hard guarantees.

Consider six 3-dimensional points forming two obvious clusters, embedded with noise:

t-SNE trace (conceptual, perplexity ≈ 3). Computing pairwise Euclidean distances shows within-cluster distances $\approx 0.2$–$0.3$ and between-cluster distances $\approx 8.6$. Binary search finds a small $\sigma_i$ for each point (since neighbors are close and dense), producing conditional distributions concentrated almost entirely on the two same-cluster neighbors, e.g., $p_{B|A} \approx 0.49,\ p_{C|A}\approx 0.49,\ p_{D|A}\approx p_{E|A}\approx p_{F|A}\approx 0.007$ each. Symmetrizing gives $p_{AB}, p_{AC} \gg p_{AD}, p_{AE}, p_{AF}$. In the embedding, random initialization places all six points near the origin; early exaggeration (multiplying $p_{ij}$ by 12) causes the attractive term between A–B–C to dominate hugely over the tiny cross-cluster $p$ values, so A, B, C rapidly pull together while D, E, F do the same, and the repulsive Student-t term (which grows relatively larger for spatially close but dissimilar points) pushes the two nascent clusters apart. After exaggeration ends, the layout fine-tunes: within-cluster $q_{ij}$ increases (points tighten) while between-cluster $q_{ij}$ stays small, producing two visually separated blobs whose relative distance in the final plot is not guaranteed to reflect the true ratio 8.6 / 0.25 — it might show any large separation, since only the ordinal fact "far apart" is preserved, not the magnitude.

UMAP trace (n_neighbors = 2). For point A, nearest neighbors are B and C, at distances $\approx 0.22, 0.22$; $\rho_A = 0.22$ (distance to nearest neighbor). Binary search sets $\sigma_A$ so $\sum w_{j|A} = \log_2(2) = 1$; since both neighbors are at distance $\approx \rho_A$, weights are near 1 and near 0 for others, giving $w_{B|A}\approx 1, w_{C|A}\approx$ (something smaller depending on exact distances), and negligible weight to D, E, F. The fuzzy union symmetrization yields a sparse graph with strong edges A–B, A–C, B–C and D–E, D–F, E–F, and essentially zero-weight (absent) edges between clusters. During SGD, only these six intra-cluster edges (plus symmetric duplicates) generate attractive forces every epoch; every point also receives a handful of repulsive forces from randomly sampled negative examples, which for a cross-cluster pair like A and D will almost always push them apart (since they are not connected by any positive edge, the objective wants $\psi_{AD}\to 0$). Because UMAP's k-NN graph here is exactly two disconnected triangles, this small example only weakly illustrates UMAP's genuine advantage — its power emerges at scale, where the sparse graph structure lets optimization skip the vast majority of the $\binom{n}{2}$ pairs entirely, unlike dense t-SNE.

Contrast. In dense t-SNE, all $\binom{6}{2}=15$ pairs contribute to every gradient computation regardless of relevance; in UMAP, only the handful of true k-NN edges plus a small constant number of negative samples per point contribute per epoch. At $n=6$ this difference is invisible in wall-clock time, but the pattern (dense $O(n^2)$ vs. sparse $O(nk)$) is exactly what makes UMAP practical on datasets with $n$ in the millions, such as single-cell RNA-seq atlases.

Both algorithms are entrenched in exploratory data analysis across fields. In single-cell genomics, UMAP and t-SNE are the standard way to visualize cell-type clusters from gene-expression data with tens of thousands of genes reduced to a 2D atlas — tools like Scanpy and Seurat build UMAP in by default. In NLP and representation learning, practitioners visualize word or sentence embeddings (e.g., BERT hidden states) to sanity-check whether semantically similar tokens cluster together. In computer vision, feature embeddings from convolutional or transformer backbones are projected to inspect class separability before deciding whether a classifier is likely to succeed. Anomaly detection dashboards use these embeddings to visually flag points that sit apart from all learned clusters. Because both build on the same "neighbor graph + optimization" recipe, they connect naturally to ideas in Manifold Learning and Nonlinear Dimensionality Reduction such as Isomap and Laplacian Eigenmaps, and they remain a canonical unsupervised technique taught alongside clustering and PCA in the broader study of The Unsupervised Learning Problem.

Ask the tutor: How does changing the perplexity or n_neighbors hyperparameter change which "resolution" of manifold structure the embedding reveals?