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

Northwestern University, Evanston IL

Investigators

Abstract

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.