[edit]

# High-Dimensional Projection Pursuit: Outer Bounds and Applications to Interpolation in Neural Networks

*Proceedings of Thirty Fifth Conference on Learning Theory*, PMLR 178:5525-5527, 2022.

#### Abstract

Given a cloud of $n$ data points in $\R^d$, consider all projections onto $m$-dimensional subspaces of $\R^d$ and, for each such projection, the empirical distribution of the projected points. What does this collection of probability distributions look like when $n,d$ grow large? We consider this question under the null model in which the points are i.i.d. standard Gaussian vectors, focusing on the asymptotic regime in which $n,d\to\infty$, with $n/d\to\alpha\in (0,\infty)$, while $m$ is fixed. Denoting by $\cuF_{m, \alpha}$ the set of probability distributions in $\R^m$ that arise as low-dimensional projections in this limit, we establish new outer bounds on $\cuF_{m, \alpha}$. In particular, we characterize the radius of $\cuF_{m,\alpha}$ in terms of Wasserstein distance and prove sharp bounds in terms of Kullback-Leibler divergence and Rényi information dimension. The previous question has application to unsupervised learning methods, such as projection pursuit and independent component analysis. We introduce a version of the same problem that is relevant for supervised learning, and prove a sharp Wasserstein radius bound. As an application, we establish an upper bound on the interpolation threshold of two-layers neural networks with $m$ hidden neurons.