Research map / Learning theory and algorithms / Prediction and decision losses

The Minimax Rate of Second-Order Calibration

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Probabilistic calibration · 0 citations (OpenAlex)

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.

Shows that sech score perturbation makes second-order calibration functions analytic, enabling polynomial-regression estimation of second-order calibration error at O_h(log^{3/2} n / sqrt n) with a matching Omega(1/sqrt n) lower bound, and proposes second-order Platt scaling.

Problem

Estimating second-order calibration error (whether a predictor's epistemic-variance estimate matches conditional label variance on level sets) without regularization is impossible distribution-free; prior work relies on fixed bucketing partitions.

Approach

Use the bandwidth-h sech perturbation of classifier scores, which makes calibration functions analytic in a strip, so low-degree tensor polynomial regression on perturbed scores estimates the calibration error at near-parametric rate; the same regression supports post-hoc second-order Platt scaling.

Key results

• Polynomial estimator shows empirical log-log slope of about -0.70 at both bandwidths, steeper than bucketing (-0.33 to -0.55) and Nadaraya-Watson in Experiment 1.
• Recalibrated sigma^2 correlation with ground truth rises from 0.10 (raw) to 0.74 after second-order Platt; CE_2 drops from 0.37 to 0.04 +/- 0.01 in Experiment 2.
• On Weather Sentiment AMT at 5% audit budget, 2-D second-order Platt yields 46.4 disagreements per 100 audited items vs 30.9 for 2-D first-order Platt and about 26 for 1-D and raw baselines; oracle 49.8.

Surprising findings

• Raw sigma^2 is essentially uncorrelated with truth (Pearson 0.10), yet recalibration raises it to 0.74.
• Empirical slope of the polynomial estimator (~-0.70) is steeper than the theoretical -1/2 rate, which the authors note as a gap rather than a claim of improvement.

Limitations

• Log^{3/2} n factor versus Omega(1/sqrt n) lower bound leaves a logarithmic gap; unknown whether it is necessary.
• Guarantees apply to the sech-perturbed predictor, not the unperturbed one; unperturbed second-order calibration is not estimable distribution-free without structure.
• Experiments use ridge regression with clipping rather than the constrained ERM analyzed in theory; the analysis is for fixed bandwidth h.

Experimental setup

Datasets: Weather Sentiment AMT synthetic Gaussian mixture DGP

Benchmarks: Weather Sentiment AMT

Metrics: estimation error of CE_2 (log-log slope) second-order calibration error Pearson correlation of sigma^2 with ground truth realised gain / audit yield AUC lift

Baselines: 2D bucketing Nadaraya-Watson with Gaussian kernel 2D first-order Platt raw plug-in (m, sigma^2) 1D second-order Platt

Builds on: higher-order calibration smooth calibration error (SmoothECE) Platt scaling

Closest papers by meaning

• Optimal and Provable Calibration in High-Dimensional Binary Classification: Angular Calibration and Platt Scaling (NeurIPS 2025 · similarity 0.89)
• Provable Uncertainty Decomposition via Higher-Order Calibration (ICLR 2025 · similarity 0.88)
• Testing Calibration in Nearly-Linear Time (NeurIPS 2024 · similarity 0.87)
• Second-Order Uncertainty Quantification: A Distance-Based Approach (ICML 2024 · similarity 0.87)
• Truthful Calibration Errors for Multi-Class Prediction (NeurIPS 2026 · similarity 0.86)
• Generalized Venn and Venn-Abers Calibration with Applications in Conformal Prediction (ICML 2025 · similarity 0.86)