Higher degree sum-of-squares relaxations robust against oblivious outliers
This work addresses robust signal recovery in high-dimensional statistics for applications like data analysis and machine learning, offering a general method to handle heavy-tailed and adversarial noise, though it builds incrementally on existing sum-of-squares techniques.
The paper tackles the problem of recovering signals from data corrupted by symmetric, heavy-tailed noise, including adversarial outliers, by introducing a framework that extends sum-of-squares algorithms designed for Gaussian noise to handle such noise models. It demonstrates this with concrete results: for tensor PCA, it achieves polynomial-time recovery with a signal-to-noise ratio matching Gaussian noise guarantees up to logarithmic factors, and for sparse PCA, it provides quasipolynomial-time recovery matching state-of-the-art Gaussian noise performance, with evidence suggesting quasipolynomial time may be necessary.
We consider estimation models of the form $Y=X^*+N$, where $X^*$ is some $m$-dimensional signal we wish to recover, and $N$ is symmetrically distributed noise that may be unbounded in all but a small $α$ fraction of the entries. We introduce a family of algorithms that under mild assumptions recover the signal $X^*$ in all estimation problems for which there exists a sum-of-squares algorithm that succeeds in recovering the signal $X^*$ when the noise $N$ is Gaussian. This essentially shows that it is enough to design a sum-of-squares algorithm for an estimation problem with Gaussian noise in order to get the algorithm that works with the symmetric noise model. Our framework extends far beyond previous results on symmetric noise models and is even robust to adversarial perturbations. As concrete examples, we investigate two problems for which no efficient algorithms were known to work for heavy-tailed noise: tensor PCA and sparse PCA. For the former, our algorithm recovers the principal component in polynomial time when the signal-to-noise ratio is at least $\tilde{O}(n^{p/4}/α)$, that matches (up to logarithmic factors) current best known algorithmic guarantees for Gaussian noise. For the latter, our algorithm runs in quasipolynomial time and matches the state-of-the-art guarantees for quasipolynomial time algorithms in the case of Gaussian noise. Using a reduction from the planted clique problem, we provide evidence that the quasipolynomial time is likely to be necessary for sparse PCA with symmetric noise. In our proofs we use bounds on the covering numbers of sets of pseudo-expectations, which we obtain by certifying in sum-of-squares upper bounds on the Gaussian complexities of sets of solutions. This approach for bounding the covering numbers of sets of pseudo-expectations may be interesting in its own right and may find other application in future works.