CS Paper Radar

Integral Probability Boundaries

Bogdan Kulynych, Shahab Asoodeh

cs.LG cs.ITstat.ML ·submitted 2026-10-27 22:41 UTC · v1
published

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.

Comment
NeurIPS 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Efficient Active Auditing of Multi-Group Fairness with Bias Probes

cs.LG cs.AIcs.CYstat.AP+1 ·2026-09-30 ·Ayoub Ajarra, Debabrota Basu
similarity 0.62
Abstract

Over the past decade, Machine Learning (ML) has been trained under dual objectives: minimizing prediction error via Empirical Risk Minimization (ERM) while controlling unfairness bias. In practice, however, fairness-aware training often yields limited improvements over standard ERM, making reliable post hoc auditing essential. Existing auditing approaches for black-box models either rely on model reconstruction --exposing systems to extraction attacks-- or directly estimate fairness metrics, offering limited insight into which regions of the data distribution drive bias. More fundamentally, property-specific auditing --aimed at extracting only targeted fairness information without reconstructing the model-- remains poorly understood. In this work, we introduce the bias probe framework, which enables targeted and adaptive querying to reveal bias structure while preserving model confidentiality. Building on this framework, we propose ALeBi, an active auditor that learns such probes to efficiently estimate multi-group fairness metrics. We establish novel sample complexity guarantees governed by a property-specific complexity measure, resolving a previously posed open question, and extend our analysis to adversarial settings where the model owner may strategically obscure bias. Our results uncover a fundamental trade-off between model confidentiality and reliable auditing, and show that property-specific probing enables both accurate estimation and interpretable identification of high and low-bias regions. Extensive experiments support our theoretical findings and demonstrate the practical effectiveness of our approach.

0.12

The Role of Uncertainty in Assessing the Fairness of Machine Learning Models

cs.LG stat.MLstat.ME ·2026-09-07 ·Francesca Panero, Ernst C. Wit, Marco Scutari
similarity 0.62
Abstract

Machine learning models are widely used in clinical applications, social media, law enforcement and critical infrastructure. Verifying whether their outputs are biased against disadvantaged groups or individuals is crucial to ensuring they are fair and allowing their use in such settings. A rigorous risk assessment of possible fairness violations requires quantifying the uncertainty associated with selecting and estimating such models. Yet, this is rarely done in the literature, which focuses on identifying a single model with a suitable trade-off between predictive accuracy and fairness. In this paper, we move beyond point estimation and discuss frequentist and Bayesian approaches to uncertainty quantification for fair machine learning, with practical examples and implications for simulated and real data.

0.24

Certification-Enhanced Generalization Bounds

cs.LG ·2026-10-05 ·Leo Elmecker-Plakolm, Matthew Wicker
top venue similarity 0.62
Abstract · Accepted at NeurIPS 2026

We investigate the use of formal methods to provide tight and sound generalization bounds for learning algorithms. By casting the traditional notion of algorithmic stability as a specification to be verified, we demonstrate that recent advances in reachability analysis can yield provable bounds on the generalization of a given model and algorithm on a sample dataset. As sample-specific algorithmic stability is insufficient to bound the usual distributional notion of generalization, we develop a novel concentration inequality to connect the sample-specific results of formal certification algorithms to the required distributional analysis for bounding the expected generalization gap. The resulting framework enables the analysis of prior generalization bounds to extend far beyond their original restrictive assumptions. Our approach computes sound bounds on the expected generalization gap in a constant number of algorithm runs without making any analytical assumptions on the algorithm; to achieve non-vacuous bounds we only require that the certified reachable parameter set is bounded --- a condition that we do not assume but formally verify. In practice, we demonstrate that our framework provides formal generalization guarantees that are orders of magnitude tighter than alternative sound computational approaches at scales ranging from toy datasets to fine-tuning classification heads on top of modern large language models. While we implement certification-enhanced versions of several well-known stability results, future extensions of our approach will enable tighter bounds and enhanced practical adoption across the spectrum of modern generalization bounds.

0.32

Statistical attribute alignment for black-box generative AI via output post-processing

cs.AI stat.MEcs.LGmath.ST ·2026-09-25 ·Kevin Jiang, Morgane Austern, Edgar Dobriban, Jason M. Klusowski
similarity 0.61
Abstract

Generative AI systems are increasingly used, but aligning their outputs with user requirements poses a continuing challenge. Here, we aim to ensure that the distribution of an attribute of an AI-generated output aligns with a user-specified target. This is motivated by examples such as fairness, where we want to ensure that a protected attribute (e.g., gender, race, or age categories) follows a desired distribution, and synthetic data generation, where we want the generated data to be representative of a target distribution. We study the practically important black-box access setting, where a user can repeatedly query a generative AI model. The goal is to return $m\ge 1$ outputs whose joint attribute distribution is as close as possible to this target. For both exact and approximate alignment, we develop algorithms that minimize the expected number of queries to the generator, and we further demonstrate their optimality as the number of requested outputs $m \rightarrow \infty$. Experiments on text-to-image generation and geocoded persona generation tasks show that our post-processing algorithms improve statistical attribute alignment, complementing prompting-based interventions.

