高维统计数据的一个基本目标是检测或恢复嘈杂数据中隐藏的种植结构（例如低级别矩阵）。越来越多的工作研究低级多项式作为此类问题的计算模型的限制模型：在各种情况下，数据的低级多项式可以与最知名的多项式时间算法的统计性能相匹配。先前的工作已经研究了低度多项式的力量，以检测隐藏结构的存在。在这项工作中，我们将这些方法扩展到解决估计和恢复问题（而不是检测）。对于大量的“信号加噪声”问题，我们给出了一个用户友好的下限，以获得最佳的均衡误差。据我们所知，这些是建立相关检测问题的恢复问题低度硬度的第一个结果。作为应用，我们对种植的子静脉和种植的密集子图问题的低度最小平方误差进行了严格的特征，在两种情况下都解决了有关恢复的计算复杂性的开放问题（在低度框架中）。

Suppose we are given an $n$-dimensional order-3 symmetric tensor $T \in (\mathbb{R}^n)^{\otimes 3}$ that is the sum of $r$ random rank-1 terms. The problem of recovering the rank-1 components is possible in principle when $r \lesssim n^2$ but polynomial-time algorithms are only known in the regime $r \ll n^{3/2}$. Similar "statistical-computational gaps" occur in many high-dimensional inference tasks, and in recent years there has been a flurry of work on explaining the apparent computational hardness in these problems by proving lower bounds against restricted (yet powerful) models of computation such as statistical queries (SQ), sum-of-squares (SoS), and low-degree polynomials (LDP). However, no such prior work exists for tensor decomposition, largely because its hardness does not appear to be explained by a "planted versus null" testing problem. We consider a model for random order-3 tensor decomposition where one component is slightly larger in norm than the rest (to break symmetry), and the components are drawn uniformly from the hypercube. We resolve the computational complexity in the LDP model: $O(\log n)$-degree polynomial functions of the tensor entries can accurately estimate the largest component when $r \ll n^{3/2}$ but fail to do so when $r \gg n^{3/2}$. This provides rigorous evidence suggesting that the best known algorithms for tensor decomposition cannot be improved, at least by known approaches. A natural extension of the result holds for tensors of any fixed order $k \ge 3$, in which case the LDP threshold is $r \sim n^{k/2}$.

我们研究了小组测试问题，其目标是根据合并测试的结果，确定一组k感染的人，这些k含有稀有疾病，这些人在经过测试中至少有一个受感染的个体时返回阳性的结果。团体。我们考虑将个人分配给测试的两个不同的简单随机过程：恒定柱设计和伯努利设计。我们的第一组结果涉及基本统计限制。对于恒定柱设计，我们给出了一个新的信息理论下限，这意味着正确识别的感染者的比例在测试数量越过特定阈值时会经历急剧的“全或全或无所不包”的相变。对于Bernoulli设计，我们确定解决相关检测问题所需的确切测试数量（目的是区分小组测试实例和纯噪声），改善Truong，Aldridge和Scarlett的上限和下限（2020）。对于两个小组测试模型，我们还研究了计算有效（多项式时间）推理程序的能力。我们确定了解决检测问题的低度多项式算法所需的精确测试数量。这为在少量稀疏度的检测和恢复问题中都存在固有的计算统计差距提供了证据。值得注意的是，我们的证据与Iliopoulos和Zadik（2021）相反，后者预测了Bernoulli设计中没有计算统计差距。

