Cover Image

Optimal Lower Bounds for Online Multicalibration

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Collina, Natalie, Lu, Jiuyao, Noarov, Georgy, Roth, Aaron
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Statistics Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Sample Complexity of Multicalibration
by: Collina, Natalie, et al.
Published: (2026)

Stronger Neyman Regret Guarantees for Adaptive Experimental Design
by: Noarov, Georgy, et al.
Published: (2025)

Dynamic Regret Bounds for Online Omniprediction with Long Term Constraints
by: Bechavod, Yahav, et al.
Published: (2025)

Online Omniprediction with Long-Term Constraints
by: Bechavod, Yahav, et al.
Published: (2025)

Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms
by: Réveillard, William, et al.
Published: (2025)

Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses
by: Lu, Jiuyao, et al.
Published: (2025)

Foundations of Top-$k$ Decoding For Language Models
by: Noarov, Georgy, et al.
Published: (2025)

Adversarial Surrogate Risk Bounds for Binary Classification
by: Frank, Natalie S.
Published: (2025)

Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions
by: Zhang, Kaihong, et al.
Published: (2024)

On the Natural Gradient of the Evidence Lower Bound
by: Ay, Nihat, et al.
Published: (2023)

Repeated Contracting with Multiple Non-Myopic Agents: Policy Regret and Limited Liability
by: Collina, Natalie, et al.
Published: (2024)

Lower Bounds on the Size of Markov Equivalence Classes
by: Jahn, Erik, et al.
Published: (2025)

Instance-Adaptive Online Multicalibration
by: Huang, Zhiming, et al.
Published: (2026)

Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning
by: Cai, T. Tony, et al.
Published: (2023)

On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds
by: Agrawal, Shubhada, et al.
Published: (2025)

A Gapped Scale-Sensitive Dimension and Lower Bounds for Offset Rademacher Complexity
by: Jia, Zeyu, et al.
Published: (2025)

General Lower Bounds for Differentially Private Federated Learning with Arbitrary Public-Transcript Interactions
by: Li, Yicheng
Published: (2026)

Optimal Bounds for Tyler's M-Estimator for Elliptical Distributions
by: Lau, Lap Chi, et al.
Published: (2025)

Learning Upper Lower Value Envelopes to Shape Online RL: A Principled Approach
by: Reboul, Sebastian, et al.
Published: (2025)

An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
by: Chen, Siyu, et al.
Published: (2025)

Tractable Agreement Protocols
by: Collina, Natalie, et al.
Published: (2024)

Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability
by: Chen, Fan, et al.
Published: (2024)

Poisson Midpoint Method for Log Concave Sampling: Beyond the Strong Error Lower Bounds
by: Srinivasan, Rishikesh, et al.
Published: (2025)

Assessing the Quality of Denoising Diffusion Models in Wasserstein Distance: Noisy Score and Optimal Bounds
by: Arsenyan, Vahan, et al.
Published: (2025)

Optimal Excess Risk Bounds for Empirical Risk Minimization on $p$-Norm Linear Regression
by: Hanchi, Ayoub El, et al.
Published: (2023)

Sharp Structure-Agnostic Lower Bounds for General Linear Functional Estimation
by: Jin, Jikai, et al.
Published: (2025)

MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound
by: Pham, Phu-Hoa, et al.
Published: (2026)

Stability Bounds for Smooth Optimal Transport Maps and their Statistical Implications
by: Balakrishnan, Sivaraman, et al.
Published: (2025)

Statistical Query Lower Bounds for Learning Truncated Gaussians
by: Diakonikolas, Ilias, et al.
Published: (2024)

A Notion of Uniqueness for the Adversarial Bayes Classifier
by: Frank, Natalie S.
Published: (2024)

Adversarial Consistency and the Uniqueness of the Adversarial Bayes Classifier
by: Frank, Natalie S.
Published: (2024)

PTF Testing Lower Bounds for Non-Gaussian Component Analysis
by: Diakonikolas, Ilias, et al.
Published: (2025)

Emergent Alignment via Competition
by: Collina, Natalie, et al.
Published: (2025)

Doubly Robust Interval Estimation for Optimal Policy Evaluation in Online Learning
by: Shen, Ye, et al.
Published: (2021)

Minimax Optimal Fair Classification with Bounded Demographic Disparity
by: Zeng, Xianli, et al.
Published: (2024)

Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression
by: Ni, Yijin, et al.
Published: (2026)

SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions
by: Diakonikolas, Ilias, et al.
Published: (2024)

Adaptive Estimation of Multivariate Piecewise Polynomials and Bounded Variation Functions by Optimal Decision Trees
by: Chatterjee, Sabyasachi, et al.
Published: (2019)

Differential privacy with dependent data
by: Roth, Valentin, et al.
Published: (2025)

Query Lower Bounds for Diffusion Sampling
by: Xun, Zhiyang, et al.
Published: (2026)