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.
