在这项工作中，我们研究了具有对抗性节点损坏的随机块模型中社区发现的问题。我们的主要结果是一种有效的算法，该算法可以忍受$ \ epsilon $ - 损坏和达到错误$ o（\ epsilon） + e^{ - \ frac {c} {2} {2}（1 \ pm o（1））} $其中$ c =（\ sqrt {a} - \ sqrt {b}）^2 $是信噪比，$ a/n $和$ b/n $是互发和intra-intra-intra-社区连接概率分别。这些界限基本上与无损坏的SBM的最小值相匹配。我们还为$ \ mathbb {z} _2 $ -Synchronization提供了可靠的算法。我们算法的核心是一个新的半决赛程序，它使用全局信息来鲁棒提高粗糙聚类的准确性。此外，我们表明我们的算法是双重的，因为它们在更具挑战性的噪声模型中起作用，该模型将对抗性腐败与无限制的单调变化混合在一起，从半随机模型中。

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

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

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.

社区检测是网络科学中的一个基本问题。在本文中，我们考虑了从$ HyperGraph $ $ $ $ $ $ $ $ $ $ $ $ $ $ $（HSBM）中绘制的HyperGraphs中的社区检测，重点是精确的社区恢复。在整个超图未知的情况下，我们研究了多项式时间算法以进行社区检测的性能。取而代之的是，我们获得了$相似性$ $ $ $ $ $ $ w $，其中$ w_ {ij} $报告包含$ i $和$ j $的超补品的数量。在此信息模型下，Kim，Bandeira和Goemans [KBG18]确定了信息理论阈值，以进行精确恢复，并提出了他们认为是最佳的半决赛编程松弛。在本文中，我们确认了这个猜想。我们还表明，一种简单，高效的光谱算法是最佳的，将光谱算法作为选择方法。我们对光谱算法的分析至关重要地依赖于$ w $的特征向量上的强$ entrywise $界限。我们的边界灵感来自Abbe，Fan，Wang和Zhong [AFWZ20]的工作，他们开发了具有独立条目的对称矩阵的特征向量的进入界。尽管相似性矩阵的依赖性结构复杂，但我们证明了相似的入口保证。

The stochastic block model (SBM) is a fundamental model for studying graph clustering or community detection in networks. It has received great attention in the last decade and the balanced case, i.e., assuming all clusters have large size, has been well studied. However, our understanding of SBM with unbalanced communities (arguably, more relevant in practice) is still very limited. In this paper, we provide a simple SVD-based algorithm for recovering the communities in the SBM with communities of varying sizes. We improve upon a result of Ailon, Chen and Xu [ICML 2013] by removing the assumption that there is a large interval such that the sizes of clusters do not fall in. Under the planted clique conjecture, the size of the clusters that can be recovered by our algorithm is nearly optimal (up to polylogarithmic factors) when the probability parameters are constant. As a byproduct, we obtain a polynomial-time algorithm with sublinear query complexity for a clustering problem with a faulty oracle, which finds all clusters of size larger than $\tilde{\Omega}({\sqrt{n}})$ even if $\Omega(n)$ small clusters co-exist in the graph. In contrast, all the previous efficient algorithms that makes sublinear number of queries cannot recover any large cluster, if there are more than $\tilde{\Omega}(n^{2/5})$ small clusters.

在这项工作中，我们研究了鲁布利地学习Mallows模型的问题。我们给出了一种算法，即使其样本的常数分数是任意损坏的恒定分数，也可以准确估计中央排名。此外，我们的稳健性保证是无关的，因为我们的整体准确性不依赖于排名的替代品的数量。我们的工作可以被认为是从算法稳健统计到投票和信息聚集中的中央推理问题之一的视角的自然输注。具体而言，我们的投票规则是有效的可计算的，并且通过一大群勾结的选民无法改变其结果。

We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to robustness which can produce private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy for a wide range of fundamental high-dimensional parameter estimation problems, including mean and covariance estimation. We show that this reduction can be implemented in polynomial time in some important special cases. In particular, using nearly-optimal polynomial-time robust estimators for the mean and covariance of high-dimensional Gaussians which are based on the Sum-of-Squares method, we design the first polynomial-time private estimators for these problems with nearly-optimal samples-accuracy-privacy tradeoffs. Our algorithms are also robust to a constant fraction of adversarially-corrupted samples.

我们考虑了在高维度中平均分离的高斯聚类混合物的问题。我们是从$ 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}不等式的分布。我们认为我们相信的主要技术工具是一种新颖的方式，可以隐含地代表和估计分配的​​高度时刻，这使我们能够明确地提取关于高度时刻的重要信息而没有明确地缩小全瞬间张量。

我们研究了在存在$ \ 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 $。我们的算法遵循基于方形的总和，对算法方法的证明。我们通过统计查询和低度多项式测试的下限来补充上限，提供了证据，表明我们算法实现的样本时间 - 错误权衡在质量上是最好的。

