We updated our paper --- and solved the open problem highlighted in the old version. Now our lower bound construction has only polylog(1/eps) many groups instead of poly(1/eps) many groups. The construction is also simplified.
Aaron Roth
Excited about a new paper! Multicalibration turns out to be strictly harder than marginal calibration. We prove tight Omega(T^{2/3}) lower bounds for online multicalibration, separating it from online marginal calibration for which better rates were recently discovered.
