The Minimax Rate of Second-Order Calibration

• URL: http://arxiv.org/abs/2605.07808v1
• Date: Fri, 08 May 2026 14:41:56 GMT
• Title: The Minimax Rate of Second-Order Calibration
• Abstract summary: We characterize the minimax rate of estimating the second-order calibration error for binary classification.<n>As a corollary, we give the first finite-sample guarantee for second-order Platt scaling.
• Score: 8.791341107339637
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We characterize the minimax rate of estimating the second-order calibration error for binary classification, which quantifies whether a higher-order predictor's epistemic-uncertainty estimate matches the conditional variance of the label probability on its level sets. Our key observation is that the sech perturbation kernel, previously used only to enforce smoothness of calibration functions, in fact makes them analytic in a strip of half-width $hπ/2$. Polynomial regression then estimates the calibration error at rate $\tilde{O}(1/\sqrt{n})$, with explicit constants, a qualitative improvement over the $O(n^{-1/4})$ rate achievable by bucketing or kernel smoothing. A matching $Ω(1/\sqrt{n})$ lower bound establishes minimax optimality up to logarithmic factors. As a corollary, we give the first finite-sample guarantee for second-order Platt scaling, yielding a post-hoc procedure that recalibrates both the mean prediction and the epistemic-variance estimate of any higher-order predictor. Along the way, we provide a bucket-free definition of second-order calibration and relate it quantitatively to the bucketed formulation of Ahdritz et al. [2025]. Our experiments confirm the predicted rate and the quality of the recalibrated uncertainties.

Related papers

• An analysis of binary isotonic regression: degrees of freedom and implications for calibration [11.823728812515839]
  We identify the binary sequences that maximize the number of distinct fitted values produced by isotonic regression.<n>We develop a sharp bound on the degrees of freedom with a leading term of $frac3(42) 1/3 n2/3$ using analytic number theory.<n>We derive the first non-trivial distribution-free guarantee on the Expected Error (ECE) of isotonic regression.
  arXiv  Detail & Related papers  (2026-07-29T16:53:12Z)
• Optimal Recalibration of an Online Predictor [17.79426749489757]
  We study the problem of recalibrating an online predictor [KE17, OKS24]: given an arbitrary "hint" sequence of forecasts, the learner must output new predictions that are calibrated while incurring small excess error relative to the original forecasts, under a proper loss.<n>We give an online algorithm that achieves $(varepsilon calibrated varepsilon2)$-recalibration for Lipschitz proper losses in $T approx varepsilon-3$ rounds.<n>We show that this tradeoff is optimal by proving a matching lower bound for recalibrating against the squared
  arXiv  Detail & Related papers  (2026-07-22T02:36:03Z)
• The Calibration Channel Determines the Bayes-Error Proxy: An Exact Law for Temperature-Induced Distortion [0.0]
  Bayes-error estimator beta(z) = E[min(z, 1-z)] of Ishida et al. estimates the irreducible error of a binary task directly from probability-valued labels.<n>Recent work by Ushio et al. showed that this estimator is fragile when the probabilities are not the true posterior.<n>We characterize exactly how the most widely used post-hoc calibration map -- temperature scaling -- distorts the proxy.
  arXiv  Detail & Related papers  (2026-07-20T17:07:26Z)
• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  We investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner.<n>The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm.<n>We establish an information-theoretic lower bound that scales as $(sqrtmathbbE[S_T])$, providing a fundamental characterization of the best achievable prediction-adaptive regret.
  arXiv  Detail & Related papers  (2026-05-21T08:57:38Z)
• Tail allocation for conformal prediction intervals [1.0163716169047106]
  We study split-conformal prediction for regression when the reported prediction set must be a single interval, at target marginal coverage $1-$, where $$ is the nominal miscoverage level.<n>Under this reporting constraint, the natural conditional target is the shortest interval with conditional mass at least $1-$, rather than an equal-tailed interval or a possibly disconnected high-probability set.<n>We parameterize this single-interval by a lower-tail allocation, which determines how the nominal miscoverage $$ is split between the two endpoints.
  arXiv  Detail & Related papers  (2026-04-28T04:14:27Z)
