AF: Small: Identifying sampling problems with efficient algorithms

抽样问题是许多科学和工程领域的基本问题，例如统计学、人工智能(机器学习和视觉)和生物学(系统学)。抽样的效率对其他重要的算法也有影响，例如统计检验的速度以及估计器和分类器的可靠性。这个项目寻求描述允许高效采样算法的组合问题的特征。该奖项下的研究解决了一大类泛在图形模型的表征的两个方面：1)有效采样的复杂性理论障碍和2)高效采样算法。最近的结果建立了关于正则树上的模型行为的有用的反铁磁2-自旋模型(例如，加权独立集和伊辛模型)的表征。这建立了与统计物理界研究的问题和技术的联系。这个项目的目的是利用与统计物理及其技术的联系(例如，信念传播递归)来将表征推广到具有两个以上自旋的模型(多自旋模型，如Potts模型，在应用中经常出现)。作为这一推广的第一步，我们将探索常用马尔可夫链(Glauber动力学，Swendsen-Wang算法)的效率与规则树上模型行为之间的关系。除了马尔可夫链，PI还将研究其他采样问题的方法(例如，动态规划和利用强空间混合)。研究的成果将是有效的采样算法和对有效采样障碍的更好理解。算法问题、概念和技术将被转移到本科生和研究生教学中(以指导性问题和实施挑战的形式)。该奖项将支持罗切斯特大学在采样和计数算法领域对两名博士生的培训。

Sampling problems are fundamental in many areas of science and engineering, for example, statistics, artificial intelligence (machine learning and vision), and biology (phylogeny). Efficiency of sampling has impact on other important algorithms, for example, the speed of statistical tests and the reliability of estimators and classifiers. This project seeks to characterize combinatorial problems that admit efficient sampling algorithms. The research under this award addresses both sides of the characterization for a broad class of ubiquitous graphical models: 1) complexity theoretic obstacles to efficient sampling and 2) efficient sampling algorithms.Recent results established a useful characterization for antiferromagnetic 2-spin models (for example, weighted independent sets and Ising model) in terms of the behavior of the model on regular trees. This created a connection to problems and techniques studied in the statistical physics community. This project aims to use the connection to the statistical physics and its techniques (for example, belief propagation recurrences) to generalize the characterization to models with more than two spins (multi-spin models, such as the Potts model, frequently occur in the applications). As a first step towards this generalization a relation between the efficiency of commonly used Markov chains (Glauber dynamics, Swendsen-Wang algorithm) and the behavior of the models on regular trees will be explored. Beside Markov chains the PI will also investigate other approaches to sampling problems (for example, dynamic programming and utilizing strong spatial mixing).The product of the research will be efficient sampling algorithms and an improved understanding of obstacles to efficient sampling. The algorithmic problems, concepts, and techniques will be transferred to both undergraduate and graduate teaching (in the form of guided problems and implementation challenges). The award will support the training of two PhD students in the area of sampling and counting algorithms at the University of Rochester.