CAREER: The Nature of Average-Case Computation

职业:平均情况计算的本质

基本信息

  • 批准号:
    2422342
  • 负责人:
  • 金额:
    $ 59.96万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Continuing Grant
  • 财政年份:
    2024
  • 资助国家:
    美国
  • 起止时间:
    2024-04-01 至 2026-01-31
  • 项目状态:
    未结题

项目摘要

The recent surge in the applications of machine learning is powered by algorithms that learn hidden patterns in large volumes of data. Designing faster and more reliable data analysis algorithms is a key challenge in broadening the scope of such applications. However, researchers have realized that the classical framework of algorithm design is inadequate for this task. This is because large data in almost every application is modeled using statistical models as opposed to the standard worst-case model used in algorithm design. Consequently, central challenges that involve an interplay between algorithms and statistically generated data remain widely unresolved not just in machine learning but also in statistical physics and cryptography. This project will address this critical deficiency by building a principled theory of algorithm design for statistical (aka average-case) data. The new paradigms explored in this work will unify the currently fragmented set of approaches for studying average-case computation. The curriculum development plan outlined in this project will train the next generation of scientists in the algorithmic methods tailor-made for problems in large scale statistical data analysis and disseminate the modern paradigms for understanding computation to both graduate and undergraduate students.Average-case complexity is a central thrust in the theory of computation with a direct impact on potential technological advances in machine learning and cryptography as well as basic questions in statistical physics. Examples include training expressive statistical models such as Gaussian mixture models and Sparse PCA to find patterns in large data in machine learning, ascertaining the security of pseudo-random generators in cryptography, and finding the lowest-energy states of spin-glass systems in statistical physics. Our current understanding of such problems is based on fragmented, domain-specific algorithmic schemes such as statistical query methods and method of moments (in machine learning), belief propagation (in statistical physics), and semidefinite programming hierarchies (in computational complexity). This project is devoted to building a unified theory of average-case computation that offers new tools to design better algorithms, prove sharp lower-bounds, and allow rigorously transferring insights between different specific frameworks. This investigation will build new bridges between theoretical computer science and several adjacent areas including machine learning, statistical physics, algebraic geometry, and probability. In addition, it will further develop the burgeoning understanding of the sum-of-squares semidefinite programming hierarchy, mixture models, and use of solution-space geometry in solving random constraint satisfaction problems.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.
最近机器学习应用的激增是由在大量数据中学习隐藏模式的算法驱动的。设计更快、更可靠的数据分析算法是扩大此类应用范围的关键挑战。然而,研究人员已经意识到算法设计的经典框架不足以完成这项任务。这是因为几乎每个应用程序中的大数据都是使用统计模型建模的,而不是算法设计中使用的标准最差情况模型。因此,涉及算法和统计生成的数据之间相互作用的核心挑战不仅在机器学习中,而且在统计物理学和密码学中仍然没有得到广泛解决。这个项目将通过建立一个统计(又名平均情况)数据的算法设计的原则性理论来解决这个关键的缺陷。在这项工作中探索的新范式将统一目前零散的一套方法来研究平均情况下的计算。该项目中概述的课程开发计划将培养下一代科学家,使其掌握为大规模统计数据分析问题量身定制的算法方法,并向研究生和本科生传播理解计算的现代范式。案例复杂性是计算理论的核心,直接影响机器学习和密码学的潜在技术进步,以及统计物理学的基本问题。例子包括训练表达性统计模型,如高斯混合模型和稀疏PCA,以在机器学习中找到大数据中的模式,确定密码学中伪随机生成器的安全性,以及在统计物理中找到自旋玻璃系统的最低能量状态。我们目前对此类问题的理解是基于碎片化的、特定于领域的算法方案,例如统计查询方法和矩量法(机器学习中)、置信传播(统计物理中)和半定编程层次结构(计算复杂性)。该项目致力于构建平均情况计算的统一理论,提供新的工具来设计更好的算法,证明尖锐的下限,并允许在不同的特定框架之间严格转移见解。这项研究将在理论计算机科学和几个相邻领域之间建立新的桥梁,包括机器学习,统计物理,代数几何和概率。此外,它将进一步发展对平方和半定规划层次结构、混合模型以及在解决随机约束满足问题中使用解空间几何的新兴理解。该奖项反映了NSF的法定使命,并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ 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 }}

