Calibration and Consistency of Adversarial Surrogate Losses

• URL: http://arxiv.org/abs/2104.09658v1
• Date: Mon, 19 Apr 2021 21:58:52 GMT
• Title: Calibration and Consistency of Adversarial Surrogate Losses
• Authors: Pranjal Awasthi and Natalie Frank and Anqi Mao and Mehryar Mohri and Yutao Zhong
• Abstract summary: Adrialversa robustness is an increasingly critical property of classifiers in applications. But which surrogate losses should be used and when do they benefit from theoretical guarantees? We present an extensive study of this question, including a detailed analysis of the H-calibration and H-consistency of adversarial surrogate losses.
• Score: 46.04004505351902
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Adversarial robustness is an increasingly critical property of classifiers in applications. The design of robust algorithms relies on surrogate losses since the optimization of the adversarial loss with most hypothesis sets is NP-hard. But which surrogate losses should be used and when do they benefit from theoretical guarantees? We present an extensive study of this question, including a detailed analysis of the H-calibration and H-consistency of adversarial surrogate losses. We show that, under some general assumptions, convex loss functions, or the supremum-based convex losses often used in applications, are not H-calibrated for important functions classes such as generalized linear models or one-layer neural networks. We then give a characterization of H-calibration and prove that some surrogate losses are indeed H-calibrated for the adversarial loss, with these function classes. Next, we show that H-calibration is not sufficient to guarantee consistency and prove that, in the absence of any distributional assumption, no continuous surrogate loss is consistent in the adversarial setting. This, in particular, falsifies a claim made in a COLT 2020 publication. Next, we identify natural conditions under which some surrogate losses that we describe in detail are H-consistent for function classes such as generalized linear models and one-layer neural networks. We also report a series of empirical results with simulated data, which show that many H-calibrated surrogate losses are indeed not H-consistent, and validate our theoretical assumptions.

Related papers

• Inference with non-differentiable surrogate loss in a general high-dimensional classification framework [4.792322531593389]
  We propose a kernel-smoothed decorrelated score to construct hypothesis testing and interval estimations. Specifically, we adopt kernel approximations to smooth the discontinuous gradient near discontinuity points. We establish the limiting distribution of the kernel-smoothed decorrelated score and its cross-fitted version in a high-dimensional setup.
  arXiv  Detail & Related papers  (2024-05-20T01:50:35Z)
• On the Dynamics Under the Unhinged Loss and Beyond [104.49565602940699]
  We introduce the unhinged loss, a concise loss function, that offers more mathematical opportunities to analyze closed-form dynamics. The unhinged loss allows for considering more practical techniques, such as time-vary learning rates and feature normalization.
  arXiv  Detail & Related papers  (2023-12-13T02:11:07Z)
• Cross-Entropy Loss Functions: Theoretical Analysis and Applications [27.3569897539488]
  We present a theoretical analysis of a broad family of loss functions, that includes cross-entropy (or logistic loss), generalized cross-entropy, the mean absolute error and other cross-entropy-like loss functions. We show that these loss functions are beneficial in the adversarial setting by proving that they admit $H$-consistency bounds. This leads to new adversarial robustness algorithms that consist of minimizing a regularized smooth adversarial comp-sum loss.
  arXiv  Detail & Related papers  (2023-04-14T17:58:23Z)
• Loss Minimization through the Lens of Outcome Indistinguishability [11.709566373491619]
  We present a new perspective on convex loss and the recent notion of Omniprediction. By design, Loss OI implies omniprediction in a direct and intuitive manner. We show that Loss OI for the important set of losses arising from Generalized Models, without requiring full multicalibration.
  arXiv  Detail & Related papers  (2022-10-16T22:25:27Z)
• An Embedding Framework for the Design and Analysis of Consistent Polyhedral Surrogates [17.596501992526477]
  We study the design of convex surrogate loss functions via embeddings, for problems such as classification, ranking, or structured links. An embedding gives rise to a consistent link function as well as a consistent link function. Our results are constructive, as we illustrate several examples.
  arXiv  Detail & Related papers  (2022-06-29T15:16:51Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  We study properties of random features (RF) regression in high dimensions optimized by gradient descent (SGD) We derive precise non-asymptotic error bounds of RF regression under both constant and adaptive step-size SGD setting. We observe the double descent phenomenon both theoretically and empirically.
  arXiv  Detail & Related papers  (2021-10-13T17:47:39Z)
• 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)
• A Symmetric Loss Perspective of Reliable Machine Learning [87.68601212686086]
  We review how a symmetric loss can yield robust classification from corrupted labels in balanced error rate (BER) minimization. We demonstrate how the robust AUC method can benefit natural language processing in the problem where we want to learn only from relevant keywords.
  arXiv  Detail & Related papers  (2021-01-05T06:25:47Z)
• Implicit Regularization in ReLU Networks with the Square Loss [56.70360094597169]
  We show that it is impossible to characterize the implicit regularization with the square loss by any explicit function of the model parameters. Our results suggest that a more general framework may be needed to understand implicit regularization for nonlinear predictors.
  arXiv  Detail & Related papers  (2020-12-09T16:48:03Z)
• 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.