This paper investigates the theoretical foundations of the t-distributed
stochastic neighbor embedding (t-SNE) algorithm, a popular nonlinear dimension
reduction and data visualization method. A novel theoretical framework for the
analysis of t-SNE based on the gradient descent approach is presented. For the
early exaggeration stage of t-SNE, we show its asymptotic equivalence to power
iterations based on the underlying graph Laplacian, characterize its limiting
behavior, and uncover its deep connection to Laplacian spectral clustering, and
fundamental principles including early stopping as implicit regularization. The
results explain the intrinsic mechanism and the empirical benefits of such a
computational strategy. For the embedding stage of t-SNE, we characterize the
kinematics of the low-dimensional map throughout the iterations, and identify
an amplification phase, featuring the intercluster repulsion and the expansive
behavior of the low-dimensional map, and a stabilization phase. The general
theory explains the fast convergence rate and the exceptional empirical
performance of t-SNE for visualizing clustered data, brings forth
interpretations of the t-SNE visualizations, and provides theoretical guidance
for applying t-SNE and selecting its tuning parameters in various applications.

本文对 t-SNE 算法的理论框架进行了研究，在梯度下降法的基础上提出了一种新的理论框架；对于 t-SNE 的 embedding 阶段，文中还对其低维映射的运动学进行了表征和说明。通过本文，我们发现了 t-SNE 的内在机制并说明其在可视化聚类数据方面具有非凡的实用性。