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

Project: Research project

Project Details


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
Effective start/end date3/15/172/28/22


  • National Science Foundation (CCF-1652491)


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.