Pravesh Kothari其他文献

Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally
多项式时间平方和可以稳健地估计高斯函数的均值和协方差
Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures
高斯和其他非球形混合物的异常值稳健聚类
Tight Bounds on ℓ1 Approximation and Learning of Self-Bounding Functions
ℓ1 逼近的紧界和自界函数的学习
A simple and sharper proof of the hypergraph Moore bound
超图摩尔界的简单而清晰的证明
  • DOI:
    10.48550/arxiv.2207.10850
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Jun;Pravesh Kothari;Sidhanth Mohanty
  • 通讯作者:
    Sidhanth Mohanty
Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method
公钥加密、本地伪随机生成器和低次方法
  • DOI:
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Andrej Bogdanov;Pravesh Kothari;Alon Rosen
  • 通讯作者:
    Alon Rosen

Pravesh Kothari的其他文献

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

{{ truncateString('Pravesh Kothari', 18)}}的其他基金

Collaborative Research: AF: Medium: Polynomial Optimization: Algorithms, Certificates and Applications
合作研究:AF:媒介:多项式优化:算法、证书和应用
  • 批准号:
    2211971
  • 财政年份:
    2022
  • 资助金额:
    $ 59.96万
  • 项目类别:
    Continuing Grant
CAREER: The Nature of Average-Case Computation
职业:平均情况计算的本质
  • 批准号:
    2047933
  • 财政年份:
    2021
  • 资助金额:
    $ 59.96万
  • 项目类别:
    Continuing Grant

相似海外基金

Long-Term Nature Reserve Human Interaction
长期自然保护区人类互动
  • 批准号:
    2345184
  • 财政年份:
    2024
  • 资助金额:
    $ 59.96万
  • 项目类别:
    Continuing Grant
Engineering Nature-based Solutions to Tackle Antimicrobial Resistance
工程基于自然的解决方案来解决抗菌素耐药性
  • 批准号:
    EP/Y003101/1
  • 财政年份:
    2024
  • 资助金额:
    $ 59.96万
  • 项目类别:
    Research Grant
RestoreDNA: Development of scalable eDNA-based solutions for biodiversity regulators and nature-related disclosure
RestoreDNA:为生物多样性监管机构和自然相关披露开发可扩展的基于 eDNA 的解决方案
  • 批准号:
    10086990
  • 财政年份:
    2024
  • 资助金额:
    $ 59.96万
  • 项目类别:
    Collaborative R&D
Job share: Embedding environmental and geospatial science in nature recovery and rewilding
工作分享:将环境和地理空间科学融入自然恢复和野化中
  • 批准号:
    NE/Y005163/1
  • 财政年份:
    2024
  • 资助金额:
    $ 59.96万
  • 项目类别:
    Research Grant
Resilient and Equitable Nature-based Pathways in Southern African Rangelands (REPAiR)
南部非洲牧场弹性且公平的基于自然的途径 (REPAiR)
  • 批准号:
    NE/Z503459/1
  • 财政年份:
    2024
  • 资助金额:
    $ 59.96万
  • 项目类别:
    Research Grant
NSF Convergence Accelerator Track L: Intelligent Nature-inspired Olfactory Sensors Engineered to Sniff (iNOSES)
NSF 融合加速器轨道 L:受自然启发的智能嗅觉传感器,专为嗅探而设计 (iNOSES)
  • 批准号:
    2344256
  • 财政年份:
    2024
  • 资助金额:
    $ 59.96万
  • 项目类别:
    Standard Grant
NSF Engines Development Award: Accelerating A Just Energy Transition Through Innovative Nature-Inclusive Offshore Wind Farms (CT,DE,MA,MD,NJ,RI,VA)
NSF 发动机开发奖:通过创新的自然包容性海上风电场加速公正的能源转型(康涅狄格州、特拉华州、马里兰州、马里兰州、新泽西州、罗德岛州、弗吉尼亚州)
  • 批准号:
    2315558
  • 财政年份:
    2024
  • 资助金额:
    $ 59.96万
  • 项目类别:
    Cooperative Agreement
Moving away from aeration – utilising computational fluid dynamics modelling ofmechanical mixing within an industrial scale nature-based wastewater treatment system
摆脱曝气 — 在工业规模的基于自然的废水处理系统中利用机械混合的计算流体动力学模型
  • 批准号:
    10092420
  • 财政年份:
    2024
  • 资助金额:
    $ 59.96万
  • 项目类别:
    Collaborative R&D
Nature-based solutions for the climate change-biodiversity nexus in cities
城市气候变化与生物多样性关系的基于自然的解决方案
  • 批准号:
    DE240100699
  • 财政年份:
    2024
  • 资助金额:
    $ 59.96万
  • 项目类别:
    Discovery Early Career Researcher Award
The nature of vocabulary in academic computer science speech
计算机科学学术演讲中词汇的本质
  • 批准号:
    24K16133
  • 财政年份:
    2024
  • 资助金额:
    $ 59.96万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了