Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction

arXiv:2602.17577v1 Announce Type: cross
Abstract: Omniprediction is a learning problem that requires suboptimality bounds for each of a family of losses $mathcal{L}$ against a family of comparator predictors $mathcal{C}$. We initiate the study of omniprediction in a multiclass setting, where the comparator family $mathcal{C}$ may be infinite. Our main result is an extension of the recent binary omniprediction algorithm of [OKK25] to the multiclass setting, with sample complexity (in statistical settings) or regret horizon (in online settings) $approx varepsilon^{-(k+1)}$, for $varepsilon$-omniprediction in a $k$-class prediction problem. En route to proving this result, we design a framework of potential broader interest for solving Blackwell approachability problems where multiple sets must simultaneously be approached via coupled actions.