Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers
Authors: Tommaso d'Orsi, Chih-Hung Liu, Rajai Nasser, Gleb Novikov, David Steurer, Stefan Tiegel
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We develop machinery to design efficiently computable and consistent estimators, achieving estimation error approaching zero as the number of observations grows, when facing an oblivious adversary that may corrupt responses in all but an α fraction of the samples. As concrete examples, we investigate two problems: sparse regression and principal component analysis (PCA). For sparse regression, we achieve consistency for optimal sample size n (k log d)/α2 and optimal error rate O( p (k log d)/(n α2)) where n is the number of observations, d is the number of dimensions and k is the sparsity of the parameter vector, allowing the fraction of inliers to be inverse-polynomial in the number of samples. Prior to this work, no estimator was known to be consistent when the fraction of inliers α is o(1/log log n), even for (non-spherical) Gaussian design matrices. Results holding under weak design assumptions and in the presence of such general noise have only been shown in dense setting (i.e., general linear regression) very recently by d Orsi et al. (d NS21). In the context of PCA, we attain optimal error guarantees under broad spikiness assumptions on the parameter matrix (usually used in matrix completion). Previous works could obtain non-trivial guarantees only under the assumptions that the measurement noise corresponding to the inliers is polynomially small in n (e.g., Gaussian with variance 1/n2). To devise our estimators, we equip the Huber loss with non-smooth regularizers such as the ℓ1 norm or the nuclear norm, and extend d Orsi et al. s approach (d NS21) in a novel way to analyze the loss function. Our machinery appears to be easily applicable to a wide range of estimation problems. We complement these algorithmic results with statistical lower bounds showing that the fraction of inliers that our PCA estimator can deal with is optimal up to a constant factor. |
| Researcher Affiliation | Academia | Tommaso d Orsi ETH Zürich Zürich, Switzerland Chih-Hung Liu ETH Zürich Zürich, Switzerland Rajai Nasser ETH Zürich Zürich, Switzerland Gleb Novikov ETH Zürich Zürich, Switzerland David Steurer ETH Zürich Zürich, Switzerland Stefan Tiegel ETH Zürich Zürich, Switzerland |
| Pseudocode | No | The paper defines estimators using mathematical equations (e.g., Eq. 2.2, Eq. 2.3) and describes their theoretical properties, but does not present any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statements about releasing open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments on a specific dataset. It discusses observations and data within the context of statistical models, but not as empirical datasets that are made available. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments with dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any specific experimental setup details, such as hyperparameters or training configurations for empirical evaluation. |