AF: Small: Beyond Worst-Case Analysis

AF:小:超越最坏情况分析

基本信息

  • 批准号:
    2006737
  • 负责人:
  • 金额:
    $ 45万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2020
  • 资助国家:
    美国
  • 起止时间:
    2020-10-01 至 2024-09-30
  • 项目状态:
    已结题

项目摘要

With algorithms increasingly dominating our world, the need to understand when and why they work has never been greater. The goal of the mathematical analysis of algorithms is to provide guidance about which algorithm is the “best” for solving a given computational problem. Worst-case analysis summarizes the performance profile of an algorithm by its worst performance on any input of a given size, implicitly advocating for the algorithm with the best-possible worst-case performance. Strong worst-case guarantees are the holy grail of algorithm design, providing an application-agnostic certification of an algorithm’s robustly good performance. However, for many fundamental problems and performance measures, such guarantees are impossible, and a more nuanced analysis approach is called for. This project investigates several alternatives to worst-case analysis, with applications to machine learning and social-network analysis.This project has three research thrusts. The first thrust concerns "smoothed analysis," where an adversarially chosen input is perturbed by nature, and focuses on two different application areas, both with striking open questions: regret-minimization in online learning, and the running time of local-search algorithms for combinatorial problems. The second thrust investigates structured prediction problems in machine learning, where the goal is to label jointly a collection of objects, using information about relationships between the objects (for example, identifying regions in an image of parts-of-speech in a sentence). Here, the questions concern to what extent a ground-truth labeling can be recovered, as a function of the combinatorial structure of the object relationships and the amount of noise in the data. The final thrust concerns distribution-free models of social networks, motivated by triadic closure. The goal here is to investigate novel graph classes that are tailored to social networks, and to prove structural and algorithmic results for them. Together, these research thrusts both deepen the state-of-the-art in "beyond worst-case analysis" and also extend its reach to important new application domains.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.
随着算法日益主导我们的世界,了解它们何时以及为何起作用的需求从未如此强烈。算法的数学分析的目标是提供关于哪种算法是解决给定计算问题的“最佳”的指导。最坏情况分析通过在给定大小的任何输入上的最差性能来总结算法的性能概况,隐含地提倡具有最佳最坏情况性能的算法。强最坏情况保证是算法设计的圣杯,它提供了与应用程序无关的算法鲁棒性良好性能的认证。然而,对于许多基本问题和性能指标,这种保证是不可能的,需要更细致的分析方法。该项目研究了最坏情况分析的几种替代方案,并将其应用于机器学习和社交网络分析。这个项目有三个研究重点。第一个重点是关于“平滑分析”,在这种分析中,一个对抗选择的输入受到自然的干扰,并关注两个不同的应用领域,这两个领域都有引人注目的开放问题:在线学习中的遗憾最小化,以及用于组合问题的局部搜索算法的运行时间。第二个重点研究机器学习中的结构化预测问题,其目标是使用对象之间的关系信息(例如,识别句子中词性图像中的区域),共同标记一组对象。这里的问题是,作为对象关系的组合结构和数据中的噪声量的函数,在多大程度上可以恢复基础真值标记。最后一个推动力涉及由三元封闭性驱动的无分布社交网络模式。这里的目标是研究为社交网络量身定制的新颖图形类,并为它们证明结构和算法结果。总之,这些研究既深化了“超越最坏情况分析”的最新技术,也将其范围扩展到重要的新应用领域。该奖项反映了美国国家科学基金会的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(10)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
From Proper Scoring Rules to Max-Min Optimal Forecast Aggregation
从适当的评分规则到最大-最小最优预测聚合
Smoothed Analysis of Online and Differentially Private Learning
在线和差异化私人学习的平滑分析
Robust Auctions for Revenue via Enhanced Competition
通过加强竞争实现稳健的拍卖收入
  • DOI:
    10.1287/opre.2019.1929
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    2.7
  • 作者:
    Roughgarden, Tim;Talgam-Cohen, Inbal;Yan, Qiqi
  • 通讯作者:
    Yan, Qiqi
Are You Smarter Than a Random Expert? The Robust Aggregation of Substitutable Signals
你比随机的专家更聪明吗?
Data-driven algorithm design
数据驱动的算法设计
  • DOI:
    10.1145/3394625
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    22.7
  • 作者:
    Gupta, Rishi;Roughgarden, Tim
  • 通讯作者:
    Roughgarden, Tim
{{ 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 }}

Tim Roughgarden其他文献

Designing networks for selfish users is hard
Intrinsic Robustness of the Price of Anarchy
  • DOI:
    10.1145/2806883
  • 发表时间:
    2015-11
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Tim Roughgarden
  • 通讯作者:
    Tim Roughgarden
