{"id":"arxiv/2611.03305","url":"https://arxiv.org/abs/2611.03305","tags":["cs.LG","cs.DS","math.ST"],"score":0,"title":"Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity","domain":"cs.LG","source":"arxiv","authors":["Jiuyao Lu","Georgy Noarov","Aaron Roth"],"reviews":0,"subject":"cs.LG","summary":"Calibrated multiaccuracy asks that a predictor be globally calibrated and multiaccurate with respect to a bounded test family $G$; that is, its residuals should be uncorrelated with every test $g(x)\\in G$. This weakening of multicalibration suffices for many applications. Its sample complexity was not known to improve on that of full multicalibration, which is $\\widetildeΘ\\left(\\frac{\\log|G|}{\\varepsilon^2} + \\frac{1}{\\varepsilon^{3}}\\right)$ when $|G|$ is at least a sufficiently large power of $\\log(1/\\varepsilon)$. We resolve the sample complexity of $\\varepsilon$-calibrated multiaccuracy,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-02","reactions":{}}