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 widetildeO(T-1/3) and widetildeO(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 (mathttOLPO). To obtain the improved rate of widetildeO(T-1/3), we introduce a linearization of mathttOLPO 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 is 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 mathttOLPO that makes only a polynomial number of calls to an offline optimization (multicalibration evaluation) oracle, resulting in oracle-efficient online (ℓ1)-multicalibration with a rate of widetildeO(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).