Toward Simultaneously Optimal Regret in U-Calibration

arXiv:2606.18527 · stat.ML, cs.LG · Submitted 2026-06-16 · Read on arXiv

Rafael Frongillo, Haipeng Luo, Nishant A. Mehta, Jon Schneider

stat.ML, cs.LG

Submitted: 2026-06-16

Comments: 30 pages; to appear at COLT 2026

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Regret — 90× in this paper · explained in 4 episodes
• Calibration — 21× in this paper · explained in 9 episodes
• Loss Function — 17× in this paper · explained in 2 episodes
• Papers — 4× in this paper · explained in 3 episodes
• Regret Bound — 4× in this paper · explained in 2 episodes
• Adam — 2× in this paper · explained in 3 episodes
• Parameterization — 2× in this paper · explained in 2 episodes
• Regret Bounds — 2× in this paper · explained in 2 episodes
• Regret Guarantees — 2× in this paper · explained in 2 episodes
• Editor — 1× in this paper · explained in 2 episodes
• FTPL and Be-the-Perturbed-Leader — 1× in this paper
• Then the Total Variation — 1× in this paper
• Total Variation (TV) distance — 1× in this paper · explained in 2 episodes

Sources

• Online Omniprediction with Long-Term Constraints
• Calibration Error for Decision Making
• Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses
• Simultaneous Swap Regret Minimization via KL-Calibration
• Near-Optimal Algorithms for Omniprediction

Related papers

• Behavior of prediction performance metrics with rare events
• Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
• A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
• Scalable Posterior Uncertainty for Flexible Density-Based Clustering
• A Transport Geometry of Benign Overfitting
• Efficient quadratic entropy with distance sketches