Equilibrium Distribution for t-Distributed Stochastic Neighbor Embedding with Generalized Kernels
Yi Gu · 2025
Read Equilibrium Distribution for t-Distributed Stochastic Neighbor Embedding with Generalized Kernels by Yi Gu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-24311.txt.
Introduction
Yi Gu and Antonio Auffinger study the equilibrium distribution for t-distributed stochastic neighbor embedding with generalized kernels, in a mathematics paper from 2025. The method, known as t-SNE, maps high-dimensional data into a low-dimensional picture that keeps neighbor structure. Its large-sample behavior was known for one kernel pair, but not for the broader family used in practice.
The authors extend the limit results to wide classes of input and output kernels. Under natural conditions, and when the perplexity setting grows in line with data size, the point clouds and their minimizers settle to an equilibrium distribution. Numerical cases compare kernels. The theory grounds choices that users make by habit.
Catalog record
| CREATOR | Yi Gu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-24311
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Equilibrium Distribution for t-Distributed Stochastic Neighbor Embedding with Generalized Kernels Yi Gu Abstract T-distributed stochastic neighbor embedding (t-SNE) is a well-known algorithm for visualizing high-dimensional data by finding low-dimensional representations ( van der Maaten and Hinton 2008 ). In this paper, we study the convergence of t-SNE with generalized kernels and extend the results of Auffinger and Fletcher 2023 . Our work starts by giving a concrete formulation of generalized input and output kernels. Then we prove that under certain conditions, the t-SNE algorithm converges to an equilibrium distribution for a wide range of input and output kernels as the number of data points diverges. 1 The Concept of Input and Output Kernels t-distributed stochastic neighbor embedding (t-SNE) is a powerful technique for visualizing high-dimensional data in a low-dimensional space, developed in 2008 by Laurens van der Maaten and Geoffrey Hinton ( van der Maaten and Hinton 2008 ). Despite its wide application (in biology for example Linderman et al. 2019 , Wallach and Lilien 2009 ), the theoretical aspects and mathematical rigor of t-SNE have rarely been discussed thoroughly. Recently, Auffinger and Fletcher proved that if data is sampled independently from a compact probability measure \mu_{X} , then the output of t-SNE converges to an equilibrium measure that is also compact as the number of data points diverges( Auffinger and Fletcher 2023 ). This, together with Arora et al. 2018 and Linderman and Steinerberger 2017 , are some of the very first results that rigorously establishes the theoretical guarantees of t-SNE. We aim to generalize the results from Auffinger and Fletcher 2023 . In the original version of the t-SNE algorithm, for each pair of input or output data points, a weight is assigned based on the distance between them. This weight is used to construct probability distributions that will be used in the loss function. A natural question to ask is: can we generalize the result for different weights such that the convergence still holds and the equilibrium measure still exists? A generalized formulation allows us to further reveal the theoretical nature of this algorithm, greatly enhancing our understanding of t-SNE and dimension reduction. Our work starts by generalizing the algorithm with the concept of input and output kernels. Let d,s\geq 2 with d>s , and n\geq 1 . Let X_{1},\cdots,X_{n}\in\mathbb{R}^{d} be the input data points and Y_{1},\cdots Y_{n}\in\mathbb{R}^{s} the output data points. We define the input and output kernels as follows: Definition 1 (Generalized Input Kernel) . The input kernel \mathbf{Ker}_{\mathbf{I}}(x,y,\sigma):\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}^{+} is a function of the input data points and parameter \sigma such that for any x,y\in\mathbb{R}^{d} and \sigma>0 , \displaystyle\mathbf{Ker}_{\mathbf{I}}(x,y,\sigma)=\mathbf{Ker}_{\mathbf{I}}(y,x,\sigma). (1.1) Definition 2 (Generalized Output Kernel) . The output kernel \mathbf{Ker}_{\mathbf{O}}(z,w):\mathbb{R}^{s}\times\mathbb{R}^{s}\to\mathbb{R}^{+} is a function of the output data points such that for any z,w\in\mathbb{R}^{s} , \displaystyle\mathbf{Ker}_{\mathbf{O}}(z,w)=\mathbf{Ker}_{\mathbf{O}}(w,z). (1.2) Clearly, by letting \displaystyle\mathbf{Ker}_{\mathbf{I}}(x,y,\sigma)=\exp\left(-\frac{||x-y||^{2}}{2\sigma^{2}}\right),\quad\mathbf{Ker}_{\mathbf{O}}(z,w)=\frac{1}{1+||z-w||^{2}}, (1.3) we recover the original t-SNE algorithm by using both \mathbf{Ker}_{\mathbf{I}} and \mathbf{Ker}_{\mathbf{O}} as the weights for the input and output data points. We can also say that the original t-SNE algorithm has a Gaussian input kernel and a t-distributed output kernel. From now on, we will use the terminology generalized t-SNE when we use the generalized formulation for input and output kernels to distinguish it from the original algorithm. Clearly, not all choices of \mathbf{Ker}_{\mathbf{I}} and \mathbf{Ker}_{\mathbf{O}} will yield a valid generalized t-SNE algorithm, such as \mathbf{Ker}_{\mathbf{I}} that diverges as ||x-y||\to\infty . To prove similar results as in Auffinger and Fletcher 2023 , we need to impose some conditions on both \mathbf{Ker}_{\mathbf{I}} and \mathbf{Ker}_{\mathbf{O}} . The conditions should provide just enough constraints for the convergence to hold, while applying to a wide range of function choices. Towards this end, we use the following conditions for the rest of our work. We will provide a detailed discussion on the generality of these conditions in section 3 . Condition 1 (Input Kernel Conditions) . Let w:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0} be a fixed function. The input kernel has the form of \displaystyle\mathbf{Ker}_{\mathbf{I}}(x,x^{\prime},\sigma)=\exp(-w(\sigma\left\lVert x-x^{\prime}\right\rVert^{\theta})) (1.4) Here, \theta>0 is a fixed constant. w satisfies: 1. \forall t\geq 0 , w^{\prime}(t)>0 . \lim_{t\to\infty}w(t)=\infty . 2. w^{\prime}(t)+tw^{\prime\prime}(t)\geq 0 for all t\geq 0 . 3. The following integral converges: \displaystyle\int_{0}^{\infty}t^{d-1}w(t^{\theta})\exp(-w(t^{\theta}))dt<\infty. (1.5) Since the all probability masses are normalized, we can assume without loss of generality that w(0)=0 from now on. Condition 2 (Output Kernel Conditions) . The output kernel depends only on the distance between two output data points y and y^{\prime} . In particular, \mathbf{Ker}_{\mathbf{O}}(y,y^{\prime})=k(\left\lVert y-y^{\prime}\right\rVert) and: 1. k:\mathbb{R}_{\geq 0}\to\mathbb{R}^{+} is decreasing and bounded. 2. \mathbf{Ker}_{\mathbf{O}} satisfies \displaystyle\iint_{(0,\infty)^{2}}\mathbf{Ker}_{\mathbf{O}}(y,y^{\prime})dydy^{\prime}<\infty. (1.6) 3. k has bounded derivative. 4. k^{\prime}(0)=0 . Setup and Notations In this subsection, we provide an introduction to the generalized t-SNE algorithm incorporating the new terminology. Recall that the input of the generalized t-SNE consists of vectors X_{1},\cdots,X_{n}\in\mathbb{R}^{d} , with the purpose of finding vectors Y_{1},\cdots Y_{n}\in\mathbb{R}^{s} that serve as a good representation of the original vectors. The algorithm starts by defining the following probability masses: \displaystyle p_{j|i}=\frac{\mathbf{Ker}_{\mathbf{I}}(X_{i},X_{j},\sigma_{i})}{\sum_{k\neq i}\mathbf{Ker}_{\mathbf{I}}(X_{i},X_{k},\sigma_{i})}. (1.7) Each \sigma_{i} satisfies that for each i=1,\dots,n , \displaystyle-\sum_{j=1,j\neq i}^{n}p_{j|i}\log p_{j|i}=\log\textbf{Perp}=:\log(n\rho). (1.8) Perp is called the perplexity and \rho\in(0,1) is a given constant. The purpose of \sigma_{i} is to make sure that for each i , the probability distribution induced by p_{j|i} has the same entropy across all i . Clearly, p_{j|i} is not symmetric. Remark 1 . For finite data set perplexity is usually set as a constant. Moreover, the scaling of perplexity with respect to \log n is strictly necessary here. In Murray and Pickarski 2024 , it has been proved that if we let \textbf{Perp}=\log n^{\gamma}\rho for some constant parameter \gamma , we cannot prove convergence and the existence of equilibrium measures for neither \gamma<1 nor \gamma>1 . We then define p_{ii}=0 and for 1\leq i\neq j\leq n , \displaystyle p_{ij}=\frac{p_{j|i}+p_{i|j}}{2n}=\frac{1}{2n}\left(\frac{\mathbf{Ker}_{\mathbf{I}}(X_{i},X_{j},\sigma_{i})}{\sum_{k\neq i}\mathbf{Ker}_{\mathbf{I}}(X_{i},X_{k},\sigma_{i})}+\frac{\mathbf{Ker}_{\mathbf{I}}(X_{i},X_{j},\sigma_{j})}{\sum_{k\neq j}\mathbf{Ker}_{\mathbf{I}}(X_{j},X_{k},\sigma_{j})}\right). (1.9) Obviously, \displaystyle\sum_{\begin{subarray}{c}j=1\\ j\neq i\end{subarray}}^{n}p_{j|i}=1,\quad\sum_{1\leq i\neq j\leq n}p_{ij}=1. (1.10) As for the output vectors Y_{1},\cdots Y_{n}\in\mathbb{R}^{s} , set for 1\leq i\neq j\leq n , \displaystyle q_{ij}=\frac{\mathbf{Ker}_{\mathbf{O}}(Yi,Yj)}{\sum_{k\neq l}\mathbf{Ker}_{\mathbf{O}}(Y_{k},Y_{l})}. (1.11) The goal of the generalized t-SNE is to find Y that minimizes the relative entropy \displaystyle L_{n,\rho}(X,Y)=\sum_{1\leq i\neq j\leq n}p_{ij}\log\left(\frac{p_{ij}}{q_{ij}}\right). (1.12) More precisely, the output of t-SNE Y^{*} is defined as \displaystyle Y^{*}=\argmin_{Y\in(\mathbb{R}^{s})^{n}}L_{n}(X,Y). (1.13) In the expression of L_{n}(X,Y) , all p_{ij} are given and q_{ij} is a function of Y_{i} and Y_{j} . Therefore, Y^{*} can be found simply by using gradient descent. This completes the description of the algorithm itself. Now we introduce necessary notations for convergence and asymptotic analysis. Let \mathcal{M}(\mathbb{R}^{d}) be the space of Borel probability measures on \mathbb{R}^{d} and \mu_{X}\in\mathcal{M}(\mathbb{R}^{d}) be a probability measure. Suppose all input X=(X_{1},\cdots,X_{n}) are i.i.d. random variables with probability measure \mu_{X} . Meanwhile, let Y^{*}=(Y_{1},\cdots,Y_{n}) be the output of the t-SNE algorithm. Consider the following empirical measure: \displaystyle\mu_{n}:=\frac{1}{n}\sum_{i=1}^{n}\delta(X_{i},Y_{i})\in\mathcal{M}(\mathbb{R}^{d}\times\mathbb{R}^{s}). (1.14) We are interested in its limiting measure as n\to\infty . To finish the setup, there are a few more remaining quantities we would like to introduce. Let \mu\in\mathcal{M}(\mathbb{R}^{d}\times\mathbb{R}^{s}) . For a given kernel \mathbf{Ker}_{\mathbf{I}}(x,y) , define F_{\rho,\mu}(x,\sigma):\mathbb{R}^{d}\times\mathbb{R}^{+}\to\mathbb{R} as \displaystyle F_{\rho,\mu}(x,\sigma)=\int\frac{\mathbf{Ker}_{\mathbf{I}}(x,x^{\prime},\sigma)}{\int\mathbf{Ker}_{\mathbf{I}}(x,x^{\prime},\sigma)d\mu(x^{\prime})}\log\left(\frac{\mathbf{Ker}_{\mathbf{I}}(x,x^{\prime},\sigma)}{\int\mathbf{Ker}_{\mathbf{I}}(x,x^{\prime},\sigma)d\mu(x^{\prime})}\right)d\mu(x^{\prime})+\log\rho. (1.15) Note that the last s variables in the integrands stay constant. It is not hard to see that F_{\rho,\mu}(x,\sigma) is the continuous version of the entropy. Next, we extend the definition of \sigma_{i} by defining \sigma^{*}_{\rho,\mu}:\mathbb{R}^{d}\to\mathbb{R} the unique solution of the equation \displaystyle F_{\rho,\mu}(x,\sigma)=0. (1.16) The introduction of