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.