PaperlayerView exact revision on arXiv

Source-linked AI summary

Cross-Entropy Loss Functions: Theoretical Analysis and Applications

Anqi Mao, Mehryar Mohri, Yutao Zhong

arXiv:2304.07288v2cs.LGstat.ML

TL;DR

The paper addresses the lack of non-asymptotic guarantees for cross-entropy under restricted hypothesis sets. It derives tight H-consistency bounds for comp-sum losses, analyzes their minimizability gaps, and introduces smooth adversarial variants. Experiments report that the resulting adversarial algorithms outperform TRADES and achieve better clean accuracy.

  • Problem

    Cross-entropy has Bayes consistency, but that does not provide non-asymptotic guarantees for approximate minimizers over restricted hypothesis sets.

  • Method

    The paper analyzes comp-sum losses through H-consistency bounds and minimizability gaps, then adds a smooth term to derive adversarial comp-sum losses and regularized robustness algorithms.

  • Results

    The bounds are tight, and experiments report that the proposed adversarial algorithms outperform TRADES while achieving substantially better clean accuracy.

  • Takeaways & Limitations

    The analysis provides hypothesis-set-specific guarantees for cross-entropy-like losses and principled surrogate losses and algorithms for adversarial robustness.

  • Takeaways & Limitations

    The results apply only to complete hypothesis sets; extensions to non-complete sets and arbitrary distributions are left for future work.

Abstract

from arXiv · show

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.

1. Introduction

The paper asks what non-asymptotic, hypothesis-set-specific guarantees justify cross-entropy as a surrogate for classification loss. It develops tight guarantees for comp-sum losses and extends the analysis to adversarial robustness, supported by empirical comparisons.

  • Cross-entropy is widely minimized because directly minimizing zero-one classification loss is computationally hard.
  • Bayes consistency does not guarantee non-asymptotic performance over restricted hypothesis sets such as neural-network families.
  • The paper gives the first H-consistency bounds for logistic loss and, more broadly, for comp-sum losses including generalized cross-entropy and mean absolute error.
  • The bounds are tight and depend on minimizability gaps, which the paper analyzes to compare guarantees across loss functions and hypothesis sets.
  • Smooth adversarial comp-sum losses add a natural smooth term and yield regularized adversarial-robustness algorithms with H-consistency bounds.
  • Experiments compare comp-sum losses across tasks and report that the proposed adversarial algorithms outperform TRADES while achieving substantially better clean accuracy.

2. Preliminaries

The preliminaries define the multiclass setting, expected loss, H-consistency bounds, and minimizability gaps. They then characterize comp-sum losses as compositions that include logistic loss, generalized cross-entropy, and mean absolute error.

  • The multiclass setting uses input space X, class set Y = [n] with n ≥ 2, and a distribution D over X × Y.
  • The zero-one loss predicts the class with the highest score, using a fixed deterministic tie-breaking rule.
  • The expected loss Rℓ(h) is the loss of hypothesis h averaged over examples drawn from D.
  • H-consistency bounds upper-bound zero-one estimation error by surrogate-loss estimation error through a non-decreasing function, making the guarantee non-asymptotic and hypothesis-set-specific.
  • The minimizability gap is the difference between best-in-class expected loss and the expected pointwise infimum, and it is always non-negative.
  • Comp-sum losses compose functions Φ1 and Φ2; the considered family uses Φ2(u) = exp(−u) and a parameterized auxiliary function Φτ.
  • At τ = 1, the comp-sum loss is multinomial logistic loss; for 1 < τ < 2 it matches generalized cross-entropy, and at τ = 2 it matches mean absolute error.

3. H-Consistency Bounds for Comp-Sum Losses

