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

Theoretical computer science has given us many wonderful paradigms such as worst-case analysis, NPcompleteness and approximation algorithms to study computational problems. However, while theory tells us that many interesting problems in combinatorial optimization and machine learning are intractable in the worst case, practitioners in areas like machine learning and computer vision have made significant progress in solving such theoretically hard problems. Bridging this gap in our theoretical and practical understanding is one of the primary challenges of modern day theoretical computer science. This proposal focuses on bridging the gap between theory and practice by using paradigms that go beyond traditional worst-case analysis, in the context of several problems in machine learning and combinatorial optimization. The broad goals are: � Studying realistic average-case models of NP-hard optimization problems, and designing algorithms with improved guarantees for these models. The goal here is to introduce new average-case models for problems like graph partitioning and clustering, that are general enough to capture real-world instances, and design new algorithms with better approximation guarantees than in the worst-case. � Developing new efficient, robust algorithms for learning probabilistic models like mixtures of Gaussians and stochastic block models. The emphasis here is develop new algorithmic techniques with provable guarantees that are robust to various kinds of modeling errors and noise. � Designing efficient algorithms with provable guarantees for unsupervised learning problems, that are intractable in the worst-case. The goal is to develop general mathematical techniques to reason about the performance of algorithms using smoothed analysis, for problems like learning hidden markov models (HMM), subspace clustering and tensor decompositions. � Developing new algorithms and tools for average-case problems with no unique, planted solution, like sparse recovery and learning parity with noise. � Using new insights from average-case analysis to design improved worst-case algorithms based on convex relaxations that obtain the same worst-case guarantees. Intellectual Merit: The project aim to bridge fundamental gaps between the theoretical and practical understanding of problems in combinatorial optimization and machine learning. The project involves developing new algorithms for non-adversarial settings, and mathematical techniques to reason about average-case behavior and smoothed analysis of various computational problems. Tackling the main goals of the project will lead to fundamental advances in both theory and practice: it will involve identifying structural properties and new beyond-worst-case paradigms that on the one hand capture real-world instances, and on the other hand allow us to provide provable guarantees. Broader Impact: The proposed work will lead to novel algorithms and a new understanding of average-case models for real-world instances of important computational problems in machine learning and statistics. The research from this proposal is likely to lead to completely new directions of study in algorithms research: a major focus of the research will be the creation of new average-case models and algorithmic frameworks that are both amenable to theoretical study and which capture the essence of real-world instances. The PI will develop new courses related to beyond worst case analysis, and will involve graduate students and undergraduate students on research proposed in this