The Sample Complexity of Multicalibration with an ERM Oracle
The paper analyzes how many samples are needed to learn a predictor that exhibits multicalibration when only allowed to use an Empirical Risk Minimization (ERM) oracle. It establishes sample complexity bounds, showing that learning swap multicalibration requires $\Theta(d/\epsilon^3)$ samples and contrasts this with the difficulty of estimating calibration errors.