权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

AF: Medium: Smoothed Analysis for Optimization and Games

AF：中：优化和游戏的平滑分析

基本信息

批准号：
2107187
负责人：
Mihalis Yannakakis
金额：
$ 120万
依托单位：
Columbia University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-07-01 至 2025-06-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2107187&HistoricalAwards=false
关键词：
AF Medium Smoothed Analysis Optimization

项目摘要

Many algorithms and heuristics that work well in practice have poor performance under the worst-case analysis due to delicate pathological instances that one may never encounter, practically speaking, creating a huge theory-practice gap in the understanding of such algorithms. One of the best known such examples is the Simplex algorithm for Linear Programming, which is widely used in practice but has exponential running time in the worst case. To provide a more realistic explanation for its success, Spielman and Teng introduced the smoothed-analysis framework, which can be viewed as a hybrid of the classical worst-case and average-case analysis. The smoothed-analysis framework has since been applied to a range of problems in areas such as mathematical programming, machine learning, numerical analysis, etc. Among them, the smoothed analysis of algorithms and problems that arise from combinatorial optimization and algorithmic game theory has been studied intensively during the past decade. However, despite much progress, some of the most fundamental problems remain wide open, and tools currently available for performing smoothed analysis remain limited. This project plans to explore some of the new directions and challenging problems that have emerged in the smoothed analysis of algorithms for optimization and game-theoretic problems. The goal of the project is to develop new techniques that will enable better understanding of a broad range of algorithms and problems through the lens of smoothed analysis. The research team is broadly disseminating new results from the project by giving talks at interdisciplinary conferences, major universities and research labs, and by developing new advanced courses on smoothed analysis. The interdisciplinary nature of the project is likely to appeal to students with diverse backgrounds. In addition to advising and mentoring Ph.D. students, the research team is actively involving undergraduate students in accessible research projects. The research team is also participating in outreach activities that may help develop interest in Computer Science from a broader population.For the smoothed analysis of combinatorial-optimization problems, the research team is focusing on the local-search paradigm. A core problem that the team plans to study is the smoothed complexity of the FLIP algorithm for Local Maximum Constraint Satisfaction problems, including examples such as MAX-CUT and MAX-3SAT. The team also plans to study the smoothed complexity of heuristics for the Traveling Salesman Problem (TSP), such as k-Opt. Improved understanding of k-Opt may shed new light on the smoothed analysis of Lin-Kernighan, one of the most widely used heuristics for TSP in practice. For the smoothed analysis of algorithms and problems from game theory and economics, the team is working to investigate the smoothed complexity of Policy and Value Iteration for solving Markov decision processes and more generally, stochastic games. The team is also working to establish unconditional lower bounds for the smoothed complexity of the Lemke-Howson algorithm for bimatrix games and the global Newton method of Smale for market equilibria.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.

实际上，许多在实践中工作良好的算法和算法在最坏情况分析下的性能很差，这是由于人们可能永远不会遇到的微妙的病理情况，实际上，在理解这些算法时产生了巨大的理论与实践差距。最著名的例子之一是线性规划的单纯形算法，它在实践中广泛使用，但在最坏的情况下具有指数运行时间。为了对其成功提供更现实的解释，Spielman和Teng引入了平滑分析框架，该框架可以被视为经典的最坏情况和平均情况分析的混合。平滑分析框架已被应用于一系列问题的领域，如数学规划，机器学习，数值分析等，其中，平滑分析的算法和问题，所产生的组合优化和算法博弈论在过去的十年中已经深入研究。然而，尽管取得了很大进展，一些最根本的问题仍然是开放的，目前可用于执行平滑分析的工具仍然有限。这个项目计划探索一些新的方向和挑战性的问题，已经出现在平滑分析的算法优化和博弈论问题。该项目的目标是开发新技术，通过平滑分析的透镜，更好地理解广泛的算法和问题。该研究团队通过在跨学科会议、主要大学和研究实验室发表演讲，以及开发关于平滑分析的新高级课程，广泛传播该项目的新成果。该项目的跨学科性质可能会吸引不同背景的学生。除了提供咨询和指导博士。学生，研究小组积极参与本科生在无障碍研究项目。研究团队还参与了一些外展活动，这些活动可能有助于更广泛的人群对计算机科学产生兴趣。对于组合优化问题的平滑分析，研究团队专注于本地搜索范式。该团队计划研究的一个核心问题是FLIP算法在局部最大约束满足问题中的平滑复杂性，包括MAX-CUT和MAX-3SAT等示例。该团队还计划研究旅行商问题（TSP）的平滑复杂性，例如k-Opt。对k-Opt的进一步理解可能会为Lin-Kernighan的平滑分析带来新的启发，Lin-Kernighan是实际中最广泛使用的TSP算法之一。对于来自博弈论和经济学的算法和问题的平滑分析，该团队正在研究用于解决马尔可夫决策过程和更普遍的随机博弈的策略和值迭代的平滑复杂性。该团队还致力于为双矩阵博弈的Lemke-Howson算法和市场均衡的Smale全局牛顿方法的平滑复杂度建立无条件下限。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（13）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Parameterized Sensitivity Oracles and Dynamic Algorithms Using Exterior Algebras

使用外代数的参数化灵敏度预言和动态算法

DOI：
10.4230/lipics.icalp.2022.9
发表时间：
2022
期刊：
and Programming {ICALP}
影响因子：
0
作者：
Alman, Josh;Hirsch, Dean
通讯作者：
Hirsch, Dean

Computational Hardness of the Hylland-Zeckhauser Scheme

DOI：
10.1137/1.9781611977073.90
发表时间：
2021-07
期刊：
影响因子：
0
作者：
Thomas Chen;Xi Chen;Binghui Peng;M. Yannakakis
通讯作者：
Thomas Chen;Xi Chen;Binghui Peng;M. Yannakakis

Distribution-free Testing for Halfspaces (Almost) Requires PAC Learning

半空间的无分布测试（几乎）需要 PAC 学习

DOI：
10.1137/1.9781611977073.70
发表时间：
2022
期刊：
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'22
影响因子：
0
作者：
Chen, Xi;Patel, Shyamal
通讯作者：
Patel, Shyamal

Memory Bounds for Continual Learning