Certifying Test KL Divergence in Label Distribution Learning with a Probability Floor

Some prediction tasks have no single correct answer. When forty people label a face, some call it "happy," some "surprised," and a few "fearful." Label distribution learning trains a model to predict that whole spread of votes, a probability vector over emotions, instead of one label. The standard training loss and evaluation score is the Kullback–Leibler divergence (KLD), a measure of how far the predicted distribution is from the human one. KLD has no upper limit. If the model assigns near-zero probability to an emotion that some annotators actually chose, the loss goes to infinity. Approximately Correct Label Distribution Learning shows the practical damage. Models trained on KLD fit a few extreme instances, and the published method SA-BFGS scores a test KLD of 0.6878 on the M²B benchmark. That is worse than the 0.6335 obtained by always predicting the uniform distribution. The same unboundedness blocks the theory side. Most generalization bounds assume the loss is bounded, and the extensions to unbounded losses need tail parameters that nobody knows for this problem.

We propose a small structural fix with an exact accounting of its cost. The model mixes every prediction with a sliver of the uniform distribution, which guarantees that each emotion gets at least probability $\epsilon/C$. With this floor, KLD has a hard ceiling. The ceiling holds for the predictor that is actually deployed, not for a clipped stand-in loss. The floor also raises the true KLD by at most a known, tiny amount. Together these two facts make three things possible: a PAC-Bayes certificate (a guarantee computed from training data that holds with high probability) on real test KLD, a principled data-driven choice of $\epsilon$, and a direct test of whether the "worse than uniform" failure is purely a tail-control failure. Our standard for a non-vacuous certificate is a bound below the uniform predictor's test KLD on the same split. A bound above that number tells a practitioner nothing they could not get for free.

Core Claim

Write $g(x)$ for any model's predicted distribution over $C$ emotions. Define the floored predictor $h_\epsilon(x) = (1-\epsilon)\,g(x) + \epsilon/C$. For every target distribution $y$ on the simplex, two inequalities hold:

$$ \mathrm{KL}(y \,\|\, h_\epsilon) \le \ln\frac{C}{\epsilon} - H(y), \qquad \mathrm{KL}(y \,\|\, h_\epsilon) \le \mathrm{KL}(y \,\|\, g) + \ln\frac{1}{1-\epsilon}, $$

where $H(y)$ is the entropy of the annotator distribution. The first inequality follows because every component satisfies $h_{\epsilon,c} \ge \epsilon/C$. The second follows because every component satisfies $h_{\epsilon,c} \ge (1-\epsilon) g_c$.

The first inequality gives a range that is known in advance. The bounded-loss machinery that the unbounded-loss literature works so hard to avoid therefore applies directly to true test KLD. The second inequality says the floor costs at most about $\epsilon$ nats on instances the model already fits well. Its benefit comes entirely from instances where $g$ collapses toward zero.

Our claim has two parts. On standard emotion LDL benchmarks, a floor tuned by the bound will (a) bring KLD-trained models below the uniform reference on test KLD, closing most of the gap to δ-LDL. It will also (b) produce a variance-aware PAC-Bayes certificate on test KLD that sits below the uniform reference for datasets with a few thousand instances.

Research Program

The theoretical piece is modest by design. We fix a stochastic predictor: a Gaussian posterior $Q$ over the weights of a linear or two-layer head on frozen image features. We restrict to the head because Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stability documents that the term measuring divergence between the learned weight distribution and the prior grows with parameter count and makes bounds on full deep networks vacuous. We certify the floored loss with two bounds. The first is a Hoeffding-style PAC-Bayes bound with range $\ln(C/\epsilon)$. The second is a Bernstein-style variant whose penalty scales with the empirical variance of the per-instance loss rather than its range.

The prediction is that the range-based bound will be loose. A floor of $\epsilon = 0.01$ with six emotions gives a range of about 6.4 nats, against typical KLD near 0.5. That is exactly the looseness Inconsistency, Instability, and Generalization Gap of Deep Neural Network Training attributes to forcing unbounded losses into bounded frameworks. The variance-aware bound should be much tighter, because the floor makes the extreme tail rare and short. That contrast is a falsifiable part of the proposal, not an assumption.

We choose $\epsilon$ by minimizing the bound over a fixed grid, which costs only the logarithm of the grid size in the confidence term. For the prior, we use a data-dependent prior learned on a held-out half of the training data. This is the standard way to avoid the circularity flagged in Adaptive Meta-Learning via data-dependent PAC-Bayes bounds. We compare it against training the prior jointly on the same data, in the manner of Improving Generalization of Complex Models under Unbounded Loss Using PAC-Bayes Bounds.

The floor can be built into training or applied after the fact to any trained model, including δ-LDL and SNEFY-LDL. Because of this, the certificate works as an add-on rather than a competing learner.

A secondary, clearly scoped extension connects to meta-learning. Once the loss is rescaled by $\ln(C/\epsilon)$, it lies in $[0,1]$. That is exactly the assumption of the unified bound in A Unified View on PAC-Bayes Bounds for Meta-Learning, whose author names unbounded losses as an open limitation. In the meta-learning version, each task is one subgroup of the data, and a shared prior is learned across tasks. We would apply the theorem with the four demographic subsets of SCUT-FBP5500 as tasks, using leave-one-subgroup-out evaluation. With only four tasks, the environment-level term will almost certainly be vacuous. We report that result as a negative finding rather than claim a meta-learning result. The point is only to show the floor removes the bounded-loss obstacle; the problem of having too few tasks remains.

Baselines

The naive reference is the uniform predictor, which always outputs $1/C$ for every emotion. Its test KLD defines vacuity in this note. On M²B the reported value is 0.6335 (Approximately Correct Label Distribution Learning). On the other datasets we compute it on our own splits.

The strongest existing method for this question is δ-LDL from the same paper. It replaces KLD with a bounded, smoothed tolerance objective and reports a test KLD of 0.4882 and a μ-metric of 58.25% on M²B, the best of twelve models tested there. We rerun it with the authors' settings on identical splits and identical frozen features. It gets the same hyperparameter search budget as our method.

A second learner baseline is SNEFY-LDL from Label Distribution Learning using the Squared Neural Family on the Probability Simplex. It models a full density over label distributions and is trained by likelihood, so it is exposed to the same unbounded tail. The file has no reported test-KLD number for it; the closest is a cosine similarity of 0.9406 for its density-weighted ensemble with SA-BFGS on SBU_3DFE. We also include plain KLD-trained heads and SA-BFGS, which reports 0.6878 KLD on M²B.

The key ablations isolate the floor. First, we compare an identical KLD-trained head with no floor, a fixed floor, and a floor chosen by the bound. Second, we compare a floor applied after training with one built into training. Third, we compare against loss clipping at a matched threshold.

We count our method as beating δ-LDL if the bound-tuned floored model matches its test KLD within seed variance and also carries a certificate below the uniform reference, which δ-LDL lacks. We count it as beating δ-LDL outright if its test KLD is lower. If δ-LDL still wins on KLD, the post-hoc-floored δ-LDL becomes the recommended system, and our contribution reduces to the certificate.

Why not just…?

Why not just clip the loss at some ceiling M? Clipping certifies a different quantity: the clipped loss. The deployed model can still put near-zero mass on a chosen emotion and incur unbounded true KLD on test data, which is precisely what Li et al. report. The floor changes the predictor, so the bounded quantity is the true KLD of what ships, and the second inequality prices the change. The clipped-loss ablation will show how far a clipped certificate sits from realized test KLD compared with the floored one.

Why not just use the bounded δ-LDL objective and the μ-metric? This is the real threat on accuracy, and we do not argue around it. δ-LDL already beats uniform on M²B. However, it changes the quantity being measured, provides no finite-sample guarantee, and leaves KLD as the field's reported number. Because the floor can be applied to δ-LDL after training, the experiment settles the question directly. If post-hoc-floored δ-LDL is best on both KLD and the certificate, we say so.

Why not just apply sub-gamma PAC-Bayes bounds, as in Germain et al. or PACOH? PAC-Bayesian Theory Meets Bayesian Inference and PACOH require known variance and scale parameters for the loss tail. Misestimating these parameters makes the bound invalid or vacuous, and Li et al.'s outlier behavior suggests KLD on the simplex does not have a well-behaved tail. The finite-moment route of Generalization Bounds via Convex Analysis avoids that assumption but pays slower rates. The floor makes every moment finite by construction, with a constant known in advance. We will report the sub-gamma bound computed with empirically estimated parameters, to show how sensitive it is to that estimate.

Why not just smooth the targets during training? Target smoothing changes what the model fits on training data. It places no constraint on the model's outputs at test time, where annotators may choose an emotion the model has driven toward zero. Smoothing the outputs is the floor itself. The only open question is whether to tune $\epsilon$ by the bound or by validation KLD, and we run both.

Proposed Experiments

We use M²B, SBU_3DFE (2,500 instances), SJAFFE (213), Natural Scene (2,000), Movie (7,755), RAF-ML, and SCUT-FBP5500. We run five random train/test splits with frozen backbone features shared by all methods. We report test KLD, Chebyshev and Clark distances, cosine similarity, the μ-metric, and, for every certified model, the bound value and its ratio to uniform test KLD.

Four checks decide the outcome. First, on M²B, KLD-trained heads with a bound-tuned floor must fall below 0.6335 test KLD while the unfloored versions do not. Otherwise the tail-control explanation is wrong. Second, the variance-aware certificate must fall below uniform test KLD on the datasets with roughly 2,000 or more instances, while the range-based certificate is expected not to. SJAFFE, with 213 instances, is the stress test we expect to fail. Third, the gap between bound and realized test KLD should shrink as the bound-chosen $\epsilon$ moves away from both extremes, confirming the trade-off between loss range and approximation cost. Fourth, the post-hoc floor applied to δ-LDL and SNEFY-LDL should cost at most about $\epsilon$ nats of test KLD, as the second inequality predicts. A larger loss would indicate an error in the analysis or the implementation.