6 papers · 1 filter
Sample Complexity of Multicalibration for Multilevel Properties
Jiuyao Lu, Krishnakumar Balasubramanian, Aleksandr Podkopaev +1
Calibration requires a predictor to be unbiased after conditioning on its own predictions. Multicalibration asks for this guarantee simultaneously across a collection of groups. Ma…
The Sample Complexity of Multicalibration
Natalie Collina, Jiuyao Lu, Georgy Noarov +1
We study the minimax sample complexity of multicalibration in the batch setting. A learner observes i.i.d. samples from an unknown distribution and must output a (possibly rand…
Optimal Lower Bounds for Online Multicalibration
Natalie Collina, Jiuyao Lu, Georgy Noarov +1
We prove tight lower bounds for online multicalibration, establishing an information-theoretic separation from marginal calibration. In the general setting where group functions ca…
Dynamic Regret Bounds for Online Omniprediction with Long Term Constraints
Yahav Bechavod, Jiuyao Lu, Aaron Roth
We present an algorithm guaranteeing dynamic regret bounds for online omniprediction with long term constraints. The goal in this recently introduced problem is for a learner to ge…
Online Omniprediction with Long-Term Constraints
Yahav Bechavod, Jiuyao Lu, Aaron Roth
We introduce and study the problem of online omniprediction with long-term constraints. At each round, a forecaster is tasked with generating predictions for an underlying (adaptiv…
Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses
Jiuyao Lu, Aaron Roth, Mirah Shi
We define "decision swap regret" which generalizes both prediction for downstream swap regret and omniprediction, and give algorithms for obtaining it for arbitrary multi-dimension…