我们研究了恢复单位 - 总稀疏主组件$ x \ in \ mathbb {r}^n $在随机矩阵中种植的计算成本，以wigner或wishart尖峰模型（观察$ w + \ lambda xx xx^xx^ \ top $带有从高斯正交集合中绘制的$ w $，或分别来自$ \ Mathcal {n}（0，i_n + \ beta xx^\ top）$的$ n $独立样本，分别为$）。先前的工作表明，当信噪比（分别$ \ lambda $或$ \ beta \ sqrt {n/n} $）是一个小常数，而种植向量中的非零入口的分数为$ \ \ \ | x \ | _0 / n = \ rho $，如果$ \ rho \ sillsim 1 / \ sqrt {n} $，可以在多项式时间内恢复$ x $。虽然可以在较弱的条件下以$ \ rho \ ll 1 $恢复指数时间的$ x $，但据信，除非$ \ rho \ rho \ simsim 1/\ sqrt {n} $，否则不可能多项式时间恢复。我们研究了“可能但难”制度中恢复所需的精确时间，$ 1/\ sqrt {n} \ ll \ ll \ rho \ ll 1 $通过探索次指定时间算法的功能，即，在时间$中运行的算法$ \ exp（n^\ delta）$对于某些常数$ \ delta \ in（0,1）$。对于任何$ 1/\ sqrt {n} \ ll \ rho \ ll 1 $，我们给出了一个恢复算法的运行时大约$ \ exp（\ rho^2 n）$，表明了稀疏和runtime之间的平稳折衷。我们的算法家族在两种现有算法之间平稳地插入：多项式时间对角线阈值算法和$ \ exp（\ rho n）$ - 时间详尽的搜索算法。此外，通过分析低度的似然比，我们提供了严格的证据，表明我们算法实现的权衡是最佳的。

聚类是无监督学习中的基本原始，它引发了丰富的计算挑战性推理任务。在这项工作中，我们专注于将$ D $ -dimential高斯混合的规范任务与未知（和可能的退化）协方差集成。最近的作品（Ghosh等人。恢复在高斯聚类实例中种植的某些隐藏结构。在许多类似的推理任务上的工作开始，这些较低界限强烈建议存在群集的固有统计到计算间隙，即群集任务是\ yringit {statistically}可能但没有\ texit {多项式 - 时间}算法成功。我们考虑的聚类任务的一个特殊情况相当于在否则随机子空间中找到种植的超立体载体的问题。我们表明，也许令人惊讶的是，这种特定的聚类模型\ extent {没有展示}统计到计算间隙，即使在这种情况下继续应用上述的低度和SOS下限。为此，我们提供了一种基于Lenstra - Lenstra - Lovasz晶格基础减少方法的多项式算法，该方法实现了$ D + 1 $样本的统计上最佳的样本复杂性。该结果扩展了猜想统计到计算间隙的问题的类问题可以通过“脆弱”多项式算法“关闭”，突出显示噪声在统计到计算间隙的发作中的关键而微妙作用。

我们研究了在存在$ \ epsilon $ - 对抗异常值的高维稀疏平均值估计的问题。先前的工作为此任务获得了该任务的样本和计算有效算法，用于辅助性Subgaussian分布。在这项工作中，我们开发了第一个有效的算法，用于强大的稀疏平均值估计，而没有对协方差的先验知识。对于$ \ Mathbb r^d $上的分布，带有“认证有限”的$ t $ tum-矩和足够轻的尾巴，我们的算法达到了$ o（\ epsilon^{1-1/t}）$带有样品复杂性$的错误（\ epsilon^{1-1/t}） m =（k \ log（d））^{o（t）}/\ epsilon^{2-2/t} $。对于高斯分布的特殊情况，我们的算法达到了$ \ tilde o（\ epsilon）$的接近最佳错误，带有样品复杂性$ m = o（k^4 \ mathrm {polylog}（d）（d））/\ epsilon^^ 2 $。我们的算法遵循基于方形的总和，对算法方法的证明。我们通过统计查询和低度多项式测试的下限来补充上限，提供了证据，表明我们算法实现的样本时间 - 错误权衡在质量上是最好的。

