Georgy Noarov, Aaron Roth
A deterministic multicalibration algorithm achieving minimax-optimal sample complexity is presented, with extensions to outcome indistinguishability and omniprediction.
Multicalibration is a fundamental property for trustworthy predictions, but all prior predictors achieving minimax-optimal sample complexity were randomized. Deterministic predictors had substantially worse sample complexity, and it was an open question whether randomization is necessary.
The authors design a deterministic multicalibration algorithm that achieves the minimax-optimal sample complexity of O~(ε^{-3}). They generalize it to outcome indistinguishability for finite or finitely covered collections of tests, and extend to deterministic omnipredictors and panpredictors.
They resolve the open problem by showing that deterministic predictors can achieve optimal sample complexity. They also achieve optimal sample complexity for deterministic omnipredictors and panpredictors, solving problems posed by [OKK25] and [BHHLZ25].