AF: Small: New Techniques for Optimal Bounds on MCMC Algorithms

AF:小:MCMC 算法最优边界的新技术

基本信息

  • 批准号:
    2147094
  • 负责人:
  • 金额:
    $ 48.74万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2022
  • 资助国家:
    美国
  • 起止时间:
    2022-05-01 至 2025-04-30
  • 项目状态:
    未结题

项目摘要

Markov Chain Monte Carlo (MCMC) algorithms are a widely used tool in a variety of scientific fields for sampling problems. Understanding the convergence rate of Markov chains to their equilibrium distribution is crucial for the efficiency and accuracy of scientific studies utilizing MCMC algorithms. This project focuses on the design and analysis of fast algorithms for randomly sampling from distributions defined on exponentially large combinatorial sets. This is a fundamental task that arises in a variety of scientific fields; some common examples include: Bayesian inference which is a key tool in machine learning, computer vision, and evolutionary biology; the study of the equilibrium state of idealized physical systems in statistical physics; and the design of algorithms for counting and sampling problems in theoretical computer science. The education plan of this project includes an interdisciplinary summer school at the University of California Santa Barbara to train graduate students on recent developments in the research area.This project will introduce new techniques for proving optimal convergence rates of Markov chains. The focus is an exciting new technique known as spectral independence, which measures the pairwise influences in graphical models or spin systems, and implies optimal mixing time bounds for a variety of Markov chains. This project will enhance the technique by strengthening the implications of spectral independence and extend its applicability by presenting new tools for establishing spectral independence. These improved techniques will yield new connections between various algorithmic approaches for approximate sampling and counting problems. In addition, this project will formalize connections between the computational complexity of approximate counting problems on general graphs with statistical physics phase transitions on trees.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.
马尔可夫链蒙特卡罗(MCMC)算法是一种广泛应用于各种科学领域的抽样工具。了解马尔可夫链对其均衡分布的收敛速度对于利用MCMC算法进行科学研究的效率和准确性至关重要。该项目致力于设计和分析从指数型大组合集上定义的分布中随机抽样的快速算法。这是一项出现在各种科学领域的基本任务;一些常见的例子包括:贝叶斯推理,它是机器学习、计算机视觉和进化生物学中的关键工具;统计物理学中对理想化物理系统的平衡状态的研究;以及理论计算机科学中计数和抽样问题的算法设计。该项目的教育计划包括在加州大学圣巴巴拉分校举办跨学科暑期班,培训研究生了解该研究领域的最新发展。该项目将引入证明马尔可夫链最优收敛速度的新技术。重点是一种令人兴奋的新技术,称为谱独立,它测量图形模型或自旋系统中的成对影响,并暗示各种马尔可夫链的最佳混合时间界限。该项目将通过加强光谱独立性的含义来加强这项技术,并通过提出建立光谱独立性的新工具来扩大其适用性。这些改进的技术将在用于近似抽样和计数问题的各种算法方法之间产生新的联系。此外,该项目将正式确定一般图形上近似计数问题的计算复杂性与树上的统计物理相变之间的联系。该奖项反映了NSF的法定使命,并通过使用基金会的智力优势和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(11)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Approximating Observables Is as Hard as Counting
近似可观测值与计数一样困难
  • DOI:
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Galanis, Andreas;Štefankovič, Daniel;Vigoda, Eric
  • 通讯作者:
    Vigoda, Eric
Spectral Independence via Stability and Applications to Holant-Type Problems
Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling
  • DOI:
  • 发表时间:
    2022-07
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Antonio Blanca;Zongchen Chen;Daniel Stefankovic;Eric Vigoda
  • 通讯作者:
    Antonio Blanca;Zongchen Chen;Daniel Stefankovic;Eric Vigoda
Counting and Sampling Labeled Chordal Graphs in Polynomial Time
  • DOI:
    10.48550/arxiv.2308.09703
  • 发表时间:
    2023-08
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Úrsula Hébert-Johnson;D. Lokshtanov;Eric Vigoda
  • 通讯作者:
    Úrsula Hébert-Johnson;D. Lokshtanov;Eric Vigoda
Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
通过张量化实现任意树上随机独立集的最佳混合
  • DOI:
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Efthymiou, Charilaos;Hayes, Thomas P.;Štefankovič, Daniel;Vigoda, Eric
  • 通讯作者:
    Vigoda, Eric
{{ 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 }}

