Description:

Monday / CS Seminar
November 10th / 12:00 PM
Hybrid / Mudd 3514

Speaker
Aravindan Vijayaraghavan, Northwestern University

Talk Title
Toward a Modern Theory of Algorithms in the Machine Learning Era

Abstract

The remarkable empirical successes of machine learning have revealed the power of computational techniques in several domains and scientific disciplines. Yet there is a striking disconnect in the algorithmic foundations of machine learning: many basic computational problems, ranging from classification and clustering to deep learning, reduce to non-convex optimization tasks that are computationally intractable in the worst case. Yet, in practice, heuristics often succeed in producing high-quality solutions, fueling the remarkable progress of modern AI. At the same time,  the absence of rigorous guarantees raises the following question:  when, and under what conditions, can we reliably use predictions of machine learning models?

In the first part of the talk, I will describe theoretical frameworks like smoothed analysis that go beyond worst-case analysis to better reason about algorithms on typical instances, and help obtain rigorous polynomial time guarantees for challenging algorithmic problems in ML and high-dimensional data analysis. In the second part of the talk, I will present recent principled approaches that treat machine learning models as powerful black boxes that are potentially unreliable or biased, and show how to design algorithms that can rigorously quantify and account for their uncertainty.

Biography
Aravindan Vijayaraghavan is an Associate Professor at Northwestern University in the department of Computer Science, and (by courtesy) Industrial Engineering and Management Sciences. He is also the co-director of the NSF Institute for Data, Econometrics, Algorithms and Learning (IDEAL). His research interests are broadly in algorithms and foundations of data science and machine learning.

---

CSPAC Community Connections: Resumé Bias
Zoom Link
Panopto Link