我们在非均匀超图随机块模型（HSBM）下的稀疏随机超图中的社区检测问题，是社区结构的随机网络的一般模型和高阶交互。当随机超图具有界定的预期度时，我们提供了一种频谱算法，该频谱算法输出分区，其中至少有$ \ gamma $分数正确分类，其中$ \ gamma \ in（0.5,1）$取决于信号 - 模型的噪声比（SNR）。当SNR随着顶点的数量转到无限的时，SNR慢慢地增长，我们的算法达到了弱的一致性，这改善了Ghoshdastidar和Dukkipati（2017）的上一个结果，用于非均匀的HSBMS。我们的谱算法由三个主要步骤组成：（1）HIFFEGE选择：选择某些尺寸的超高率，为诱导的子图像提供最大信噪比; （2）光谱分区：构造正则化邻接矩阵，并基于奇异向量获得近似分区; （3）纠正和合并：将超代表信息从邻接张于升级升级错误率保证。我们的算法的理论分析依赖于稀疏非均匀随机超图的邻接矩阵的浓度和正则化，这可以是独立的兴趣。

在这里，我们重新审视线性二次估计的经典问题，即估计线性动力系统从嘈杂测量的轨迹。当测量噪声是高斯时，庆祝的卡尔曼滤波器提供了最佳估计器，但是当一个人偏离这种假设时，广泛众所周知，众所周知会破裂。当噪音重尾时。许多临时启发式机启发式就是处理异常值的实践中。在开创性的工作中，Schick和Mitter在测量噪声是高斯的已知无穷无尽的扰动时给予了可证明的保证，并提出了一个可以获得类似的禁令的重要担保的重要问题。在这项工作中，我们给出了一个真正强大的过滤器：当甚至恒定的测量分数都存在对比腐败时，我们给出了线性二次估计的第一个强化保证。该框架可以模拟重型且甚至是非静止噪声过程。我们的算法在与知道损坏位置的最佳算法竞争的意义上强调了卡尔曼过滤器。我们的作品处于挑战性的贝叶斯环境，其中测量数量与我们需要估计的复杂性缩放。此外，在线性动态系统中过去信息随时间衰减。我们开发了一套新技术，以强大地提取不同时间步长和不同时间尺度的信息。

在这项工作中，我们解决了从$ \ epsilon $ -corrupted样本的$ k $组件稳健地学习高斯高斯混合模型的问题，以准确率$ \ widetilde {o}（\ epsilon）在总变化距离中持续$ k $，并在混合物上具有温和的假设。这种稳健性保证是最佳的积极因素因素。主要挑战是，大多数早期的作品依赖于在混合中学习各个组件，但在我们的环境中是不可能的，至少对于我们旨在保证的强大稳健性的类型是不可能的。相反，我们介绍了一个新的框架，我们称之为{\ em强烈的可观察性}，这为我们提供了一条规避这障碍的途径。

Mazumdar和Saha \ Cite {MS17A}的开创性论文引入了有关聚类的广泛工作，并带有嘈杂的查询。然而，尽管在问题上取得了重大进展，但所提出的方法至关重要地取决于了解基础全随随随之而来的甲骨文错误的确切概率。在这项工作中，我们开发了可靠的学习方法，这些方法可以忍受一般的半随机噪声，从而在定性上获得与全随机模型中最佳方法相同的保证。更具体地说，给定一组$ n $点带有未知的基础分区，我们可以查询点$ u，v $检查它们是否在同一群集中，但是有了概率$ p $，答案可能可以受到对抗的选择。我们在理论上显示信息$ o \ left（\ frac {nk \ log n} {（1-2p）^2} \ right）$查询足以学习任何足够大尺寸的群集。我们的主要结果是一种计算高效算法，可以用$ o \ left（\ frac {nk \ log n} {（1-2p）^2} \ right） + \ text {poly} \ left（\ log（\ log） n，k，\ frac {1} {1-2p} \ right）$查询，与完全随机模型中最知名算法的保证相匹配。作为我们方法的推论，我们为全随机模型开发了第一个无参数算法，并通过\ cite {ms17a}回答一个空的问题。

We study the fundamental task of outlier-robust mean estimation for heavy-tailed distributions in the presence of sparsity. Specifically, given a small number of corrupted samples from a high-dimensional heavy-tailed distribution whose mean $\mu$ is guaranteed to be sparse, the goal is to efficiently compute a hypothesis that accurately approximates $\mu$ with high probability. Prior work had obtained efficient algorithms for robust sparse mean estimation of light-tailed distributions. In this work, we give the first sample-efficient and polynomial-time robust sparse mean estimator for heavy-tailed distributions under mild moment assumptions. Our algorithm achieves the optimal asymptotic error using a number of samples scaling logarithmically with the ambient dimension. Importantly, the sample complexity of our method is optimal as a function of the failure probability $\tau$, having an additive $\log(1/\tau)$ dependence. Our algorithm leverages the stability-based approach from the algorithmic robust statistics literature, with crucial (and necessary) adaptations required in our setting. Our analysis may be of independent interest, involving the delicate design of a (non-spectral) decomposition for positive semi-definite matrices satisfying certain sparsity properties.

