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.