AF: Medium:Smoothed Analysis in Multi-Objective Optimization, Machine Learning, and Algorithmic Game Theory

AF：中：多目标优化、机器学习和算法博弈论中的平滑分析

• 批准号: 0964481
• 负责人: Shanghua Teng
• 金额: $ 109.99万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-03-01 至 2015-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0964481&HistoricalAwards=false
• 关键词: AF; Medium; Smoothed; Analysis; Multi

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.

项目技术说明：引入平滑分析来研究算法在其良好的实际性能无法通过传统框架（如最坏情况和平均情况分析）预测时的行为。在介绍平滑分析的原始论文中，Spielman和Teng证明了单纯形方法，这是已知具有较差最坏情况性能的令人惊讶的实用算法之一，具有良好的平滑复杂性。自提出以来，平滑分析已被应用于数学规划、数值分析和组合优化等领域的优化。为了跟进线性规划的这一突破，其主要关注的是优化单个线性目标函数，本项目的目标是将平滑分析扩展到涉及多个目标函数和多个代理的优化问题，在计算博弈和经济学理论中经常被考虑。该项目的计划还将包括在平滑设置中的机器学习算法的设计和分析。多目标优化计划是为了改进最近的工作，该工作表明，任何具有恒定数量目标函数的二元线性优化问题的Pareto集在平滑模型中具有多项式大小。在博弈论中，研究将集中在资源分配和调度的几个潜在的游戏的平滑复杂性。对于这两个问题，需要一个新的分析方法的性能的迭代过程。 在机器学习中，目标是将PAC的平滑分析和产品分布的不可知学习的结果扩展到其他更实际的分布。该项目更广泛的意义和重要性：这项研究将深入了解为什么多目标优化，局部搜索和机器学习中的算法学是成功的，并允许理论计算机科学的研究人员将这些算法学纳入算法规范。它还将提供算法的见解涉及多个代理和多目标优化问题只涉及一个代理的博弈论问题之间的差异。通过开发一种理论，更好地预测算法在实践中的性能，这项研究有希望让研究人员开发更强大的算法。当一个人设计一个算法的时候，他在设计的时候就已经考虑到了为什么它应该工作。通过提供一个新的分析概念，它意味着一个算法“在实践中工作”，这项研究可以塑造算法设计者的直觉，包括算法，否则可能会被丢弃的“坏的最坏的情况。“这个项目的主要目标是在理论计算机科学（TCS）学科与运筹学，博弈论和数学经济学学科之间建立桥梁。如果成功，该项目将有助于提供一个框架，在TCS的研究人员可以了解这些学科的一些伟大的实际成就。反过来，通过提供尊重这些学科研究人员对什么是“实际投入”的敏感性的分析，该项目将增加理论分析对这些领域研究人员的价值。由于该项目将来自许多学科的想法结合在一个连贯的研究工作中，因此就该项目的成果所提供的讲座和教程将有助于其范围内的学科交叉。在这个项目中，对算法学成功的理论解释的发展应该简化算法教育，并允许在计算机科学家教育的早期阶段讨论实际重要的算法学。这些解释也简化了设计这些主题的易于理解的讲座的任务，并且由本研究启发的这些讲座笔记将由PI和合作者在互联网上提供。