For symmetric and complete hypothesis sets, the paper derives non-asymptotic H-consistency bounds for the full comp-sum loss family, including logistic loss. The bounds relate surrogate estimation error to zero-one estimation error, incorporate minimizability gaps, and are tight in key regimes.

  • H-consistency theorem: Theorem 3.1 gives H-consistency bounds for every comp-sum loss when H is symmetric and complete.The proof uses general H-consistency tools and a loss-family-wide analysis of calibration gaps.
  • Minimizability gaps: The bounds depend on minimizability gaps, which are zero for the full measurable-function family but generally non-zero for restricted H.The gap is the difference between best-in-class expected loss and expected pointwise infimum.
  • Rates by loss: For τ ∈ [0,2), including logistic and generalized cross-entropy losses, zero-one estimation error is bounded by a constant times √ϵ when surrogate estimation error is ϵ.The guarantee applies when the relevant minimizability gaps vanish.
  • Rates by loss: For τ ≥ 2, including mean absolute error at τ = 2, zero-one estimation error is bounded by a constant times ϵ.This functional dependence is more favorable than the √ϵ regime.
  • Tightness: The transformation-based bound is tight for τ ∈ [0,1], including logistic loss at τ = 1.The paper constructs distributions and hypotheses attaining the stated functional form.
  • Learning bounds: The paper also derives zero-one estimation guarantees for empirical minimizers using Rademacher complexity and explicitly accounting for minimizability gaps.These are presented as the first such guarantees for empirical minimizers of comp-sum losses such as logistic loss.

4. Comparison of Minimizability Gaps

The paper analyzes minimizability gaps for comp-sum losses and shows how their magnitude varies with the loss parameter and class-probability structure. These characterizations make the H-consistency guarantees more explicit for common losses.

  • Gap characterization: For symmetric and complete H, stochastic-case minimizability gaps are upper bounded by expressions determined by the class-probability distribution.The special cases τ = 1 and τ = 2 involve Shannon entropy and one minus the maximum class probability, respectively.
  • Entropy representation: The expressions for C*τ(H,x) can be formulated using (2 − τ)-Rényi entropy.This provides an entropy-based representation of the gap-related quantity.
  • Gap characterization: The corresponding deterministic-case gaps can also be upper bounded under a hypothesis-set score condition spanning [−Λ,+Λ]^n.The result applies to comp-sum losses under the stated deterministic assumption.
  • Comparison across losses: For any fixed hypothesis set H, the minimizability gap is non-increasing as τ increases.This follows from the monotonicity of Φτ(u1) − Φτ(u2) for u1 ≥ u2 ≥ 0.
  • Comparison across losses: The ordering compares sum-exponential, logistic, generalized cross-entropy, and mean absolute error gaps through their corresponding τ values.The comparison combines the gap ordering with the inverse H-consistency transformation Γτ.

5. Smooth Adversarial Comp-Sum Losses

The paper introduces smooth adversarial comp-sum losses for adversarial robustness by augmenting comp-sum losses with a related smooth term. It proves H-consistency guarantees and derives regularized training algorithms based on these losses.

  • Loss construction: Smooth adversarial comp-sum losses augment comp-sum losses with a natural corresponding smooth term for adversarial training.The construction is motivated by the difficulty of directly optimizing adversarial zero-one loss over most hypothesis sets.
  • Loss construction: The supremum-based adversarial comp-sum ρ-margin loss admits an H-consistency bound, while its smooth counterpart is better to optimize.The smooth loss retains similar H-consistency guarantees.
  • Adversarial guarantees: Under symmetric and locally ρ-consistent hypothesis sets, the paper proves H-consistency bounds for adversarial and smooth adversarial comp-sum losses.The guarantees hold for any positive hyperparameters τ and ρ.
  • Adversarial guarantees: The adversarial comp-sum results are presented as the first H-consistency bounds for comp-sum losses in adversarial robustness.The bounds become H-consistency guarantees when the relevant minimizability gaps vanish.
  • Algorithms and experiments: The resulting ADV-COMP-SUM algorithms minimize a regularized empirical smooth adversarial comp-sum loss.The paper reports empirical comparisons of ADV-COMP-SUM with TRADES.
  • Algorithms and experiments: ADV-COMP-SUM is reported to significantly outperform TRADES in the experiments.The comparison is stated for the current state-of-the-art loss/algorithm TRADES.

