How well do local algorithms solve semidefinite programs?
How well do local algorithms solve semidefinite programs?
复制标题
局部算法求解半定程序的效果如何？
DOI：
10.1145/3055399.3055451
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Montanari, Andrea
中科院分区：
文献类型：
--
作者：
Fan, Zhou;Montanari, Andrea
来自高维统计和机器学习的几个概率模型揭示了一个有趣但知之甚少的二分法。要么简单的局部算法成功地估计感兴趣的对象，甚至复杂的半定规划（SDP）松弛失败。为了探索这一现象，我们研究了经典的最小图二分问题的SDP松弛，当应用于平均度d > 1的Erdos-Renyi随机图时，得到了几类结果.首先，我们使用一个双重见证结构（使用所谓的图的非回溯矩阵）来上界SDP值。其次，我们证明了一个简单的局部算法近似解决SDP的上限的一个因素2d^2/（2d^2 + d - 1）。特别地，局部算法至多是8/9次优的，并且对于大的度是1 + O（d^-1）次优的.然后我们分析了一个更复杂的局部算法，它根据有限Galton-Watson（GW）树上的调和测度来聚合信息.由此产生的下限表示的GW树的电导和匹配令人惊讶的是，以及经验确定的SDP值大规模的Erdos-Renyi graphs.We最后考虑种植分区模型。在这种情况下，已知纯局部算法会失败，但如果有少量辅助信息可用，它们确实会成功。我们的研究结果意味着在这个模型中使用SDP的部分恢复的阈值的定量界限。
Several probabilistic models from high-dimensional statistics and machine learning reveal an intriguing and yet poorly understood dichotomy. Either simple local algorithms succeed in estimating the object of interest, or even sophisticated semi-definite programming (SDP) relaxations fail. In order to explore this phenomenon, we study a classical SDP relaxation of the minimum graph bisection problem, when applied to Erdos-Renyi random graphs with bounded average degree d > 1, and obtain several types of results. First, we use a dual witness construction (using the so-called non-backtracking matrix of the graph) to upper bound the SDP value. Second, we prove that a simple local algorithm approximately solves the SDP to within a factor 2d^2/(2d^2 + d - 1) of the upper bound. In particular, the local algorithm is at most 8/9 suboptimal, and 1 + O(d^-1) suboptimal for large degree.We then analyze a more sophisticated local algorithm, which aggregates information according to the harmonic measure on the limiting Galton-Watson (GW) tree. The resulting lower bound is expressed in terms of the conductance of the GW tree and matches surprisingly well the empirically determined SDP values on large-scale Erdos-Renyi graphs.We finally consider the planted partition model. In this case, purely local algorithms are known to fail, but they do succeed if a small amount of side information is available. Our results imply quantitative bounds on the threshold for partial recovery using SDP in this model.
登录
查看更多内容
在稀疏图中找到一个社区
影响因子：
1.6
作者：
A. Montanari
通讯作者：
A. Montanari
影响因子：
2.5
作者：
Hajek, Bruce;Wu, Yihong;Xu, Jiaming
通讯作者：
Xu, Jiaming
有关树上随机游走的未解决问题
DOI：
10.1007/978-1-4612-1862-3_18
发表时间：
1997
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
R. Lyons;Robin Pemantle;Y. Peres
通讯作者：
Y. Peres
DOI：
--
发表时间：
2008
期刊：
Comb.
影响因子：
--
作者：
G. Elek
通讯作者：
G. Elek
影响因子：
2.3
作者：
Rahman, Mustazee;Virag, Balint
通讯作者：
Virag, Balint