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

Kangjie Zhou; Andrea Montanari

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

Kangjie Zhou, Andrea Montanari

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.

Cite this Paper

BibTeX


@InProceedings{pmlr-v178-zhou22a,
  title = 	 {High-Dimensional Projection Pursuit: Outer Bounds and Applications to Interpolation in Neural Networks},
  author =       {Zhou, Kangjie and Montanari, Andrea},
  booktitle = 	 {Proceedings of Thirty Fifth Conference on Learning Theory},
  pages = 	 {5525--5527},
  year = 	 {2022},
  editor = 	 {Loh, Po-Ling and Raginsky, Maxim},
  volume = 	 {178},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {02--05 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v178/zhou22a/zhou22a.pdf},
  url = 	 {https://proceedings.mlr.press/v178/zhou22a.html},
  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.}
}

Endnote

%0 Conference Paper
%T High-Dimensional Projection Pursuit: Outer Bounds and Applications to Interpolation in Neural Networks
%A Kangjie Zhou
%A Andrea Montanari
%B Proceedings of Thirty Fifth Conference on Learning Theory
%C Proceedings of Machine Learning Research
%D 2022
%E Po-Ling Loh
%E Maxim Raginsky	
%F pmlr-v178-zhou22a
%I PMLR
%P 5525--5527
%U https://proceedings.mlr.press/v178/zhou22a.html
%V 178
%X 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.

APA


Zhou, K. & Montanari, A.. (2022). High-Dimensional Projection Pursuit: Outer Bounds and Applications to Interpolation in Neural Networks. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:5525-5527 Available from https://proceedings.mlr.press/v178/zhou22a.html.

Related Material

Download PDF