Optimal Deterministic Multicalibration and Omniprediction

2026-06-19 · Source: stat.ML updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences · Depth: Expert, extended

Summary

A new algorithm resolves a long-standing open problem in trustworthy machine learning by achieving minimax-optimal sample complexity for deterministic multicalibrated and omnipredicting models. Previously, only randomized predictors could attain the \u00d5(\u03b5⁻³) sample complexity rate for \u03b5-multicalibration, while deterministic methods were substantially worse, often \u00d5(\u03b5⁻⁶). This work presents an algorithm that outputs a deterministic predictor with \u00d5(\u03b5⁻³) sample complexity for multicalibration. It generalizes to produce deterministic predictors satisfying outcome indistinguishability with \u00d5(log|\u2130|/\u03b5²) samples and optimal deterministic omnipredictors and panpredictors with \u00d5((p+log(1/\u03b5))/\u03b5²) samples. The approach uses a three-part sample split for confidence intervals, online learning, and finite rounding cells, smoothly integrating statistical information to overcome limitations of prior derandomization attempts.

Key takeaway

For AI scientists designing trustworthy machine learning systems, you can now achieve optimal sample efficiency with deterministic multicalibrated and omnipredicting models. This eliminates the need for prediction-time randomness, simplifying auditing and improving reproducibility for your models. You should prioritize implementing these deterministic approaches to enhance model transparency and ensure consistent outcomes across diverse contexts and subgroups.

Key insights

Deterministic predictors can achieve minimax-optimal sample complexity for multicalibration and omniprediction, resolving a key open problem.

Principles

• Multicalibration ensures unbiased predictions across diverse groups.
• Prediction-time randomness complicates auditing and reproducibility.
• Optimal sample complexity for multicalibration is \u00d5(\u03b5⁻³).

Method

The algorithm splits samples into confidence, online-learning, and partition sets. It uses interval hints and an online-to-batch reduction, then rounds the randomized predictor using one sampler seed per cell.

In practice

• Implement deterministic multicalibrated models for auditing.
• Apply to omniprediction for diverse loss functions.
• Use for panprediction across subgroups.

Topics

• Multicalibration
• Omniprediction
• Deterministic Predictors
• Sample Complexity
• Outcome Indistinguishability
• Trustworthy AI

Best for: Research Scientist, AI Scientist

Related on AIssential

• Towards Provably Fair Machine Learning: Bayesian Approaches For Consistent and Transparent Predictions — The Fair Bayesian classifier ensures consistent, fair predictions across all subgroups by enforcing determinism and statistical consistency with principled abstention.
• Differential Privacy of Gaussian Process Posterior Sampling — Intrinsic randomness in GP posterior sampling provides differential privacy, critically dependent on effective ridge regularization.
• Consistency Training while Mitigating Obfuscation via Rate Matching — RMCT improves LLM behavioral robustness by matching target behavior rates across inputs, mitigating obfuscation without sacrificing monitorability.
• Identifying Information from Observations with Uncertainty and Novelty — Identification and sample complexity are unified across computational, statistical, and PAC-Bayes learning frameworks.
• Hot but correct take - deterministic processes will ALWAYS beat AI/neural networks — Deterministic decision trees offer theoretical optimal play for full-information, non-stochastic games but are computationally intractable for real-world complexity.
• Tight prediction sets under miscalibration — the regularised and sorted refinements of adaptive prediction sets — Regularized and sorted refinements improve adaptive prediction sets by addressing miscalibration and tightening set sizes.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.