AF: Small: Markov Chain Algorithms for Problems from Computer Science and Statistical Physics

AF：小：计算机科学和统计物理问题的马尔可夫链算法

• 批准号: 1526900
• 负责人: Dana Randall
• 金额: $ 40万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-08-01 至 2020-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1526900&HistoricalAwards=false
• 关键词: AF; Small; Markov; Chain; Algorithms

Sampling algorithms based on Markov chains are used across the sciences, primarily for approximate counting, combinatorial optimization and modeling. These algorithms use random walks to explore a large state space, and determining their convergence time is typically the critical step for establishing the efficiency of many approximation algorithms using random sampling. The primary goals of this project are identifying problems amenable to this approach, designing provably efficient algorithms, and developing probabilistic techniques to enable such analyses. For each of these goals, computer science benefits from insights from related fields, especially statistical physics and discrete probability.The project explores strong connections between phase transitions of physical systems and convergence rates of local Markov chains to explain the limitations of various natural approaches to sampling. This correspondence also guides our search for more efficient algorithms by allowing nonlocal moves or designing Markov chains on modified state spaces. This PI will explore both aspects, by designing methods from stronger analysis in the efficient and non-efficient regimes on both sides of the phase transition, and by searching for alternative non-local algorithms for sampling when local algorithms have been proven to be prohibitively slow. Applications to be explored include the hard-core model from statistical physics, the Schelling model of segregation from economics, geometric sampling problems form planning and design, and sampling problems from data science where inputs are noisy or evolving over time.The broader impacts of this interdisciplinary work have many facets, especially for bridging scientific fields by bringing insights from one field to another. The PI regularly gives technical and survey talks to students and faculty across fields, directs an interdisciplinary research center and organizes workshops and conferences including participants from disparate disciplines. The results disseminated by talks, publications and will be made accessible on websites. The PI continues to be a strong advocate for women in academia, including serving as the ADVANCE Professor of Computing, participating on equity panels, presenting lectures to broad groups of women, and advising women Ph.D. students.

基于马尔可夫链的采样算法被广泛应用于科学领域，主要用于近似计数、组合优化和建模。 这些算法使用随机游走来探索大的状态空间，并且确定它们的收敛时间通常是建立使用随机采样的许多近似算法的效率的关键步骤。 这个项目的主要目标是确定问题服从这种方法，设计可证明有效的算法，并开发概率技术，使这种分析。 对于这些目标中的每一个，计算机科学受益于相关领域的见解，特别是统计物理学和离散概率。该项目探讨了物理系统的相变和局部马尔可夫链的收敛速率之间的紧密联系，以解释各种自然方法的局限性。这种对应关系也指导我们通过允许非局部移动或在修改的状态空间上设计马尔可夫链来寻找更有效的算法。这个PI将探索这两个方面，通过设计方法，从更强的分析在有效和非有效的制度两侧的相变，并通过寻找替代的非本地算法采样时，本地算法已被证明是非常慢。 将探索的应用包括统计物理学的核心模型，经济学隔离的谢林模型，规划和设计中的几何抽样问题，以及数据科学中输入噪声或随时间变化的抽样问题。这种跨学科工作的更广泛影响有很多方面，特别是通过将见解从一个领域带到另一个领域来弥合科学领域。 PI定期为各领域的学生和教师提供技术和调查讲座，指导跨学科研究中心，并组织研讨会和会议，包括来自不同学科的参与者。 通过讲座、出版物传播成果，并将在网站上公布。 PI继续是学术界女性的有力倡导者，包括担任计算的高级教授，参与公平小组，向广大女性群体发表演讲，并为女性博士提供咨询。学生