Abstract

A sequence of predictions is calibrated if and only if it induces no swap regret to all down-stream decision tasks. We study the Maximum Swap Regret (MSR) of predictions for binary events: the swap regret maximized over all downstream tasks with bounded payoffs. Previously, the best online prediction algorithm for minimizing MSR is obtained by minimizing the K1 calibration error, which upper bounds MSR up to a constant factor. However, recent work (Qiao and Valiant, 2021) gives an Ω(T0.528) lower bound for the worst-case expected K1 calibration error incurred by any randomized algorithm in T rounds, presenting a barrier to achieving better rates for MSR. Several relaxations of MSR have been considered to overcome this barrier, via external regret (Kleinberg et al., 2023) and regret bounds depending polynomially on the number of actions in downstream tasks (Noarov et al., 2023; Roth and Shi, 2024). We show that the barrier can be surpassed without any relaxations: we give an efficient randomized prediction algorithm that guarantees O(T√logT) expected MSR. We also discuss the economic utility of calibration by viewing MSR as a decision-theoretic calibration error metric and study its relationship to existing metrics.

Biography

Yifan Wu is a fourth year PhD student at Northwestern University, advised by Prof. Jason Hartline. She received my B.S. in Computer Science from Peking University in 2020, where she worked with Prof. Yuqing Kong.

Yifan has a broad interest in theoretical computer science and economics. Currently, she works on data economics, and specifically on algorithmic acquisition and evaluation of information, under a statistical decision theory framework.