近似消息传递（AMP）是解决高维统计问题的有效迭代范式。但是，当迭代次数超过$ o \ big（\ frac {\ log n} {\ log log \ log \ log n} \时big）$（带有$ n $问题维度）。为了解决这一不足，本文开发了一个非吸附框架，用于理解峰值矩阵估计中的AMP。基于AMP更新的新分解和可控的残差项，我们布置了一个分析配方，以表征在存在独立初始化的情况下AMP的有限样本行为，该过程被进一步概括以进行光谱初始化。作为提出的分析配方的两个具体后果：（i）求解$ \ mathbb {z} _2 $同步时，我们预测了频谱初始化AMP的行为，最高为$ o \ big（\ frac {n} {\ mathrm {\ mathrm { poly} \ log n} \ big）$迭代，表明该算法成功而无需随后的细化阶段（如最近由\ citet {celentano2021local}推测）; （ii）我们表征了稀疏PCA中AMP的非反应性行为（在尖刺的Wigner模型中），以广泛的信噪比。

随机块模型（SBM）是一个随机图模型，其连接不同的顶点组不同。它被广泛用作研究聚类和社区检测的规范模型，并提供了肥沃的基础来研究组合统计和更普遍的数据科学中出现的信息理论和计算权衡。该专着调查了最近在SBM中建立社区检测的基本限制的最新发展，无论是在信息理论和计算方案方面，以及各种恢复要求，例如精确，部分和弱恢复。讨论的主要结果是在Chernoff-Hellinger阈值中进行精确恢复的相转换，Kesten-Stigum阈值弱恢复的相变，最佳的SNR - 单位信息折衷的部分恢复以及信息理论和信息理论之间的差距计算阈值。该专着给出了在寻求限制时开发的主要算法的原则推导，特别是通过绘制绘制，半定义编程，（线性化）信念传播，经典/非背带频谱和图形供电。还讨论了其他块模型的扩展，例如几何模型和一些开放问题。

Random graph models with community structure have been studied extensively in the literature. For both the problems of detecting and recovering community structure, an interesting landscape of statistical and computational phase transitions has emerged. A natural unanswered question is: might it be possible to infer properties of the community structure (for instance, the number and sizes of communities) even in situations where actually finding those communities is believed to be computationally hard? We show the answer is no. In particular, we consider certain hypothesis testing problems between models with different community structures, and we show (in the low-degree polynomial framework) that testing between two options is as hard as finding the communities. In addition, our methods give the first computational lower bounds for testing between two different `planted' distributions, whereas previous results have considered testing between a planted distribution and an i.i.d. `null' distribution.

我们研究了稀疏张量主成分分析的问题：给定张量$ \ pmb y = \ pmb w + \ lambda x ^ {\ otimes p} $ with $ \ pmb w \ in \ otimes ^ p \ mathbb {r} ^ n $拥有iid高斯条目，目标是恢复$ k $ -parse单位矢量$ x \ in \ mathbb {r} ^ n $。该模型捕获稀疏PCA（其Wigner形式）和张量PCA。对于$ k \ leq \ sqrt {n} $的高稀疏制度，我们介绍了一系列平滑地插值在简单的多项式算法和指数时穷举搜索算法之间的算法。对于任何$ 1 \ leq t \ leq k $，我们的算法恢复了信噪比$ \ lambda \ geq \ tilde {\ mathcal {o}}（\ sqrt {t} \ cdot（k / t ）^ {p / 2}）$时间$ \ tilde {\ mathcal {o}}（n ^ {p + t}）$，捕获矩阵设置的最先进的保证（在两者中多项式时间和子指数时间制度）。我们的结果自然地延伸到$ r $ distinct $ k $ -parse信号的案例与不相交的支持，保证与尖峰的数量无关。即使在稀疏PCA的局限性情况下，已知的算法也仅恢复$ \ lambda \ geq \ tilde {\ mathcal {o}}（k \ cdot r）$的稀疏向量，而我们的算法需要$ \ lambda \ geq \ tilde { \ mathcal {o}}（k）$。最后，通过分析低度似然比，我们将这些算法结果补充，具体证据说明信噪比和运行时间之间的权衡。该下限捕获稀疏PCA和张量PCA的已知下限。在这一普通模型中，我们在标准数量$ N $，稀疏$ k $的样本数量之间观察更复杂的三方权衡，以及张力电源$ p $。

我们调查与高斯的混合的数据分享共同但未知，潜在虐待协方差矩阵的数据。我们首先考虑具有两个等级大小的组件的高斯混合，并根据最大似然估计导出最大切割整数程序。当样品的数量在维度下线性增长时，我们证明其解决方案实现了最佳的错误分类率，直到对数因子。但是，解决最大切割问题似乎是在计算上棘手的。为了克服这一点，我们开发了一种高效的频谱算法，该算法达到最佳速率，但需要一种二次样本量。虽然这种样本复杂性比最大切割问题更差，但我们猜测没有多项式方法可以更好地执行。此外，我们收集了支持统计计算差距存在的数值和理论证据。最后，我们将MAX-CUT程序概括为$ k $ -means程序，该程序处理多组分混合物的可能性不平等。它享有相似的最优性保证，用于满足运输成本不平等的分布式的混合物，包括高斯和强烈的对数的分布。

我们开发了一种高效的随机块模型中的弱恢复算法。该算法与随机块模型的Vanilla版本的最佳已知算法的统计保证匹配。从这个意义上讲，我们的结果表明，随机块模型没有稳健性。我们的工作受到最近的银行，Mohanty和Raghavendra（SODA 2021）的工作，为相应的区别问题提供了高效的算法。我们的算法及其分析显着脱离了以前的恢复。关键挑战是我们算法的特殊优化景观：种植的分区可能远非最佳意义，即完全不相关的解决方案可以实现相同的客观值。这种现象与PCA的BBP相转变的推出效应有关。据我们所知，我们的算法是第一个在非渐近设置中存在这种推出效果的鲁棒恢复。我们的算法是基于凸优化的框架的实例化（与平方和不同的不同），这对于其他鲁棒矩阵估计问题可能是有用的。我们的分析的副产物是一种通用技术，其提高了任意强大的弱恢复算法的成功（输入的随机性）从恒定（或缓慢消失）概率以指数高概率。

我们考虑强大的线性回归模型$ \ boldsymbol {y} = x \ beta^* + \ boldsymbol {\ eta} $，其中一个对手忽略了design $ x \ in \ mathbb {r}^r}^n \ times D } $可以选择$ \ boldsymbol {\ eta} $以损坏所有观测值的（可能消失的）$ \ boldsymbol {y} $以任意方式。最近的工作[DLN+21，DNS21]引入了有效的算法，以持续恢复参数矢量。这些算法至关重要地依赖于设计矩阵非常广泛（如果其列跨度远非任何稀疏矢量，矩阵就可以很好地扩展）。在本文中，我们表明存在一个缺乏良好性的设计矩阵家族，因此从理论上讲，在上述稳健线性回归模型中，参数向量的持续恢复是不可能的。我们进一步研究了随机矩阵的良好表现的平均案例时间复杂性。我们表明，如果观察值的数量在环境维度上是二次的，则可以有效地证明给定的$ n $ by-by-by-by-by-by-d $ d $ d $高斯矩阵是否会很好地扩展。当观察数为$ O（d^2）$时，我们通过显示出相同认证问题的计算硬度的严格证据来补充这一结果。

