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

Given $d$-dimensional standard Gaussian vectors ${\mathit{x}}_1,\dots ,{\mathit{x}}_n$, 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\mathrm{/}d\to \mathrm{\infty }$, all such distributions converge to the standard Gaussian distribution. In contrast, we study the proportional asymptotics, whereby $n,d\to \mathrm{\infty }$ with $n\mathrm{/}d\to \alpha \in (0,\mathrm{\infty })$. In this case, the projection of the data points along a typical random subspace is again Gaussian, but the set ${\mathcal{F}}_{m,\alpha }$ 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 ${\mathcal{F}}_{m,\alpha }$ 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 ${\mathcal{F}}_{m,\alpha }^{\mathrm{a}\mathrm{l}\mathrm{g}}\subseteq {\mathcal{F}}_{m,\alpha }$ 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.