Abstract
We present a polynomial-time algorithm for robustly learning an unknown affine transformation of the standard hypercube from samples, a well-studied setting of independent component analysis (ICA). Specifically, given an $\epsilon$-corrupted sample from the distribution $D$ obtained by applying an unknown affine transformation $x \rightarrow Ax+b$ to the uniform distribution on the $d$-dimensional hypercube $[-1,1]^d$, our algorithm constructs $\hat{A}, \hat{b}$ such that the total variation distance of the distribution $\hat{D}$ from $D$ is $O(\epsilon)$, using poly$(d)$ time and samples. TV-distance is information-theoretically the strongest possible notion of distance in this setting and our recovery guarantees are asymptotically optimal. Prior work based on the method of moments had polynomial dependence on the dimension. It turns out that any approach that relies on the (robust) method of moments provably fails, unlike the situation for most other robust estimation problems. The key ingredient of our algorithm, Robust Gradient Descent, relies on a new geometric certificate of correctness of an affine transformation. It iteratively improves its estimate of the affine transformation whenever the requirements of the certificate are not met.
This is joint work with He Jia and Pravesh Kothari. The use of SoS and sentient AI will be minimal.