Seminars

View all Seminars  |  Download ICal for this event

Robustly Learning Affine Transformations with Asymptotically Optimal Error

Series: Bangalore Theory Seminars

Speaker: He Jia Georgia Tech

Date/Time: Sep 22 11:00:00

Location: CSA Lecture Hall (Room No. 112, Ground Floor)

Abstract:
We present a polynomial-time algorithm for robustly learning an unknown affine transformation of the standard hypercube from samples, an important and well-studied setting for independent component analysis (ICA). Total variation distance is the information-theoretically strongest possible notion of distance in our setting and our recovery guarantees in this distance are optimal up to the absolute constant factor multiplying the fraction of corruption. Our key innovation is a new approach to ICA (even to outlier-free ICA) that circumvents the difficulties in the classical method of moments and instead relies on a new geometric certificate of correctness of an affine transformation. Our algorithm is based on a new method that iteratively improves an estimate of the unknown affine transformation whenever the requirements of the certificate are not met.


Microsoft Teams link:

Link

We are grateful to the Kirani family for generously supporting the theory seminar series

Hosts: Rameesh Paul, Rahul Madhavan, Rachana Gusain, KVN Sreenivas