我们考虑从数据学习树结构ising模型的问题,使得使用模型计算的后续预测是准确的。具体而言,我们的目标是学习一个模型,使得小组变量$ S $的后海报$ p(x_i | x_s)$。自推出超过50年以来,有效计算最大似然树的Chow-Liu算法一直是学习树结构图形模型的基准算法。 [BK19]示出了关于以预测的局部总变化损耗的CHOW-LIU算法的样本复杂性的界限。虽然这些结果表明,即使在恢复真正的基础图中也可以学习有用的模型是不可能的,它们的绑定取决于相互作用的最大强度,因此不会达到信息理论的最佳选择。在本文中,我们介绍了一种新的算法,仔细结合了Chow-Liu算法的元素,以便在预测的损失下有效地和最佳地学习树ising模型。我们的算法对模型拼写和对抗损坏具有鲁棒性。相比之下,我们表明庆祝的Chow-Liu算法可以任意次优。
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 谷歌翻译
我们根据计算一个扎根于每个顶点的某个加权树的家族而构成的相似性得分提出了一种有效的图形匹配算法。对于两个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 consider the problem of learning the structure underlying a Gaussian graphical model when the variables (or subsets thereof) are corrupted by independent noise. A recent line of work establishes that even for tree-structured graphical models, only partial structure recovery is possible and goes on to devise algorithms to identify the structure up to an (unavoidable) equivalence class of trees. We extend these results beyond trees and consider the model selection problem under noise for non tree-structured graphs, as tree graphs cannot model several real-world scenarios. Although unidentifiable, we show that, like the tree-structured graphs, the ambiguity is limited to an equivalence class. This limited ambiguity can help provide meaningful clustering information (even with noise), which is helpful in computer and social networks, protein-protein interaction networks, and power networks. Furthermore, we devise an algorithm based on a novel ancestral testing method for recovering the equivalence class. We complement these results with finite sample guarantees for the algorithm in the high-dimensional regime.
translated by 谷歌翻译
随机块模型(SBM)是一个随机图模型,其连接不同的顶点组不同。它被广泛用作研究聚类和社区检测的规范模型,并提供了肥沃的基础来研究组合统计和更普遍的数据科学中出现的信息理论和计算权衡。该专着调查了最近在SBM中建立社区检测的基本限制的最新发展,无论是在信息理论和计算方案方面,以及各种恢复要求,例如精确,部分和弱恢复。讨论的主要结果是在Chernoff-Hellinger阈值中进行精确恢复的相转换,Kesten-Stigum阈值弱恢复的相变,最佳的SNR - 单位信息折衷的部分恢复以及信息理论和信息理论之间的差距计算阈值。该专着给出了在寻求限制时开发的主要算法的原则推导,特别是通过绘制绘制,半定义编程,(线性化)信念传播,经典/非背带频谱和图形供电。还讨论了其他块模型的扩展,例如几何模型和一些开放问题。
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 谷歌翻译
我们开发了一种高效的随机块模型中的弱恢复算法。该算法与随机块模型的Vanilla版本的最佳已知算法的统计保证匹配。从这个意义上讲,我们的结果表明,随机块模型没有稳健性。我们的工作受到最近的银行,Mohanty和Raghavendra(SODA 2021)的工作,为相应的区别问题提供了高效的算法。我们的算法及其分析显着脱离了以前的恢复。关键挑战是我们算法的特殊优化景观:种植的分区可能远非最佳意义,即完全不相关的解决方案可以实现相同的客观值。这种现象与PCA的BBP相转变的推出效应有关。据我们所知,我们的算法是第一个在非渐近设置中存在这种推出效果的鲁棒恢复。我们的算法是基于凸优化的框架的实例化(与平方和不同的不同),这对于其他鲁棒矩阵估计问题可能是有用的。我们的分析的副产物是一种通用技术,其提高了任意强大的弱恢复算法的成功(输入的随机性)从恒定(或缓慢消失)概率以指数高概率。
translated by 谷歌翻译
图形上的分层聚类是数据挖掘和机器学习中的一项基本任务,并在系统发育学,社交网络分析和信息检索等领域中进行了应用。具体而言,我们考虑了由于Dasgupta引起的层次聚类的最近普及的目标函数。以前(大约)最小化此目标函数的算法需要线性时间/空间复杂性。在许多应用程序中,底层图的大小可能很大,即使使用线性时间/空间算法,也可以在计算上具有挑战性。结果,人们对设计只能使用sublinear资源执行全局计算的算法有浓厚的兴趣。这项工作的重点是在三个经过良好的sublinear计算模型下研究大量图的层次聚类,分别侧重于时空,时间和通信,作为要优化的主要资源:(1)(动态)流模型。边缘作为流,(2)查询模型表示,其中使用邻居和度查询查询图形,(3)MPC模型,其中图边缘通过通信通道连接的几台机器进行了分区。我们在上面的所有三个模型中设计用于层次聚类的sublinear算法。我们算法结果的核心是图表中的剪切方面的视图,这使我们能够使用宽松的剪刀示意图进行分层聚类,同时仅引入目标函数中的较小失真。然后,我们的主要算法贡献是如何在查询模型和MPC模型中有效地构建所需形式的切割稀疏器。我们通过建立几乎匹配的下限来补充我们的算法结果,该界限排除了在每个模型中设计更好的算法的可能性。
translated by 谷歌翻译
在本文中,我们提出了一个基于树张量网状状态的密度估计框架。所提出的方法包括使用Chow-Liu算法确定树拓扑,并获得线性系统通过草图技术定义张量 - 网络组件的线性系统。开发了草图功能的新颖选择,以考虑包含循环的图形模型。提供样品复杂性保证,并通过数值实验进一步证实。
translated by 谷歌翻译
由于机器学习,统计和科学的应用,多边缘最佳运输(MOT)引起了极大的兴趣。但是,在大多数应用中,MOT的成功受到缺乏有效算法的严重限制。实际上,MOT一般需要在边际K及其支撑大小n的数量中指数时间n。本文开发了一个关于“结构”在poly(n,k)时间中可溶解的一般理论。我们开发了一个统一的算法框架,用于通过表征不同算法所需的“结构”来解决poly(n,k)时间中的MOT,这是根据双重可行性甲骨文的简单变体所需的。该框架有几个好处。首先,它使我们能够证明当前是最流行的MOT算法的Sinkhorn算法比其他算法要在poly(n,k)时间中求解MOT所需的结构更严格。其次,我们的框架使得为给定的MOT问题开发poly(n,k)时间算法变得更加简单。特别是(大约)解决双重可行性Oracle是必要和足够的 - 这更适合标准算法技术。我们通过为三个通用类成本结构类别的poly(n,k)时间算法开发poly(n,k)时间算法来说明这种易用性:(1)图形结构; (2)设定优化结构; (3)低阶和稀疏结构。对于结构(1),我们恢复了Sindhorn具有poly(n,k)运行时的已知结果;此外,我们为计算精确且稀疏的解决方案提供了第一个poly(n,k)时间算法。对于结构(2) - (3),我们给出了第一个poly(n,k)时间算法,甚至用于近似计算。这三个结构一起涵盖了许多MOT的当前应用。
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 谷歌翻译
高维统计数据的一个基本目标是检测或恢复嘈杂数据中隐藏的种植结构(例如低级别矩阵)。越来越多的工作研究低级多项式作为此类问题的计算模型的限制模型:在各种情况下,数据的低级多项式可以与最知名的多项式时间算法的统计性能相匹配。先前的工作已经研究了低度多项式的力量,以检测隐藏结构的存在。在这项工作中,我们将这些方法扩展到解决估计和恢复问题(而不是检测)。对于大量的“信号加噪声”问题,我们给出了一个用户友好的下限,以获得最佳的均衡误差。据我们所知,这些是建立相关检测问题的恢复问题低度硬度的第一个结果。作为应用,我们对种植的子静脉和种植的密集子图问题的低度最小平方误差进行了严格的特征,在两种情况下都解决了有关恢复的计算复杂性的开放问题(在低度框架中)。
translated by 谷歌翻译
Motivated by alignment of correlated sparse random graphs, we introduce a hypothesis testing problem of deciding whether or not two random trees are correlated. We obtain sufficient conditions under which this testing is impossible or feasible. We propose MPAlign, a message-passing algorithm for graph alignment inspired by the tree correlation detection problem. We prove MPAlign to succeed in polynomial time at partial alignment whenever tree detection is feasible. As a result our analysis of tree detection reveals new ranges of parameters for which partial alignment of sparse random graphs is feasible in polynomial time. We then conjecture that graph alignment is not feasible in polynomial time when the associated tree detection problem is impossible. If true, this conjecture together with our sufficient conditions on tree detection impossibility would imply the existence of a hard phase for graph alignment, i.e. a parameter range where alignment cannot be done in polynomial time even though it is known to be feasible in non-polynomial time.
translated by 谷歌翻译
我们研究了清单可解放的平均估计问题,而对手可能会破坏大多数数据集。具体来说,我们在$ \ mathbb {r} ^ $和参数$ 0 <\ alpha <\ frac 1 2 $中给出了一个$ $ n $ points的$ t $ points。$ \ alpha $ -flaction的点$ t $是iid来自乖巧的分发$ \ Mathcal {D} $的样本,剩余的$(1- \ alpha)$ - 分数是任意的。目标是输出小型的vectors列表,其中至少一个接近$ \ mathcal {d} $的均值。我们开发新的算法,用于列出可解码的平均值估计,实现几乎最佳的统计保证,运行时间$ O(n ^ {1 + \ epsilon_0} d)$,适用于任何固定$ \ epsilon_0> 0 $。所有先前的此问题算法都有额外的多项式因素在$ \ frac 1 \ alpha $。我们与额外技术一起利用此结果,以获得用于聚类混合物的第一个近几个线性时间算法,用于分开的良好表现良好的分布,几乎匹配谱方法的统计保证。先前的聚类算法本身依赖于$ k $ -pca的应用程序,从而产生$ \ omega(n d k)$的运行时。这标志着近二十年来这个基本统计问题的第一次运行时间改进。我们的方法的起点是基于单次矩阵乘法权重激发电位减少的$ \ Alpha \至1 $制度中的新颖和更简单的近线性时间较强的估计算法。在Diakonikolas等人的迭代多滤波技术的背景下,我们迫切地利用了这种新的算法框架。 '18,'20,提供一种使用一维投影的同时群集和下群点的方法 - 因此,绕过先前算法所需的$ k $ -pca子程序。
translated by 谷歌翻译
我们研究了学习哈密顿$ h $ to precision $ \ varepsilon $的问题,假设我们将获得其gibbs state $ \ rho = \ exp( - \ beta h)/\ operatoratorname {tr}(\ exp(\ exp)( - \ beta h))$在已知的反温度$ \ beta $处。 Anshu,Arunachalam,Kuwahara和Soleimanifar(Nature Physics,2021,Arxiv:2004.07266)最近研究了此问题的样品复杂性(需要$ \ rho $的副本数量)。在高温(低$ \ beta $)制度中,他们的算法具有样品复杂性poly poly $(n,1/\ beta,1/\ varepsilon)$,并且可以用多项式但次优的时间复杂性实现。在本文中,我们研究了更一般的哈密顿人的同样问题。我们展示了如何学习哈密顿量的系数到错误$ \ varepsilon $带有样本复杂性$ s = o(\ log n/(\ beta \ varepsilon)^{2})$和样本大小的时间复杂性,$ o(s n)$。此外,我们证明了匹配的下限,表明我们算法的样品复杂性是最佳的,因此我们的时间复杂性也是最佳的。在附录中,我们证明,几乎可以使用相同的算法来从实时进化的统一$ e^{ - it H} $中学习$ h $,其中具有相似的示例和时间复杂性的小$ t $制度。
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 谷歌翻译
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 谷歌翻译
Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency -- given $n$ input points, most kernel-based algorithms need to materialize the full $n \times n$ kernel matrix before performing any subsequent computation, thus incurring $\Omega(n^2)$ runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts. We break the quadratic barrier and obtain $\textit{subquadratic}$ time algorithms for several fundamental linear-algebraic and graph processing primitives, including approximating the top eigenvalue and eigenvector, spectral sparsification, solving linear systems, local clustering, low-rank approximation, arboricity estimation and counting weighted triangles. We build on the recent Kernel Density Estimation framework, which (after preprocessing in time subquadratic in $n$) can return estimates of row/column sums of the kernel matrix. In particular, we develop efficient reductions from $\textit{weighted vertex}$ and $\textit{weighted edge sampling}$ on kernel graphs, $\textit{simulating random walks}$ on kernel graphs, and $\textit{importance sampling}$ on matrices to Kernel Density Estimation and show that we can generate samples from these distributions in $\textit{sublinear}$ (in the support of the distribution) time. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest. We empirically demonstrate the efficacy of our algorithms on low-rank approximation (LRA) and spectral sparsification, where we observe a $\textbf{9x}$ decrease in the number of kernel evaluations over baselines for LRA and a $\textbf{41x}$ reduction in the graph size for spectral sparsification.
translated by 谷歌翻译
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.
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 谷歌翻译