我们研究了$ N $节点上稳健地估计参数$ P $'ENY ACLY图的问题，其中$ \ gamma $小点的节点可能是对抗的。在展示规范估计器的缺陷之后，我们设计了一种计算上有效的频谱算法，估计$ P $高精度$ \ tilde o（\ sqrt {p（1-p）} / n + \ gamma \ sqrt {p（1-p）} / \ sqrt {n} + \ gamma / n）$ for $ \ gamma <1/60 $。此外，我们为所有$ \ Gamma <1/2 $，信息定理限制提供了一种效率低下的算法。最后，我们证明了几乎匹配的统计下限，表明我们的算法的错误是最佳的对数因子。

我们给出了\ emph {list-codobable协方差估计}的第一个多项式时间算法。对于任何$ \ alpha> 0 $，我们的算法获取输入样本$ y \ subseteq \ subseteq \ mathbb {r}^d $ size $ n \ geq d^{\ mathsf {poly}（1/\ alpha）} $获得通过对抗损坏I.I.D的$（1- \ alpha）n $点。从高斯分布中的样本$ x $ size $ n $，其未知平均值$ \ mu _*$和协方差$ \ sigma _*$。在$ n^{\ mathsf {poly}（1/\ alpha）} $ time中，它输出$ k = k（\ alpha）=（1/\ alpha）^{\ mathsf {poly}的常数大小列表（1/\ alpha）} $候选参数，具有高概率，包含$（\ hat {\ mu}，\ hat {\ sigma}）$，使得总变化距离$ tv（\ Mathcal {n}（n}）（n}（n}）（ \ mu _*，\ sigma _*），\ Mathcal {n}（\ hat {\ mu}，\ hat {\ sigma}））<1-o _ {\ alpha}（1）$。这是距离的统计上最强的概念，意味着具有独立尺寸误差的参数的乘法光谱和相对Frobenius距离近似。我们的算法更普遍地适用于$（1- \ alpha）$ - 任何具有低度平方总和证书的分布$ d $的损坏，这是两个自然分析属性的：1）一维边际和抗浓度2）2度多项式的超收缩率。在我们工作之前，估计可定性设置的协方差的唯一已知结果是针对Karmarkar，Klivans和Kothari（2019），Raghavendra和Yau（2019和2019和2019和2019和2019年）的特殊情况。 2020年）和巴克西（Bakshi）和科塔里（Kothari）（2020年）。这些结果需要超级物理时间，以在基础维度中获得任何子构误差。我们的结果意味着第一个多项式\ emph {extcect}算法，用于列表可解码的线性回归和子空间恢复，尤其允许获得$ 2^{ - \ Mathsf { - \ Mathsf {poly}（d）} $多项式时间错误。我们的结果还意味着改进了用于聚类非球体混合物的算法。

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

本文研究了一般D-均匀的HyperGraph随机块模型（D-HSBM）中精确恢复的基本限制，其中n个节点被分配到具有相对大小的k差异群落中（p1，...，pk）。具有基数d的节点的每个子集都是独立生成的，作为订单-D超边，其一定概率取决于D节点所属的地面真相群落。目标是根据观察到的超图准确地恢复K隐藏的社区。我们表明存在一个尖锐的阈值，因此可以在阈值之上实现精确的恢复，而不可能在阈值以下（除了将精确指定的小参数制度之外）。该阈值是根据我们称为社区之间普遍的Chernoff-Hellinger分歧的数量来表示的。我们对该通用模型的结果恢复了标准SBM和D-HSBM的先前结果，其中两个对称群落作为特殊情况。在证明我们的可实现结果的途径中，我们开发了一种符合阈值的多项式两阶段算法。第一阶段采用某种超图光谱聚类方法来获得社区的粗略估计，第二阶段通过局部细化步骤单独完善每个节点，以确保精确恢复。

我们考虑从数据学习树结构ising模型的问题，使得使用模型计算的后续预测是准确的。具体而言，我们的目标是学习一个模型，使得小组变量$ S $的后海报$ p（x_i | x_s）$。自推出超过50年以来，有效计算最大似然树的Chow-Liu算法一直是学习树结构图形模型的基准算法。 [BK19]示出了关于以预测的局部总变化损耗的CHOW-LIU算法的样本复杂性的界限。虽然这些结果表明，即使在恢复真正的基础图中也可以学习有用的模型是不可能的，它们的绑定取决于相互作用的最大强度，因此不会达到信息理论的最佳选择。在本文中，我们介绍了一种新的算法，仔细结合了Chow-Liu算法的元素，以便在预测的损失下有效地和最佳地学习树ising模型。我们的算法对模型拼写和对抗损坏具有鲁棒性。相比之下，我们表明庆祝的Chow-Liu算法可以任意次优。