我们建立了最佳的统计查询（SQ）下限，以鲁棒地学习某些离散高维分布的家庭。特别是，我们表明，没有访问$ \ epsilon $ -Cruntupted二进制产品分布的有效SQ算法可以在$ \ ell_2 $ -error $ o（\ epsilon \ sqrt {\ log（\ log（1/\ epsilon））内学习其平均值}）$。同样，我们表明，没有访问$ \ epsilon $ - 腐败的铁磁高温岛模型的有效SQ算法可以学习到总变量距离$ O（\ Epsilon \ log（1/\ Epsilon））$。我们的SQ下限符合这些问题已知算法的错误保证，提供证据表明这些任务的当前上限是最好的。在技​​术层面上，我们为离散的高维分布开发了一个通用的SQ下限，从低维矩匹配构建体开始，我们认为这将找到其他应用程序。此外，我们介绍了新的想法，以分析这些矩匹配的结构，以进行离散的单变量分布。

本文讨论了ERD \ H {O} S-R \'enyi图的图形匹配或网络对齐问题，可以将其视为图同构问题的嘈杂平均案例版本。令$ g $和$ g'$ be $ g（n，p）$ erd \ h {o} s--r \'enyi略微图形，并用其邻接矩阵识别。假设$ g $和$ g'$是相关的，因此$ \ mathbb {e} [g_ {ij} g'_ {ij}] = p（1- \ alpha）$。对于置换$ \ pi $，代表$ g $和$ g'$之间的潜在匹配，用$ g^\ pi $表示从$ \ pi $的$ g $的顶点获得的图表。观察$ g^\ pi $和$ g'$，我们的目标是恢复匹配的$ \ pi $。在这项工作中，我们证明，在（0,1] $中，每$ \ varepsilon \ in（0,1] $，都有$ n_0> 0 $，具体取决于$ \ varepsilon $和绝对常数$ \ alpha_0，r> 0 $，带有以下属性。令$ n \ ge n_0 $，$（1+ \ varepsilon）\ log n \ le np \ le n^{\ frac {1} {r \ log \ log \ log n}} $ （\ alpha_0，\ varepsilon/4）$。有一个多项式时算法$ f $，因此$ \ m athbb {p} \ {f（g^\ pi，g'）= \ pi \} = 1-o （1）$。这是第一种多项式时算法，它恢复了相关的ERD \ H {O} S-r \'enyi图与具有恒定相关性的相关性图与高概率相关性的确切匹配。该算法是基于比较的比较与图形顶点关联的分区树。

The stochastic block model (SBM) is a random graph model with planted clusters. It is widely employed as a canonical model to study clustering and community detection, and provides generally a fertile ground to study the statistical and computational tradeoffs that arise in network and data sciences.This note surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational thresholds, and for various recovery requirements such as exact, partial and weak recovery (a.k.a., detection). The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal distortion-SNR tradeoff for partial recovery, the learning of the SBM parameters and the gap between information-theoretic and computational thresholds.The note also covers some of the algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, linearized belief propagation, classical and nonbacktracking spectral methods. A few open problems are also discussed.

我们在高斯分布下使用Massart噪声与Massart噪声进行PAC学习半个空间的问题。在Massart模型中，允许对手将每个点$ \ mathbf {x} $的标签与未知概率$ \ eta（\ mathbf {x}）\ leq \ eta $，用于某些参数$ \ eta \ [0,1 / 2] $。目标是找到一个假设$ \ mathrm {opt} + \ epsilon $的错误分类错误，其中$ \ mathrm {opt} $是目标半空间的错误。此前已经在两个假设下研究了这个问题：（i）目标半空间是同质的（即，分离超平面通过原点），并且（ii）参数$ \ eta $严格小于$ 1/2 $。在此工作之前，当除去这些假设中的任何一个时，不知道非增长的界限。我们研究了一般问题并建立以下内容：对于$ \ eta <1/2 $，我们为一般半个空间提供了一个学习算法，采用样本和计算复杂度$ d ^ {o_ {\ eta}（\ log（1 / \ gamma） ）））}} \ mathrm {poly}（1 / \ epsilon）$，其中$ \ gamma = \ max \ {\ epsilon，\ min \ {\ mathbf {pr} [f（\ mathbf {x}）= 1]， \ mathbf {pr} [f（\ mathbf {x}）= -1] \} \} $是目标半空间$ f $的偏差。现有的高效算法只能处理$ \ gamma = 1/2 $的特殊情况。有趣的是，我们建立了$ d ^ {\ oomega（\ log（\ log（\ log（\ log））}}的质量匹配的下限，而是任何统计查询（SQ）算法的复杂性。对于$ \ eta = 1/2 $，我们为一般半空间提供了一个学习算法，具有样本和计算复杂度$ o_ \ epsilon（1）d ^ {o（\ log（1 / epsilon））} $。即使对于均匀半空间的子类，这个结果也是新的;均匀Massart半个空间的现有算法为$ \ eta = 1/2 $提供可持续的保证。我们与D ^ {\ omega（\ log（\ log（\ log（\ log（\ epsilon））} $的近似匹配的sq下限补充了我们的上限，这甚至可以为同类半空间的特殊情况而保持。

