Cover Image

Breaking the $T^{2/3}$ Barrier for Sequential Calibration

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dagan, Yuval, Daskalakis, Constantinos, Fishelson, Maxwell, Golowich, Noah, Kleinberg, Robert, Okoroafor, Princewill
Format:	Preprint
Published:	2024
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Near-Optimal Algorithms for Omniprediction
by: Okoroafor, Princewill, et al.
Published: (2025)

High-Dimensional Calibration from Swap Regret
by: Fishelson, Maxwell, et al.
Published: (2025)

Smooth Nash Equilibria: Algorithms and Complexity
by: Daskalakis, Constantinos, et al.
Published: (2023)

From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces
by: Dagan, Yuval, et al.
Published: (2023)

Fixed Point Computation: Beating Brute Force with Smoothed Analysis
by: Attias, Idan, et al.
Published: (2025)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
by: Gopalan, Parikshit, et al.
Published: (2024)

Provably Learning from Modern Language Models via Low Logit Rank
by: Golowich, Noah, et al.
Published: (2025)

High-accuracy log-concave sampling with stochastic queries
by: Chen, Fan, et al.
Published: (2026)

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

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
by: Golowich, Noah, et al.
Published: (2024)

Mistake-Bounded Language Generation
by: Kleinberg, Jon, et al.
Published: (2026)

Full Swap Regret and Discretized Calibration
by: Fishelson, Maxwell, et al.
Published: (2025)

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

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

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

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

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

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

Distribution-Free Sequential Prediction with Abstentions
by: Yu, Jialin, et al.
Published: (2026)

Adversarial Resilience in Sequential Prediction via Abstention
by: Goel, Surbhi, et al.
Published: (2023)

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

Computational and Statistical Hardness of Calibration Distance
by: Qiao, Mingda
Published: (2026)

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

On Learning Parities with Dependent Noise
by: Golowich, Noah, et al.
Published: (2024)

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

Language Generation in the Limit
by: Kleinberg, Jon, et al.
Published: (2024)

Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations
by: Kleinberg, Jon, et al.
Published: (2025)

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

Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics
by: Gaitonde, Jason, et al.
Published: (2024)

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

Water-Filling is Universally Minimax Optimal
by: Banerjee, Siddhartha, et al.
Published: (2026)

Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk
by: Gu, Yuzhou, et al.
Published: (2024)

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

Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems
by: Puchkin, Nikita, et al.
Published: (2023)

Bin Packing under Random-Order: Breaking the Barrier of 3/2
by: Hebbar, Anish, et al.
Published: (2024)

Improving Pinwheel Density Bounds for Small Minimums
by: Mishra, Ahan, et al.
Published: (2025)

The Conflict Graph Design: Estimating Causal Effects under Arbitrary Neighborhood Interference
by: Kandiros, Vardis, et al.
Published: (2024)

On Language Generation in the Limit with Bounded Memory
by: Kleinberg, Jon, et al.
Published: (2026)

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

Sinkhorn Algorithm for Sequentially Composed Optimal Transports
by: Watanabe, Kazuki, et al.
Published: (2024)