Generalization Bounds for Unbounded Loss Functions

694 concepts382 papers2 proposals

To trust a machine learning model in production, we need theoretical guarantees that its performance on training data will translate to unseen test data. Historically, statistical learning theory has provided these guarantees in the form of generalization bounds. However, if you look closely at the mathematical foundations of classical PAC-Bayesian, information-theoretic, or stability-based bounds, you will almost always find a restrictive assumption: the loss function must be strictly bounded (e.g., restricted to a fixed range like $[0, 1]$) or follow a light-tailed, sub-Gaussian distribution.

This creates a stark disconnect between theory and practice. Modern deep learning relies heavily on loss functions like cross-entropy or mean squared error, which are inherently unbounded. If a model makes a highly confident but incorrect prediction, its cross-entropy loss can theoretically approach infinity. When theorists try to force these unbounded losses into classical frameworks by artificially clipping them, the resulting bounds often become loose or entirely vacuous, failing to reflect real-world performance as noted by Rie Johnson in Inconsistency, Instability, and Generalization Gap of Deep Neural Network Training.

To bridge this gap, a major research direction focuses on relaxing or eliminating the bounded loss assumption, developing new mathematical machinery capable of handling unbounded and heavy-tailed loss distributions.

Why Boundedness Matters (and Where It Fails)

To understand why early learning theory relied so heavily on bounded losses, we have to look at how concentration inequalities work. Traditional proofs rely on tools like Hoeffding's inequality to show that the empirical average of a loss function concentrates tightly around its true expected risk. Hoeffding's inequality requires a hard envelope; it scales with the maximum possible range of the function. If the loss can be infinitely large, the range is infinite, and the bound completely collapses.

When moving to unbounded settings, a single outlier or a heavy-tailed data distribution can cause massive variance in the loss. This behavior violates the tail assumptions necessary to maintain tight error estimates. As a result, standard divergence measures yield overly conservative complexity terms that fail to capture the true generalization capabilities of models trained on real-world, non-idealized data.

Mechanism 1: Shifting to Sub-Gamma Profiles and Finite Moments

The first major strategy for bypassing the bounded loss constraint involves replacing the strict binary or sub-Gaussian assumption with more flexible tail conditions.

In PAC-Bayesian Theory Meets Bayesian Inference, Pascal Germain et al. demonstrated that generalization bounds can be extended to regression tasks with unbounded losses by assuming the loss distribution follows a sub-gamma profile. Instead of assuming the loss never exceeds a threshold, a sub-gamma assumption dictates that the probability of experiencing an extreme loss decays exponentially, controlled by a variance factor and a scale parameter. This allows for rigorous frequentist guarantees without requiring artificial clipping.

Tail Assumptions & Generalization Capability:
[ Bounded / [0,1] ]  --> Strict, fails on cross-entropy / squared error
[ Sub-Gaussian    ]  --> Fails on heavy-tailed real-world data (finance, physics)
[ Sub-Gamma       ]  --> Accommodates unbounded regression losses via exponential decay
[ Finite Moments  ]  --> Widest applicability; uses p-norm divergences for heavy tails

However, some domains—like finance or physics—exhibit extreme outliers where even sub-gamma assumptions fail. To resolve this, Gábor Lugosi and Gergely Neu developed a framework in Generalization Bounds via Convex Analysis that replaces sub-Gaussian assumptions entirely with finite moment requirements. By utilizing $p$-norm divergences instead of traditional Kullback-Leibler (KL) divergence, the authors proved that learning algorithms can be theoretically validated using only higher-order moments of the loss, providing a path forward for heavy-tailed data distributions.

Mechanism 2: The $(\eta, c)$-Central Condition

While relaxing tail assumptions makes bounds valid, it often slows down the guaranteed convergence rate from a "fast" rate of $O(1/n)$ to a "slow" rate of $O(1/\sqrt{n})$, where $n$ is the number of training samples.

To achieve the tightest possible error estimates for unbounded losses, Xuetong Wu et al. introduced a technical framework known as the $(\eta, c)$-central condition in Fast Rate Generalization Error Bounds: Variations on a Theme.

The central condition acts as a geometric constraint on the cumulant generating function of the loss. Intuitively, it bounds the variance of the exponentiated loss relative to its expectation. By satisfying this condition, researchers can leverage information-theoretic tools to prove that Empirical Risk Minimization (ERM) still achieves fast $O(1/n)$ convergence rates, even when the underlying data distribution is heavy-tailed and the loss function is unbounded.

Mechanism 3: Loss Entropy and Oracle Inequalities

Another prominent approach changes the perspective entirely: instead of trying to bound the complex, high-dimensional relationship between the model weights and the input data, why not analyze the distribution of the loss values directly?

In Rethinking Information-theoretic Generalization: Loss Entropy Induced PAC Bounds, Yuxin Dong proposed focusing on loss entropy—the intrinsic randomness and uncertainty within the one-dimensional loss distribution itself. By reducing multi-dimensional information metrics to a simple one-dimensional variable, Dong derived high-probability PAC bounds that naturally accommodate long-tailed losses like cross-entropy. This framework remains numerically tight even in the "interpolating regime," where modern deep networks achieve zero training error yet continue to generalize well.

For classification tasks where predictions approach absolute certainty (probabilities of 0 or 1), the log-odds ratio in logistic loss naturally diverges to infinity. To handle this specific flavor of unboundedness, Zihan Zhang and Lei Shi established oracle-type inequalities in Classification with Deep Neural Networks and Logistic Loss. These inequalities bound the excess risk by comparing the model's performance directly to an ideal "oracle" target function, allowing for optimal learning rates without requiring any artificial clipping of the target probabilities.

Open Frontiers

While these mathematical workarounds have successfully extended generalization theory to standard regression and classification tasks, adapting them to more complex paradigms remains an active area of research. For instance, current frameworks for multi-group learning (ensuring fairness across subgroups) and non-pointwise learning (where losses depend on multiple samples simultaneously) are still largely restricted to bounded settings. Fully translating these advanced concentration techniques to non-Lipschitz, unbounded objectives continues to be a vital frontier in statistical learning theory.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 410 papers
  2. Version 1 · 2026-10-04 · 444 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_bounded_loss_assumption_9150cdce,
  title = {bounded loss assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bounded-loss-assumption/rdr_9150cdce06e34a57818a52b11e572297},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_bounded_loss_assumption_9150cdce_v2,
  title = {bounded loss assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bounded-loss-assumption/rdr_9150cdce06e34a57818a52b11e572297/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake