Research map / Learning theory and algorithms / Kernels and regression theory
Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a PAC-Bayes bound on the KL divergence between empirical and true error-type distributions (multinomial risk vectors), yielding simultaneous bounds on all linear combinations of error probabilities, and turns it into a differentiable training objective.
Problem
Existing PAC-Bayes bounds control only scalar risks (loss or error rate) or a single pre-chosen weighting of error types, so they cannot certify the full distribution of error outcomes (e.g., confusion matrix, test loss distribution in discretized bins).
Approach
Generalise the PAC-Bayes kl bound from binary error to a vector of M error-type probabilities by bounding kl between empirical and true risk vectors on the simplex using a multinomial-based constant; then derive a closed-form-ish vectorised kl-inverse with gradients for optimising a total-risk bound.
Key results
- Bound on total risk R^T_D(Q) of 0.2640 on binarised MNIST (loss vector (0,1,3)), holding with probability 0.94.
- Bound on total risk of 0.8379 on HAM10000 with the same loss vector.
- Confidence region volume is smaller than union of Maurer bounds on MNIST (0.0025 vs 0.0028) but larger on HAM10000 (0.0012 vs 0.0011).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the PAC-Bayes error-type bound instead of unioning individual Maurer bounds | confidence region for the error-probability vector · MNIST | confidence-region volume: 0.0028 (0.002793, 0.002800) -> 0.0025 (0.002498, 0.002504) | Helped |
| Use the PAC-Bayes error-type bound instead of unioning individual Maurer bounds | confidence region for the error-probability vector · HAM10000 | confidence-region volume: 0.0011 (0.001142, 0.001146) -> 0.0012 (0.001207, 0.001211) | Hurt |
| Tune the posterior with the differentiable total-risk objective | PAC-Bayes error-type bound · binarised MNIST | total-risk bound | Helped |
| Tune the posterior with the differentiable total-risk objective | PAC-Bayes error-type bound · HAM10000 | total-risk bound | No clear effect |
Surprising findings
- On HAM10000 the proposed region is larger than the union of Maurer bounds, so the method is not uniformly better.
- Optimising the posterior via the bound barely moved Q on HAM10000 (KL below 0.1), so the bound did not improve beyond initialisation there.
Limitations
- Requires i.i.d. data and a finite number of error types M.
- Bound term grows roughly linearly in M up to logarithmic factors; the method is not uniformly tighter than union of Maurer bounds.
Experimental setup
Datasets: MNIST HAM10000
Benchmarks: MNIST HAM10000
Metrics: total risk bound confidence region volume kl bound
Baselines: Maurer's inequality with union bound Morvant's bound
Builds on: Maurer's PAC-Bayes kl bound Germain et al. unifying PAC-Bayes bound change of measure inequality Morvant et al. confidence region bound
Closest papers by meaning
- How Tight Can PAC-Bayes be in the Small Data Regime? (NeurIPS 2021 · similarity 0.91)
- PAC-Bayes-Chernoff bounds for unbounded losses (NeurIPS 2024 · similarity 0.87)
- Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Loss (NeurIPS 2024 · similarity 0.87)
- Learning via Surrogate PAC-Bayes (NeurIPS 2024 · similarity 0.87)
- PAC-Bayes Bounds for Multivariate Linear Regression and Linear Autoencoders (NeurIPS 2025 · similarity 0.86)
- PAC-Bayes Generalisation Bounds for Dynamical Systems including Stable RNNs (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.