We learn from our alumni in this interaction series, often technically, sometimes semi-technically.

Aravindan Vijayaraghavan Northwestern University

Aravindan is an Associate Professor in the CS department at Northwestern University. His research interests are broadly in theoretical computer science. He works on the algorithmic foundations of machine learning, data science, combinatorial optimization, and more recently, quantum information. He is particularly interested in using paradigms that go Beyond Worst-Case Analysis to obtain good algorithmic guarantees. He serves as the Institute Director (2023-24) and a Site Director (Northwestern) of the Institute for Data, Economics, Algorithms and Learning (IDEAL), a NSF-funded collaborative institute across Northwestern, TTI Chicago, UIC, U of Chicago, and IIT. Prior to joining Northwestern in Fall 2015, he was at Courant, NYU for a year as a part of the Simons Collaboration on Algorithms and Geometry , and was a Simons Postdoctoral Research Fellow with the Theory Group at Carnegie Mellon University. He obtained PhD from Princeton University in Computer Science with Prof. Moses Charika. Prior to that, he finished the bachelor's degree in CS from the Indian Institute of Technology Madras in 2007.

Smoothed analysis is a powerful paradigm in overcoming worst-case intractability for algorithmic problems in many domains including machine learning. In this talk, I will describe a general framework for showing polynomial time smoothed analysis guarantees, and demonstrate its use through applications for some basic problems in machine learning including learning latent variable models, 2-layer neural networks etc., and for problems in quantum entanglement certification. The main technical contribution that enables these smoothed analysis guarantees are new probabilistic techniques to prove lower bounds on the least singular value of random matrix ensembles with highly dependent entries.

Organizers