CS364A: Algorithmic Game Theory Lecture #1: Introduction and Examples ∗
CS364A:算法博弈论讲座1:简介和示例*
  • DOI:
  • 发表时间:
    2013
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Tim Roughgarden
  • 通讯作者:
    Tim Roughgarden
Resource Augmentation
  • DOI:
    10.1017/9781108637435.006
  • 发表时间:
    2020-07
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Tim Roughgarden
  • 通讯作者:
    Tim Roughgarden
Online Stackelberg Optimization via Nonlinear Control
通过非线性控制进行在线 Stackelberg 优化

Tim Roughgarden的其他文献

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

{{ truncateString('Tim Roughgarden', 18)}}的其他基金

Collaborative Research: SaTC: CORE: Medium: Game Theory, Economics, and Mechanism Design for Blockchains
协作研究:SaTC:核心:媒介:区块链的博弈论、经济学和机制设计
  • 批准号:
    2212745
  • 财政年份:
    2022
  • 资助金额:
    $ 45万
  • 项目类别:
    Continuing Grant
AF: Small: New Directions in Algorithmic Game Theory
AF:小:算法博弈论的新方向
  • 批准号:
    1929788
  • 财政年份:
    2019
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: Small: New Directions in Algorithmic Game Theory
AF:小:算法博弈论的新方向
  • 批准号:
    1813188
  • 财政年份:
    2018
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: Small: Connections Between Algorithmic Game Theory, Complexity Theory, and Learning Theory
AF:小:算法博弈论、复杂性理论和学习理论之间的联系
  • 批准号:
    1524062
  • 财政年份:
    2015
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
ICES: Small: Frontiers in Mechanism Design
ICES:小:机制设计的前沿
  • 批准号:
    1215965
  • 财政年份:
    2012
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: Small: Frontiers in Algorithmic Game Theory
AF:小:算法博弈论的前沿
  • 批准号:
    1016885
  • 财政年份:
    2010
  • 资助金额:
    $ 45万
  • 项目类别:
    Continuing Grant
CAREER: Algorithmic Game Theory
职业:算法博弈论
  • 批准号:
    0448664
  • 财政年份:
    2005
  • 资助金额:
    $ 45万
  • 项目类别:
    Continuing Grant
PostDoctoral Research Fellowship
博士后研究奖学金
  • 批准号:
    0303464
  • 财政年份:
    2003
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard 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 RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.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: U.S.-Ireland R&D Partnership: CIF: AF: Small: Enabling Beyond-5G Wireless Access Networks with Robust and Scalable Cell-Free Massive MIMO
合作研究:美国-爱尔兰 R
  • 批准号:
    2322191
  • 财政年份:
    2023
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
Collaborative Research: U.S.-Ireland R&D Partnership: CIF: AF: Small: Enabling Beyond-5G Wireless Access Networks with Robust and Scalable Cell-Free Massive MIMO
合作研究:美国-爱尔兰 R
  • 批准号:
    2322190
  • 财政年份:
    2023
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: Small: The Polymorphic Gateway between Structure and Algorithms: Beyond CSP Dichotomy
AF:小:结构和算法之间的多态网关:超越 CSP 二分法
  • 批准号:
    2228287
  • 财政年份:
    2022
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
NSF-BSF: AF: Small: Algorithmic Game Theory: Equilibria and Beyond
NSF-BSF:AF:小:算法博弈论:均衡及超越
  • 批准号:
    2112824
  • 财政年份:
    2021
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: SMALL: Beyond Worst-Case Analysis for Computing with Polynomials
AF:SMALL:多项式计算的超越最坏情况分析
  • 批准号:
    2110075
  • 财政年份:
    2021
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: Small: Graph Theory and Its Uses in Algorithms and Beyond
AF:小:图论及其在算法及其他领域的应用
  • 批准号:
    2006464
  • 财政年份:
    2020
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: CIF: Small: Communication complexity techniques beyond classical information theory
AF:CIF:小:超越经典信息论的通信复杂性技术
  • 批准号:
    2006589
  • 财政年份:
    2020
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: Small: Distributed Optimization Beyond Worst Case Topologies
AF:小型:超越最坏情况拓扑的分布式优化
  • 批准号:
    1910588
  • 财政年份:
    2019
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: Small: Learning Theory for a Modern World: Transfer Learning, Unsupervised Learning, and Beyond Prediction
AF:小:现代世界的学习理论:迁移学习、无监督学习和超越预测
  • 批准号:
    1910321
  • 财政年份:
    2019
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: Small: Cuts, Connectivity and Partitioning in Graphs, Hypergraphs and Beyond
AF:小:图、超图及其他领域的切割、连接和分区
  • 批准号:
    1907937
  • 财政年份:
    2019
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了