AF: Small: Beyond Worst-Case Analysis

随着算法日益主导我们的世界，理解它们何时起作用以及为什么起作用的需求从未像现在这样强烈。算法的数学分析的目标是提供关于哪种算法是解决给定计算问题的“最佳”算法的指导。最坏情况分析通过算法在给定大小的任何输入上的最差性能来总结算法的性能概况，隐含地倡导具有最佳可能最坏情况性能的算法。强大的最坏情况保证是算法设计的圣杯，它为算法的稳健良好性能提供了与应用无关的证明。然而，对于许多基本问题和业绩衡量标准，这样的保证是不可能的，需要一种更微妙的分析方法。这个项目调查了最坏情况分析的几种替代方案，并将其应用于机器学习和社会网络分析。该项目有三个研究主题。第一个重点是“平滑分析”，即对手选择的输入受到自然干扰，并集中在两个不同的应用领域，都有突出的开放问题：在线学习中的后悔最小化，以及组合问题的局部搜索算法的运行时间。第二个重点是研究机器学习中的结构化预测问题，其中的目标是使用关于对象之间关系的信息(例如，识别句子中的词性图像中的区域)来联合标记对象的集合。在这里，问题涉及作为对象关系的组合结构和数据中的噪声量的函数的地面真相标记可以恢复到什么程度。最后一个要点是关于社交网络的无分销模式，这种模式的动机是三分封闭。这里的目标是研究为社交网络量身定做的新图类，并证明它们的结构和算法结果。总而言之，这些研究既深化了“超越最坏情况分析”的最先进水平，也将其延伸到重要的新应用领域。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.