Integral Probability Boundaries

Bogdan Kulynych; Shahab Asoodeh

cs.LGOct 27, 2026

Integral Probability Boundaries

Authors: Bogdan Kulynych, Shahab Asoodeh

Organizations: Biomedical Data Science Center, Lausanne University Hospital (CHUV) · McMaster University and Vector Institute

Abstract

Bounds based on Integral Probability Metrics (IPMs) are ubiquitous in machine learning and statistics, appearing, e.g., in generalization, alignment, fairness, and privacy. IPMs reduce the discrepancy between two distributions to a single worst-case gap between expectations. This compression is costly: for rare events, safety failures, or under-represented groups, IPM-based bounds are loose or vacuous. We introduce a non-linear generalization of IPMs, which we term Integral Probability Boundaries (IPBs). Unlike IPMs, IPBs provide bounds that are tight at the extremes. We derive their basic properties and present algorithms for estimating them in practically relevant settings. We demonstrate the usage of IPBs in both theoretical and practical applications for alignment, judge-free performance estimation, and fairness, where they enable us to obtain sharp bounds on performance and fairness gaps, e.g., 15 p.p. more precise estimates on fairness gaps for rare groups in a realistic generative modeling task, compared to the state of the art.

Figures & tables

Panel of Figure 1 — Figure 1: Integral Probability Boundaries (IPBs) characterize the difference in expectations of any function from a given class $\mathcal{F}$ under two distributions $P$ and $Q$ more precisely than a standard Integral Probability Metric (IPM). We show the tight IPBs and IPM for $P\sim\mathcal{N}(0,1)$ and $Q\sim\mathcal{N}(1,1)$ over the set of all bounded functions where the IPM is given by the TV distance $\delta=D_{\mathsf{TV}}(P,Q)$ , and the IPB is given by the ROC of the Neyman–Pearson test (see Section 2 ). We show IPM-based bounds with grey lines ( – ), and IPB-based bounds that trace the contour of the achievable region $\mathcal{C}_{\mathcal{F}}(P~\|~Q)$ with blue lines ( – ).

Panel of Figure 2 — Figure 2: IPB-based bounds ( – ) and IPM-based bounds ( – ) for three groups with $(q_{1},q_{2},q_{3})=(0.7,0.2,0.1)$ and $(p_{1},p_{2},p_{3})=(0.4,0.2,0.4)$ .

\hat{h}(\lambda)\leftarrow\max_{f\in\mathcal{F}}\left[\frac{1}{n_{P}}\sum_{x\in X_{P}}f(x)-\lambda\frac{1}{n_{Q}}\sum_{x\in X_{Q}}f(x)\right]

(10)

Algorithm 2 IPB estimation for a learnable family

\mathcal{F}

Panel of Figure 3 — Figure 3: IPBs provide tighter bounds on performance differences for best-of- $N$ sampling. Left: Upper bound on the gap $\mathbb{E}_{P_{N}}[f]-\mathbb{E}_{Q}[f]$ , for $\mathbb{E}_{Q}[f]\leq\alpha$ , as a function of $N$ . The IPB-based bounds from Theorem 5.1 are in solid lines. We show KL-based bounds via Pinsker’s inequality and the Bretagnolle–Huber (BH) inequality in dashed lines. Right: IPBs for several fixed values of $N$ .

Figure 4: Unlike KL-based bounds, IPBs enable accurate judge-free estimation of benchmark scores when deploying a model to vLLM. We show the compliance rate to harmful requests (lower is better) under different benchmarks for three different deployment backends, as well as the estimated bounds on the compliance rate from IPBs between the original model

Q

and its version under a given backend

P

, computed using Algorithm 1 , and the bounds from the estimated KL divergence.

Figure 5: Estimated IPB bounds for multi-group proportional representation are substantially tighter for rare groups, whereas the bounds based on an IPM are often loose. We show the bounds on the representation of intersectional groups defined by depth-3 decision trees, obtained from an IPM using the algorithm from Oesterling et al. (2024) . We also show an upper bound and lower bound from IPBs computed using Algorithm 2 and Algorithm 4 , respectively. Each point shows the prevalence of one such group in the synthetic dataset (x axis) and the real population (y axis). Left: Over the entire

[0,1]

. Right: Zoom into the

[0,0.05]

region of rare groups.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

\hat{v}(\lambda)\leftarrow\min_{f\in\mathcal{F}}\left[\frac{1}{n_{P}}\sum_{x\in X_{P}}f(x)-\lambda\frac{1}{n_{Q}}\sum_{x\in X_{Q}}f(x)\right]

(21)

Appendix

Algorithm 4 Lower-boundary IPB estimation for a learnable family

\mathcal{F}

Operation	Trials	Runtime (mean $\pm$ std)
Single grid point	30	$44.0\pm 9.3$ ms
Entire grid ( $\|\Lambda\|=10$ )	10	$0.50\pm 0.05$ s

Appendix

Table 1: Runtime of Algorithm 2 in the setup of Section 5.3 (depth-3 decision trees,

n_{P}=n_{Q}=75{,}763

) on a commodity laptop. We report the mean and standard deviation over the given number of trials.

Figure 6: Certified IPB for a family based on bounded linear functions in the setup of Section 5.3 . We show the exact empirical boundary, the output of Algorithm 2 , the certified envelope from Proposition B.9 at the

95\%

confidence level, and the IPM-based bound. The shaded regions are the certified envelopes at the

95\%

confidence level. We show the entire

\alpha

range

[0,\|\hat{\mu}_{Q}\|_{2}]

. The certified upper bound improves over the estimated IPM bound at both ends of the range, for

