Live Stream link:

https://northwestern.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=622cd1a9-eccb-40d4-8f7c-ac42013ca002

Title:

How to reason about typical instances of algorithmic problems

Abstract

Worst-case analysis has traditionally been the tool of choice to measure the performance of algorithms and has led to a rich theory of algorithms and computational complexity. However, for many computational problems there is a large disconnect between our theoretical and practical understanding of their complexity. Many fundamental problems in machine learning and data analysis like clustering and inference correspond to well-studied algorithmic problems that are NP-hard in the worst-case, yet heuristics seem effective in solving ``typical'' instances of these theoretically hard problems. On the other extreme, statistical models of data are ubiquitous in machine learning. However, real-world instances are often noisy. Yet many algorithms for these models are often not robust - they are tailored to the specific distribution or model, and brittle to small amounts of modeling errors. This leads to the following major challenge.

Can we develop new theoretical frameworks that address the disconnect between theory and practice, by reasoning about ``typical'' instances of problems?

Towards addressing this challenge, we will consider paradigms like smoothed analysis and semi-random models that go beyond traditional worst-case analysis to reason about typical instances of algorithmic problems. I will use these paradigms to design efficient algorithms with strong guarantees for NP-hard problems like clustering, learning probabilistic models, tensor decompositions, high-dimensional inference etc. We will also see how these approaches can help in designing robust and reliable algorithms for machine learning that are reliable in the presence of errors and adversarial corruptions.

Biography

Aravindan Vijayaraghavan is an Assistant Professor of Computer Science at Northwestern University. He obtained his PhD in Computer Science from Princeton University in 2012, followed by postdoctoral fellowships at Carnegie Mellon University (as the Simons postdoctoral fellow), and the Courant Institute (with the Simons Collaboration on Algorithms & Geometry). His research interests are in designing efficient algorithms for problems in machine learning and combinatorial optimization, and in using paradigms that go beyond worst-case analysis to obtain good algorithmic guarantees. He is a recipient of the NSF CAREER award and is a co-director of the NSF-funded Institute for Data, Econometrics, Algorithms and Learning (IDEAL).