Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks

• URL: http://arxiv.org/abs/2205.06127v1
• Date: Thu, 12 May 2022 14:40:18 GMT
• Title: Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks
• Authors: Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska and James Worrell
• Abstract summary: A fundamental problem in adversarial machine learning is to quantify how much training data is needed in the presence of evasion attacks. We work with probability distributions on the input data that satisfy a Lipschitz condition: nearby points have similar probability. For every fixed $k$ the class of $k$-decision lists has sample complexity against a $log(n)$-bounded adversary.
• Score: 25.832511407411637
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A fundamental problem in adversarial machine learning is to quantify how much training data is needed in the presence of evasion attacks. In this paper we address this issue within the framework of PAC learning, focusing on the class of decision lists. Given that distributional assumptions are essential in the adversarial setting, we work with probability distributions on the input data that satisfy a Lipschitz condition: nearby points have similar probability. Our key results illustrate that the adversary's budget (that is, the number of bits it can perturb on each input) is a fundamental quantity in determining the sample complexity of robust learning. Our first main result is a sample-complexity lower bound: the class of monotone conjunctions (essentially the simplest non-trivial hypothesis class on the Boolean hypercube) and any superclass has sample complexity at least exponential in the adversary's budget. Our second main result is a corresponding upper bound: for every fixed $k$ the class of $k$-decision lists has polynomial sample complexity against a $\log(n)$-bounded adversary. This sheds further light on the question of whether an efficient PAC learning algorithm can always be used as an efficient $\log(n)$-robust learning algorithm under the uniform distribution.

Related papers

• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  Longtailed distributions frequently emerge in real-world data, where a large number of minority categories contain a limited number of samples. Recent investigations have revealed that supervised contrastive learning exhibits promising potential in alleviating the data imbalance. We propose a novel probabilistic contrastive (ProCo) learning algorithm that estimates the data distribution of the samples from each class in the feature space.
  arXiv  Detail & Related papers  (2024-03-11T13:44:49Z)
• Sample Complexity of Robust Learning against Evasion Attacks [3.8888996044605855]
  We study the feasibility of adversarially robust learning from the perspective of learning theory, considering sample complexity. We show that, under the uniform distribution, the exponential dependence on the adversary's budget to robustly learn conjunctions remains inevitable. We show that if the query radius is equal to the adversary's budget, we can develop robust empirical risk algorithms in the distribution-free setting.
  arXiv  Detail & Related papers  (2023-08-23T10:51:33Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
  arXiv  Detail & Related papers  (2023-06-28T16:33:39Z)
• Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
  We study two basic statistical tasks in non-interactive local differential privacy (LDP): learning and refutation. Our main result is a complete characterization of the sample complexity of PAC learning for non-interactive LDP protocols.
  arXiv  Detail & Related papers  (2022-10-26T03:19:24Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  Social and real-world considerations have given rise to multi-distribution learning paradigms. We establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving zero-sum games.
  arXiv  Detail & Related papers  (2022-10-22T19:07:26Z)
• When are Local Queries Useful for Robust Learning? [25.832511407411637]
  We study learning models where the learner is given more power through the use of local queries. We give the first distribution-free algorithms that perform robust empirical risk minimization. We finish by giving robust learning algorithms for halfspaces on $0,1n$ and then obtaining robustness guarantees for halfspaces in $mathbbRn$ against precision-bounded adversaries.
  arXiv  Detail & Related papers  (2022-10-12T11:04:22Z)
• Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
  We propose an ensemble learning algorithm called textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) for imbalanced classification problems.
  arXiv  Detail & Related papers  (2021-09-01T14:10:38Z)
• Robust learning under clean-label attack [26.323812778809913]
  We study the problem of robust learning under clean-label data-poisoning attacks. The learning goal is to minimize the attackable rate, which is more difficult than optimal PAC learning.
  arXiv  Detail & Related papers  (2021-03-01T00:21:15Z)
• Sample Complexity of Adversarially Robust Linear Classification on Separated Data [41.30425613353595]
  We consider the sample complexity of learning with adversarial robustness. We show that for very well-separated data, convergence rates of $O(frac1n)$ are achievable.
  arXiv  Detail & Related papers  (2020-12-19T22:04:59Z)
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
  We study the computational complexity of adversarially robust proper learning of halfspaces in the distribution-independent PAC model. We give a computationally efficient learning algorithm and a nearly matching computational hardness result for this problem.
  arXiv  Detail & Related papers  (2020-07-30T04:18:51Z)

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.