权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Combinatorial Optimization, Spin Models, and the Geometry of Sparse Random Graphs

组合优化、自旋模型和稀疏随机图的几何形状

基本信息

批准号：
1613091
负责人：
Amir Dembo
金额：
$ 60万
依托单位：
Stanford University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2016
资助国家：
美国
起止时间：
2016-07-01 至 2021-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1613091&HistoricalAwards=false
关键词：
Combinatorial Optimization Spin Models Geometry

项目摘要

Networks and graphs are ubiquitous mathematical models to describe important systems (social networks, transportation networks, and biological systems, among others). A network is comprised of a certain number of objects (normally referred to as 'nodes' or 'vertices') connected by links of various importance ('edges' and their 'weights'). Analyzing network data is notoriously challenging. An important task is to group the vertices into subgroups such that each subgroup is highly connected, and any two subgroups have only loose interconnections. Even if one is only trying to identify merely two subgroups (known as the min-bisection problem), no efficient algorithm is known to partition the nodes of large graphs in general. The situation changes when one considers that the graphs might have a random structure. Indeed, for many reasonable probabilistic models on graphs, there appear to be efficient algorithms to solve the min-bisection problem. This project will develop our fundamental understanding of these probabilistic models and will study efficient algorithms to treat them.The project focuses on various models of sparse random graphs, the simplest being the Erdos-Renyi (independent edges) random graph, with bounded average degree. Many statistical inference tasks can be addressed by suitably defined combinatorial optimization problems. For instance, the min-bisection problem requires to find a balanced partition of the vertex set that minimizes the number of edges across the partition. These optimization problems are associated to certain Gibbs measures on the underlying graph, from which the optimizers are recovered as ground states. Statistical physicists conjectured that these Gibbs measures are asymptotically equivalent (for random graphs) to Gibbs measures of suitably defined spin glass models. This project aims at establishing this connection on a firm basis and exploiting it to study the structure of large random graphs. It has also recently been suggested that semidefinite-programming relaxations for the same problems can be studied through other Gibbs measures (with vector spins). Studying these spin models will improve our understanding of efficient algorithms for solving these tasks.

网络和图是描述重要系统(社会网络、交通网络和生物系统等)的普遍数学模型。网络由一定数量的对象(通常称为“节点”或“顶点”)组成，这些对象通过不同重要性的链接(“边”及其“权重”)相连。分析网络数据是出了名的挑战。一项重要的任务是将顶点分组为子组，使每个子组高度相连，而任何两个子组只有松散的互连。即使只试图识别两个子群(称为最小二等分问题)，通常也没有有效的算法来划分大图的节点。当人们考虑到图可能具有随机结构时，情况就会改变。事实上，对于图上的许多合理的概率模型，似乎都有有效的算法来解决最小二分问题。这个项目将加深我们对这些概率模型的基本理解，并将研究处理它们的有效算法。该项目专注于稀疏随机图的各种模型，最简单的是具有有界平均度的Erdos-Renyi(独立边)随机图。许多统计推理任务可以通过适当定义的组合优化问题来解决。例如，最小二分问题需要找到顶点集的一个平衡划分，以最小化该划分上的边数。这些优化问题与基础图上的某些Gibbs度量相关联，从这些Gibbs度量中，优化器被恢复为基态。统计物理学家推测，这些Gibbs度量(对于随机图)与适当定义的自旋玻璃模型的Gibbs度量渐近等价。这个项目的目的是在坚实的基础上建立这种联系，并利用它来研究大型随机图的结构。最近也有人提出，同样问题的半定规划松弛可以通过其他吉布斯度量(带有向量自旋)来研究。研究这些自旋模型将提高我们对解决这些任务的有效算法的理解。

项目成果

期刊论文数量（15）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Discussion of: “Nonparametric regression using deep neural networks with ReLU activation function”

DOI：
10.1214/19-aos1910
发表时间：
2020-08
期刊：
The Annals of Statistics
影响因子：
0
作者：
B. Ghorbani;Song Mei;Theodor Misiakiewicz;A. Montanari
通讯作者：
B. Ghorbani;Song Mei;Theodor Misiakiewicz;A. Montanari

Dynamics for Spherical Spin Glasses: Disorder Dependent Initial Conditions

球形旋转玻璃的动力学：无序相关的初始条件

DOI：
10.1007/s10955-020-02587-z
发表时间：
2020
期刊：
Journal of Statistical Physics
影响因子：
1.6
作者：
Dembo, Amir;Subag, Eliran
通讯作者：
Subag, Eliran

On the Connection Between Learning Two-Layer Neural Networks and Tensor Decomposition

论学习两层神经网络与张量分解的联系

DOI：
发表时间：
2019
期刊：
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics
影响因子：
0
作者：
Marco Mondelli, Andrea Montanari
通讯作者：
Marco Mondelli, Andrea Montanari

How well do local algorithms solve semidefinite programs?

局部算法求解半定程序的效果如何？

DOI：
10.1145/3055399.3055451
发表时间：
2017
期刊：
STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
0
作者：
Fan, Zhou;Montanari, Andrea
通讯作者：
Montanari, Andrea

State evolution for approximate message passing with non-separable functions