Sample-efficient Multiclass Calibration under $\ell_{p}$ Error

• URL: http://arxiv.org/abs/2509.23000v1
• Date: Fri, 26 Sep 2025 23:30:31 GMT
• Title: Sample-efficient Multiclass Calibration under $\ell_{p}$ Error
• Authors: Konstantina Bairaktari, Huy L. Nguyen,
• Abstract summary: Calibrating a multiclass predictor that outputs a distribution over labels is challenging due to the exponential number of possible prediction values.<n>In this work, we propose a new definition of error that interpolates between two established calibration error notions.<n>A key technical contribution is a novel application of data analysis with high adaptivity but only logarithmic overhead in the sample complexity.
• Score: 11.36431801454661
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Calibrating a multiclass predictor, that outputs a distribution over labels, is particularly challenging due to the exponential number of possible prediction values. In this work, we propose a new definition of calibration error that interpolates between two established calibration error notions, one with known exponential sample complexity and one with polynomial sample complexity for calibrating a given predictor. Our algorithm can calibrate any given predictor for the entire range of interpolation, except for one endpoint, using only a polynomial number of samples. At the other endpoint, we achieve nearly optimal dependence on the error parameter, improving upon previous work. A key technical contribution is a novel application of adaptive data analysis with high adaptivity but only logarithmic overhead in the sample complexity.

Related papers

• A Variational Estimator for $L_p$ Calibration Errors [44.81527473428586]
  We show how to extend a recent variational framework for estimating calibration errors beyond divergences induced by $_p$ divergences to cover a broad class calibration errors induced by $L_p$ divergences.
  arXiv  Detail & Related papers  (2026-02-27T17:56:52Z)
• Enforcing Calibration in Multi-Output Probabilistic Regression with Pre-rank Regularization [4.065502917666599]
  We introduce a general regularization framework to enforce multivariate calibration during training for arbitrary pre-rank functions.<n>We show that our methods significantly improve calibration across all pre-rank functions without sacrificing predictive accuracy.
  arXiv  Detail & Related papers  (2025-10-24T09:16:12Z)
• Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications [79.53938312089308]
  The MIDX-Sampler is a novel adaptive sampling strategy based on an inverted multi-index approach.<n>Our method is backed by rigorous theoretical analysis, addressing key concerns such as sampling bias, gradient bias, convergence rates, and generalization error bounds.
  arXiv  Detail & Related papers  (2025-01-15T04:09:21Z)
• Optimal Algorithms for Augmented Testing of Discrete Distributions [25.818433126197036]
  We show that a predictor can indeed reduce the number of samples required for all three property testing tasks.<n>A key advantage of our algorithms is their adaptability to the precision of the prediction.<n>We provide lower bounds to indicate that the improvements in sample complexity achieved by our algorithms are information-theoretically optimal.
  arXiv  Detail & Related papers  (2024-12-01T21:31:22Z)
• Semiparametric conformal prediction [79.6147286161434]
  We construct a conformal prediction set accounting for the joint correlation structure of the vector-valued non-conformity scores.<n>We flexibly estimate the joint cumulative distribution function (CDF) of the scores.<n>Our method yields desired coverage and competitive efficiency on a range of real-world regression problems.
  arXiv  Detail & Related papers  (2024-11-04T14:29:02Z)
• 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)
• On Computationally Efficient Multi-Class Calibration [9.032290717007065]
  Project calibration gives strong guarantees for all downstream decision makers. It ensures that the probabilities predicted by summing the probabilities assigned to labels in $T$ are close to some perfectly calibrated binary predictor.
  arXiv  Detail & Related papers  (2024-02-12T17:25:23Z)
• Distributed Estimation and Inference for Semi-parametric Binary Response Models [8.309294338998539]
  This paper studies the maximum score estimator of a semi-parametric binary choice model under a distributed computing environment. An intuitive divide-and-conquer estimator is computationally expensive and restricted by a non-regular constraint on the number of machines.
  arXiv  Detail & Related papers  (2022-10-15T23:06:46Z)
• 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)
• Prototypical Calibration for Few-shot Learning of Language Models [84.5759596754605]
  GPT-like models have been recognized as fragile across different hand-crafted templates, and demonstration permutations. We propose prototypical calibration to adaptively learn a more robust decision boundary for zero- and few-shot classification. Our method calibrates the decision boundary as expected, greatly improving the robustness of GPT to templates, permutations, and class imbalance.
  arXiv  Detail & Related papers  (2022-05-20T13:50:07Z)
• T-Cal: An optimal test for the calibration of predictive models [49.11538724574202]
  We consider detecting mis-calibration of predictive models using a finite validation dataset as a hypothesis testing problem. detecting mis-calibration is only possible when the conditional probabilities of the classes are sufficiently smooth functions of the predictions. We propose T-Cal, a minimax test for calibration based on a de-biased plug-in estimator of the $ell$-Expected Error (ECE)
  arXiv  Detail & Related papers  (2022-03-03T16:58:54Z)
• Information-Theoretic Generalization Bounds for Iterative Semi-Supervised Learning [81.1071978288003]
  In particular, we seek to understand the behaviour of the em generalization error of iterative SSL algorithms using information-theoretic principles. Our theoretical results suggest that when the class conditional variances are not too large, the upper bound on the generalization error decreases monotonically with the number of iterations, but quickly saturates.
  arXiv  Detail & Related papers  (2021-10-03T05:38:49Z)

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.