AF: Small: Beyond Worst-Case Analysis

点击翻译按钮获取中文摘要

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.