Back

Cross-Entropy Loss Functions: Theoretical Analysis and Applications

Anqi MaoMehryar MohriYutao Zhong

article2023ICML767 citations

Establishes the first tight non-asymptotic HH-consistency bounds for cross-entropy and general comp-sum loss functions, using these theoretical guarantees to develop new adversarial training objectives that improve defense against attacks without sacrificing standard accuracy.

Listen

Modern machine learning systems rely heavily on classification models trained with surrogate objectives, primarily the cross-entropy (multinomial logistic) loss, because directly minimizing classification errors is computationally intractable. While cross-entropy is known to be statistically consistent in an asymptotic, unconstrained setting, this property offers no concrete performance guarantees when using real-world, restricted model families such as deep neural networks on finite samples. Furthermore, standard neural networks remain critically vulnerable to small, imperceptible adversarial input perturbations. The article addresses these core challenges by establishing rigorous, non-asymptotic theoretical guarantees for cross-entropy and related loss functions, and by deriving theoretically grounded algorithms for adversarial defense.

The main objective of the article is to provide the first tight, model-specific error bounds—known as hypothesis-set consistency bounds—for a broad class of composed loss functions (including standard cross-entropy, generalized cross-entropy, and mean absolute error), and to demonstrate how these principles can be extended to design superior, adversarially robust learning algorithms.

To achieve this, the article analyzes a unified mathematical family called composite-sum (comp-sum) losses parameterized by a scalar value that captures various standard classification objectives. The authors derive exact non-asymptotic bounds that connect surrogate training errors directly to actual classification errors across realistic, symmetric, and complete hypothesis sets, without imposing restrictive distribution assumptions. They analyze key structural quantities called minimizability gaps that capture approximation quality. Additionally, the authors formulate a new class of smooth adversarial comp-sum losses with matching theoretical guarantees and evaluate both standard and robust models empirically across image benchmark datasets (CIFAR-10, CIFAR-100, and SVHN) using various WideResNet and ResNet architectures against established attacks.

The findings reveal several crucial theoretical and practical insights. First, the article proves tight hypothesis-set consistency bounds for cross-entropy and related functions, showing that cross-entropy achieves a square-root error-scaling relationship with classification error. Second, while objectives like the mean absolute error possess a theoretically linear error rate, their bounds degrade with the total number of classes and face severe optimization difficulties in practice, explaining why cross-entropy strikes the best operational balance. Third, the newly introduced defense algorithm, ADV-COMP-SUM, consistently outperforms the current state-of-the-art adversarial defense benchmark (TRADES) across all tested architectures and datasets. Specifically, ADV-COMP-SUM achieves up to a 1.45% increase in robust accuracy under standard margin attacks and up to 1.12% higher robust accuracy under AutoAttack, while simultaneously improving clean (non-adversarial) classification accuracy by up to 2.54%.

These results provide a solid theoretical justification for the long-standing empirical dominance of cross-entropy in standard machine learning workflows. Crucially, in adversarial defense, where improving robustness has traditionally required sacrificing clean test accuracy, the findings demonstrate that smooth adversarial comp-sum losses eliminate this trade-off. This enhances model reliability and reduces deployment risk in safety-critical applications without compromising regular predictive performance.

Organizations developing machine learning models should continue prioritizing cross-entropy-style objectives for multi-class classification and adopt smooth adversarial comp-sum loss formulations for adversarial training pipelines. When implementing these robust algorithms, practitioners can tune key regularization and margin hyperparameters through standard cross-validation to maximize accuracy. Future work should focus on extending these theoretical bounds to incomplete hypothesis sets, exploring noisy label environments, and addressing general neural network generalization challenges under adversarial attacks.

Confidence in these findings is high due to the mathematical proofs of tightness and rigorous empirical comparisons matching benchmark protocols without data augmentation artifacts. However, users should note that the primary non-adversarial theoretical guarantees assume complete hypothesis sets whose generated output scores span the real space, and the empirical validations were conducted primarily on standard vision benchmark datasets.

GoogleNew York Universitycompempirical analysisestimation methodcross-entropy loss functionssurrogate loss functionscomp-sum loss functions
arXiv: 2304.07288

No sufficiently relevant recommendations were found.

Cover for Cross-Entropy Loss Functions: Theoretical Analysis and Applications

Abstract

Cross-entropy is a widely used loss function in applications. It coincides with the logistic loss applied to the outputs of a neural network, when the softmax is used. But, what guarantees can we rely on when using cross-entropy as a surrogate loss? We present a theoretical analysis of a broad family of loss functions, comp-sum losses, that includes cross-entropy (or logistic loss), generalized cross-entropy, the mean absolute error and other cross-entropy-like loss functions. We give the first HH-consistency bounds for these loss functions. These are non-asymptotic guarantees that upper bound the zero-one loss estimation error in terms of the estimation error of a surrogate loss, for the specific hypothesis set HH used. We further show that our bounds are tight. These bounds depend on quantities called minimizability gaps. To make them more explicit, we give a specific analysis of these gaps for comp-sum losses. We also introduce a new family of loss functions, smooth adversarial comp-sum losses, that are derived from their comp-sum counterparts by adding in a related smooth term. We show that these loss functions are beneficial in the adversarial setting by proving that they admit HH-consistency bounds. This leads to new adversarial robustness algorithms that consist of minimizing a regularized smooth adversarial comp-sum loss. While our main purpose is a theoretical analysis, we also present an extensive empirical analysis comparing comp-sum losses. We further report the results of a series of experiments demonstrating that our adversarial robustness algorithms outperform the current state-of-the-art, while also achieving a superior non-adversarial accuracy.

Topics

compempirical analysisestimation methodlogisticsmean absolute errorneural networks

Keywords

cross-entropy loss functionssurrogate loss functionscomp-sum loss functionsmulticlass classificationRademacher complexityrisk minimizationadversarial learningrisk boundsstochastic gradient descent

Table of Contents

  • 1 Introduction
  • 2 Preliminaries
  • 3 ℋ{\mathscr{H}}-Consistency Bounds for Comp-Sum Losses
  • 3.1 ℋ{\mathscr{H}}-Consistency Guarantees
  • 3.2 Learning Bounds
  • 4 Comparison of Minimizability Gaps
  • 5 Smooth Adversarial Comp-Sum Losses
  • 5.1 Definition
  • 5.2 Adversarial ℋ{\mathscr{H}}-Consistency Guarantees
  • 6 Experiments
  • 6.1 Standard Multi-Class Classification
  • 6.2 Adversarial Multi-Class Classification
  • 7 Discussion
  • 8 Conclusion
  • References
  • A Related work
  • B Proofs of ℋ{\mathscr{H}}-consistency bounds for comp-sum losses (Theorem ) and tightness (Theorem )
  • C Approximations of 𝒯τ{\mathscr{T}}_{\tau} and Γτ\Gamma_{\tau}
  • D Characterization of minimizability gaps (proofs of Theorem and Theorem )
  • E Proof of Lemma
  • F Proof of adversarial ℋ{\mathscr{H}}-consistency bound for adversarial comp-sum losses (Theorem )
  • G Learning bounds (proof of Theorem )

