我们开发了一种高效的随机块模型中的弱恢复算法。该算法与随机块模型的Vanilla版本的最佳已知算法的统计保证匹配。从这个意义上讲,我们的结果表明,随机块模型没有稳健性。我们的工作受到最近的银行,Mohanty和Raghavendra(SODA 2021)的工作,为相应的区别问题提供了高效的算法。我们的算法及其分析显着脱离了以前的恢复。关键挑战是我们算法的特殊优化景观:种植的分区可能远非最佳意义,即完全不相关的解决方案可以实现相同的客观值。这种现象与PCA的BBP相转变的推出效应有关。据我们所知,我们的算法是第一个在非渐近设置中存在这种推出效果的鲁棒恢复。我们的算法是基于凸优化的框架的实例化(与平方和不同的不同),这对于其他鲁棒矩阵估计问题可能是有用的。我们的分析的副产物是一种通用技术,其提高了任意强大的弱恢复算法的成功(输入的随机性)从恒定(或缓慢消失)概率以指数高概率。
translated by 谷歌翻译
在这项工作中,我们研究了具有对抗性节点损坏的随机块模型中社区发现的问题。我们的主要结果是一种有效的算法,该算法可以忍受$ \ 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提供了可靠的算法。我们算法的核心是一个新的半决赛程序,它使用全局信息来鲁棒提高粗糙聚类的准确性。此外,我们表明我们的算法是双重的,因为它们在更具挑战性的噪声模型中起作用,该模型将对抗性腐败与无限制的单调变化混合在一起,从半随机模型中。
translated by 谷歌翻译
随机块模型(SBM)是一个随机图模型,其连接不同的顶点组不同。它被广泛用作研究聚类和社区检测的规范模型,并提供了肥沃的基础来研究组合统计和更普遍的数据科学中出现的信息理论和计算权衡。该专着调查了最近在SBM中建立社区检测的基本限制的最新发展,无论是在信息理论和计算方案方面,以及各种恢复要求,例如精确,部分和弱恢复。讨论的主要结果是在Chernoff-Hellinger阈值中进行精确恢复的相转换,Kesten-Stigum阈值弱恢复的相变,最佳的SNR - 单位信息折衷的部分恢复以及信息理论和信息理论之间的差距计算阈值。该专着给出了在寻求限制时开发的主要算法的原则推导,特别是通过绘制绘制,半定义编程,(线性化)信念传播,经典/非背带频谱和图形供电。还讨论了其他块模型的扩展,例如几何模型和一些开放问题。
translated by 谷歌翻译
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.
translated by 谷歌翻译
假设$ g $是根据所谓的HyperGraph随机块模型(HSBM)产生的,我们考虑了稀疏$ Q $均匀的HyperGraph $ G $中的社区检测问题。我们证明,基于非折线操作员的光谱方法具有很高的概率,可以降低到Angelini等人猜想的广义kesten-Stigum检测阈值。我们表征了稀疏HSBM的非背带操作员的频谱,并使用Ihara-Bass公式为超图提供有效的尺寸降低程序。结果,可以将稀疏HSBM的社区检测减少为$ 2N \ times 2n $非正态矩阵的特征向量问题,该矩阵从邻接矩阵和超级格雷普的学位矩阵中构建。据我们所知,这是第一种可证明,有效的光谱算法,它可以根据一般对称概率张量生成$ K $块的HSBMS阈值。
translated by 谷歌翻译
分析大型随机矩阵的浓度是多种领域的常见任务。给定独立的随机变量,许多工具可用于分析随机矩阵,其条目在变量中是线性的,例如基质 - 伯恩斯坦不平等。但是,在许多应用中,我们需要分析其条目是变量中多项式的随机矩阵。这些自然出现在光谱算法的分析中,例如霍普金斯等人。 [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]使用痕量功率方法的非平地应用,并且是其工作中的核心组成部分。我们希望我们的框架对涉及非线性随机矩阵浓度现象的其他应用有帮助。
translated by 谷歌翻译
我们根据计算一个扎根于每个顶点的某个加权树的家族而构成的相似性得分提出了一种有效的图形匹配算法。对于两个erd \ h {o} s-r \'enyi图$ \ mathcal {g}(n,q)$,其边缘通过潜在顶点通信相关联,我们表明该算法正确地匹配了所有范围的范围,除了所有的vertices分数外,有了很高的概率,前提是$ nq \ to \ infty $,而边缘相关系数$ \ rho $满足$ \ rho^2> \ alpha \ ailpha \大约0.338 $,其中$ \ alpha $是Otter的树木计数常数。此外,在理论上是必需的额外条件下,可以精确地匹配。这是第一个以显式常数相关性成功的多项式图匹配算法,并适用于稀疏和密集图。相比之下,以前的方法要么需要$ \ rho = 1-o(1)$,要么仅限于稀疏图。该算法的症结是一个经过精心策划的植根树的家族,称为吊灯,它可以有效地从同一树的计数中提取图形相关性,同时抑制不同树木之间的不良相关性。
translated by 谷歌翻译
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.
translated by 谷歌翻译
本文讨论了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图与具有恒定相关性的相关性图与高概率相关性的确切匹配。该算法是基于比较的比较与图形顶点关联的分区树。
translated by 谷歌翻译
随机奇异值分解(RSVD)是用于计算大型数据矩阵截断的SVD的一类计算算法。给定A $ n \ times n $对称矩阵$ \ mathbf {m} $,原型RSVD算法输出通过计算$ \ mathbf {m mathbf {m} $的$ k $引导singular vectors的近似m}^{g} \ mathbf {g} $;这里$ g \ geq 1 $是一个整数,$ \ mathbf {g} \ in \ mathbb {r}^{n \ times k} $是一个随机的高斯素描矩阵。在本文中,我们研究了一般的“信号加上噪声”框架下的RSVD的统计特性,即,观察到的矩阵$ \ hat {\ mathbf {m}} $被认为是某种真实但未知的加法扰动信号矩阵$ \ mathbf {m} $。我们首先得出$ \ ell_2 $(频谱规范)和$ \ ell_ {2 \ to \ infty} $(最大行行列$ \ ell_2 $ norm)$ \ hat {\ hat {\ Mathbf {M}} $和信号矩阵$ \ Mathbf {M} $的真实单数向量。这些上限取决于信噪比(SNR)和功率迭代$ g $的数量。观察到一个相变现象,其中较小的SNR需要较大的$ g $值以保证$ \ ell_2 $和$ \ ell_ {2 \ to \ fo \ infty} $ distances的收敛。我们还表明,每当噪声矩阵满足一定的痕量生长条件时,这些相变发生的$ g $的阈值都会很清晰。最后,我们得出了近似奇异向量的行波和近似矩阵的进入波动的正常近似。我们通过将RSVD的几乎最佳性能保证在应用于三个统计推断问题的情况下,即社区检测,矩阵完成和主要的组件分析,并使用缺失的数据来说明我们的理论结果。
translated by 谷歌翻译
随着大型网络在重要领域的相关领域的相关性,例如对疾病传播的联系网络的研究,或社交网络对地缘政治的影响,已经有必要研究可扩展到非常大的网络的机器学习工具,通常包含数百万节点。一种主要类别可扩展算法称为网络表示学习或网络嵌入。这些算法尝试通过首次运行多个随机散步,然后使用观察到的随机步行段中的每对节点的共同数量来学习网络功能(例如〜节点)的表示,以获得一些节点的低维表示欧几里德空间。本文的目的是严格地了解两个主要算法,深途化和Node2VEC的性能,以恢复与地面真理社区的规范网络模型的社区。根据图的稀疏性,我们发现所需的随机步道段的长度,使得相应的观察到的共生窗口能够对底层社区分配的几乎精确恢复。我们证明,考虑到一些固定的共同发生窗口,使用随机散步的Node2Vec与低横向概率的随机散步可以相比,与使用简单随机散步的深度扫视相比,稀疏网络可以成功。此外,如果稀疏参数低,我们提供了证据表明这些算法几乎完全恢复可能不会成功。该分析需要开发用于对具有底层低级结构的随机网络计数的通用工具,这与独立兴趣。
translated by 谷歌翻译
高维统计数据的一个基本目标是检测或恢复嘈杂数据中隐藏的种植结构(例如低级别矩阵)。越来越多的工作研究低级多项式作为此类问题的计算模型的限制模型:在各种情况下,数据的低级多项式可以与最知名的多项式时间算法的统计性能相匹配。先前的工作已经研究了低度多项式的力量,以检测隐藏结构的存在。在这项工作中,我们将这些方法扩展到解决估计和恢复问题(而不是检测)。对于大量的“信号加噪声”问题,我们给出了一个用户友好的下限,以获得最佳的均衡误差。据我们所知,这些是建立相关检测问题的恢复问题低度硬度的第一个结果。作为应用,我们对种植的子静脉和种植的密集子图问题的低度最小平方误差进行了严格的特征,在两种情况下都解决了有关恢复的计算复杂性的开放问题(在低度框架中)。
translated by 谷歌翻译
我们研究了在存在$ \ 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 $。我们的算法遵循基于方形的总和,对算法方法的证明。我们通过统计查询和低度多项式测试的下限来补充上限,提供了证据,表明我们算法实现的样本时间 - 错误权衡在质量上是最好的。
translated by 谷歌翻译
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}$.
translated by 谷歌翻译
我们重新审视量子状态认证的基本问题:给定混合状态$ \ rho \中的副本\ mathbb {c} ^ {d \ times d} $和混合状态$ \ sigma $的描述,决定是否$ \ sigma = \ rho $或$ \ | \ sigma - \ rho \ | _ {\ mathsf {tr}} \ ge \ epsilon $。当$ \ sigma $最大化时,这是混合性测试,众所周知,$ \ omega(d ^ {\ theta(1)} / \ epsilon ^ 2)$副本是必要的,所以确切的指数取决于测量类型学习者可以使[OW15,BCL20],并且在许多这些设置中,有一个匹配的上限[OW15,Bow19,BCL20]。可以避免这种$ d ^ {\ theta(1)} $依赖于某些类型的混合状态$ \ sigma $,例如。大约低等级的人?更常见地,是否存在一个简单的功能$ f:\ mathbb {c} ^ {d \ times d} \ to \ mathbb {r} _ {\ ge 0} $,其中一个人可以显示$ \ theta(f( \ sigma)/ \ epsilon ^ 2)$副本是必要的,并且足以就任何$ \ sigma $的国家认证?这种实例 - 最佳边界在经典分布测试的背景下是已知的,例如, [VV17]。在这里,我们为量子设置提供了这个性质的第一个界限,显示(达到日志因子),即使用非接受不连贯测量的状态认证的复杂性复杂性基本上是通过复制复杂性进行诸如$ \ sigma $之间的保真度的复杂性。和最大混合的状态。令人惊讶的是,我们的界限与经典问题的实例基本上不同,展示了两个设置之间的定性差异。
translated by 谷歌翻译
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.
translated by 谷歌翻译
我们提出了改进的算法,并为身份测试$ n $维分布的问题提供了统计和计算下限。在身份测试问题中,我们将作为输入作为显式分发$ \ mu $,$ \ varepsilon> 0 $,并访问对隐藏分布$ \ pi $的采样甲骨文。目标是区分两个分布$ \ mu $和$ \ pi $是相同的还是至少$ \ varepsilon $ -far分开。当仅从隐藏分布$ \ pi $中访问完整样本时,众所周知,可能需要许多样本,因此以前的作品已经研究了身份测试,并额外访问了各种有条件采样牙齿。我们在这里考虑一个明显弱的条件采样甲骨文,称为坐标Oracle,并在此新模型中提供了身份测试问题的相当完整的计算和统计表征。我们证明,如果一个称为熵的分析属性为可见分布$ \ mu $保留,那么对于任何使用$ \ tilde {o}(n/\ tilde {o}),有一个有效的身份测试算法Varepsilon)$查询坐标Oracle。熵的近似张力是一种经典的工具,用于证明马尔可夫链的最佳混合时间边界用于高维分布,并且最近通过光谱独立性为许多分布族建立了最佳的混合时间。我们将算法结果与匹配的$ \ omega(n/\ varepsilon)$统计下键进行匹配的算法结果补充,以供坐标Oracle下的查询数量。我们还证明了一个计算相变:对于$ \ {+1,-1,-1 \}^n $以上的稀疏抗抗铁磁性模型,在熵失败的近似张力失败的状态下,除非RP = np,否则没有有效的身份测试算法。
translated by 谷歌翻译
社区检测是网络科学中的一个基本问题。在本文中,我们考虑了从$ HyperGraph $ $ $ $ $ $ $ $ $ $ $ $ $ $ $(HSBM)中绘制的HyperGraphs中的社区检测,重点是精确的社区恢复。在整个超图未知的情况下,我们研究了多项式时间算法以进行社区检测的性能。取而代之的是,我们获得了$相似性$ $ $ $ $ $ $ w $,其中$ w_ {ij} $报告包含$ i $和$ j $的超补品的数量。在此信息模型下,Kim,Bandeira和Goemans [KBG18]确定了信息理论阈值,以进行精确恢复,并提出了他们认为是最佳的半决赛编程松弛。在本文中,我们确认了这个猜想。我们还表明,一种简单,高效的光谱算法是最佳的,将光谱算法作为选择方法。我们对光谱算法的分析至关重要地依赖于$ w $的特征向量上的强$ entrywise $界限。我们的边界灵感来自Abbe,Fan,Wang和Zhong [AFWZ20]的工作,他们开发了具有独立条目的对称矩阵的特征向量的进入界。尽管相似性矩阵的依赖性结构复杂,但我们证明了相似的入口保证。
translated by 谷歌翻译
我们给出了\ 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)} $多项式时间错误。我们的结果还意味着改进了用于聚类非球体混合物的算法。
translated by 谷歌翻译
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.
translated by 谷歌翻译