\alpha\leq 0.15

and for

\alpha\geq 0.56

Area	Family $\mathcal{F}$	Baseline	Reference
Theoretical
Capability deterioration in alignment (BoN)	$\mathcal{F}_{1}$	KL + Pinsker/BH	Section 5.1
Generalization under $f$ -DP	$\mathcal{F}_{1}$	—	Section B.3
Attack risk under $f$ -DP	$\mathcal{F}_{1}$	—	Section B.3
Empirical ( Algorithm 1 / Algorithm 2 )
Judge-free model performance estimation	$\mathcal{F}_{1}$	KL + Pinsker/BH	Section 5.2

Appendix

Table 2: Summary of applications of IPBs described in this paper.

Figure 7: Estimated IPB curves for the judge-free performance estimation experiment in Section 5.2 . For each benchmark and deployment backend

P

, we show the IPB upper bound

g\in\mathcal{B}_{\mathcal{F}_{1}}(P~\|~Q)

and the lower bound

\check{g}^{-1}

for

\check{g}\in\mathcal{B}_{\mathcal{F}_{1}}(Q~\|~P)

, computed with Algorithm 1 from the samples of the original model

Q

. The dotted vertical line marks the audited compliance rate

\mathbb{E}_{Q}[f]

of the original model, and the diamonds mark the observed compliance rate

\mathbb{E}_{P}[f]

under each backend. The intervals in Fig. 4 are the vertical slices of these curves at

\mathbb{E}_{Q}[f]

. As in Fig. 1 , the curves are tightest near the diagonal for small deviations (vLLM) and widen for quantized backends. Top: Over the entire

[0,1]

. Bottom: Zoom into the

[0,0.2]

region containing the observed compliance rates.

Figure 8: IPB bounds for CTGAN synthetic data trained on two other training–test splits. Same setup as Fig. 5 .

Integral Probability Metrics

Integral probability metrics compare probability distributions by the largest expectation gap over a chosen class of test functions.

See all 15 papers

Jun 17, 2023

Understanding Certified Training with Interval Bound Propagation

As robustness verification methods are becoming more precise, training certifiably robust neural networks is becoming ever more relevant. To this end, certified training methods compute and then optimize an upper bound on the worst-case loss over a robustness specification. Curiously, training methods based on the imprecise interval bound propagation (IBP) consistently outperform those leveraging more precise bounding methods. Still, we lack an understanding of the mechanisms making IBP so successful. In this work, we thoroughly investigate these mechanisms by leveraging a novel metric measuring the tightness of IBP bounds. We first show theoretically that, for deep linear models, tightness decreases with width and depth at initialization, but improves with IBP training, given sufficient network width. We, then, derive sufficient and necessary conditions on weight matrices for IBP bounds to become exact and demonstrate that these impose strong regularization, explaining the empirically observed trade-off between robustness and accuracy in certified training. Our extensive experimental evaluation validates our theoretical predictions for ReLU networks, including that wider networks improve performance, yielding state-of-the-art results. Interestingly, we observe that while all IBP-based training methods lead to high tightness, this is neither sufficient nor necessary to achieve high certifiable robustness. This hints at the existence of new training methods that do not induce the strong regularization required for tight IBP bounds, leading to improved robustness and standard accuracy.

Yuhao Mao, Mark Niklas Müller, Marc Fischer +1

Department of Computer Science, ETH Zürich, Swizterland

Neural Network Verification Neural Network Robustness Certified Robustness

Ask PDF

Oct 29, 2026

Learning to Bound: Monotonic, Calibrated Neural Upper Bounds for MPE Inference

Probabilistic graphical models (PGMs) compactly encode structured joint distributions, but Most Probable Explanation (MPE), which finds the highest-probability assignment to unobserved variables, remains computationally intractable in large, densely structured models. Anytime systematic search, such as branch-and-bound (B&B), is a popular approach, but its efficiency depends on tight admissible upper bounds that are often prohibitively expensive to compute using classical methods like Mini-Bucket Elimination (MBE). We introduce Learning to Bound (L2B), a data-driven framework that amortizes bound computation cost by training a neural predictor. L2B targets two key properties required for effective search bounds: admissibility, which is achieved via statistical calibration techniques, and progressive tightening as evidence accumulates, which is enforced through structural architectural constraints that ensure monotonicity by construction. Across challenging benchmarks, L2B delivers tighter, monotonic bounds at orders-of-magnitude lower cost on every PGM family, and yields measurable improvements when integrated with branch-and-bound on high-treewidth instances.

Akshay Vyas, Hailiang Dong, Shivvrat Arya +4

The University of Texas at Dallas

Probabilistic Graphical Models Amortized Inference Abductive Reasoning Branch and Bound

Ask PDF

May 28, 2026

Improved Distribution Estimation in $\ell_\infty$

We present improved bounds for estimating discrete probability distributions under the

\ell_\infty

norm. These include minimax bounds in expectation and high-probability tail bounds. We resolve some of the open questions posed in Kontorovich and Painsky (JMLR, 2025) -- including a fully empirical version of the tightest risk bound they presented and identifying the form of the worst-case extremal distribution. Encouraging empirical results are reported as well.

Doron Cohen, Aryeh Kontorovich, Yonatan Livshitz

Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel

Minimax Estimation

Ask PDF

Abstract

Integral Probability Metrics

Explore similar work

Understanding Certified Training with Interval Bound Propagation

Learning to Bound: Monotonic, Calibrated Neural Upper Bounds for MPE Inference

Improved Distribution Estimation in ℓ∞\ell_\inftyℓ∞​

Improved Distribution Estimation in $\ell_\infty$