Algorithms & Randomness Center (ARC)
Ainesh Bakshi (CMU)
Monday, January 31, 2022
Virtual via BlueJeans - 11:00 am
Title: Analytic Techniques for Robust Algorithm Design
Abstract: Modern machine learning relies on algorithms that fit expressive models to large datasets. While such tasks are easy in low dimensions, real-world datasets are truly high-dimensional. Additionally, a prerequisite to deploying models in real-world systems is to ensure that their behavior degrades gracefully when the modeling assumptions no longer hold. Therefore, there is a growing need for efficient algorithms that fit reliable and robust models to data.
In this talk, I will provide an overview of designing such efficient and robust algorithms, with provable guarantees, for fundamental tasks in machine learning and statistics. In particular, I will describe two complementary themes arising in this area: high-dimensional robust statistics and fast numerical linear algebra. The first addresses how to fit expressive models to high-dimensional datasets in the presence of outliers and the second develops fast algorithmic primitives to reduce dimensionality and de-noise large datasets. I will focus on recent results on robustly learning mixtures of arbitrary Gaussians and describe the new algorithmic ideas obtained along the way. Finally, I will make the case for analytic techniques, such as convex relaxations, being the natural choice for robust algorithm design.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
