Collaborative Research: AF: Small: Sampling and Optimization under Global Constraints
合作研究:AF:小型:全局约束下的采样和优化
基本信息
- 批准号:2309708
- 负责人:
- 金额:$ 29.97万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2023
- 资助国家:美国
- 起止时间:2023-06-01 至 2026-05-31
- 项目状态:未结题
- 来源:
- 关键词:
项目摘要
Sampling from complex, high dimensional probability distributions and optimizing high dimensional functions are two central computational tasks, with applications in machine learning, statistics, physics, and many other fields, both industrial and scientific. A widespread and very useful framework for studying both of these tasks is provided by probabilistic graphical models. This framework originates in statistical physics, and physical intuition has guided both the development of algorithms and the understanding of computational complexity. A common setting in both practical and scientific applications is the imposition of global constraints on a graphical model; examples including fixing the number of interacting particles in a system, fixing magnetization in a mathematical model of a magnet, or fixing the sizes of a partition of elements. A rigorous understanding of the performance of algorithms in this setting is still largely absent. The goal of this project is to develop new techniques in algorithms and complexity to understand how global constraints influence the tractability of these sampling and optimization problems. Guided by insights from statistical physics, this research project will develop new algorithms and study the limits of algorithmic approaches. The project also involves the training of graduate students in interdisciplinary research and a high-school outreach program.The main research goal of the project is to build a robust theory of sampling and optimization in the presence of global constraints in several algorithmic contexts: computational thresholds for approximate counting and sampling; Markov chain mixing times; and the structure of optimization problems on random graphs. Preliminary work shows that imposing a global constraint on a Markov random field can transform the behavior and complexity of the associated sampling and optimization problems. Specific problems the project focuses on include the determination of computational thresholds for the antiferromagnetic Ising model at fixed magnetization on bounded degree graphs; proving optimal mixing time bounds for conservative dynamics like the Kawasaki dynamics; and understanding the limiting values of optimization problems on sparse random graphs. The approach is guided by intuition from statistical physics, a field that provides a natural language and suite of techniques for analyzing graphical models and a wealth of examples of different phenomena that result from imposing global constraints.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
从复杂的高维概率分布中采样和优化高维函数是两项核心计算任务,在机器学习、统计、物理和许多其他领域都有应用,包括工业和科学领域。概率图形模型为研究这两项任务提供了一个广泛且非常有用的框架。这一框架起源于统计物理学,物理直觉指导了算法的发展和对计算复杂性的理解。在实际和科学应用中,一种常见的设置是对图形模型施加全局约束;例如,固定系统中相互作用的粒子的数量,固定磁体的数学模型中的磁化强度,或固定元素分区的大小。对算法在这种情况下的性能的严格理解在很大程度上仍然缺乏。这个项目的目标是开发算法和复杂性方面的新技术,以了解全局约束如何影响这些采样和优化问题的可处理性。在统计物理学见解的指导下,这项研究项目将开发新的算法,并研究算法方法的局限性。该项目还包括对研究生的跨学科研究和高中推广计划的培训。该项目的主要研究目标是在以下几个算法环境中建立一个健壮的抽样和优化理论:近似计数和抽样的计算阈值;马尔可夫链混合时间;以及随机图上的优化问题的结构。初步工作表明,对马尔可夫随机场施加全局约束可以改变相关抽样和优化问题的行为和复杂性。该项目关注的具体问题包括:确定有界度图上固定磁化强度下反铁磁性伊辛模型的计算阈值;证明保守动力学(如川崎动力学)的最优混合时间界限;以及理解稀疏随机图上优化问题的极限值。这一方法是由统计物理学的直觉指导的,该领域提供了一种自然语言和一套技术来分析图形模型和大量由于施加全球约束而导致的不同现象的例子。这一奖项反映了NSF的法定使命,并通过使用基金会的智力优势和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(2)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Leibniz International Proceedings in Informatics (LIPIcs):Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
莱布尼茨国际信息学论文集 (LIPIcs):近似、随机化和组合优化。
- DOI:10.4230/lipics.approx/random.2023.26
- 发表时间:2023
- 期刊:
- 影响因子:0
- 作者:Chawla, Shuchi;Gergatsouli, Evangelia;McMahan, Jeremy;Tzamos, Christos
- 通讯作者:Tzamos, Christos
On the hardness of finding balanced independent sets in random bipartite graphs
论随机二分图中寻找平衡独立集的难度
- DOI:
- 发表时间:2024
- 期刊:
- 影响因子:0
- 作者:Perkins, Will;Wang, Yuzhou
- 通讯作者:Wang, Yuzhou
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
William Perkins其他文献
33. Basal Cell Carcinoma
33.基底细胞癌
- DOI:
- 发表时间:
2014 - 期刊:
- 影响因子:0
- 作者:
Fiona Bath;William Perkins - 通讯作者:
William Perkins
Power grid simulation applications developed using the GridPACK™ high performance computing framework
- DOI:
10.1016/j.epsr.2016.06.024 - 发表时间:
2016-12-01 - 期刊:
- 影响因子:
- 作者:
Shuangshuang Jin;Yousu Chen;Ruisheng Diao;Zhenyu (Henry) Huang;William Perkins;Bruce Palmer - 通讯作者:
Bruce Palmer
Aluminium and heavy metals in potable waters of the north Ceredigion area, mid-Wales
- DOI:
10.1007/bf01734295 - 发表时间:
1991-06-01 - 期刊:
- 影响因子:3.800
- 作者:
Ronald Fuge;William Perkins - 通讯作者:
William Perkins
Preparation of an ultra-oriented polyethylene morphology
- DOI:
10.1007/bf00566275 - 发表时间:
1977-02-01 - 期刊:
- 影响因子:3.900
- 作者:
Numa Capiati;Shunji Kojima;William Perkins;Roger S. Porter - 通讯作者:
Roger S. Porter
On the transferability of residence time distributions in two 10-km long river sections with similar hydromorphic units
关于两个具有相似水成岩单元的 10 公里长河流段中停留时间分布的可转移性
- DOI:
10.1016/j.jhydrol.2024.131723 - 发表时间:
2024-08-01 - 期刊:
- 影响因子:6.300
- 作者:
Jie Bao;Xuehang Song;Yunxiang Chen;Yilin Fang;Xinming Lin;Zhangshuan Hou;Zhuoran Duan;Huiying Ren;William Perkins;Xiaoliang He;Timothy Scheibe - 通讯作者:
Timothy Scheibe
William Perkins的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('William Perkins', 18)}}的其他基金
CAREER:Phase Transitions in Algorithms, Complexity, and Geometry
职业:算法、复杂性和几何中的相变
- 批准号:
2309958 - 财政年份:2022
- 资助金额:
$ 29.97万 - 项目类别:
Continuing Grant
7th Lake Michigan Workshop on Combinatorics and Graph Theory
第七届密歇根湖组合学和图论研讨会
- 批准号:
1952959 - 财政年份:2019
- 资助金额:
$ 29.97万 - 项目类别:
Standard Grant
CAREER:Phase Transitions in Algorithms, Complexity, and Geometry
职业:算法、复杂性和几何中的相变
- 批准号:
1847451 - 财政年份:2019
- 资助金额:
$ 29.97万 - 项目类别:
Continuing Grant
Intelligent Control of Dynamic Systems
动态系统的智能控制
- 批准号:
9216487 - 财政年份:1992
- 资助金额:
$ 29.97万 - 项目类别:
Standard Grant
A Unified Approach to Singular Perturbations, Aggregation, Multimodeling and Decentralized Control
奇异扰动、聚合、多建模和分散控制的统一方法
- 批准号:
8217631 - 财政年份:1983
- 资助金额:
$ 29.97万 - 项目类别:
Standard Grant
相似国自然基金
Research on Quantum Field Theory without a Lagrangian Description
- 批准号:24ZR1403900
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
Cell Research
- 批准号:31224802
- 批准年份:2012
- 资助金额:24.0 万元
- 项目类别:专项基金项目
Cell Research
- 批准号:31024804
- 批准年份:2010
- 资助金额:24.0 万元
- 项目类别:专项基金项目
Cell Research (细胞研究)
- 批准号:30824808
- 批准年份:2008
- 资助金额:24.0 万元
- 项目类别:专项基金项目
Research on the Rapid Growth Mechanism of KDP Crystal
- 批准号:10774081
- 批准年份:2007
- 资助金额:45.0 万元
- 项目类别:面上项目
相似海外基金
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
- 批准号:
2402836 - 财政年份:2024
- 资助金额:
$ 29.97万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: Foundations of Oblivious Reconfigurable Networks
合作研究:AF:媒介:遗忘可重构网络的基础
- 批准号:
2402851 - 财政年份:2024
- 资助金额:
$ 29.97万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
- 批准号:
2342244 - 财政年份:2024
- 资助金额:
$ 29.97万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Exploring the Frontiers of Adversarial Robustness
合作研究:AF:小型:探索对抗鲁棒性的前沿
- 批准号:
2335411 - 财政年份:2024
- 资助金额:
$ 29.97万 - 项目类别:
Standard Grant
NSF-BSF: Collaborative Research: AF: Small: Algorithmic Performance through History Independence
NSF-BSF:协作研究:AF:小型:通过历史独立性实现算法性能
- 批准号:
2420942 - 财政年份:2024
- 资助金额:
$ 29.97万 - 项目类别:
Standard Grant
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
协作研究:AF:媒介:算法遇见机器学习:减轻优化中的不确定性
- 批准号:
2422926 - 财政年份:2024
- 资助金额:
$ 29.97万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347322 - 财政年份:2024
- 资助金额:
$ 29.97万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331401 - 财政年份:2024
- 资助金额:
$ 29.97万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331400 - 财政年份:2024
- 资助金额:
$ 29.97万 - 项目类别:
Standard Grant
Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths
合作研究:AF:中:(动态)匹配和最短路径的快速组合算法
- 批准号:
2402283 - 财政年份:2024
- 资助金额:
$ 29.97万 - 项目类别:
Continuing Grant