分析大型随机矩阵的浓度是多种领域的常见任务。给定独立的随机变量，许多工具可用于分析随机矩阵，其条目在变量中是线性的，例如基质 - 伯恩斯坦不平等。但是，在许多应用中，我们需要分析其条目是变量中多项式的随机矩阵。这些自然出现在光谱算法的分析中，例如霍普金斯等人。 [Stoc 2016]，Moitra-Wein [Stoc 2019]；并根据正方形层次结构的总和（例如Barak等。 [FOCS 2016]，Jones等。 [焦点2021]。在这项工作中，我们基于Paulin-Mackey-Tropp（概率Annals of Poylibity of Poyliby of 2016]，我们提出了一个通用框架来获得此类界限。 Efron-Stein不等式通过另一个简单（但仍然是随机）矩阵的范围来界定随机矩阵的规范，我们将其视为通过“区分”起始矩阵而引起的。通过递归区分，我们的框架减少了分析更简单的矩阵的主要任务。对于Rademacher变量，这些简单的矩阵实际上是确定性的，因此，分析它们要容易得多。对于一般的非拉多巴纳变量，任务减少到标量浓度，这要容易得多。此外，在多项式矩阵的设置中，我们的结果推广了Paulin-Mackey-Tropp的工作。使用我们的基本框架，我们在文献中恢复了简单的“张量网络”和“密集图矩阵”的已知界限。使用我们的一般框架，我们得出了“稀疏图矩阵”的边界，琼斯等人最近才获得。 [焦点2021]使用痕量功率方法的非平地应用，并且是其工作中的核心组成部分。我们希望我们的框架对涉及非线性随机矩阵浓度现象的其他应用有帮助。

We consider the problem of estimating a multivariate function $f_0$ of bounded variation (BV), from noisy observations $y_i = f_0(x_i) + z_i$ made at random design points $x_i \in \mathbb{R}^d$, $i=1,\ldots,n$. We study an estimator that forms the Voronoi diagram of the design points, and then solves an optimization problem that regularizes according to a certain discrete notion of total variation (TV): the sum of weighted absolute differences of parameters $\theta_i,\theta_j$ (which estimate the function values $f_0(x_i),f_0(x_j)$) at all neighboring cells $i,j$ in the Voronoi diagram. This is seen to be equivalent to a variational optimization problem that regularizes according to the usual continuum (measure-theoretic) notion of TV, once we restrict the domain to functions that are piecewise constant over the Voronoi diagram. The regression estimator under consideration hence performs (shrunken) local averaging over adaptively formed unions of Voronoi cells, and we refer to it as the Voronoigram, following the ideas in Koenker (2005), and drawing inspiration from Tukey's regressogram (Tukey, 1961). Our contributions in this paper span both the conceptual and theoretical frontiers: we discuss some of the unique properties of the Voronoigram in comparison to TV-regularized estimators that use other graph-based discretizations; we derive the asymptotic limit of the Voronoi TV functional; and we prove that the Voronoigram is minimax rate optimal (up to log factors) for estimating BV functions that are essentially bounded.

我们考虑了在高维度中平均分离的高斯聚类混合物的问题。我们是从$ k $身份协方差高斯的混合物提供的样本，使任何两对手段之间的最小成对距离至少为$ \ delta $，对于某些参数$ \ delta> 0 $，目标是恢复这些样本的地面真相聚类。它是分离$ \ delta = \ theta（\ sqrt {\ log k}）$既有必要且足以理解恢复良好的聚类。但是，实现这种担保的估计值效率低下。我们提供了在多项式时间内运行的第一算法，几乎符合此保证。更确切地说，我们给出了一种算法，它需要多项式许多样本和时间，并且可以成功恢复良好的聚类，只要分离为$ \ delta = \ oomega（\ log ^ {1/2 + c} k）$ ，任何$ c> 0 $。以前，当分离以k $的分离和可以容忍$ \ textsf {poly}（\ log k）$分离所需的quasi arynomial时间时，才知道该问题的多项式时间算法。我们还将我们的结果扩展到分布的分布式的混合物，该分布在额外的温和假设下满足Poincar \ {e}不等式的分布。我们认为我们相信的主要技术工具是一种新颖的方式，可以隐含地代表和估计分配的​​高度时刻，这使我们能够明确地提取关于高度时刻的重要信息而没有明确地缩小全瞬间张量。