Improved and Oracle-Efficient Online ℓ1-Multicalibration

We study online multicalibration, a framework for ensuring calibrated predictions across multiple groups in adversarial settings, across T rounds. Although online calibration is typically studied in the ℓ 1 norm, prior approaches to online multicalibration have taken the indirect approach of obtaining rates in other norms (such as ℓ 2 and ℓ ∞ ) and then transferred these guarantees to ℓ 1 at additional loss. In contrast, we propose a direct method that achieves improved and oracle-efficient rates of O(T -1/3 ) and O(T -1/4 ) respectively, for online ℓ 1 -multicalibration. Our key insight is a novel reduction of online ℓ 1 -multicalibration to an online learning problem with product-based rewards, which we refer to as online linear-product optimization (OLPO). To obtain the improved rate of O(T -1/3 ), we introduce a linearization of OLPO and design a no-regret algorithm for this linearized problem. Although this method guarantees the desired sublinear rate (nearly matching the best rate for online calibration), it becomes computationally expensive when the group family H is large or infinite, since it enumerates all possible groups. To address scalability, we propose a second approach to OLPO that makes only a polynomial number of calls to an offline optimization (multicalibration evaluation) oracle, resulting in oracleefficient online ℓ 1 -multicalibration with a rate of O(T -1/4 ). Our framework also extends to certain infinite families of groups (e.g., all linear functions on the context space) by exploiting a 1-Lipschitz property of the ℓ 1 -multicalibration error with respect to H.