Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error

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). Specifically, given an $\varepsilon$-corrupted sample from a distribution D obtained by applying an unknown affine transformation $x \rightarrow A x+b$ to the uniform distribution on a d-dimensional hypercube $[-1,1]^{d}$, our algorithm constructs $\widehat{A}, \hat{b}$ such that the total variation distance of the distribution $\widehat{D}$ from D is $O(\varepsilon)$ using poly $(d)$ time and samples. 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 $\varepsilon$. In particular, if the rows of A are normalized to be unit length, our total variation distance guarantee implies a bound on the sum of the $\ell_{2}$ distances between the row vectors of A and $A^{\prime}, \sum_{i=1}^{d}\left\|a_{(i)}-\hat{a}_{(i)}\right\|_{2}=O(\varepsilon)$. In contrast, the strongest known prior results only yield an $\varepsilon^{O(1)}$ (relative) bound on the distance between individual $a_{i}$’s and their estimates and translate into an $O\left(d \varepsilon^{O(1)}\right)$ bound on the total variation distance.Prior algorithms for this problem rely on implementing standard approaches [12] for ICA based on the classical method of moments [18], [32] combined with robust moment estimators. We prove that any approach that relies on method of moments must provably fail to obtain a dimension independent bound on the total error $\sum_{i}\left\|a_{(i)}-\hat{a}_{(i)}\right\|_{2}$ (and consequently, also in total variation distance). 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, Robust Gradient Descent, is based on a new method that iteratively improves its estimate of the unknown affine transformation whenever the requirements of the certificate are not met.