Estimating Principal Components under Adversarial Perturbations
- URL: http://arxiv.org/abs/2006.00602v2
- Date: Tue, 2 Jun 2020 03:31:04 GMT
- Title: Estimating Principal Components under Adversarial Perturbations
- Authors: Pranjal Awasthi, Xue Chen, Aravindan Vijayaraghavan
- Abstract summary: We study a natural model of robustness for high-dimensional statistical estimation problems.
Our model is motivated by emerging paradigms such as low precision machine learning and adversarial training.
- Score: 25.778123431786653
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Robustness is a key requirement for widespread deployment of machine learning
algorithms, and has received much attention in both statistics and computer
science. We study a natural model of robustness for high-dimensional
statistical estimation problems that we call the adversarial perturbation
model. An adversary can perturb every sample arbitrarily up to a specified
magnitude $\delta$ measured in some $\ell_q$ norm, say $\ell_\infty$. Our model
is motivated by emerging paradigms such as low precision machine learning and
adversarial training.
We study the classical problem of estimating the top-$r$ principal subspace
of the Gaussian covariance matrix in high dimensions, under the adversarial
perturbation model. We design a computationally efficient algorithm that given
corrupted data, recovers an estimate of the top-$r$ principal subspace with
error that depends on a robustness parameter $\kappa$ that we identify. This
parameter corresponds to the $q \to 2$ operator norm of the projector onto the
principal subspace, and generalizes well-studied analytic notions of sparsity.
Additionally, in the absence of corruptions, our algorithmic guarantees recover
existing bounds for problems such as sparse PCA and its higher rank analogs. We
also prove that the above dependence on the parameter $\kappa$ is almost
optimal asymptotically, not just in a minimax sense, but remarkably for every
instance of the problem. This instance-optimal guarantee shows that the $q \to
2$ operator norm of the subspace essentially characterizes the estimation error
under adversarial perturbations.
Related papers
- Wasserstein Distributionally Robust Multiclass Support Vector Machine [1.8570591025615457]
We study the problem of multiclass classification for settings where data features $mathbfx$ and their labels $mathbfy$ are uncertain.
We use Wasserstein distributionally robust optimization to develop a robust version of the multiclass support vector machine (SVM) characterized by the Crammer-Singer (CS) loss.
Our numerical experiments demonstrate that our model outperforms state-of-the art OVA models in settings where the training data is highly imbalanced.
arXiv Detail & Related papers (2024-09-12T21:40:04Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
Single-Index Models are high-dimensional regression problems with planted structure.
We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
arXiv Detail & Related papers (2024-03-08T18:50:19Z) - Sparse PCA with Oracle Property [115.72363972222622]
We propose a family of estimators based on the semidefinite relaxation of sparse PCA with novel regularizations.
We prove that, another estimator within the family achieves a sharper statistical rate of convergence than the standard semidefinite relaxation of sparse PCA.
arXiv Detail & Related papers (2023-12-28T02:52:54Z) - Universality of max-margin classifiers [10.797131009370219]
We study the role of featurization maps and the high-dimensional universality of the misclassification error for non-Gaussian features.
In particular, the overparametrization threshold and generalization error can be computed within a simpler model.
arXiv Detail & Related papers (2023-09-29T22:45:56Z) - On the Identifiability and Estimation of Causal Location-Scale Noise
Models [122.65417012597754]
We study the class of location-scale or heteroscedastic noise models (LSNMs)
We show the causal direction is identifiable up to some pathological cases.
We propose two estimators for LSNMs: an estimator based on (non-linear) feature maps, and one based on neural networks.
arXiv Detail & Related papers (2022-10-13T17:18:59Z) - Consistent Estimation for PCA and Sparse Regression with Oblivious
Outliers [13.244654316770815]
We develop machinery to design efficiently computable and consistent estimators.
For sparse regression, we achieve consistency for optimal sample size $ngsim (klog d)/alpha2$.
In the context of PCA, we attain optimal error guarantees under broad spikiness assumptions on the parameter matrix.
arXiv Detail & Related papers (2021-11-04T15:59:44Z) - Learning with User-Level Privacy [61.62978104304273]
We analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints.
Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution.
We derive an algorithm that privately answers a sequence of $K$ adaptively chosen queries with privacy cost proportional to $tau$, and apply it to solve the learning tasks we consider.
arXiv Detail & Related papers (2021-02-23T18:25:13Z) - Sharp Statistical Guarantees for Adversarially Robust Gaussian
Classification [54.22421582955454]
We provide the first result of the optimal minimax guarantees for the excess risk for adversarially robust classification.
Results are stated in terms of the Adversarial Signal-to-Noise Ratio (AdvSNR), which generalizes a similar notion for standard linear classification to the adversarial setting.
arXiv Detail & Related papers (2020-06-29T21:06:52Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator)
We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$.
We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
arXiv Detail & Related papers (2020-05-26T17:53:18Z) - A Precise High-Dimensional Asymptotic Theory for Boosting and
Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
This paper establishes a precise high-dimensional theory for boosting on separable data.
Under a class of statistical models, we provide an exact analysis of the universality error of boosting.
We also explicitly pin down the relation between the boosting test error and the optimal Bayes error.
arXiv Detail & Related papers (2020-02-05T00:24:53Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.