Knowls

  1. Knowl 1 — Family of Comp-Sum Multi-Class Loss Functions

    definition

    Let X\mathcal{X} denote the input space, Y=[n]={1,…,n}\mathcal{Y} = [n] = \{1, \dots, n\} the label set with n≥2n \ge 2, and h:X×Y→Rh: \mathcal{X} \times \mathcal{Y} \to \mathbb{R} a scoring hypothesis function. A comp-sum loss function ℓΦ1[Φ2]comp\ell^{\text{comp}}_{\Phi_1[\Phi_2]} is defined by composing an auxiliary non-decreasing function Φ1:[0,∞)→R\Phi_1: [0, \infty) \to \mathbb{R} with a sum of margin-based penalties Φ2:R→[0,∞)\Phi_2: \mathbb{R} \to [0, \infty):

    ℓΦ1[Φ2]comp(h,x,y)=Φ1(∑y′≠yΦ2(h(x,y)−h(x,y′)))\ell^{\text{comp}}_{\Phi_1[\Phi_2]}(h, x, y) = \Phi_1\left( \sum_{y' \ne y} \Phi_2(h(x, y) - h(x, y')) \right)

    When choosing Φ2(u)=exp⁡(−u)\Phi_2(u) = \exp(-u) and defining the family of concave, non-decreasing, 11-Lipschitz functions Φτ(u)\Phi_\tau(u) for τ≥0\tau \ge 0 as:

    Φτ(u)={11−τ((1+u)1−τ−1)τ≥0,τ≠1log⁡(1+u)τ=1\Phi_\tau(u) = \begin{cases} \frac{1}{1-\tau}\left((1+u)^{1-\tau} - 1\right) & \tau \ge 0, \tau \ne 1 \\ \log(1+u) & \tau = 1 \end{cases}

    the resulting comp-sum loss ℓτcomp(h,x,y)=Φτ(∑y′∈Yeh(x,y′)−h(x,y)−1)\ell^{\text{comp}}_\tau(h, x, y) = \Phi_\tau\left(\sum_{y' \in \mathcal{Y}} e^{h(x, y') - h(x, y)} - 1\right) yields:

    ℓτcomp(h,x,y)={11−τ([∑y′∈Yeh(x,y′)−h(x,y)]1−τ−1)τ≥0,τ≠1log⁡(∑y′∈Yeh(x,y′)−h(x,y))=−log⁡(eh(x,y)∑y′∈Yeh(x,y′))τ=1\ell^{\text{comp}}_\tau(h, x, y) = \begin{cases} \frac{1}{1-\tau}\left(\left[\sum_{y' \in \mathcal{Y}} e^{h(x, y') - h(x, y)}\right]^{1-\tau} - 1\right) & \tau \ge 0, \tau \ne 1 \\ \log\left(\sum_{y' \in \mathcal{Y}} e^{h(x, y') - h(x, y)}\right) = -\log\left(\frac{e^{h(x, y)}}{\sum_{y' \in \mathcal{Y}} e^{h(x, y')}}\right) & \tau = 1 \end{cases}

    Special cases of this parametric family include:

    1. τ=0\tau = 0: The sum-exponential loss ℓτ=0comp(h,x,y)=∑y′≠yeh(x,y′)−h(x,y)\ell^{\text{comp}}_{\tau=0}(h, x, y) = \sum_{y' \ne y} e^{h(x, y') - h(x, y)}.
    2. τ=1\tau = 1: The multinomial logistic loss (cross-entropy with softmax).
    3. 1<τ<21 < \tau < 2: The generalized cross-entropy loss ℓ1<τ<2comp(h,x,y)=1τ−1(1−[eh(x,y)∑y′∈Yeh(x,y′)]τ−1)\ell^{\text{comp}}_{1<\tau<2}(h, x, y) = \frac{1}{\tau - 1}\left(1 - \left[\frac{e^{h(x, y)}}{\sum_{y' \in \mathcal{Y}} e^{h(x, y')}}\right]^{\tau - 1}\right).
    4. τ=2\tau = 2: The mean absolute error (MAE) loss ℓτ=2comp(h,x,y)=1−eh(x,y)∑y′∈Yeh(x,y′)\ell^{\text{comp}}_{\tau=2}(h, x, y) = 1 - \frac{e^{h(x, y)}}{\sum_{y' \in \mathcal{Y}} e^{h(x, y')}}.

  2. Knowl 2 — H-Consistency Bounds for Comp-Sum Loss Functions

    theoretical result

    Let D\mathcal{D} be a distribution over X×Y\mathcal{X} \times \mathcal{Y} where Y=[n]\mathcal{Y} = [n] (n≥2n \ge 2). Let H⊆RX×Y\mathcal{H} \subseteq \mathbb{R}^{\mathcal{X} \times \mathcal{Y}} be a hypothesis set that is symmetric (invariant to label permutations) and complete (satisfying {h(x,y):h∈H}=R\{h(x, y) : h \in \mathcal{H}\} = \mathbb{R} for every (x,y)(x, y)). For any loss ℓ\ell, let Rℓ(h)=E(x,y)∼D[ℓ(h,x,y)]\mathcal{R}_\ell(h) = \mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(h, x, y)], Rℓ∗(H)=inf⁡h∈HRℓ(h)\mathcal{R}^*_\ell(\mathcal{H}) = \inf_{h \in \mathcal{H}} \mathcal{R}_\ell(h), and Mℓ(H)=Rℓ∗(H)−Ex[inf⁡h∈HEy[ℓ(h,x,y)∣X=x]]\mathcal{M}_\ell(\mathcal{H}) = \mathcal{R}^*_\ell(\mathcal{H}) - \mathbb{E}_x\left[\inf_{h \in \mathcal{H}} \mathbb{E}_y[\ell(h, x, y) \mid X = x]\right] denote the expected loss, best-in-class risk, and minimizability gap, respectively. The zero-one classification loss is ℓ0−1(h,x,y)=1h(x)≠y\ell_{0-1}(h, x, y) = \mathbf{1}_{h(x) \ne y}, where h(x)=argmax⁡y∈Yh(x,y)h(x) = \operatorname{argmax}_{y \in \mathcal{Y}} h(x, y) with deterministic tie-breaking.

    For any τ∈[0,∞)\tau \in [0, \infty) and any hypothesis h∈Hh \in \mathcal{H}, the estimation error of the zero-one loss is upper bounded by the surrogate estimation error via:

    Rℓ0−1(h)−Rℓ0−1∗(H)≤Γτ(Rℓτcomp(h)−Rℓτcomp∗(H)+Mℓτcomp(H))−Mℓ0−1(H)\mathcal{R}_{\ell_{0-1}}(h) - \mathcal{R}^*_{\ell_{0-1}}(\mathcal{H}) \le \Gamma_\tau\left( \mathcal{R}_{\ell^{\text{comp}}_\tau}(h) - \mathcal{R}^*_{\ell^{\text{comp}}_\tau}(\mathcal{H}) + \mathcal{M}_{\ell^{\text{comp}}_\tau}(\mathcal{H}) \right) - \mathcal{M}_{\ell_{0-1}}(\mathcal{H})

    where Γτ(t)=Tτ−1(t)\Gamma_\tau(t) = \mathcal{T}_\tau^{-1}(t) is the inverse of the convex, strictly increasing H\mathcal{H}-consistency transformation Tτ:[0,1]→[0,∞)\mathcal{T}_\tau: [0, 1] \to [0, \infty), defined for all β∈[0,1]\beta \in [0, 1] by:

    Tτ(β)={21−τ1−τ[1−((1+β)12−τ+(1−β)12−τ2)2−τ]τ∈[0,1)1+β2log⁡(1+β)+1−β2log⁡(1−β)τ=11(τ−1)nτ−1[((1+β)12−τ+(1−β)12−τ2)2−τ−1]τ∈(1,2)1(τ−1)nτ−1βτ∈[2,+∞)\mathcal{T}_\tau(\beta) = \begin{cases} \frac{2^{1-\tau}}{1-\tau} \left[ 1 - \left( \frac{(1+\beta)^{\frac{1}{2-\tau}} + (1-\beta)^{\frac{1}{2-\tau}}}{2} \right)^{2-\tau} \right] & \tau \in [0, 1) \\ \frac{1+\beta}{2} \log(1+\beta) + \frac{1-\beta}{2} \log(1-\beta) & \tau = 1 \\ \frac{1}{(\tau - 1) n^{\tau - 1}} \left[ \left( \frac{(1+\beta)^{\frac{1}{2-\tau}} + (1-\beta)^{\frac{1}{2-\tau}}}{2} \right)^{2-\tau} - 1 \right] & \tau \in (1, 2) \\ \frac{1}{(\tau - 1) n^{\tau - 1}} \beta & \tau \in [2, +\infty) \end{cases}

  3. Knowl 3 — Tightness of Comp-Sum H-Consistency Bounds

    theoretical result

    Assume that the hypothesis set H⊆RX×Y\mathcal{H} \subseteq \mathbb{R}^{\mathcal{X} \times \mathcal{Y}} is symmetric and complete. For any τ∈[0,1]\tau \in [0, 1] and any β∈[0,1]\beta \in [0, 1], there exists a data distribution D\mathcal{D} concentrated on a single point x0∈Xx_0 \in \mathcal{X} and a hypothesis h∈Hh \in \mathcal{H} such that:

    Rℓ0−1(h)−Rℓ0−1∗(H)+Mℓ0−1(H)=β\mathcal{R}_{\ell_{0-1}}(h) - \mathcal{R}^*_{\ell_{0-1}}(\mathcal{H}) + \mathcal{M}_{\ell_{0-1}}(\mathcal{H}) = \beta

    and

    Rℓτcomp(h)−Rℓτcomp∗(H)+Mℓτcomp(H)=Tτ(β)\mathcal{R}_{\ell^{\text{comp}}_\tau}(h) - \mathcal{R}^*_{\ell^{\text{comp}}_\tau}(\mathcal{H}) + \mathcal{M}_{\ell^{\text{comp}}_\tau}(\mathcal{H}) = \mathcal{T}_\tau(\beta)

    where Tτ\mathcal{T}_\tau is the H\mathcal{H}-consistency transformation for the comp-sum loss ℓτcomp\ell^{\text{comp}}_\tau. This shows that the functional form Tτ\mathcal{T}_\tau (and therefore its inverse Γτ\Gamma_\tau) is tight and cannot be improved for any τ∈[0,1]\tau \in [0, 1], including the sum-exponential loss (τ=0\tau = 0) and the logistic loss (τ=1\tau = 1).

  4. Knowl 4 — Polynomial Approximations and Explicit Upper Bounds for Inverse Transformations

    theoretical result

    By Taylor expansion, the H\mathcal{H}-consistency comp-sum transformation Tτ(β)\mathcal{T}_\tau(\beta) is lower bounded by its tightest polynomial approximation T~τ(β)≤Tτ(β)\tilde{\mathcal{T}}_\tau(\beta) \le \mathcal{T}_\tau(\beta) for all β∈[0,1]\beta \in [0, 1]:

    T~τ(β)={β22τ(2−τ)τ∈[0,1)β22nτ−1τ∈[1,2)β(τ−1)nτ−1τ∈[2,+∞)\tilde{\mathcal{T}}_\tau(\beta) = \begin{cases} \frac{\beta^2}{2^\tau (2-\tau)} & \tau \in [0, 1) \\ \frac{\beta^2}{2 n^{\tau - 1}} & \tau \in [1, 2) \\ \frac{\beta}{(\tau - 1) n^{\tau - 1}} & \tau \in [2, +\infty) \end{cases}

    Consequently, the inverse error transformation Γτ(t)=Tτ−1(t)\Gamma_\tau(t) = \mathcal{T}_\tau^{-1}(t) is upper bounded by Γ~τ(t)=T~τ−1(t)\tilde{\Gamma}_\tau(t) = \tilde{\mathcal{T}}_\tau^{-1}(t):

    Γτ(t)≤Γ~τ(t)={2τ(2−τ)tτ∈[0,1)2nτ−1tτ∈[1,2)(τ−1)nτ−1tτ∈[2,+∞)\Gamma_\tau(t) \le \tilde{\Gamma}_\tau(t) = \begin{cases} \sqrt{2^\tau (2-\tau) t} & \tau \in [0, 1) \\ \sqrt{2 n^{\tau - 1} t} & \tau \in [1, 2) \\ (\tau - 1) n^{\tau - 1} t & \tau \in [2, +\infty) \end{cases}

    For the multinomial logistic loss (τ=1\tau = 1), this provides the non-asymptotic bound:

    Rℓ0−1(h)−Rℓ0−1∗(H)≤2(Rℓ1comp(h)−Rℓ1comp∗(H)+Mℓ1comp(H))−Mℓ0−1(H)\mathcal{R}_{\ell_{0-1}}(h) - \mathcal{R}^*_{\ell_{0-1}}(\mathcal{H}) \le \sqrt{2 \left( \mathcal{R}_{\ell^{\text{comp}}_1}(h) - \mathcal{R}^*_{\ell^{\text{comp}}_1}(\mathcal{H}) + \mathcal{M}_{\ell^{\text{comp}}_1}(\mathcal{H}) \right)} - \mathcal{M}_{\ell_{0-1}}(\mathcal{H})

    which features a square-root estimation-error rate independent of the number of classes nn. For τ≥2\tau \ge 2 (including MAE at τ=2\tau = 2), the rate is linear in error, but scaled by a multiplicative factor of (τ−1)nτ−1(\tau-1)n^{\tau-1} depending on the number of classes nn.

  5. Knowl 5 — Characterization and Monotonicity of Minimizability Gaps for Comp-Sum Losses

    theoretical result

    For any symmetric and complete hypothesis set H\mathcal{H} and conditional class probabilities p(x,y)=P(Y=y∣X=x)p(x, y) = \mathbb{P}(Y = y \mid X = x), the minimizability gap Mℓτcomp(H)=Rℓτcomp∗(H)−Ex[inf⁡h∈HEy[ℓτcomp(h,x,y)∣X=x]]\mathcal{M}_{\ell^{\text{comp}}_\tau}(\mathcal{H}) = \mathcal{R}^*_{\ell^{\text{comp}}_\tau}(\mathcal{H}) - \mathbb{E}_x\left[\inf_{h \in \mathcal{H}} \mathbb{E}_y[\ell^{\text{comp}}_\tau(h, x, y) \mid X = x]\right] satisfies:

    Mℓτcomp(H)≤Φτ(Rℓτ=0comp∗(H))−Ex[Cℓτcomp∗(H,x)]\mathcal{M}_{\ell^{\text{comp}}_\tau}(\mathcal{H}) \le \Phi_\tau\left(\mathcal{R}^*_{\ell^{\text{comp}}_{\tau=0}}(\mathcal{H})\right) - \mathbb{E}_x\left[\mathcal{C}^*_{\ell^{\text{comp}}_\tau}(\mathcal{H}, x)\right]

    where the conditional risk minimum Cℓτcomp∗(H,x)\mathcal{C}^*_{\ell^{\text{comp}}_\tau}(\mathcal{H}, x) is given by:

    Cℓτcomp∗(H,x)={11−τ([∑y∈Yp(x,y)12−τ]2−τ−1)τ≥0,τ≠1,τ≠2−∑y∈Yp(x,y)log⁡p(x,y)τ=11−max⁡y∈Yp(x,y)τ=2\mathcal{C}^*_{\ell^{\text{comp}}_\tau}(\mathcal{H}, x) = \begin{cases} \frac{1}{1-\tau} \left( \left[ \sum_{y \in \mathcal{Y}} p(x, y)^{\frac{1}{2-\tau}} \right]^{2-\tau} - 1 \right) & \tau \ge 0, \tau \ne 1, \tau \ne 2 \\ -\sum_{y \in \mathcal{Y}} p(x, y) \log p(x, y) & \tau = 1 \\ 1 - \max_{y \in \mathcal{Y}} p(x, y) & \tau = 2 \end{cases}

    which corresponds to the (2−τ)(2-\tau)-Rényi entropy.

    For deterministic distributions with score bounded hypothesis sets {(h(x,1),…,h(x,n)):h∈H}=[−Λ,+Λ]n\{(h(x, 1), \dots, h(x, n)) : h \in \mathcal{H}\} = [-\Lambda, +\Lambda]^n, the upper bound simplifies to:

    M~ℓτcomp(H)=Φτ(Rℓτ=0comp∗(H))−Φτ(e−2Λ(n−1))\tilde{\mathcal{M}}_{\ell^{\text{comp}}_\tau}(\mathcal{H}) = \Phi_\tau\left(\mathcal{R}^*_{\ell^{\text{comp}}_{\tau=0}}(\mathcal{H})\right) - \Phi_\tau\left(e^{-2\Lambda}(n - 1)\right)

    Since Φτ(u1)−Φτ(u2)\Phi_\tau(u_1) - \Phi_\tau(u_2) is non-increasing in τ\tau for all u1≥u2≥0u_1 \ge u_2 \ge 0, the gap bound is monotonically non-increasing in τ\tau:

    M~ℓτ=0comp(H)≥M~ℓτ=1comp(H)≥M~ℓ1<τ<2comp(H)≥M~ℓτ=2comp(H)\tilde{\mathcal{M}}_{\ell^{\text{comp}}_{\tau=0}}(\mathcal{H}) \ge \tilde{\mathcal{M}}_{\ell^{\text{comp}}_{\tau=1}}(\mathcal{H}) \ge \tilde{\mathcal{M}}_{\ell^{\text{comp}}_{1<\tau<2}}(\mathcal{H}) \ge \tilde{\mathcal{M}}_{\ell^{\text{comp}}_{\tau=2}}(\mathcal{H})

  6. Knowl 6 — Generalization Error Bounds for Empirical Minimizers of Comp-Sum Losses

    theoretical result

    Let S=((x1,y1),…,(xm,ym))S = ((x_1, y_1), \dots, (x_m, y_m)) be an i.i.d. sample of size mm drawn from Dm\mathcal{D}^m. Let Rmτ(H)\mathfrak{R}_m^\tau(\mathcal{H}) denote the Rademacher complexity of the loss family {(x,y)↦ℓτcomp(h,x,y):h∈H}\{(x, y) \mapsto \ell^{\text{comp}}_\tau(h, x, y) : h \in \mathcal{H}\}, and let BτB_\tau be an upper bound on ℓτcomp\ell^{\text{comp}}_\tau.

    Let h^S∈H\hat{h}_S \in \mathcal{H} be an empirical risk minimizer of the comp-sum loss over SS, h^S=argmin⁡h∈H1m∑i=1mℓτcomp(h,xi,yi)\hat{h}_S = \operatorname{argmin}_{h \in \mathcal{H}} \frac{1}{m} \sum_{i=1}^m \ell^{\text{comp}}_\tau(h, x_i, y_i). Then, for any δ∈(0,1)\delta \in (0, 1), with probability at least 1−δ1 - \delta over the draw of SS, the estimation zero-one error is bounded by:

    Rℓ0−1(h^S)−Rℓ0−1∗(H)≤Γτ(Mℓτcomp(H)+4Rmτ(H)+2Bτlog⁡(2/δ)2m)−Mℓ0−1(H)\mathcal{R}_{\ell_{0-1}}(\hat{h}_S) - \mathcal{R}^*_{\ell_{0-1}}(\mathcal{H}) \le \Gamma_\tau\left( \mathcal{M}_{\ell^{\text{comp}}_\tau}(\mathcal{H}) + 4 \mathfrak{R}_m^\tau(\mathcal{H}) + 2 B_\tau \sqrt{\frac{\log(2/\delta)}{2m}} \right) - \mathcal{M}_{\ell_{0-1}}(\mathcal{H})

    where Γτ\Gamma_\tau is the inverse H\mathcal{H}-consistency comp-sum transformation and Mℓ(H)\mathcal{M}_\ell(\mathcal{H}) are the respective minimizability gaps.

  7. Knowl 7 — Smooth Adversarial Comp-Sum Loss and ADV-COMP-SUM Algorithm

    model/method

    Let Bp(x,γ)={x′∈X:∥x−x′∥p≤γ}\mathcal{B}_p(x, \gamma) = \{x' \in \mathcal{X} : \|x - x'\|_p \le \gamma\} denote the ℓp\ell_p perturbation ball of radius γ>0\gamma > 0 centered at xx. The target adversarial zero-one classification loss is ℓγ(h,x,y)=sup⁡x′∈Bp(x,γ)ℓ0−1(h,x′,y)\ell_\gamma(h, x, y) = \sup_{x' \in \mathcal{B}_p(x, \gamma)} \ell_{0-1}(h, x', y). Let Δh(x,y,y′)=h(x,y)−h(x,y′)\Delta h(x, y, y') = h(x, y) - h(x, y') and Δh(x,y)=(Δh(x,y,1),…,Δh(x,y,y−1),Δh(x,y,y+1),…,Δh(x,y,n))∈Rn−1\Delta h(x, y) = (\Delta h(x, y, 1), \dots, \Delta h(x, y, y-1), \Delta h(x, y, y+1), \dots, \Delta h(x, y, n)) \in \mathbb{R}^{n-1}.

    To construct a smooth, optimizable surrogate for ℓγ\ell_\gamma, the non-convex adversarial ρ\rho-margin comp-sum loss ℓ~τ,ρcomp(h,x,y)=sup⁡x′∈Bp(x,γ)Φτ(∑y′≠yΦρ(h(x′,y′)−h(x′,y)))\tilde{\ell}^{\text{comp}}_{\tau, \rho}(h, x, y) = \sup_{x' \in \mathcal{B}_p(x, \gamma)} \Phi_\tau\left(\sum_{y' \ne y} \Phi_\rho(h(x', y') - h(x', y))\right) with Φρ(u)=min⁡{max⁡{0,1−u/ρ},1}\Phi_\rho(u) = \min\{\max\{0, 1 - u/\rho\}, 1\} is upper bounded by the smooth adversarial comp-sum loss ℓsmoothcomp\ell^{\text{comp}}_{\text{smooth}}:

    ℓsmoothcomp(h,x,y)=ℓτcomp(hρ,x,y)+νsup⁡x′∈Bp(x,γ)∥Δh(x′,y)−Δh(x,y)∥2\ell^{\text{comp}}_{\text{smooth}}(h, x, y) = \ell^{\text{comp}}_\tau\left(\frac{h}{\rho}, x, y\right) + \nu \sup_{x' \in \mathcal{B}_p(x, \gamma)} \|\Delta h(x', y) - \Delta h(x, y)\|_2

    where τ≥0\tau \ge 0, margin scale ρ>0\rho > 0, and smoothness parameter ν≥n−1ρ\nu \ge \frac{\sqrt{n-1}}{\rho}.

    The ADV-COMP-SUM algorithm trains neural network models by minimizing ℓsmoothcomp\ell^{\text{comp}}_{\text{smooth}} across training samples, computing the inner supremum perturbation using multi-step Projected Gradient Descent (PGD) with random starts.

  8. Knowl 8 — Adversarial H-Consistency Guarantees for Smooth Comp-Sum Losses

    theoretical result

    A hypothesis set H\mathcal{H} is defined to be locally ρ\rho-consistent (ho>0 ho > 0) if for any x∈Xx \in \mathcal{X}, there exists h∈Hh \in \mathcal{H} such that inf⁡x′:∥x−x′∥≤γ∣h(x′,i)−h(x′,j)∣≥ρ>0\inf_{x': \|x - x'\| \le \gamma} |h(x', i) - h(x', j)| \ge \rho > 0 for all i≠j∈Yi \ne j \in \mathcal{Y}, and the score ordering of {h(x′,y):y∈Y}\{h(x', y) : y \in \mathcal{Y}\} is constant over all x′∈Bp(x,γ)x' \in \mathcal{B}_p(x, \gamma).

    For any symmetric and locally ρ\rho-consistent hypothesis set H\mathcal{H}, and any τ,ρ>0\tau, \rho > 0, the following adversarial H\mathcal{H}-consistency bound holds for all h∈Hh \in \mathcal{H}:

    Rℓγ(h)−Rℓγ∗(H)≤Φτ(1)[Rℓ~τ,ρcomp(h)−Rℓ~τ,ρcomp∗(H)+Mℓ~τ,ρcomp(H)]−Mℓγ(H)\mathcal{R}_{\ell_\gamma}(h) - \mathcal{R}^*_{\ell_\gamma}(\mathcal{H}) \le \Phi_\tau(1) \left[ \mathcal{R}_{\tilde{\ell}^{\text{comp}}_{\tau, \rho}}(h) - \mathcal{R}^*_{\tilde{\ell}^{\text{comp}}_{\tau, \rho}}(\mathcal{H}) + \mathcal{M}_{\tilde{\ell}^{\text{comp}}_{\tau, \rho}}(\mathcal{H}) \right] - \mathcal{M}_{\ell_\gamma}(\mathcal{H})

    Since ℓsmoothcomp≥ℓ~τ,ρcomp\ell^{\text{comp}}_{\text{smooth}} \ge \tilde{\ell}^{\text{comp}}_{\tau, \rho}, the smooth adversarial comp-sum loss satisfies:

    Rℓγ(h)−Rℓγ∗(H)≤Φτ(1)[Rℓsmoothcomp(h)−Rℓ~τ,ρcomp∗(H)+Mℓ~τ,ρcomp(H)]−Mℓγ(H)\mathcal{R}_{\ell_\gamma}(h) - \mathcal{R}^*_{\ell_\gamma}(\mathcal{H}) \le \Phi_\tau(1) \left[ \mathcal{R}_{\ell^{\text{comp}}_{\text{smooth}}}(h) - \mathcal{R}^*_{\tilde{\ell}^{\text{comp}}_{\tau, \rho}}(\mathcal{H}) + \mathcal{M}_{\tilde{\ell}^{\text{comp}}_{\tau, \rho}}(\mathcal{H}) \right] - \mathcal{M}_{\ell_\gamma}(\mathcal{H})

    When the minimizability gaps vanish, reducing the surrogate excess risk (Rℓsmoothcomp(h)−Rℓ~τ,ρcomp∗(H))(\mathcal{R}_{\ell^{\text{comp}}_{\text{smooth}}}(h) - \mathcal{R}^*_{\tilde{\ell}^{\text{comp}}_{\tau, \rho}}(\mathcal{H})) to ϵ\epsilon bounds the adversarial zero-one excess error by Φτ(1)ϵ\Phi_\tau(1) \epsilon, giving a linear surrogate-to-target rate.

  9. Knowl 9 — Empirical Classification Accuracy of Comp-Sum Losses Across Parameter Tau

    data/table

    ResNet-34 models were trained on CIFAR-10 and CIFAR-100 using SGD with Nesterov momentum (batch size 1024, weight decay 10−410^{-4}, 200 epochs with cosine decay learning rate schedule) for different comp-sum loss parameters τ∈{0,0.5,1.0,1.5,2.0}\tau \in \{0, 0.5, 1.0, 1.5, 2.0\}.

    Dataset τ=0\tau=0 τ=0.5\tau=0.5 τ=1.0\tau=1.0 τ=1.5\tau=1.5 τ=2.0\tau=2.0
    CIFAR-10 87.37±0.57%87.37 \pm 0.57\% 90.28±0.10%90.28 \pm 0.10\% 92.59±0.10%92.59 \pm 0.10\% 92.03±0.08%92.03 \pm 0.08\% 90.35±0.24%90.35 \pm 0.24\%
    CIFAR-100 57.87±0.60%57.87 \pm 0.60\% 65.52±0.34%65.52 \pm 0.34\% 70.93±0.34%70.93 \pm 0.34\% 69.87±0.39%69.87 \pm 0.39\% 8.99±0.98%8.99 \pm 0.98\%

    The results match the theoretical predictions of the H\mathcal{H}-consistency analysis:

    1. The multinomial logistic loss (τ=1.0\tau = 1.0) outperforms the sum-exponential loss (τ=0\tau = 0) and τ=0.5\tau = 0.5 because its minimizability gap is smaller while retaining the same square-root error transformation rate.
    2. The generalized cross-entropy loss (τ=1.5\tau = 1.5) achieves competitive performance to τ=1.0\tau = 1.0 on CIFAR-10 (92.03%92.03\% vs 92.59%92.59\%) but exhibits a larger gap on CIFAR-100 (69.87%69.87\% vs 70.93%70.93\%) due to its n\sqrt{n} constant dependency.
    3. The mean absolute error loss (τ=2.0\tau = 2.0) degrades severely on CIFAR-100 (8.99%8.99\%) because of its linear dependency on the number of classes nn (n=100n = 100) and its non-smooth optimization profile.

  10. Knowl 10 — Adversarial Robustness Benchmarks of ADV-COMP-SUM versus TRADES

    data/table

    WideResNet (WRN) architectures were evaluated on CIFAR-10, CIFAR-100, and SVHN under standard test accuracy (Clean), 40-step PGD margin attack (PGDmargin40\text{PGD}^{40}_{\text{margin}}), and AutoAttack under ℓ∞\ell_\infty perturbations with γ=8/255\gamma = 8/255. Models were trained for 400 epochs with weight averaging (decay 0.9975) without extra or synthetic data. ADV-COMP-SUM used default settings τ=0.4\tau = 0.4, ρ=1\rho = 1, and ν=1\nu = 1.

    Method Architecture Clean Acc. (%) PGDmargin40\text{PGD}^{40}_{\text{margin}} (%) AutoAttack (%)
    CIFAR-10
    Gowal et al. (2020) WRN-70-16 85.34±0.0485.34 \pm 0.04 57.90±0.1357.90 \pm 0.13 57.05±0.1757.05 \pm 0.17
    ADV-COMP-SUM WRN-70-16 86.16±0.1686.16 \pm 0.16 59.35±0.0759.35 \pm 0.07 57.77±0.0857.77 \pm 0.08
    Gowal et al. (2020) WRN-34-20 85.21±0.1685.21 \pm 0.16 57.54±0.1857.54 \pm 0.18 56.70±0.1456.70 \pm 0.14
    ADV-COMP-SUM WRN-34-20 85.59±0.1785.59 \pm 0.17 58.92±0.0658.92 \pm 0.06 57.41±0.0657.41 \pm 0.06
    Gowal et al. (2020) WRN-28-10 84.33±0.1884.33 \pm 0.18 55.92±0.2055.92 \pm 0.20 55.19±0.2355.19 \pm 0.23
    ADV-COMP-SUM WRN-28-10 84.50±0.3384.50 \pm 0.33 57.28±0.0557.28 \pm 0.05 55.79±0.0655.79 \pm 0.06
    Pang et al. (2020a) WRN-34-20 86.43 — 54.39
    Rice et al. (2020) WRN-34-20 85.34 — 53.42
    Wu et al. (2020) WRN-34-10 85.36 — 56.17
    Qin et al. (2019) WRN-40-8 86.28 — 52.84
    CIFAR-100
    Gowal et al. (2020) WRN-70-16 60.56±0.3160.56 \pm 0.31 31.39±0.1931.39 \pm 0.19 29.93±0.1429.93 \pm 0.14
    ADV-COMP-SUM WRN-70-16 63.10±0.2463.10 \pm 0.24 33.76±0.1833.76 \pm 0.18 31.05±0.1531.05 \pm 0.15
    SVHN
    Gowal et al. (2020) WRN-34-20 93.03±0.1393.03 \pm 0.13 61.01±0.1661.01 \pm 0.16 57.84±0.1957.84 \pm 0.19
    ADV-COMP-SUM WRN-34-20 93.98±0.1293.98 \pm 0.12 62.97±0.0562.97 \pm 0.05 58.13±0.1258.13 \pm 0.12

    ADV-COMP-SUM consistently outperforms TRADES across all datasets and models, improving AutoAttack accuracy by 0.60%0.60\% to 1.12%1.12\% and PGDmargin40\text{PGD}^{40}_{\text{margin}} by 1.36%1.36\% to 2.37%2.37\%, while simultaneously achieving superior clean accuracy (e.g., +2.54%+2.54\% on CIFAR-100 for WRN-70-16 and +0.82%+0.82\% on CIFAR-10).

Coverage note — No substantial contributed material was omitted; the extracted knowls cover the unified comp-sum family, theoretical H-consistency bounds, tightness, polynomial simplifications, minimizability gap characterizations, learning bounds, smooth adversarial comp-sum losses with their adversarial H-consistency guarantees, and empirical evaluations across standard and adversarial multi-class classification tasks.

References

  1. 1.Agarwal, A. and Agarwal, S. On consistent surrogate risk minimization and property elicitation. In Conference on Learning Theory, pp. 4–22, 2015.
  2. 2.Alayrac, J.-B., Uesato, J., Huang, P.-S., Fawzi, A., Stanforth, R., and Kohli, P. Are labels required for improving adversarial robustness? In Advances in Neural Information Processing Systems, 2019.
  3. 3.Andriushchenko, M. and Flammarion, N. Understanding and improving fast adversarial training. In Advances in Neural Information Processing Systems, pp. 16048–16059, 2020.
  4. 4.Ashtiani, H., Pathak, V., and Urner, R. Black-box certification and learning under adversarial perturbations. In International Conference on Machine Learning, pp. 388–398, 2020.
  5. 5.Attias, I. and Hanneke, S. Adversarially robust learning of real-valued functions. arXiv preprint arXiv:2206.12977, 2022.
  6. 6.Attias, I., Kontorovich, A., and Mansour, Y. Improved generalization bounds for robust learning. In Algorithmic Learning Theory, pp. 162–183, 2019.
  7. 7.Attias, I., Hanneke, S., and Mansour, Y. A characterization of semi-supervised adversarially robust pac learnability. In Advances in Neural Information Processing Systems, 2022a.
  8. 8.Attias, I., Kontorovich, A., and Mansour, Y. Improved generalization bounds for adversarially robust learning. The Journal of Machine Learning Research, 23(1):7897–7927, 2022b.
  9. 9.Awasthi, P., Dutta, A., and Vijayaraghavan, A. On robustness to adversarial examples and polynomial optimization. In Advances in Neural Information Processing Systems, pp. 13737–13747, 2019.
  10. 10.Awasthi, P., Frank, N., and Mohri, M. Adversarial learning guarantees for linear hypotheses and neural networks. In International Conference on Machine Learning, pp. 431–441, 2020.
  11. 11.Awasthi, P., Frank, N., Mao, A., Mohri, M., and Zhong, Y. Calibration and consistency of adversarial surrogate losses. In Advances in Neural Information Processing Systems, pp. 9804–9815, 2021a.
  12. 12.Awasthi, P., Frank, N., and Mohri, M. On the existence of the adversarial bayes classifier. In Advances in Neural Information Processing Systems, pp. 2978–2990, 2021b.
  13. 13.Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. A finer calibration analysis for adversarial robustness. arXiv preprint arXiv:2105.01550, 2021c.
  14. 14.Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. Multi-class H-consistency bounds. In Advances in neural information processing systems, 2022a.
  15. 15.Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. H-consistency bounds for surrogate loss minimizers. In International Conference on Machine Learning, 2022b.
  16. 16.Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. DC-programming for neural network optimizations. Journal of Global Optimization, 2023a.
  17. 17.Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. Theoretically grounded loss functions and algorithms for adversarial robustness. In International Conference on Artificial Intelligence and Statistics, pp. 10077–10094, 2023b.
  18. 18.Bao, H., Scott, C., and Sugiyama, M. Calibrated surrogate losses for adversarially robust classification. In Conference on Learning Theory, pp. 408–451, 2020.
  19. 19.Bartlett, P., Bubeck, S., and Cherapanamjeri, Y. Adversarial examples in multi-layer random relu networks. In Advances in Neural Information Processing Systems, pp. 9241–9252, 2021.
  20. 20.Bartlett, P. L., Jordan, M. I., and McAuliffe, J. D. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138–156, 2006.
  21. 21.Berkson, J. Application of the logistic function to bio-assay. Journal of the American Statistical Association, 39:357—-365, 1944.
  22. 22.Berkson, J. Why I prefer logits to probits. Biometrics, 7(4):327—-339, 1951.
  23. 23.Bhattacharjee, R., Jha, S., and Chaudhuri, K. Sample complexity of robust linear classification on separated data. In International Conference on Machine Learning, pp. 884–893, 2021.
  24. 24.Biggio, B., Corona, I., Maiorca, D., Nelson, B., Šrndic, N., ´ Laskov, P., Giacinto, G., and Roli, F. Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery in databases, pp. 387–402, 2013.
  25. 25.Blondel, M. Structured prediction with projection oracles. In Advances in neural information processing systems, 2019.
  26. 26.Bubeck, S. and Sellke, M. A universal law of robustness via isoperimetry. In Advances in Neural Information Processing Systems, 2021.
  27. 27.Bubeck, S., Lee, Y. T., Price, E., and Razenshteyn, I. Adversarial examples from cryptographic pseudo-random generators. arXiv preprint arXiv:1811.06418, 2018.
  28. 28.Bubeck, S., Lee, Y. T., Price, E., and Razenshteyn, I. Adversarial examples from computational constraints. In International Conference on Machine Learning, pp. 831–840, 2019.
  29. 29.Bubeck, S., Cherapanamjeri, Y., Gidel, G., and Tachet des Combes, R. A single gradient step finds adversarial examples on random two-layers neural networks. In Advances in Neural Information Processing Systems, pp. 10081–10091, 2021.
  30. 30.Cai, Q.-Z., Liu, C., and Song, D. Curriculum adversarial training. In International Joint Conference on Artificial Intelligence, pp. 3740–3747, 2018.
  31. 31.Cao, Y., Cai, T., Feng, L., Gu, L., Gu, J., An, B., Niu, G., and Sugiyama, M. Generalizing consistent multi-class classification with rejection to be compatible with arbitrary losses. In Advances in Neural Information Processing Systems, pp. 521–534, 2022.
  32. 32.Carlini, N. and Wagner, D. Towards evaluating the robustness of neural networks. In IEEE Symposium on Security and Privacy (SP), pp. 39–57, 2017.
  33. 33.Carmon, Y., Raghunathan, A., Schmidt, L., Duchi, J. C., and Liang, P. S. Unlabeled data improves adversarial robustness. In Advances in neural information processing systems, 2019.
  34. 34.Chen, D.-R. and Sun, T. Consistency of multiclass empirical risk minimization methods based on convex loss. Journal of Machine Learning Research, 7:2435–2447, 2006.
  35. 35.Chen, D.-R. and Xiang, D.-H. The consistency of multicategory support vector machines. Advances in Computational Mathematics, 24(1):155–169, 2006.
  36. 36.Cheng, M., Lei, Q., Chen, P. Y., Dhillon, I., and Hsieh, C. J. Cat: Customized adversarial training for improved robustness. In International Joint Conference on Artificial Intelligence, pp. 673–679, 2022.
  37. 37.Ciliberto, C., Rosasco, L., and Rudi, A. A consistent regularization approach for structured prediction. In Advances in neural information processing systems, 2016.
  38. 38.Cortes, C., DeSalvo, G., and Mohri, M. Boosting with abstention. In Advances in Neural Information Processing Systems, 2016a.
  39. 39.Cortes, C., DeSalvo, G., and Mohri, M. Learning with rejection. In International Conference on Algorithmic Learning Theory, pp. 67–82, 2016b.
  40. 40.Croce, F. and Hein, M. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International conference on machine learning, pp. 2206–2216, 2020.
  41. 41.Cullina, D., Bhagoji, A. N., and Mittal, P. Pac-learning in the presence of adversaries. Advances in Neural Information Processing Systems, 2018.
  42. 42.Dan, C., Wei, Y., and Ravikumar, P. Sharp statistical guarantees for adversarially robust gaussian classification. In International Conference on Machine Learning, pp. 2345–2355, 2020.
  43. 43.Dembczynski, K., Kotlowski, W., and Hüllermeier, E. Consistent multilabel ranking through univariate losses. arXiv preprint arXiv:1206.6401, 2012.
  44. 44.Diakonikolas, I., Kane, D. M., and Manurangsi, P. The complexity of adversarially robust proper learning of halfspaces with agnostic noise. arXiv preprint arXiv:2007.15220, 2020.
  45. 45.Ding, G. W., Sharma, Y., Lui, K. Y. C., and Huang, R. Mma training: Direct input space margin maximization through adversarial training. In International Conference on Learning Representations, 2022.
  46. 46.Dogan, U., Glasmachers, T., and Igel, C. A unified view on multi-class support vector classification. Journal of Machine Learning Research, 17:1–32, 2016.
  47. 47.Duchi, J. C., Mackey, L. W., and Jordan, M. I. On the consistency of ranking algorithms. In International Conference on Machine Learning, 2010.
  48. 48.Feige, U., Mansour, Y., and Schapire, R. Learning and inference in the presence of corrupted inputs. In Conference on Learning Theory, pp. 637–657, 2015.
  49. 49.Feige, U., Mansour, Y., and Schapire, R. E. Robust inference for multiclass classification. In Algorithmic Learning Theory, pp. 368–386, 2018.
  50. 50.Finocchiaro, J., Frongillo, R., and Waggoner, B. An embedding framework for consistent polyhedral surrogates. In Advances in neural information processing systems, 2019.
  51. 51.Finocchiaro, J., Frongillo, R. M., and Waggoner, B. An embedding framework for the design and analysis of consistent polyhedral surrogates. arXiv preprint arXiv:2206.14707, 2022.
  52. 52.Frank, N. and Niles-Weed, J. The adversarial consistency of surrogate risks for binary classification. arXiv preprint arXiv:2305.09956, 2023.
  53. 53.Freund, Y. and Schapire, R. E. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119–139, 1997.
  54. 54.Frongillo, R. and Waggoner, B. Surrogate regret bounds for polyhedral losses. In Advances in Neural Information Processing Systems, pp. 21569–21580, 2021.
  55. 55.Gao, W. and Zhou, Z.-H. On the consistency of multi-label learning. In Conference on learning theory, pp. 341–358, 2011.
  56. 56.Gao, W. and Zhou, Z.-H. On the consistency of auc pairwise optimization. In International Joint Conference on Artificial Intelligence, 2015.
  57. 57.Ghosh, A., Kumar, H., and Sastry, P. S. Robust loss functions under label noise for deep neural networks. In Proceedings of the AAAI conference on artificial intelligence, 2017.
  58. 58.Goldblum, M., Fowl, L., Feizi, S., and Goldstein, T. Adversarially robust distillation. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 3996–4003, 2020.
  59. 59.Goodfellow, I. J., Shlens, J., and Szegedy, C. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
  60. 60.Gowal, S., Qin, C., Uesato, J., Mann, T., and Kohli, P. Uncovering the limits of adversarial training against norm-bounded adversarial examples. arXiv preprint arXiv:2010.03593, 2020.
  61. 61.Guo, J.-Q., Teng, M.-Z., Gao, W., and Zhou, Z.-H. Fast provably robust decision trees and boosting. In International Conference on Machine Learning, pp. 8127–8144, 2022.
  62. 62.Guo, M., Yang, Y., Xu, R., Liu, Z., and Lin, D. When nas meets robustness: In search of robust architectures against adversarial attacks. In Conference on Computer Vision and Pattern Recognition, pp. 631–640, 2020.
  63. 63.Hendrycks, D. and Gimpel, K. Gaussian error linear units (gelus). arXiv preprint arXiv:1606.08415, 2016.
  64. 64.Izmailov, P., Podoprikhin, D., Garipov, T., Vetrov, D. P., and Wilson, A. G. Averaging weights leads to wider optima and better generalization. In Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, pp. 876–885, 2018.
  65. 65.Jin, G., Yi, X., Huang, W., Schewe, S., and Huang, X. Enhancing adversarial training with second-order statistics of weights. In Conference on Computer Vision and Pattern Recognition, pp. 15273–15283, 2022.
  66. 66.Kannan, H., Kurakin, A., and Goodfellow, I. Adversarial logit pairing. arXiv preprint arXiv:1803.06373, 2018.
  67. 67.Khim, J. and Loh, P.-L. Adversarial risk bounds via function transformation. arXiv preprint arXiv:1810.09519, 2018.
  68. 68.Kontorovich, A. and Attias, I. Fat-shattering dimension of k-fold maxima. arXiv preprint arXiv:2110.04763, 2021.
  69. 69.Krizhevsky, A. Learning multiple layers of features from tiny images. Technical report, Toronto University, 2009.
  70. 70.Krizhevsky, A., Sutskever, I., and Hinton, G. E. Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, pp. 1097–1105, 2012.
  71. 71.Kurakin, A., Goodfellow, I., and Bengio, S. Adversarial machine learning at scale. arXiv preprint arXiv:1611.01236, 2016.
  72. 72.Kuznetsov, V. and Mohri, M. Theory and algorithms for forecasting time series. CoRR, abs/1803.05814, 2018.
  73. 73.Kuznetsov, V. and Mohri, M. Discrepancy-based theory and algorithms for forecasting non-stationary time series. Annals of Mathematics and Artificial Intelligence, 88(4):367–399, 2020.
  74. 74.Kuznetsov, V., Mohri, M., and Syed, U. Multi-class deep boosting. In Advances in Neural Information Processing Systems, pp. 2501–2509, 2014.
  75. 75.Lee, S., Lee, H., and Yoon, S. Adversarial vertex mixup: Toward better adversarially robust generalization. In Conference on Computer Vision and Pattern Recognition, pp. 272–281, 2020.
  76. 76.Lee, Y., Lin, Y., and Wahba, G. Multicategory support vector machines: Theory and application to the classification of microarray data and satellite radiance data. Journal of the American Statistical Association, 99(465):67–81, 2004.
  77. 77.Levi, M., Attias, I., and Kontorovich, A. Domain invariant adversarial learning. Transactions of Machine Learning Research, 2022.
  78. 78.Li, J. D. and Telgarsky, M. On achieving optimal adversarial test error. In International Conference on Learning Representations, 2023.
  79. 79.Liu, A., Tang, S., Liu, X., Chen, X., Huang, L., Tu, Z., Song, D., and Tao, D. Towards defending multiple adversarial perturbations via gated batch normalization. arXiv preprint arXiv:2012.01654, 2020.
  80. 80.Liu, Y. Fisher consistency of multicategory support vector machines. In Artificial intelligence and statistics, pp. 291–298, 2007.
  81. 81.Long, P. and Servedio, R. Consistency versus realizable H-consistency for multiclass classification. In International Conference on Machine Learning, pp. 801–809, 2013.
  82. 82.Loshchilov, I. and Hutter, F. SGDR: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:1608.03983, 2016.
  83. 83.Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083, 2017.
  84. 84.Mao, A., Mohri, M., and Zhong, Y. H-consistency bounds for pairwise misranking loss surrogates. In International conference on Machine learning, 2023.
  85. 85.Meunier, L., Ettedgui, R., Pinot, R., Chevaleyre, Y., and Atif, J. Towards consistency in adversarial classification. In Advances in Neural Information Processing Systems, 2022.
  86. 86.Mohri, M. and Medina, A. M. New analysis and algorithm for learning with drifting distributions. In Algorithmic Learning Theory, pp. 124–138, 2012.
  87. 87.Mohri, M., Rostamizadeh, A., and Talwalkar, A. Foundations of Machine Learning. MIT Press, second edition, 2018.
  88. 88.Montasser, O., Hanneke, S., and Srebro, N. Vc classes are adversarially robustly learnable, but only improperly. In Conference on Learning Theory, pp. 2512–2530, 2019.
  89. 89.Montasser, O., Goel, S., Diakonikolas, I., and Srebro, N. Efficiently learning adversarially robust halfspaces with noise. In International Conference on Machine Learning, pp. 7010–7021, 2020a.
  90. 90.Montasser, O., Hanneke, S., and Srebro, N. Reducing adversarially robust learning to non-robust pac learning. In Advances in Neural Information Processing Systems, volume 33, pp. 14626–14637, 2020b.
  91. 91.Montasser, O., Hanneke, S., and Srebro, N. Adversarially robust learning with unknown perturbation sets. In Conference on Learning Theory, pp. 3452–3482, 2021.
  92. 92.Montasser, O., Hanneke, S., and Srebro, N. Transductive robust learning guarantees. In International Conference on Artificial Intelligence and Statistics, pp. 11461–11471, 2022.
  93. 93.Narasimhan, H., Ramaswamy, H., Saha, A., and Agarwal, S. Consistent multiclass algorithms for complex performance measures. In International Conference on Machine Learning, pp. 2398–2407, 2015.
  94. 94.Nesterov, Y. E. A method for solving the convex programming problem with convergence rate o(1/k²). Dokl. akad. nauk Sssr, 269:543–547, 1983.
  95. 95.Netzer, Y., Wang, T., Coates, A., Bissacco, A., Wu, B., and Ng, A. Y. Reading digits in natural images with unsupervised feature learning. In Advances in Neural Information Processing Systems, 2011.
  96. 96.Nueve, E. B., Frongillo, R., and Finocchiaro, J. J. The structured abstain problem and the lovász hinge. In Conference on Learning Theory, pp. 3718–3740, 2022.
  97. 97.Osokin, A., Bach, F., and Lacoste-Julien, S. On structured prediction theory with calibrated convex surrogate losses. In Advances in Neural Information Processing Systems, 2017.
  98. 98.Pang, T., Xu, K., Du, C., Chen, N., and Zhu, J. Improving adversarial robustness via promoting ensemble diversity. In International Conference on Machine Learning, pp. 4970–4979, 2019.
  99. 99.Pang, T., Yang, X., Dong, Y., Su, H., and Zhu, J. Bag of tricks for adversarial training. arXiv preprint arXiv:2010.00467, 2020a.
  100. 100.Pang, T., Yang, X., Dong, Y., Xu, K., Zhu, J., and Su, H. Boosting adversarial training with hypersphere embedding. In Advances in Neural Information Processing Systems, pp. 7779–7792, 2020b.
  101. 101.Pedregosa, F., Bach, F., and Gramfort, A. On the consistency of ordinal regression methods. Journal of Machine Learning Research, 18:1–35, 2017.
  102. 102.Pires, B. Á. and Szepesvári, C. Multiclass classification calibration functions. arXiv preprint arXiv:1609.06385, 2016.
  103. 103.Pires, B. A., Szepesvari, C., and Ghavamzadeh, M. Cost-sensitive multiclass classification risk bounds. In International Conference on Machine Learning, pp. 1391–1399, 2013.
  104. 104.Prabhu, V. U., Yap, D. A., Xu, J., and Whaley, J. Understanding adversarial robustness through loss landscape geometries. arXiv preprint arXiv:1907.09061, 2019.
  105. 105.Qian, Z., Zhang, S., Huang, K., Wang, Q., Zhang, R., and Yi, X. Improving model robustness with latent distribution locally and globally. arXiv preprint arXiv:2107.04401, 2021.
  106. 106.Qin, C., Martens, J., Gowal, S., Krishnan, D., Dvijotham, K., Fawzi, A., De, S., Stanforth, R., and Kohli, P. Adversarial robustness through local linearization. In Advances in Neural Information Processing Systems, 2019.
  107. 107.Ramaswamy, H. G. and Agarwal, S. Classification calibration dimension for general multiclass losses. In Advances in Neural Information Processing Systems, 2012.
  108. 108.Ramaswamy, H. G. and Agarwal, S. Convex calibration dimension for multiclass loss matrices. Journal of Machine Learning Research, 17(1):397–441, 2016.
  109. 109.Ramaswamy, H. G., Agarwal, S., and Tewari, A. Convex calibrated surrogates for low-rank loss matrices with applications to subset ranking losses. In Advances in Neural Information Processing Systems, 2013.
  110. 110.Ramaswamy, H. G., Tewari, A., and Agarwal, S. Consistent algorithms for multiclass classification with a reject option. arXiv preprint arXiv:1505.04137, 2015.
  111. 111.Ravikumar, P., Tewari, A., and Yang, E. On NDCG consistency of listwise ranking methods. In International Conference on Artificial Intelligence and Statistics, pp. 618–626, 2011.
  112. 112.Rebuffi, S.-A., Gowal, S., Calian, D. A., Stimberg, F., Wiles, O., and Mann, T. Fixing data augmentation to improve adversarial robustness. arXiv preprint arXiv:2103.01946, 2021a.
  113. 113.Rebuffi, S.-A., Gowal, S., Calian, D. A., Stimberg, F., Wiles, O., and Mann, T. A. Data augmentation can improve robustness. In Advances in Neural Information Processing Systems, pp. 29935–29948, 2021b.
  114. 114.Rice, L., Wong, E., and Kolter, J. Z. Overfitting in adversarially robust deep learning. In International Conference on Machine Learning, pp. 8093–8104, 2020.
  115. 115.Robey, A., Chamon, L., Pappas, G., Hassani, H., and Ribeiro, A. Adversarial robustness with semi-infinite constrained learning. In Advances in Neural Information Processing Systems, pp. 6198–6215, 2021.
  116. 116.Schmidt, L., Santurkar, S., Tsipras, D., Talwar, K., and Madry, A. Adversarially robust generalization requires more data. In Advances in neural information processing systems, 2018.
  117. 117.Shafahi, A., Najibi, M., Ghiasi, M. A., Xu, Z., Dickerson, J., Studer, C., Davis, L. S., Taylor, G., and Goldstein, T. Adversarial training for free! In Advances in Neural Information Processing Systems, pp. 3353–3364, 2019.
  118. 118.Song, C., He, K., Wang, L., and Hopcroft, J. E. Improving the generalization of adversarial training with domain adaptation. In International Conference on Learning Representations, 2019.
  119. 119.Steinwart, I. How to compare different loss functions and their risks. Constructive Approximation, 26(2):225–287, 2007.
  120. 120.Sutskever, I., Vinyals, O., and Le, Q. V. Sequence to sequence learning with neural networks. In Advances in Neural Information Processing Systems, pp. 3104–3112, 2014.
  121. 121.Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.
  122. 122.Tewari, A. and Bartlett, P. L. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 8(36):1007–1025, 2007.
  123. 123.Thilagar, A., Frongillo, R., Finocchiaro, J. J., and Goodwill, E. Consistent polyhedral surrogates for top-k classification and variants. In International Conference on Machine Learning, pp. 21329–21359, 2022.
  124. 124.Tramèr, F., Kurakin, A., Papernot, N., Goodfellow, I., Boneh, D., and McDaniel, P. Ensemble adversarial training: Attacks and defenses. In International Conference on Learning Representations, 2018.
  125. 125.Tsai, Y.-L., Hsu, C.-Y., Yu, C.-M., and Chen, P.-Y. Formalizing generalization and robustness of neural networks to weight perturbations. In International Conference on Learning Representations, 2021.
  126. 126.Tsipras, D., Santurkar, S., Engstrom, L., Turner, A., and Madry, A. Robustness may be at odds with accuracy. arXiv preprint arXiv:1805.12152, 2018.
  127. 127.Uematsu, K. and Lee, Y. On theoretically optimal ranking functions in bipartite ranking. Journal of the American Statistical Association, 112(519):1311–1322, 2017.
  128. 128.Verhulst, P. F. Notice sur la loi que la population suit dans son accroissement. Correspondance mathématique et physique, 10:113—-121, 1838.
  129. 129.Verhulst, P. F. Recherches mathématiques sur la loi d’accroissement de la population. Nouveaux Mémoires de l’Académie Royale des Sciences et Belles-Lettres de Bruxelles, 18:1—-42, 1845.
  130. 130.Viallard, P., VIDOT, E. G., Habrard, A., and Morvant, E. A pac-bayes analysis of adversarial robustness. In Advances in Neural Information Processing Systems, pp. 14421–14433, 2021.
  131. 131.Wang, Y. and Scott, C. Weston-Watkins hinge loss and ordered partitions. In Advances in neural information processing systems, pp. 19873–19883, 2020.
  132. 132.Wang, Y. and Scott, C. D. On classification-calibration of gamma-phi losses. arXiv preprint arXiv:2302.07321, 2023.
  133. 133.Wang, Y., Ma, X., Bailey, J., Yi, J., Zhou, B., and Gu, Q. On the convergence and robustness of adversarial training. In International Conference on Machine Learning, pp. 6586–6595, 2019.
  134. 134.Wang, Y., Zou, D., Yi, J., Bailey, J., Ma, X., and Gu, Q. Improving adversarial robustness requires revisiting misclassified examples. In International Conference on Learning Representations, 2020.
  135. 135.Weston, J. and Watkins, C. Multi-class support vector machines. Technical report, Citeseer, 1998.
  136. 136.Williamson, R. C., Vernet, E., and Reid, M. D. Composite multiclass losses. Journal of Machine Learning Research, 17:1–52, 2016.
  137. 137.Wong, E., Rice, L., and Kolter, J. Z. Fast is better than free: Revisiting adversarial training. arXiv preprint arXiv:2001.03994, 2020.
  138. 138.Wu, D., Xia, S.-T., and Wang, Y. Adversarial weight perturbation helps robust generalization. In Advances in Neural Information Processing Systems, pp. 2958–2969, 2020.
  139. 139.Xiao, J., Fan, Y., Sun, R., Wang, J., and Luo, Z.-Q. Stability analysis and generalization bounds of adversarial training. In Advances in Neural Information Processing Systems, 2022.
  140. 140.Xie, C. and Yuille, A. Intriguing properties of adversarial training at scale. In International Conference on Learning Representations, 2020.
  141. 141.Xie, C., Wu, Y., Maaten, L. v. d., Yuille, A. L., and He, K. Feature denoising for improving adversarial robustness. In Conference on computer vision and pattern recognition, pp. 501–509, 2019.
  142. 142.Xing, Y., Zhang, R., and Cheng, G. Adversarially robust estimate and risk analysis in linear regression. In International Conference on Artificial Intelligence and Statistics, pp. 514–522, 2021.
  143. 143.Yang, H., Zhang, J., Dong, H., Inkawhich, N., Gardner, A., Touchet, A., Wilkes, W., Berry, H., and Li, H. Dverge: diversifying vulnerabilities for enhanced robust generation of ensembles. Advances in Neural Information Processing Systems, pp. 5505–5515, 2020.
  144. 144.Yin, D., Kannan, R., and Bartlett, P. Rademacher complexity for adversarially robust generalization. In International conference on machine learning, pp. 7085–7094, 2019.
  145. 145.Yu, F., Liu, C., Wang, Y., Zhao, L., and Chen, X. Interpreting adversarial robustness: A view from decision surface in input space. arXiv preprint arXiv:1810.00144, 2018.
  146. 146.Zagoruyko, S. and Komodakis, N. Wide residual networks. arXiv preprint arXiv:1605.07146, 2016.
  147. 147.Zhai, R., Cai, T., He, D., Dan, C., He, K., Hopcroft, J., and Wang, L. Adversarially robust generalization just requires more unlabeled data. arXiv preprint arXiv:1906.00555, 2019.
  148. 148.Zhang, D., Zhang, T., Lu, Y., Zhu, Z., and Dong, B. You only propagate once: Accelerating adversarial training via maximal principle. In Advances in Neural Information Processing Systems, 2019a.
  149. 149.Zhang, H. and Wang, J. Defense against adversarial attacks using feature scattering-based adversarial training. In Advances in Neural Information Processing Systems, 2019.
  150. 150.Zhang, H., Yu, Y., Jiao, J., Xing, E. P., Ghaoui, L. E., and Jordan, M. I. Theoretically principled trade-off between robustness and accuracy. arXiv preprint arXiv:1901.08573, 2019b.
  151. 151.Zhang, J., Xu, X., Han, B., Niu, G., Cui, L., Sugiyama, M., and Kankanhalli, M. Attacks which do not kill training make adversarial learning stronger. In International conference on machine learning, pp. 11278–11287, 2020a.
  152. 152.Zhang, M. and Agarwal, S. Bayes consistency vs. H-consistency: The interplay between surrogate loss functions and the scoring function class. In Advances in Neural Information Processing Systems, 2020.
  153. 153.Zhang, M., Ramaswamy, H. G., and Agarwal, S. Convex calibrated surrogates for the multi-label f-measure. In International Conference on Machine Learning, pp. 11246–11255, 2020b.
  154. 154.Zhang, T. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56–85, 2004a.
  155. 155.Zhang, T. Statistical analysis of some multi-category large margin classification methods. Journal of Machine Learning Research, 5(Oct):1225–1251, 2004b.
  156. 156.Zhang, Z. and Sabuncu, M. Generalized cross entropy loss for training deep neural networks with noisy labels. In Advances in neural information processing systems, 2018.
  157. 157.Zheng, C., Wu, G., Bao, F., Cao, Y., Li, C., and Zhu, J. Revisiting discriminative vs. generative classifiers: Theory and implications. arXiv preprint arXiv:2302.02334, 2023.

Citation

MLA
Mao, A., et al. “Cross-Entropy Loss Functions: Theoretical Analysis and Applications”. International Conference on Machine Learning, vol. 202, 2023, pp. 23803–28, https://proceedings.mlr.press/v202/mao23b.html.
APA
Mao, A., Mohri, M., & Zhong, Y. (2023). Cross-Entropy Loss Functions: Theoretical Analysis and Applications. International Conference on Machine Learning, 202, 23803–23828. https://proceedings.mlr.press/v202/mao23b.html
Chicago
Mao, A., M. Mohri, and Y. Zhong. 2023. “Cross-Entropy Loss Functions: Theoretical Analysis and Applications”. International Conference on Machine Learning 202: 23803–28. https://proceedings.mlr.press/v202/mao23b.html.
Harvard
Mao, A., Mohri, M. and Zhong, Y. (2023) “Cross-Entropy Loss Functions: Theoretical Analysis and Applications”, International Conference on Machine Learning. PMLR, pp. 23803–23828. Available at: https://proceedings.mlr.press/v202/mao23b.html.
Vancouver
1. Mao A, Mohri M, Zhong Y (2023) Cross-Entropy Loss Functions: Theoretical Analysis and Applications. In: International Conference on Machine Learning. PMLR, pp 23803–23828

BibTeX

@InProceedings{pmlr-v202-mao23b,
  title = 	 {Cross-Entropy Loss Functions: Theoretical Analysis and Applications},
  author =       {Mao, Anqi and Mohri, Mehryar and Zhong, Yutao},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {23803--23828},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/mao23b/mao23b.pdf},
  url = 	 {https://proceedings.mlr.press/v202/mao23b.html},
  abstract = 	 {Cross-entropy is a widely used loss function in applications. It coincides with the logistic loss applied to the outputs of a neural network, when the softmax is used. But, what guarantees can we rely on when using cross-entropy as a surrogate loss? We present a theoretical analysis of a broad family of loss functions, comp-sum losses, that includes cross-entropy (or logistic loss), generalized cross-entropy, the mean absolute error and other cross-entropy-like loss functions. We give the first $H$-consistency bounds for these loss functions. These are non-asymptotic guarantees that upper bound the zero-one loss estimation error in terms of the estimation error of a surrogate loss, for the specific hypothesis set $H$ used. We further show that our bounds are tight. These bounds depend on quantities called minimizability gaps. To make them more explicit, we give a specific analysis of these gaps for comp-sum losses. We also introduce a new family of loss functions, smooth adversarial comp-sum losses, that are derived from their comp-sum counterparts by adding in a related smooth term. 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. While our main purpose is a theoretical analysis, we also present an extensive empirical analysis comparing comp-sum losses. We further report the results of a series of experiments demonstrating that our adversarial robustness algorithms outperform the current state-of-the-art, while also achieving a superior non-adversarial accuracy.}
}
Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: https://creativecommons.org/licenses/by/4.0/