Research map / Learning theory and algorithms / Sample complexity
Testing Calibration in Nearly-Linear Time
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.
Defines calibration testing from samples under the lower distance to calibration and gives a nearly-linear-time (O(n log^2 n)) exact DP/min-cost-flow solver for empirical smooth calibration, plus faster tolerant testers and sample-complexity lower bounds for other calibration measures.
Problem
Testing whether a binary prediction distribution is perfectly calibrated versus epsilon-far from calibration from n samples, where existing black-box LP solvers need Omega(n^omega) time.
Approach
Reformulate the empirical smooth calibration LP as a min-cost flow on a star-plus-path graph, solve it exactly with a dynamic program over piecewise-linear convex functions using a segment tree with lazy add/set operations; for tolerant testing of LDTC, use an augmented-Lagrangian/rounding approach.
Key results
- Exact empirical smooth calibration solver runs in O(n log^2 n), improving on Omega(n^omega) black-box LP solvers, and yields an O(n log^2 n) calibration tester.
- Tolerant LDTC tester runs in O(n^2 log n) time (improving state-of-the-art LP approaches requiring Omega(n^2.5)), and smooth-calibration tolerant tester works for eps1 > 4 eps2.
- Binned ECE variants and convolved ECE / interval CE require about eps^{-2.5} samples for calibration testing (lower bounds), showing LDTC-based testing is statistically better.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reformulate empirical smooth calibration as minimum-cost flow and solve it with dynamic programming | Empirical smooth calibration · Empirical smooth calibration | runtime: \Omega(n^\omega) -> O(n\log^2(n)) | Helped |
| Use a custom direct LDTC approximation algorithm | Tolerant calibration testing · Tolerant calibration testing | runtime: \Omega(n^{2.5}) -> O(\frac{n\log(n)}{(\varepsilon_1 - \varepsilon_2)^2}) = O(n^2\log(n)) | Helped |
Surprising findings
- Binned ECE-style calibration measures need substantially more samples than LDTC-based testing, a statistical disadvantage.
Limitations
- Tolerant smooth-calibration tester loses a constant factor (requires eps1 > 4 eps2), and this loss is inherent to the approach.
- The LDTC tolerant tester runs in O(n^2 log n) for the stated parameters, slower than the smooth calibration solver.
- Analysis is restricted to binary classification (k=2).
Experimental setup
Datasets: synthetic Bernoulli data postprocessed neural network predictions
Metrics: runtime tester reliability
Baselines: CVXPY linear program solver Gurobi min-cost flow solver binned ECE variants convolved ECE estimator interval calibration error estimator
Builds on: Blasiok et al 2023 distance to calibration framework smooth calibration error lower distance to calibration
Closest papers by meaning
- Reassessing How to Compare and Improve the Calibration of Machine Learning Models (ICLR 2025 · similarity 0.90)
- Calibration without labels in multiple testing (NeurIPS 2026 · similarity 0.88)
- Algorithms with Calibrated Machine Learning Predictions (ICML 2025 · similarity 0.88)
- Combining Priors with Experience: Confidence Calibration Based on Binomial Process Modeling (AAAI 2025 · similarity 0.87)
- The Minimax Rate of Second-Order Calibration (NeurIPS 2026 · similarity 0.87)
- A Benchmark Study on Calibration (ICLR 2024 · similarity 0.87)
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.