Robust Classification Under $\ell_0$ Attack for the Gaussian Mixture Model

• URL: http://arxiv.org/abs/2104.02189v1
• Date: Mon, 5 Apr 2021 23:31:25 GMT
• Title: Robust Classification Under $\ell_0$ Attack for the Gaussian Mixture Model
• Authors: Payam Delgosha, Hamed Hassani, Ramtin Pedarsani
• Abstract summary: We develop a novel classification algorithm called FilTrun that has two main modules: filtration and Truncation. We discuss several examples that illustrate interesting behaviors such as a phase transition for adversary's budget determining whether the effect of adversarial perturbation can be fully neutralized.
• Score: 39.414875342234204
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It is well-known that machine learning models are vulnerable to small but cleverly-designed adversarial perturbations that can cause misclassification. While there has been major progress in designing attacks and defenses for various adversarial settings, many fundamental and theoretical problems are yet to be resolved. In this paper, we consider classification in the presence of $\ell_0$-bounded adversarial perturbations, a.k.a. sparse attacks. This setting is significantly different from other $\ell_p$-adversarial settings, with $p\geq 1$, as the $\ell_0$-ball is non-convex and highly non-smooth. Under the assumption that data is distributed according to the Gaussian mixture model, our goal is to characterize the optimal robust classifier and the corresponding robust classification error as well as a variety of trade-offs between robustness, accuracy, and the adversary's budget. To this end, we develop a novel classification algorithm called FilTrun that has two main modules: Filtration and Truncation. The key idea of our method is to first filter out the non-robust coordinates of the input and then apply a carefully-designed truncated inner product for classification. By analyzing the performance of FilTrun, we derive an upper bound on the optimal robust classification error. We also find a lower bound by designing a specific adversarial strategy that enables us to derive the corresponding robust classifier and its achieved error. For the case that the covariance matrix of the Gaussian mixtures is diagonal, we show that as the input's dimension gets large, the upper and lower bounds converge; i.e. we characterize the asymptotically-optimal robust classifier. Throughout, we discuss several examples that illustrate interesting behaviors such as the existence of a phase transition for adversary's budget determining whether the effect of adversarial perturbation can be fully neutralized.

Related papers

• Generalization Properties of Adversarial Training for $\ell_0$-Bounded Adversarial Attacks [47.22918498465056]
  In this paper, we aim to theoretically characterize the performance of adversarial training for an important class of neural networks. Deriving a generalization in this setting has two main challenges.
  arXiv  Detail & Related papers  (2024-02-05T22:57:33Z)
• Towards Compositional Adversarial Robustness: Generalizing Adversarial Training to Composite Semantic Perturbations [70.05004034081377]
  We first propose a novel method for generating composite adversarial examples. Our method can find the optimal attack composition by utilizing component-wise projected gradient descent. We then propose generalized adversarial training (GAT) to extend model robustness from $ell_p$-ball to composite semantic perturbations.
  arXiv  Detail & Related papers  (2022-02-09T02:41:56Z)
• The Interplay between Distribution Parameters and the Accuracy-Robustness Tradeoff in Classification [0.0]
  Adrial training tends to result in models that are less accurate on natural (unperturbed) examples compared to standard models. This can be attributed to either an algorithmic shortcoming or a fundamental property of the training data distribution. In this work, we focus on the latter case under a binary Gaussian mixture classification problem.
  arXiv  Detail & Related papers  (2021-07-01T06:57:50Z)
• Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions [79.35722941720734]
  Generalised linear models for multi-class classification problems are one of the fundamental building blocks of modern machine learning tasks. We prove exacts characterising the estimator in high-dimensions via empirical risk minimisation. We discuss how our theory can be applied beyond the scope of synthetic data.
  arXiv  Detail & Related papers  (2021-06-07T16:53:56Z)
• Shaping Deep Feature Space towards Gaussian Mixture for Visual Classification [74.48695037007306]
  We propose a Gaussian mixture (GM) loss function for deep neural networks for visual classification. With a classification margin and a likelihood regularization, the GM loss facilitates both high classification performance and accurate modeling of the feature distribution. The proposed model can be implemented easily and efficiently without using extra trainable parameters.
  arXiv  Detail & Related papers  (2020-11-18T03:32:27Z)
• Beyond cross-entropy: learning highly separable feature distributions for robust and accurate classification [22.806324361016863]
  We propose a novel approach for training deep robust multiclass classifiers that provides adversarial robustness. We show that the regularization of the latent space based on our approach yields excellent classification accuracy.
  arXiv  Detail & Related papers  (2020-10-29T11:15:17Z)
• Classifier-independent Lower-Bounds for Adversarial Robustness [13.247278149124757]
  We theoretically analyse the limits of robustness to test-time adversarial and noisy examples in classification. We use optimal transport theory to derive variational formulae for the Bayes-optimal error a classifier can make on a given classification problem. We derive explicit lower-bounds on the Bayes-optimal error in the case of the popular distance-based attacks.
  arXiv  Detail & Related papers  (2020-06-17T16:46:39Z)
• Provable tradeoffs in adversarially robust classification [96.48180210364893]
  We develop and leverage new tools, including recent breakthroughs from probability theory on robust isoperimetry. Our results reveal fundamental tradeoffs between standard and robust accuracy that grow when data is imbalanced.
  arXiv  Detail & Related papers  (2020-06-09T09:58:19Z)
• Consistency Regularization for Certified Robustness of Smoothed Classifiers [89.72878906950208]
  A recent technique of randomized smoothing has shown that the worst-case $ell$-robustness can be transformed into the average-case robustness. We found that the trade-off between accuracy and certified robustness of smoothed classifiers can be greatly controlled by simply regularizing the prediction consistency over noise.
  arXiv  Detail & Related papers  (2020-06-07T06:57:43Z)

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.