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 继续大力倡导学术界女性的地位，包括担任计算机高级教授、参加股权小组、向广大女性群体演讲以及为女性博士生提供建议。学生。