# The PAV algorithm optimizes binary proper scoring rules

arXiv: https://arxiv.org/abs/1304.2331 · HTML: https://mlsanity.com/paper/1304.2331/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Apr 2013.

## Built on by (most cited first, 8 of 8)

- [A Speaker Verification Backend with Robust Performance across Conditions](https://mlsanity.com/paper/2102.01760/) (2021)
- [Omnipredicting Single-Index Models with Multi-Index Models](https://mlsanity.com/paper/2411.13083/) (2024)
- [Efficient Calibration for Decision Making](https://mlsanity.com/paper/2511.13699/) (2025)
- [Improving Multi-Class Calibration through Normalization-Aware Isotonic Techniques](https://mlsanity.com/paper/2512.09054/) (2025)
- [Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction](https://mlsanity.com/paper/2602.17577/) (2026)
- [Visualizing Classifier Adjacency Relations: A Case Study in Speaker Verification and Voice Anti-Spoofing](https://mlsanity.com/paper/2106.06362/) (2021)
- [The distribution of calibrated likelihood functions on the probability-likelihood Aitchison simplex](https://mlsanity.com/paper/2509.03365/) (2025)
- [PS-PPO: Prefix-Sampling PPO for Critic-Free RLHF](https://mlsanity.com/paper/2606.29758/) (2026)

## Abstract (arXiv)

There has been much recent interest in application of the pool-adjacent-violators (PAV) algorithm for the purpose of calibrating the probabilistic outputs of automatic pattern recognition and machine learning algorithms. Special cost functions, known as proper scoring rules form natural objective functions to judge the goodness of such calibration. We show that for binary pattern classifiers, the non-parametric optimization of calibration, subject to a monotonicity constraint, can be solved by PAV and that this solution is optimal for all regular binary proper scoring rules. This extends previous results which were limited to convex binary proper scoring rules. We further show that this result holds not only for calibration of probabilities, but also for calibration of log-likelihood-ratios, in which case optimality holds independently of the prior probabilities of the pattern classes.