The Adversarial Consistency of Surrogate Risks for Binary Classification

• URL: http://arxiv.org/abs/2305.09956v3
• Date: Sat, 23 Dec 2023 02:47:28 GMT
• Title: The Adversarial Consistency of Surrogate Risks for Binary Classification
• Authors: Natalie Frank and Jonathan Niles-Weed
• Abstract summary: adversarial training seeks to minimize the expected $0$-$1$ loss when each example can be maliciously corrupted within a small ball. We give a simple and complete characterization of the set of surrogate loss functions that are consistent. Our results reveal that the class of adversarially consistent surrogates is substantially smaller than in the standard setting.
• Score: 20.03511985572199
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the consistency of surrogate risks for robust binary classification. It is common to learn robust classifiers by adversarial training, which seeks to minimize the expected $0$-$1$ loss when each example can be maliciously corrupted within a small ball. We give a simple and complete characterization of the set of surrogate loss functions that are \emph{consistent}, i.e., that can replace the $0$-$1$ loss without affecting the minimizing sequences of the original adversarial risk, for any data distribution. We also prove a quantitative version of adversarial consistency for the $\rho$-margin loss. Our results reveal that the class of adversarially consistent surrogates is substantially smaller than in the standard setting, where many common surrogates are known to be consistent.

Related papers

• A Universal Growth Rate for Learning with Smooth Surrogate Losses [30.389055604165222]
  We prove a square-root growth rate near zero for smooth margin-based surrogate losses in binary classification. We extend this analysis to multi-class classification with a series of novel results.
  arXiv  Detail & Related papers  (2024-05-09T17:59:55Z)
• Adversarial Consistency and the Uniqueness of the Adversarial Bayes Classifier [0.0]
  Minimizing an adversarial surrogate risk is a common technique for learning robust classifiers. We show that under reasonable distributional assumptions, a convex surrogate loss is statistically consistent for adversarial learning iff the adversarial Bayes classifier satisfies a certain notion of uniqueness.
  arXiv  Detail & Related papers  (2024-04-26T12:16:08Z)
• Adversarial Training Should Be Cast as a Non-Zero-Sum Game [121.95628660889628]
  Two-player zero-sum paradigm of adversarial training has not engendered sufficient levels of robustness. We show that the commonly used surrogate-based relaxation used in adversarial training algorithms voids all guarantees on robustness. A novel non-zero-sum bilevel formulation of adversarial training yields a framework that matches and in some cases outperforms state-of-the-art attacks.
  arXiv  Detail & Related papers  (2023-06-19T16:00:48Z)
• Robust Lipschitz Bandits to Adversarial Corruptions [61.85150061213987]
  Lipschitz bandit is a variant of bandits that deals with a continuous arm set defined on a metric space. In this paper, we introduce a new problem of Lipschitz bandits in the presence of adversarial corruptions. Our work presents the first line of robust Lipschitz bandit algorithms that can achieve sub-linear regret under both types of adversary.
  arXiv  Detail & Related papers  (2023-05-29T18:16:59Z)
• The Consistency of Adversarial Training for Binary Classification [12.208787849155048]
  adversarial training involves minimizing a supremum-based surrogate risk. We characterize which supremum-based surrogates are consistent for distributions absolutely continuous with respect to Lebesgue measure in binary classification.
  arXiv  Detail & Related papers  (2022-06-18T03:37:43Z)
• Label Distributionally Robust Losses for Multi-class Classification: Consistency, Robustness and Adaptivity [55.29408396918968]
  We study a family of loss functions named label-distributionally robust (LDR) losses for multi-class classification. Our contributions include both consistency and robustness by establishing top-$k$ consistency of LDR losses for multi-class classification. We propose a new adaptive LDR loss that automatically adapts the individualized temperature parameter to the noise degree of class label of each instance.
  arXiv  Detail & Related papers  (2021-12-30T00:27:30Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  We study the linear contextual bandit problem in the presence of adversarial corruption. We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$.
  arXiv  Detail & Related papers  (2021-10-25T02:53:24Z)
• Constrained Classification and Policy Learning [0.0]
  We study consistency of surrogate loss procedures under a constrained set of classifiers. We show that hinge losses are the only surrogate losses that preserve consistency in second-best scenarios.
  arXiv  Detail & Related papers  (2021-06-24T10:43:00Z)
• 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)
• Calibrated Surrogate Losses for Adversarially Robust Classification [92.37268323142307]
  We show that no convex surrogate loss is respect with respect to adversarial 0-1 loss when restricted to linear models. We also show that if the underlying distribution satisfies the Massart's noise condition, convex losses can also be calibrated in the adversarial setting.
  arXiv  Detail & Related papers  (2020-05-28T02:40:42Z)

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.