Eric Vigoda其他文献

Improved bounds for sampling colorings
Structure Learning of H-Colorings
H-着色的结构学习
Torpid mixing of some Monte Carlo Markov chain algorithms in statistical physics
统计物理中一些蒙特卡洛马尔可夫链算法的迟缓混合
Random Bichromatic Matchings
随机双色匹配
  • DOI:
  • 发表时间:
    2006
  • 期刊:
  • 影响因子:
    1.1
  • 作者:
    Nayantara Bhatnagar;Dana Randall;V. Vazirani;Eric Vigoda
  • 通讯作者:
    Eric Vigoda
General upper bounds for covering numbers
覆盖数字的一般上限
  • DOI:
  • 发表时间:
    1996
  • 期刊:
  • 影响因子:
    0
  • 作者:
    A. Godbole;S. E. Thompson;Eric Vigoda
  • 通讯作者:
    Eric Vigoda

Eric Vigoda的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Eric Vigoda', 18)}}的其他基金

Collaborative Research: AF: Small: Phase Transitions in Sampling Related Problems
合作研究:AF:小:采样相关问题中的相变
  • 批准号:
    2205743
  • 财政年份:
    2021
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: Phase Transitions in Sampling Related Problems
合作研究:AF:小:采样相关问题中的相变
  • 批准号:
    2007022
  • 财政年份:
    2020
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Standard Grant
AF: Small: Approximate Counting, Markov Chains and Phase Transitions
AF:小:近似计数、马尔可夫链和相变
  • 批准号:
    1617306
  • 财政年份:
    2016
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Standard Grant
AF: EAGER: Phase Transitions in Markov Chain Mixing Times
AF:EAGER:马尔可夫链混合时间中的相变
  • 批准号:
    1555579
  • 财政年份:
    2015
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Standard Grant
AF: Small: Phase Transitions in Approximate Counting Problems
AF:小:近似计数问题中的相变
  • 批准号:
    1217458
  • 财政年份:
    2012
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Standard Grant
Markov Chain Monte Carlo Algorithms
马尔可夫链蒙特卡罗算法
  • 批准号:
    0830298
  • 财政年份:
    2008
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Continuing Grant
CAREER: Markov Chain Monte Carlo Methods
职业:马尔可夫链蒙特卡罗方法
  • 批准号:
    0455666
  • 财政年份:
    2004
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Continuing Grant
CAREER: Markov Chain Monte Carlo Methods
职业:马尔可夫链蒙特卡罗方法
  • 批准号:
    0237834
  • 财政年份:
    2003
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Continuing Grant

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
  • 批准号:
    2342244
  • 财政年份:
    2024
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: New Connections between Optimization and Property Testing
合作研究:AF:小型:优化和性能测试之间的新联系
  • 批准号:
    2402572
  • 财政年份:
    2024
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
  • 批准号:
    2342245
  • 财政年份:
    2024
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: New Connections between Optimization and Property Testing
合作研究:AF:小型:优化和性能测试之间的新联系
  • 批准号:
    2402571
  • 财政年份:
    2024
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: New Directions and Approaches in Discrepancy Theory
合作研究:AF:小:差异理论的新方向和方法
  • 批准号:
    2327010
  • 财政年份:
    2023
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: New Directions and Approaches in Discrepancy Theory
合作研究:AF:小:差异理论的新方向和方法
  • 批准号:
    2327011
  • 财政年份:
    2023
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Standard Grant
AF: Small: New Challenges and Approaches in Clustering Algorithms
AF:小:聚类算法的新挑战和方法
  • 批准号:
    2311397
  • 财政年份:
    2023
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Standard Grant
NSF-BSF: AF: Small: New directions in geometric traversal theory
NSF-BSF:AF:小:几何遍历理论的新方向
  • 批准号:
    2317241
  • 财政年份:
    2023
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Standard Grant
AF: Small: New Tools to Analyze Random Walks
AF:小:分析随机游走的新工具
  • 批准号:
    2203541
  • 财政年份:
    2022
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Standard Grant
AF: Small: Towards New Relaxations for Online Algorithms
AF:小:在线算法的新放松
  • 批准号:
    2224718
  • 财政年份:
    2022
  • 资助金额:
    $ 48.74万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了