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

通过研究高斯向量、比例渐近性、经验分布、随机子空间和随机最优控制问题，我们证明了一类分布可以通过迭代算法实现，并获得了关于这个问题的对偶表述和拓展帕里西公式的变分原理。

高斯点云中可以在多项式时间内找到的例外低维投影

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

Recovering a planted vector $v$ in an $n$-dimensional random subspace of
$\mathbb{R}^N$ is a generic task related to many problems in machine learning
and statistics, such as dictionary learning, subspace recovery, principal
component analysis, and non-Gaussian component analysis. In this work, we study
computationally efficient estimation and detection of a planted vector $v$
whose $\ell_4$ norm differs from that of a Gaussian vector with the same
$\ell_2$ norm. For instance, in the special case where $v$ is an $N
\rho$-sparse vector with Bernoulli-Gaussian or Bernoulli-Rademacher entries,
our results include the following:
(1) We give an improved analysis of a slight variant of the spectral method
proposed by Hopkins, Schramm, Shi, and Steurer (2016), showing that it
approximately recovers $v$ with high probability in the regime $n \rho \ll
\sqrt{N}$. This condition subsumes the conditions $\rho \ll 1/\sqrt{n}$ or $n
\sqrt{\rho} \lesssim \sqrt{N}$ required by previous work up to polylogarithmic
factors. We achieve $\ell_\infty$ error bounds for the spectral estimator via a
leave-one-out analysis, from which it follows that a simple thresholding
procedure exactly recovers $v$ with Bernoulli-Rademacher entries, even in the
dense case $\rho = 1$.
(2) We study the associated detection problem and show that in the regime $n
\rho \gg \sqrt{N}$, any spectral method from a large class (and more generally,
any low-degree polynomial of the input) fails to detect the planted vector.
This matches the condition for recovery and offers evidence that no
polynomial-time algorithm can succeed in recovering a Bernoulli-Gaussian vector
$v$ when $n \rho \gg \sqrt{N}$.

本文研究高斯正交和伯努利 - 高斯随机矩阵下种植向量的估计和检测问题，主要通过谱方法解决其中的计算问题。

子空间种植向量的最优谱恢复

Optimal Spectral Recovery of a Planted Vector in a Subspace

The design and complexity analysis of randomized coordinate descent methods,
and in particular of variants which update a random subset (sampling) of
coordinates in each iteration, depends on the notion of expected separable
overapproximation (ESO). This refers to an inequality involving the objective
function and the sampling, capturing in a compact way certain smoothness
properties of the function in a random subspace spanned by the sampled
coordinates. ESO inequalities were previously established for special classes
of samplings only, almost invariably for uniform samplings. In this paper we
develop a systematic technique for deriving these inequalities for a large
class of functions and for arbitrary samplings. We demonstrate that one can
recover existing ESO results using our general approach, which is based on the
study of eigenvalues associated with samplings and the data describing the
function.

研究并分析随机坐标下降方法的设计和复杂度，特别是每次迭代在一个随机子集（采样）中更新的变体，这取决于期望可分离过逼近（ESO）的概念。本文为一类函数和任意采样推导了这种不等式，该方法基于与采样和描述函数的数据相关的特征值的研究。