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.