6. Experiments

The experiments compare comp-sum surrogates in standard classification and evaluate ADV-COMP-SUM against TRADES for adversarial robustness. Logistic loss generally performs best among the standard surrogates, while ADV-COMP-SUM improves both robust and clean accuracy over TRADES.

  • Standard Multi-Class Classification: Logistic loss (τ = 1) outperforms comp-sum loss (τ = 0.5) and, by a larger margin, sum-exponential loss (τ = 0) on CIFAR-10 and CIFAR-100.The comparison is consistent with the H-consistency analysis because the minimizability gap decreases with τ.
  • Standard Multi-Class Classification: Logistic loss (τ = 1) and generalized cross-entropy (τ = 1.5) achieve relatively close results and outperform mean absolute error (τ = 2) on CIFAR-10 and CIFAR-100.Mean absolute error is also difficult to optimize with deep neural networks on complex datasets.
  • Experimental Setup: The adversarial experiments use CIFAR-10, CIFAR-100, and SVHN without generated or extra data, following specified WideResNet training and evaluation procedures.Evaluation reports clean accuracy and robust accuracy under PGD40 and AutoAttack, averaging three runs.
  • Adversarial Robustness: ADV-COMP-SUM outperforms TRADES on CIFAR-10 across WRN-70-16, WRN-34-20, and WRN-28-10 architectures.Its robust accuracy under AutoAttack is higher by at least 0.6%, and under PGD40 by at least 1.36%.
  • Adversarial Robustness: ADV-COMP-SUM consistently outperforms TRADES in clean accuracy as well as robust accuracy.For WRN-70-16, the clean-accuracy improvement is over 0.8%; on other reported comparisons, gains include more than 1.2% in robust and clean accuracy.
  • Adversarial Robustness: On CIFAR-100 with WRN-70-16, ADV-COMP-SUM exceeds TRADES by 1.12% robust accuracy and 2.54% clean accuracy.On SVHN with WRN-34-20, it exceeds TRADES by 0.29% robust accuracy and 0.95% clean accuracy.

7. Discussion

The discussion presents H-consistency bounds as tools for selecting surrogate losses and deriving generalization guarantees. It also identifies scope limits involving complete hypothesis sets, selected comp-sum components, noisy labels, and neural-network generalization.

  • Applications: H-consistency bounds can guide surrogate-loss selection using their functional form, minimizability gap, class-count dependence, and approximation properties.The bounds can also support generalization bounds for surrogate-loss minimizers.
  • Adversarial Results: The paper reports that ADV-COMP-SUM significantly outperforms TRADES in both robust and clean accuracy across all settings shown.
  • Applications: The linear dependency on the number of classes in the mean absolute error bound makes it less favorable than logistic loss.
  • Scope and Limitations: The paper’s bounds require complete hypothesis sets and do not require distributional assumptions, unlike the cited concurrent bound for constrained linear hypotheses.Bounds for non-complete hypothesis sets and arbitrary distributions are identified as future work.
  • Future Work: Future work includes extending H-consistency analysis to noisy labels, other comp-sum loss components, and other multiclass loss families.The paper also notes that adversarial robustness remains challenging, particularly for generalization to complex neural-network families.

8. Conclusion

The paper develops tighter, hypothesis-set-specific guarantees for comp-sum surrogate losses and extends the framework to adversarial robustness. Its analysis supports comparing surrogate losses and yields algorithms with reported gains in adversarial and non-adversarial performance.

  • Theoretical guarantees: The paper provides non-asymptotic, hypothesis-set-specific guarantees that are more informative than Bayes consistency for surrogate-loss analysis.These guarantees apply to the hypothesis set actually used rather than to all measurable functions.
  • Theoretical guarantees: The bounds are tight and become more explicit through the analysis of minimizability gaps.The gaps depend on the loss function and the chosen hypothesis set.
  • Theoretical guarantees: The analyzed family includes logistic loss, or softmax cross-entropy, along with generalized cross-entropy, mean absolute error, and related losses.
  • Adversarial robustness: Smooth adversarial comp-sum losses extend comp-sum losses with a related smooth term and admit H-consistency bounds in adversarial settings.The resulting algorithms minimize a regularized smooth adversarial comp-sum loss.
  • Adversarial robustness: Experiments report that the proposed adversarial robustness algorithms outperform the current state-of-the-art while achieving superior non-adversarial accuracy.

