Search papers, labs, and topics across Lattice.
This paper addresses the challenge of achieving optimal sample complexity for multicalibration in deterministic predictors, a property crucial for trustworthy machine learning. The authors present a minimax-optimal algorithm that achieves the desired $\widetilde O(\varepsilon^{-3})$ sample complexity without the need for randomization, thus resolving a significant open question in the field. Additionally, they extend their approach to create deterministic omnipredictors and panpredictors, further enhancing the utility of their findings for various applications.
Deterministic predictors can now achieve optimal multicalibration sample complexity, challenging the long-held belief that randomization was necessary.
A model is multicalibrated on a collection of group weights $G$ if it is calibrated -- i.e. unbiased even conditional on its prediction -- not just overall, but also after reweighting contexts by each $g \in G$. It is a useful property for many downstream applications and is a basic desideratum of trustworthy machine learning. Before this work, all predictors known to attain the minimax-optimal $\widetilde O(\varepsilon^{-3})$ sample complexity rate for $\varepsilon$-multicalibration were randomized, while deterministic predictors were known only with substantially worse sample complexity. Whether randomization is necessary for optimal sample complexity in multicalibration was explicitly asked by [CLNR26] and implicitly in several prior works. We resolve this open problem by giving a minimax-optimal multicalibration algorithm that outputs a deterministic predictor. We then generalize the algorithm to produce optimal deterministic predictors that satisfy outcome indistinguishability (OI) with respect to finite or finitely covered collections of tests. As an application, this also gives deterministic omnipredictors and panpredictors with optimal sample complexity, resolving open problems posed by [OKK25] and [BHHLZ25].
