Robust Gradient Descent - Agnostically Estimating an Unknown Affine Transformation

Explore a groundbreaking polynomial-time algorithm for robustly learning unknown affine transformations in this 51-minute lecture by Santosh Vempala from Georgia Tech. Delve into the world of independent component analysis (ICA) and discover how this algorithm efficiently constructs estimates for affine transformations using corrupted samples from a uniform distribution on a d-dimensional hypercube. Learn about the algorithm's ability to achieve optimal recovery guarantees and its superiority over previous methods based on moments. Understand the key component, Robust Gradient Descent, and its novel geometric certificate for verifying affine transformations. Gain insights into the iterative improvement process and the algorithm's applications in optimization and algorithm design. This talk, part of the Simons Institute's series, presents joint work with He Jia and Pravesh Kothari, offering a deep dive into advanced concepts in robust estimation and machine learning.