0.17

Sample-Grained Approximate Unlearning with Provable Per-Sample Bounds

cs.LG ·2026-11-03 ·Yaxin Xiao, Yulin Jin, Li Tang, Haoyang LI, Huadi Zheng +2 more
top venue similarity 0.60
Abstract · accepted by NeurIPS 2026

Machine unlearning aims to erase the influence of a designated forget set from a trained model while preserving strong utility on the retain set. Approximate unlearning methods efficiently achieve this goal without full retraining, but their effectiveness is primarily assessed using dataset-level aggregate metrics. These aggregate metrics can mask deviations from retraining at the level of individual samples. In this work, we focus on per-sample unlearning effectiveness. We introduce SALA (Sample-grained Likelihoods ALignment), a plug-in optimization framework that enables approximate unlearning methods to operate at the level of individual samples by steering each example toward its correct target distribution. To quantitatively assess this behavior, we further propose the sample-grained distribution gap, a metric that captures per-sample discrepancies between approximate unlearning and exact retraining output distributions. We provide theoretical guarantees showing that SALA contracts this gap and yields a bounded per-sample discrepancy to retraining. To make this framework practical, we develop a low-cost estimation method for the member and non-member target distributions. Extensive experiments on classification and generation tasks demonstrate that SALA reduces the sample-grained distribution gap by up to $86.67\%$ when paired with existing approximate unlearning baselines, while also improving robustness to unlearning hyperparameters.

0.35

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

cs.LG cs.AI ·2026-10-29 ·Akshay Vyas, Hailiang Dong, Shivvrat Arya, Brij Malhotra, Tahrima Rahman +2 more
similarity 0.60
Abstract · 37 pages, 4 figures

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.

0.21

Overcoming the Resolution Limit: Significance-Aware Regularization for Intersectional Fairness

cs.LG ·2026-11-11 ·Antonio Ferrara, André Panisson, Francesco Cozzi, Alan Perotti, Francesco Bonchi
top venuebenchmark similarity 0.60
Abstract · Accepted at NeurIPS 2026

Intersectional fairness requires evaluating models across fine-grained subgroups. However, as group definitions become more granular, the sample size per subgroup shrinks, causing fairness estimates to become increasingly unstable. Existing in-processing methods are certainty-blind: they penalize observed disparities without distinguishing statistically certified unfairness from sampling noise. This leads to fairness overfitting, where models sacrifice utility to "fix" spurious disparities in sparse regimes. To address this, we introduce the significant-excess metric family, a continuous, uncertainty-aware fairness score that measures only the portion of a subgroup's disparity exceeding what sampling variation can explain at a specific confidence level. Building on this metric, we propose SAFER (Significance-Aware Fairness Regularizer), a differentiable in-processing method that gates fairness penalties using a soft-count likelihood-ratio evidence statistic. SAFER satisfies a provable safety property: when every subgroup disparity lies well below the gate threshold, the unconstrained optimum is nearly stationary for SAFER. At that optimum, the back-propagated contribution of its significance-gated component is exponentially small, and the additional fairness contribution comes from a small ungated term with a fixed weight. Mechanism ablations across three benchmark datasets and purpose-built stress variants show that removing any component of SAFER (threshold smoothing, the significance gate, or a dense-tail term) produces the failure the theory predicts on at least one stress variant. In sparse intersectional settings, SAFER achieves a better fairness-utility Pareto frontier than the baseline methods, and it preserves utility when certified unfairness is absent.

0.24

Practical Estimation of the Bayes Optimal Fairness-Accuracy Tradeoff with Soft Labels

cs.LG cs.AI ·2026-11-04 ·Mohit Sharma, Okan Koç, Amit Deshpande, Takashi Ishida, Gang Niu +2 more
publishedbenchmark similarity 0.59
Abstract · Accepted at Neurips 2026

There is a fundamental limit to the best prediction error of any model for a given data distribution. In classification, the Bayes error quantifies this limit and serves as both a benchmark for trained models and a criterion to detect overfitting. The state-of-the-art Bayes error estimation techniques for binary classification use only soft labels (positive class probabilities) and require no input features or auxiliary training. We extend such notions to constrained classification problems, such as fairness. Fair classification is an important case of constrained or multi-objective classification. It requires a model not only to be accurate but also to yield fair outcomes (equal or near-equal true positive rates) across different demographic groups (e.g., race and gender). This leads to an inherent fairness-accuracy tradeoff or a Pareto frontier that is used to compare fair classifiers against each other. The focus of our work is to estimate the fundamental limit for this fairness-accuracy tradeoff. We derive an explicit expression for the fair Bayes error rate (i.e., best achievable error rate subject to given fairness constraints), and construct consistent, instance-free estimators for it using only soft labels and group information. We provably bound the bias and the sample complexity of our estimators. Empirically, our method produces a robust, low-variance estimate of the optimal fairness-accuracy tradeoff curve, even when the soft labels are noisy and derived from a classification model on hard labels.

0.29