CAREER: Beyond Worst-Case Analysis: New Approaches in Approximation Algorithms and Machine Learning

聚类、概率模型的无监督学习等组合优化问题是机器学习、计算机视觉、运筹学和数据分析等领域的重要计算问题。然而，我们对这些问题的理论理解和实践理解之间存在着很大的脱节--虽然理论告诉我们，在最坏的情况下，组合优化和机器学习中许多有趣的计算问题是难以解决的，但机器学习和计算机视觉等领域的实践者在解决这些理论上的困难问题方面取得了重大进展。这个项目专注于通过开发范式和机制来弥合理论和实践之间的根本鸿沟，这些范式和机制将允许我们对算法在现实世界实例中的性能进行推理。这项研究有可能对计算机科学、机器学习和统计学的不同领域的计算问题的理论和实践产生广泛的影响。该项目将涉及所有研究水平的学生，将在研究生和本科课程中整合平均案例分析的各个方面，并将包括在埃文斯顿和更广泛的芝加哥地区的高中的推广活动。PI将通过使用现实的平均案例模型和平滑分析来研究机器学习和组合优化中的几个问题。广泛的目标包括设计新的独立于模型的算法，并为图划分和集群的现实平均情况模型提供可证明的保证，以及挑战没有唯一或种植解决方案的平均情况设置。这些算法还将导致新的算法技术，用于学习概率模型，例如对各种建模误差和噪声具有鲁棒性的高斯和随机分块模型的混合。该项目的另一个重点是开发新的高效算法，用于学习潜变量模型，并使用平滑分析对算法的性能进行推理。

Combinatorial optimization problems such as clustering, and unsupervised learning of probabilistic models are important computational problems that arise in diverse areas including machine learning, computer vision, operations research and data analysis. However, there is a large disconnect between our theoretical and practical understanding of these problems -- while theory tells us that many interesting computational problems in combinatorial optimization and machine learning are intractable in the worst case, practitioners in areas such as machine learning and computer vision have made significant progress in solving such theoretically hard problems. This project focuses on bridging the fundamental gap between theory and practice by developing paradigms and machinery that will allow us to reason about the performance of algorithms on real-world instances. This research has the potential to have broad impact on both theory and practice of computational problems across different areas of computer science, machine learning and statistics. The project will involve students at all levels of research, will integrate aspects of average-case analysis in both graduate and undergraduate courses, and will include outreach activities in high schools in Evanston and the broader Chicago area.The PI will study several problems in machine learning and combinatorial optimization by using realistic average-case models and smoothed analysis. Broad goals include designing new model-independent algorithms with provable guarantees for realistic average-case models of graph partitioning and clustering and challenging average-case settings where there is no unique or planted solution. These algorithms will also lead to new algorithmic techniques for learning probabilistic models such as mixtures of Gaussians and stochastic block models that are robust to various kinds of modeling errors and noise. Another focus of the project is on developing new efficient algorithms for learning latent variable models and for reasoning about the performance of algorithms using smoothed analysis.