# On the Hardness of Robust Classification

@inproceedings{Gourdeau2019OnTH, title={On the Hardness of Robust Classification}, author={Pascale Gourdeau and Varun Kanade and Marta Z. Kwiatkowska and James Worrell}, booktitle={Electron. Colloquium Comput. Complex.}, year={2019} }

It is becoming increasingly important to understand the vulnerability of machine learning models to adversarial attacks. In this paper we study the feasibility of robust learning from the perspective of computational learning theory, considering both sample and computational complexity. In particular, our definition of robust learnability requires polynomial sample complexity. We start with two negative results. We show that no non-trivial concept class can be robustly learned in the… Expand

#### Figures and Topics from this paper

#### 21 Citations

Lower Bounds for Adversarially Robust PAC Learning under Evasion and Hybrid Attacks

- Computer Science
- 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA)
- 2020

It is proved that for many theoretically natural input spaces of high dimension n, PAC learning requires sample complexity that is exponential in the data dimension n and it is shown that PAC learning is sometimes impossible under such hybrid attacks, while it is possible without the attack. Expand

On Robustness to Adversarial Examples and Polynomial Optimization

- Computer Science, Mathematics
- NeurIPS
- 2019

The main contribution of this work is to exhibit a strong connection between achieving robustness to adversarial examples, and a rich class of polynomial optimization problems, thereby making progress on the above questions. Expand

Towards Deep Learning Models Resistant to Large Perturbations

- Computer Science, Mathematics
- ArXiv
- 2020

It is shown that the well-established algorithm called "adversarial training" fails to train a deep neural network given a large, but reasonable, perturbation magnitude, and a simple yet effective initialization of the network weights is proposed that makes learning on higher levels of noise possible. Expand

Unique properties of adversarially trained linear classifiers on Gaussian data

- Computer Science, Mathematics
- ArXiv
- 2020

It is shown with a linear classifier, it is always possible to solve a binary classification problem on Gaussian data under arbitrary levels of adversarial corruption during training, and that this property is not observed with non-linear classifiers on the CIFAR-10 dataset. Expand

Robust Learning against Logical Adversaries

- Computer Science, Mathematics
- ArXiv
- 2020

Investigation of logical adversaries, a broad class of attackers who create adversarial examples within a reflexive-transitive closure of a logical relation, produces a learning framework with provable robustness guarantee for malware detection and applies it to malware detection. Expand

Black-box Certification and Learning under Adversarial Perturbations

- Computer Science, Mathematics
- ICML
- 2020

We formally study the problem of classification under adversarial perturbations, both from the learner's perspective, and from the viewpoint of a third-party who aims at certifying the robustness of… Expand

On the (Un-)Avoidability of Adversarial Examples

- Computer Science, Mathematics
- ArXiv
- 2021

This work carefully argues that adversarial robustness should be defined as a locally adaptive measure complying with the underlying distribution, and suggests a definition for an adaptive robust loss, derive an empirical version of it, and develop a resulting data-augmentation framework. Expand

Adversarial examples and where to find them

- Computer Science, Mathematics
- ArXiv
- 2020

This work analyzes where adversarial examples occur, in which ways they are peculiar, and how they are processed by robust models to provide concrete recommendations for anyone looking to train a robust model or to estimate how much robustness they should require for their operation. Expand

Adversarial robustness via stochastic regularization of neural activation sensitivity

- Computer Science
- ArXiv
- 2020

This work flatten the gradients of the loss surface, making adversarial examples harder to find, using a novel stochastic regularization term that explicitly decreases the sensitivity of individual neurons to small input perturbations, and pushes the decision boundary away from correctly classified inputs by leveraging Jacobian regularization. Expand

Efficiently Learning Adversarially Robust Halfspaces with Noise

- Computer Science, Mathematics
- ICML
- 2020

A simple computationally efficient algorithm is given for learning adversarially robust halfspaces in the distribution-independent setting with respect to any $\ell_p$-perturbation. Expand

#### References

SHOWING 1-10 OF 29 REFERENCES

Adversarial examples from computational constraints

- Computer Science, Mathematics
- ICML
- 2019

This work proves that, for a broad set of classification tasks, the mere existence of a robust classifier implies that it can be found by a possibly exponential-time algorithm with relatively few training examples and gives an exponential separation between classical learning and robust learning in the statistical query model. Expand

Can Adversarially Robust Learning Leverage Computational Hardness?

- Computer Science, Mathematics
- ALT
- 2019

This work proves strong barriers against achieving envisioned computational robustness both for evasion and poisoning attacks and proves that for any learning algorithm with sample complexity $m and any efficiently computable "predicate" defining some "bad" property $B$ for the produced hypothesis, there exists polynomial-time online poisoning attacks. Expand

The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure

- Computer Science, Mathematics
- AAAI
- 2019

This work investigates the adversarial risk and robustness of classifiers and draws a connection to the well-known phenomenon of concentration of measure in metric measure spaces, showing that if the metric probability space of the test instance is concentrated, any classifier with some initial constant error is inherently vulnerable to adversarial perturbations. Expand

Adversarial Examples from Cryptographic Pseudo-Random Generators

- Computer Science, Mathematics
- ArXiv
- 2018

This paper constructs a binary classification task for which a robust classifier exists; yet no non-trivial accuracy can be obtained with an efficient algorithm in (i) the statistical query model and proves computational hardness of learning this task under a standard cryptographic assumption. Expand

Analysis of classifiers’ robustness to adversarial perturbations

- Computer Science, Mathematics
- Machine Learning
- 2017

A general upper bound on the robustness of classifiers to adversarial perturbations is established, and the phenomenon of adversarial instability is suggested to be due to the low flexibility ofclassifiers, compared to the difficulty of the classification task (captured mathematically by the distinguishability measure). Expand

Robustness of classifiers: from adversarial to random noise

- Computer Science, Mathematics
- NIPS
- 2016

This paper proposes the first quantitative analysis of the robustness of nonlinear classifiers in this general noise regime, and establishes precise theoretical bounds on the robustity of classifier's decision boundary, which depend on the curvature of the classifiers' decision boundary. Expand

On Basing Lower-Bounds for Learning on Worst-Case Assumptions

- Mathematics, Computer Science
- 2008 49th Annual IEEE Symposium on Foundations of Computer Science
- 2008

It is proved that if alanguage L reduces to the task of improper learning of circuits, then, depending on the type of the reduction in use, either L has a statistical zero-knowledge argument system, or the worst-case hardness of L implies the existence of a weak variant of one-way functions defined by Ostrovsky-Wigderson (ISTCS '93). Expand

Computational Limitations in Robust Classification and Win-Win Results

- Computer Science, Mathematics
- IACR Cryptol. ePrint Arch.
- 2019

Even though an efficient classifier that is robust to large perturbations exists, it is computationally hard to learn any non-trivial robust classifier, even when computationally unbounded robust classifiers exist. Expand

Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution

- Computer Science, Mathematics
- NeurIPS
- 2018

This study advocates the use of the error-region definition of adversarial perturbations, and studies inherent bounds on risk and robustness of any classifier for any classification problem whose instances are uniformly distributed over $\{0,1\}^n". Expand

Adversarial vulnerability for any classifier

- Computer Science, Mathematics
- NeurIPS
- 2018

This paper derives fundamental upper bounds on the robustness to perturbation of any classification function, and proves the existence of adversarial perturbations that transfer well across different classifiers with small risk. Expand