| Title | : | Reasoning about Typical Instances through Smoothed analysis |
| Speaker | : | Aravindan Vijayaraghavan (Northwestern University, USA) |
| Details | : | Fri, 2 Aug, 2024 2:00 PM @ Turing Hall (SSB 334 |
| Abstract: | : | 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. |
