AF: Medium:Smoothed Analysis in Multi-Objective Optimization, Machine Learning, and Algorithmic Game Theory
AF: Medium:Smoothed Analysis in Multi-Objective Optimization, Machine Learning, and Algorithmic Game Theory
批准号:
0964481
负责人:
Shanghua Teng
金额:
$109.99万
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
2010
资助国家:
美国
项目状态:
已结题
起止时间:
2010-03-01 至 2015-02-28
中文摘要
项目技术描述:在最坏情况和平均情况分析等传统框架无法预测算法的良好实际性能时,引入平滑分析来研究算法的行为。在介绍平滑分析的原始论文中,Spielman和Teng证明了单纯形法具有良好的平滑复杂度,而单纯形法是一种非常实用的启发式方法,已知它的最坏情况性能很差。自引入以来,平滑分析已被应用于启发式领域,包括数学规划、数值分析和组合优化。线性规划的主要关注点是优化单个线性目标函数,为了跟进这一突破,本项目的目标是将平滑分析扩展到涉及多个目标函数和多个代理的优化问题,如计算博弈论和经济学理论中经常考虑的那样。该项目的计划还将包括在平滑设置中设计和分析机器学习算法。多目标优化的计划是改进最近的工作,这些工作表明,任何具有常数个目标函数的二元线性优化问题的Pareto集在光滑模型中具有多项式大小。在博弈论中,研究将集中在平滑复杂性的几个潜在的博弈资源分配和调度。对于这两个问题,需要一种新的迭代过程性能分析方法。在机器学习中,目标是将PAC的平滑分析和不可知学习的结果从产品分布扩展到其他更实际的分布。该项目的更广泛意义和重要性:这项研究将深入了解为什么多目标优化、局部搜索和机器学习中的启发式方法是成功的,并允许理论计算机科学的研究人员将这些启发式方法纳入算法的经典中。它还将为涉及多个代理的博弈论问题和仅涉及单个代理的多目标优化问题之间的差异提供算法见解。通过发展一种理论,更好地预测算法在实践中的表现,这项研究有希望让研究人员开发更强大的算法。当一个人设计一个算法时,他会在头脑中考虑为什么它应该起作用。通过对算法“在实践中工作”意味着什么提供一种新的分析概念,这项研究可以塑造算法设计者的直觉,使其包括那些可能因“在最坏情况下糟糕”而被抛弃的算法。该项目的主要目标是在理论计算机科学(TCS)学科与运筹学、博弈论和数学经济学学科之间建立桥梁。如果成功,该项目将有助于提供一个框架,在这个框架内,TCS的研究人员可以了解这些学科的一些伟大的实践成就。反过来,通过提供分析,尊重这些学科的研究人员对构成“实际投入”的敏感性,该项目将增加理论分析对这些领域的研究人员的价值。由于这个项目在一个连贯的研究工作中结合了许多学科的想法,关于项目成果的讲座和教程将有助于在其范围内交叉施肥。在这个项目中检验的启发式的成功理论解释的发展应该简化算法的教育,并允许在计算机科学家教育的早期阶段讨论实际重要的启发式。这些解释也简化了设计这些主题的易于理解的讲座的任务,这些受这项研究启发的课堂笔记将由PI和合作者在互联网上提供。
英文摘要
Technical description of the project:Smoothed analysis has been introduced to study the behavior of algorithms when their good practical performance cannot be predicted by the traditional frameworks such as the worst-case and average-case analyses. In the original paper that introduced smoothed analysis, Spielman and Teng proved that the simplex method, which was one of the amazingly practical heuristics known to have poor worst-case performance, had good smoothed complexity. Since its introduction, smoothed analysis has been applied to heuristics in areas that include mathematical programming, numerical analysis, and combinatorial optimization.To follow up on this breakthrough in linear programming, whose primary concern is to optimize a single linear objective function, the goal of this project is to extend smoothed analysis to optimization problems involving multiple objective functions and multiple agents, as often considered in Computational Game and Economics Theory. The plan of the project will also include the design and analysis of machine learning algorithms in the smoothed setting.The plan for multiobjective optimization is to improve the recent work which show that the Pareto set of any binary linear optimization problem with a constant number of objective functions has a polynomial size in the smoothed model. In game theory, the research will focus on the smoothed complexity of several potential games for resource allocation and scheduling. For both of these problems, a new analytical approach for the performance of an iterative process is needed. In machine learning, the goal is to extend the results on the smoothed analysis of PAC and agnostic learning from product distributions to other more practical distributions.The broader significance and importance of the project:This research will provide insight into why heuristics in multi-objective optimization, local search, and machine learning are successful and allow researchers in Theoretical Computer Science to incorporate these heuristics into the canon of Algorithms. It will also provide algorithmic insights into the differences between game-theoretic problems involving multiple agents and multi-objective optimization problems concerning only a single agent. By developing a theory that better predicts the performance of algorithms in practice, this research has the promise to allow researchers to develop more powerful algorithms. When one designs an algorithm, one does so with some reason in mind as to why it should work. By providing a new analytical notion of what it means for an algorithm to "work in practice," this research can shape the intuition of algorithm designers to include algorithms that might otherwise have been discarded for being "bad in the worst-case."A primary objective of this project is to build bridges between the discipline of Theoretical Computer Science (TCS) and communities within the disciplines of Operations Research, Game Theory, and Mathematical Economics. If successful, the project will help to provide a framework within which researchers in TCS can understand some of the great practical achievements of these disciplines. In turn, by providing analyses that respect the sensibilities of researchers in these disciplines as to what constitutes a "practical input," this project will increase the value of theoretical analyses to researchers in these fields. As this project combines ideas from many disciplines within one coherent research effort, lectures and tutorials presented on the fruits of the project will help cross-fertilize the disciplines within its scope. The development of theoretical explanations for the success of the heuristics examined in this project should simplify education in algorithms and allow discussion of practically important heuristics at earlier stages of a computer scientist's education. These explanations also simplify the task of designing easily digestible lectures on these topics, and such lecture notes inspired by this research will be made available by the PI and collaborators on the internet.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Conference: FOCS Conference Student and Postdoc Travel Support
-
批准号:2332110
-
项目类别:Standard Grant
-
资助金额:$2.0万
-
财政年份:2023
-
负责人:Shanghua Teng
-
依托单位:
AF:Small: Transformation of Mathematical Games: Quantum Inspiration
-
批准号:2308744
-
项目类别:Standard Grant
-
资助金额:$19.27万
-
财政年份:2023
-
负责人:Shanghua Teng
-
依托单位:
SODA Conference Student and Postdoc Travel Support
-
批准号:2204906
-
项目类别:Standard Grant
-
资助金额:$1.0万
-
财政年份:2022
-
负责人:Shanghua Teng
-
依托单位:
FOCS Conference Student and Postdoc Travel Support
-
批准号:2204910
-
项目类别:Standard Grant
-
资助金额:$1.5万
-
财政年份:2022
-
负责人:Shanghua Teng
-
依托单位:
Conference: FOCS Conference Student and Postdoc Travel Support
-
批准号:2232320
-
项目类别:Standard Grant
-
资助金额:$0.5万
-
财政年份:2022
-
负责人:Shanghua Teng
-
依托单位:
SODA Conference Student and Postdoc Travel Support
-
批准号:2004246
-
项目类别:Standard Grant
-
资助金额:$1.5万
-
财政年份:2020
-
负责人:Shanghua Teng
-
依托单位:
Student and Post-Doctoral Travel Grants for the 2019 Foundations of Computer Science (FOCS) Conference
-
批准号:1935617
-
项目类别:Standard Grant
-
资助金额:$1.5万
-
财政年份:2019
-
负责人:Shanghua Teng
-
依托单位:
Foundations of Computer Science (FOCS) Conference Student and Postdoc Travel Support
-
批准号:1833230
-
项目类别:Standard Grant
-
资助金额:$2.0万
-
财政年份:2018
-
负责人:Shanghua Teng
-
依托单位:
AF: Small: Scalable Algorithms for Data and Network Analysis
-
批准号:1815254
-
项目类别:Standard Grant
-
资助金额:$50.0万
-
财政年份:2018
-
负责人:Shanghua Teng
-
依托单位:
AF: Large: Collaborative Research: Algebraic Graph Algorithms: The Laplacian and Beyond
-
批准号:1111270
-
项目类别:Standard Grant
-
资助金额:$72.47万
-
财政年份:2011
-
负责人:Shanghua Teng
-
依托单位:
Collaborative Research: Spectral Graph Theory and Its Applications
-
批准号:1032367
-
项目类别:Continuing Grant
-
资助金额:$4.77万
-
财政年份:2009
-
负责人:Shanghua Teng
-
依托单位:
Collaborative Research: Spectral Graph Theory and Its Applications
-
批准号:0635102
-
项目类别:Continuing Grant
-
资助金额:$17.6万
-
财政年份:2007
-
负责人:Shanghua Teng
-
依托单位:
Collaborative Research: Coordinating Robot Teams Using Market-Based Mechanisms
-
批准号:0413196
-
项目类别:Continuing Grant
-
资助金额:$0.0万
-
财政年份:2005
-
负责人:Shanghua Teng
-
依托单位:
Spectral Analysis for Graph Partitioning
-
批准号:0311430
-
项目类别:Continuing Grant
-
资助金额:$25.0万
-
财政年份:2003
-
负责人:Shanghua Teng
-
依托单位:
ITR: Collaborative Research: Smoothed Analysis of Algorithms
-
批准号:0325630
-
项目类别:Continuing Grant
-
资助金额:$50.0万
-
财政年份:2003
-
负责人:Shanghua Teng
-
依托单位:
The Eigenvalue Problem in Geometry and Combinatorial Optimization
-
批准号:0224966
-
项目类别:Standard Grant
-
资助金额:$11.88万
-
财政年份:2002
-
负责人:Shanghua Teng
-
依托单位:
The Eigenvalue Problem in Geometry and Combinatorial Optimization
-
批准号:9972532
-
项目类别:Standard Grant
-
资助金额:$24.0万
-
财政年份:1999
-
负责人:Shanghua Teng
-
依托单位:
CAREER: Geometric Methods for Numerical Computing: Graph Partitioning, Mesh Generation and Parallel Computation
-
批准号:9996047
-
项目类别:Standard Grant
-
资助金额:$4.95万
-
财政年份:1998
-
负责人:Shanghua Teng
-
依托单位:
CAREER: Geometric Methods for Numerical Computing: Graph Partitioning, Mesh Generation and Parallel Computation
-
批准号:9502540
-
项目类别:Standard Grant
-
资助金额:$12.99万
-
财政年份:1995
-
负责人:Shanghua Teng
-
依托单位:
海外基金