Undergraduate Research Seminar – Nearest Neighbor Graphs, Percolation, and Nonlinear Dimension Reduction

 Abstract. Nonlinear dimension reduction algorithms take an important role in data exploration in modern science and engineering problems. However, many of these algorithms exhibit surprising, counter-intuitive behavior that is poorly understood. In this talk we will discuss t-SNE, a popular algorithm for this task. We will draw links with classical theory of percolation for nearest neighborhood graphs, and use it to develop rigorous theory for t-SNE in specific hyperparameter regimes. In this setting, using ideas from variational analysis, we will show that t-SNE plots exhibit universal behavior independent of the inputted data, a failure mode with practical implications.