B. Proofs of H-consistency bounds for comp-sum losses (Theorem 3.1) and tightness (Theorem 3.2)

The proofs establish H-consistency bounds for comp-sum losses through conditional-risk analysis and characterize the associated transformation. A separate construction shows that the bounds are tight, while polynomial approximations make the transformation more explicit.

  • Theorem 3.1: The transformation Tτ is defined piecewise, including a logarithmic expression at τ = 1 and a power expression for τ ≥ 2.
  • Theorem 3.1: The proof derives comp-sum H-consistency bounds under symmetric and complete hypothesis sets for all τ ∈ [0,+∞).The bound is expressed through the inverse Γτ of the H-consistency comp-sum transformation Tτ.
  • Theorem 3.2: For every β ∈ [0,1] and τ ∈ [0,1], a distribution and hypothesis attain the bound, establishing tightness.
  • Polynomial approximations: The polynomial order of the approximation is tight, and its inverse provides an upper bound on Γτ.
  • Polynomial approximations: For τ ≥ 2, the polynomial approximation satisfies Tτ(β) = β^(τ−1)n^(τ−1).The same approximation is bounded piecewise for τ in [1,2) and τ ≥ 2.

D. Characterization of minimizability gaps (proofs of Theorem 4.1 and Theorem 4.2)

The paper characterizes minimizability gaps for comp-sum losses under stochastic and deterministic settings. These characterizations rely on symmetric, complete hypothesis sets or bounded score-realizability assumptions.

  • Stochastic case: The stochastic characterization assumes that H is symmetric and complete and gives a theorem for minimizability gaps of comp-sum losses.
  • Deterministic case: Under that assumption, the deterministic minimizability gaps are upper bounded using concavity and monotonicity of Φτ.
  • Stochastic case: For τ ≠ 1 and τ ≠ 2, the characterized expression uses a power transform of the conditional label probabilities.
  • Stochastic case: At τ = 1, the expression becomes the negative entropy −∑y∈Y p(x,y)log[p(x,y)].
  • Deterministic case: The deterministic characterization assumes that each x can realize every score vector in [−Λ,+Λ]^n through H.

F. Proof of adversarial H-consistency bound for adversarial comp-sum losses (Theorem 5.2)

The proof uses symmetry and local ρ-consistency to construct hypotheses with separated score differences within an adversarial neighborhood. It then applies the resulting structure to derive the adversarial bound.

  • Assumptions: The proof assumes that H is symmetric and locally ρ-consistent for the chosen hyperparameters τ and ρ.
  • Hypothesis construction: The proof defines Hγ(x) as hypotheses with positive worst-case local score separation and notes that this set is nonempty under the assumption.
  • Hypothesis construction: Local ρ-consistency supplies a hypothesis whose relevant score differences remain at least ρ within the γ-neighborhood.
  • Bound derivation: The constructed separation is inserted into the adversarial conditional-risk derivation to obtain the bound for any h ∈ H.

G. Learning bounds (proof of Theorem 3.3)

Theorem 3.3 establishes a high-probability zero-one loss estimation bound for an empirical minimizer of the comp-sum loss over H. Its proof combines standard Rademacher complexity bounds with an infimum argument and Theorem 3.1.

  • Theorem 3.3 gives a zero-one loss estimation bound holding with probability at least 1 −δ for an empirical comp-sum-loss minimizer in H.
  • Standard Rademacher complexity bounds are applied uniformly to all h ∈H as the main proof ingredient.
  • The proof selects h∗∈H using the definition of the infimum, then lets ϵ approach zero to obtain the stated inequality.
  • Substituting the resulting inequality into Theorem 3.1 completes the proof.
Loading 2304.07288v2…