# Which exceptional low-dimensional projections of a Gaussian point cloud can be found in polynomial time?

arXiv: https://arxiv.org/abs/2406.02970 · HTML: https://mlsanity.com/paper/2406.02970/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2024.

## Built on by (most cited first, 1 of 1)

- [Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model](https://mlsanity.com/paper/2606.28573/) (2026)

## Abstract (arXiv)

Given d-dimensional standard Gaussian vectors boldsymbolx1,dots, boldsymbolxn, we consider the set of all empirical distributions of its m-dimensional projections, for m a fixed constant. Diaconis and Freedman (1984) proved that, if n/d→ ∞, all such distributions converge to the standard Gaussian distribution. In contrast, we study the proportional asymptotics, whereby n,d→ ∞ with n/d→ α ∈ (0, ∞). In this case, the projection of the data points along a typical random subspace is again Gaussian, but the set mathscrFm,α of all probability distributions that are asymptotically feasible as m-dimensional projections contains non-Gaussian distributions corresponding to exceptional subspaces. Non-rigorous methods from statistical physics yield an indirect characterization of mathscrFm,α in terms of a generalized Parisi formula. Motivated by the goal of putting this formula on a rigorous basis, and to understand whether these projections can be found efficiently, we study the subset mathscrFrm algm,αsubseteq mathscrFm,α of distributions that can be realized by a class of iterative algorithms. We prove that this set is characterized by a certain stochastic optimal control problem, and obtain a dual characterization of this problem in terms of a variational principle that extends Parisi's formula. As a byproduct, we obtain computationally achievable values for a class of random optimization problems including `generalized spherical perceptron' models.