• Refining Covariance Matrix Estimation in Stochastic Gradient Descent Through Bias Reduction [9.294518380204154]
  We study online inference and covariance estimation for the gradient descent (SGD) algorithm.<n>Our method employs a bias-reduction technique to achieve a convergence rate of $n(-1)/2 sqrtlog n$, outperforming existing Hessian-free alternatives.
  arXiv  Detail & Related papers  (2026-04-23T01:48:08Z)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  Self-distillation (SD) is the process of retraining a student on a mixture of ground-truth and the teacher's own predictions.<n>We show that for any prediction risk, the optimally mixed student improves upon the ridge teacher for every regularization level.<n>We propose a consistent one-shot tuning method to estimate $star$ without grid search, sample splitting, or refitting.
  arXiv  Detail & Related papers  (2026-02-19T17:21:15Z)
• Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noise [17.899443444882888]
  We develop a worst-case complexity theory for inequalityally preconditioned gradient descent (SPSGD)<n>We demonstrate that normalization guarantees convergence to a first-order stationary point at rate $mathcalO(T-fracp-13p-2)$ when problem parameters are known, and $mathcalO(T-fracp-12p)$ when problem parameters are unknown.<n>In contrast, we prove that clipping may fail to converge in the worst case due to the statistical dependence between the preconditioner and the gradient estimates.
  arXiv  Detail & Related papers  (2026-02-13T19:29:17Z)
• Orthogonal Causal Calibration [55.28164682911196]
  We develop general algorithms for reducing the task of causal calibration to that of calibrating a standard (non-causal) predictive model.<n>Our results are exceedingly general, showing that essentially any existing calibration algorithm can be used in causal settings.
  arXiv  Detail & Related papers  (2024-06-04T03:35:25Z)
• Minimum-Risk Recalibration of Classifiers [9.31067660373791]
  We introduce the concept of minimum-risk recalibration within the framework of mean-squared-error decomposition. We show that transferring a calibrated classifier requires significantly fewer target samples compared to recalibrating from scratch.
  arXiv  Detail & Related papers  (2023-05-18T11:27:02Z)
• Minimax Instrumental Variable Regression and $L_2$ Convergence Guarantees without Identification or Closedness [71.42652863687117]
  We study nonparametric estimation of instrumental variable (IV) regressions. We propose a new penalized minimax estimator that can converge to a fixed IV solution. We derive a strong $L$ error rate for our estimator under lax conditions.
  arXiv  Detail & Related papers  (2023-02-10T18:08:49Z)
• A Consistent and Differentiable Lp Canonical Calibration Error Estimator [21.67616079217758]
  Deep neural networks are poorly calibrated and tend to output overconfident predictions. We propose a low-bias, trainable calibration error estimator based on Dirichlet kernel density estimates. Our method has a natural choice of kernel, and can be used to generate consistent estimates of other quantities.
  arXiv  Detail & Related papers  (2022-10-13T15:11:11Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  We consider non- Hilbert optimization using first-order algorithms for which the gradient estimates may have tails. We show that a combination of gradient, momentum, and normalized gradient descent convergence to critical points in high-probability with best-known iteration for smooth losses.
  arXiv  Detail & Related papers  (2021-06-28T00:17:01Z)
• Calibration of Neural Networks using Splines [51.42640515410253]
  Measuring calibration error amounts to comparing two empirical distributions. We introduce a binning-free calibration measure inspired by the classical Kolmogorov-Smirnov (KS) statistical test. Our method consistently outperforms existing methods on KS error as well as other commonly used calibration measures.
  arXiv  Detail & Related papers  (2020-06-23T07:18:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.