# Higher degree sum-of-squares relaxations robust against oblivious outliers

arXiv: https://arxiv.org/abs/2211.07327 · HTML: https://mlsanity.com/paper/2211.07327/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 44 references that are in the map.
- First posted on arXiv 14 Nov 2022.

## Builds on (most cited first, 27 of 27)

- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [Adaptive Huber Regression](https://mlsanity.com/paper/1706.06991/) (2017)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Robust regression with covariate filtering: Heavy tails and adversarial contamination](https://mlsanity.com/paper/2009.12976/) (2020)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Tensor principal component analysis via sum-of-squares proofs](https://mlsanity.com/paper/1507.03269/) (2015)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [Mean Estimation with Sub-Gaussian Rates in Polynomial Time](https://mlsanity.com/paper/1809.07425/) (2018)
- [Statistical limits of spiked tensor models](https://mlsanity.com/paper/1612.07728/) (2016)
- [Statistical and computational trade-offs in estimation of sparse principal components](https://mlsanity.com/paper/1408.5369/) (2014)
- [Sparse CCA: Adaptive Estimation and Computational Barriers](https://mlsanity.com/paper/1409.8565/) (2014)
- [Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression](https://mlsanity.com/paper/1903.08192/) (2019)
- [Sparse PCA via Covariance Thresholding](https://mlsanity.com/paper/1311.5179/) (2013)
- [Sparse PCA: Algorithms, Adversarial Perturbations and Certificates](https://mlsanity.com/paper/2011.06585/) (2020)
- [Robust recovery for stochastic block models](https://mlsanity.com/paper/2111.08568/) (2021)
- [Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness](https://mlsanity.com/paper/1902.07380/) (2019)
- [Consistent regression when oblivious outliers overwhelm](https://mlsanity.com/paper/2009.14774/) (2020)
- [Computational Lower Bounds for Sparse PCA](https://mlsanity.com/paper/1304.0828/) (2013)
- [Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection](https://mlsanity.com/paper/2009.05870/) (2020)
- [On Estimating Rank-One Spiked Tensors in the Presence of Heavy Tailed Errors](https://mlsanity.com/paper/2107.09660/) (2021)
- [Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers](https://mlsanity.com/paper/2111.02966/) (2021)
- [The Complexity of Sparse Tensor PCA](https://mlsanity.com/paper/2106.06308/) (2021)
- [Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks](https://mlsanity.com/paper/2008.13735/) (2020)
- [The Strongish Planted Clique Hypothesis and Its Consequences](https://mlsanity.com/paper/2011.05555/) (2020)
- [On the well-spread property and its relation to linear regression](https://mlsanity.com/paper/2206.08092/) (2022)

## Built on by (most cited first, 6 of 6)

- [Sparse PCA Beyond Covariance Thresholding](https://mlsanity.com/paper/2302.10158/) (2023)
- [Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions](https://mlsanity.com/paper/2309.11657/) (2023)
- [Perturb-and-Project: Differentially Private Similarities and Marginals](https://mlsanity.com/paper/2406.04868/) (2024)
- [Robust Mean Estimation Without Moments for Symmetric Distributions](https://mlsanity.com/paper/2302.10844/) (2023)
- [Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians](https://mlsanity.com/paper/2502.06564/) (2025)
- [Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination](https://mlsanity.com/paper/2510.10665/) (2025)

## Abstract (arXiv)

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 tildeO(np/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.