Cover Image

Computational and Statistical Hardness of Calibration Distance

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Qiao, Mingda
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Distance from Calibration in Sequential Prediction
by: Qiao, Mingda, et al.
Published: (2024)

Truthfulness of Calibration Measures
by: Haghtalab, Nika, et al.
Published: (2024)

Online Prediction with Limited Selectivity
by: Liu, Licheng, et al.
Published: (2025)

Limitations of Membership Queries in Testable Learning
by: Lange, Jane, et al.
Published: (2025)

Collaborative Learning with Different Labeling Functions
by: Deng, Yuyang, et al.
Published: (2024)

Sample-Adaptivity Tradeoff in On-Demand Sampling
by: Haghtalab, Nika, et al.
Published: (2025)

An Elementary Predictor Obtaining $2\sqrt{T}+1$ Distance to Calibration
by: Arunachaleswaran, Eshwar Ram, et al.
Published: (2024)

Statistical-Computational Trade-offs for Density Estimation
by: Aamand, Anders, et al.
Published: (2024)

New Statistical and Computational Results for Learning Junta Distributions
by: Beretta, Lorenzo
Published: (2025)

Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification
by: Rohatgi, Dhruv, et al.
Published: (2025)

On Computing Total Variation Distance Between Mixtures of Product Distributions
by: Feng, Weiming, et al.
Published: (2026)

Improved Approximations for Hard Graph Problems using Predictions
by: Aamand, Anders, et al.
Published: (2025)

The Importance of Being Smoothly Calibrated
by: Gopalan, Parikshit, et al.
Published: (2026)

Efficient Calibration for Decision Making
by: Gopalan, Parikshit, et al.
Published: (2025)

Calibration Error for Decision Making
by: Hu, Lunjia, et al.
Published: (2024)

Smooth Calibration and Decision Making
by: Hartline, Jason, et al.
Published: (2025)

Optimal $k$-Secretary with Logarithmic Memory
by: Qiao, Mingda, et al.
Published: (2025)

A Perfectly Truthful Calibration Measure
by: Hartline, Jason, et al.
Published: (2025)

Algorithms with Calibrated Machine Learning Predictions
by: Shen, Judy Hanwen, et al.
Published: (2025)

Breaking the $T^{2/3}$ Barrier for Sequential Calibration
by: Dagan, Yuval, et al.
Published: (2024)

Truthful Calibration Errors for Multi-Class Prediction
by: Lu, Yuxuan, et al.
Published: (2025)

Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample
by: Chauhan, Rohan, et al.
Published: (2025)

Interpreting the Curse of Dimensionality from Distance Concentration and Manifold Effect
by: Peng, Dehua, et al.
Published: (2023)

Sample-efficient Multiclass Calibration under $\ell_{p}$ Error
by: Bairaktari, Konstantina, et al.
Published: (2025)

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
by: Beretta, Lorenzo, et al.
Published: (2025)

Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)

No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting
by: Oki, Taihei, et al.
Published: (2024)

Statistical Query Lower Bounds for Smoothed Agnostic Learning
by: Diakonikolas, Ilias, et al.
Published: (2026)

On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries
by: Joshi, Nirmit, et al.
Published: (2024)

Testing Calibration in Nearly-Linear Time
by: Hu, Lunjia, et al.
Published: (2024)

SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
by: Diakonikolas, Ilias, et al.
Published: (2024)

On Computing Optimal Tree Ensembles
by: Komusiewicz, Christian, et al.
Published: (2023)

Approximating the Total Variation Distance between Gaussians
by: Bhattacharyya, Arnab, et al.
Published: (2025)

Private Synthetic Graph Generation and Fused Gromov-Wasserstein Distance
by: Wirth, Leoni Carla, et al.
Published: (2025)

Breaking Hard Isomorphism Benchmarks with DRESS
by: Velilla, Eduar Castrillo
Published: (2026)

Hardness of High-Dimensional Linear Classification
by: Munteanu, Alexander, et al.
Published: (2026)

Tokenisation over Bounded Alphabets is Hard
by: Kastreva, Violeta, et al.
Published: (2025)

Hardness of Maximum Likelihood Learning of DPPs
by: Grigorescu, Elena, et al.
Published: (2022)

A Statistical View of Column Subset Selection
by: Sood, Anav, et al.
Published: (2023)

On the Hardness of Approximation of the Fair k-Center Problem
by: Thejaswi, Suhas
Published: (2026)