PACMAN: PAC-style bounds accounting for the Mismatch between Accuracy and Negative log-loss

Matías Vera, Leonardo Rey Vega, Pablo PiantanidaarXiv 2021 · OpenReview

Introduction

In modern machine learning, there exists a fundamental discrepancy between how models are trained and how they are evaluated. For classification tasks, the ultimate goal is high accuracy (minimizing the 0-1 loss). However, because the 0-1 loss function is non-differentiable and computationally difficult to optimize, practitioners almost universally use a "surrogate" loss function during training—most commonly the negative log-loss (cross-entropy).

While this approach is effective in practice, it creates a theoretical blind spot. Classical generalization theories, such as those based on VC-dimension or Rademacher complexity, typically assume that the loss function used for training is identical to the one used for testing. This paper introduces PACMAN (PAC-style bounds over the Mismatch of Accuracy and Negative log-loss), a theoretical framework designed to bridge this gap and provide rigorous guarantees for testing accuracy based on training log-loss.

The PACMAN Framework

The PACMAN analysis addresses the "bait-and-switch" of loss functions by treating the mismatch as a likelihood ratio problem. The authors develop a point-wise PAC approach that relates the empirical cross-entropy risk on a training set to the expected error probability on unseen data.

Technical Pillars

To achieve this, the framework relies on several key innovations:

  1. Metric Alignment: The authors define a "cross-entropy of the expected risk" ($\widetilde{CE}_p$), a bijective transformation of the error probability. This allows accuracy and log-loss to be compared on a mathematically consistent scale.
  2. Likelihood Ratios: The generalization gap is expressed as a likelihood ratio between the true data distribution and a distribution conditioned on correctly classified samples.
  3. Information-Theoretic Tools: The bounds are derived using sophisticated measures, including Renyi $\alpha$-divergences and Mutual Information ($I(S; \mathbf{h})$). These tools quantify the "information leakage" or the degree to which a model memorizes specific training samples versus learning generalizable patterns.

Key Theoretical Insights

The $1/n$ Fast Rate

One of the most significant findings of the PACMAN framework is the scaling of the generalization bound. While many traditional bounds scale at a rate of $1/\sqrt{n}$ (where $n$ is the number of training samples), PACMAN bounds achieve a "fast rate" of $1/n$. This suggests that as datasets grow, the mismatch between training performance and testing accuracy vanishes much more rapidly than previously assumed.

Information Sharing and Complexity

The framework reinforces the intuition that generalization is inversely related to how much information a model "shares" with its training set. Models that achieve low training loss without excessive memorization (low mutual information density) are guaranteed better generalization. For regular parametric models, the bound is explicitly linked to the number of trainable parameters ($\nu$), providing a formal connection between model size and the generalization gap.

The Role of Calibration

The analysis also highlights the importance of model calibration. In scenarios where an algorithm is well-calibrated—meaning the predicted probabilities accurately reflect the true class frequencies—the gap between the "soft risk" (log-loss) and "hard risk" (accuracy) is minimized.

Empirical Validation

The authors validated the PACMAN insights through experiments on two standard benchmarks:

  • CIFAR-100 with ResNet18: By varying the width of ResNet18 architectures, the authors observed how the generalization gap behaves in overparameterized regimes. The results confirmed that as model width increases, the "bias" term in the PACMAN bound becomes negligible, making training log-loss an increasingly reliable proxy for testing accuracy.
  • Fashion-MNIST with Deep Neural Networks: Using a 3-layer fully connected network, the researchers empirically measured the relationship between soft and hard risk across different hidden unit counts, further supporting the theoretical link between information-theoretic quantities and model performance.

Conclusion and Future Directions

PACMAN provides a robust theoretical foundation for understanding why models trained on cross-entropy succeed in accuracy-based evaluation. By moving beyond the assumption of matching loss functions, it offers a more realistic view of the generalization process in deep learning.

While the current framework provides powerful insights, it faces challenges in non-identifiable models (common in deep learning due to neuron shuffling symmetries) and cases of extreme model overconfidence. Future work may involve using PACMAN bounds as explicit regularization terms during training, encouraging models to minimize the information-theoretic quantities that lead to better generalization.

Summary updated

Abstract

The ultimate performance of machine learning algorithms for classification tasks is usually measured in terms of the empirical error probability (or accuracy) based on a testing dataset. Whereas, these algorithms are optimized through the minimization of a typically different--more convenient--loss function based on a training set. For classification tasks, this loss function is often the negative log-loss that leads to the well-known cross-entropy risk which is typically better behaved (from a numerical perspective) than the error probability. Conventional studies on the generalization error do not usually take into account the underlying mismatch between losses at training and testing phases. In this work, we introduce an analysis based on point-wise PAC approach over the generalization gap considering the mismatch of testing based on the accuracy metric and training on the negative log-loss. We label this analysis PACMAN. Building on the fact that the mentioned mismatch can be written as a likelihood ratio, concentration inequalities can be used to provide some insights for the generalization problem in terms of some point-wise PAC bounds depending on some meaningful information-theoretic quantities. An analysis of the obtained bounds and a comparison with available results in the literature are also provided.
BibTeX
@misc{vera2021pacman,
  author = {Matías Vera and Leonardo Rey Vega and Pablo Piantanida},
  title = {{PACMAN: PAC-style bounds accounting for the Mismatch between Accuracy and Negative log-loss}},
  year = {2021},
  eprint = {2112.05547},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.05547},
}
Figure