Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction
This work addresses multiclass prediction challenges in machine learning, representing an incremental extension of binary omniprediction methods.
The paper tackles the problem of extending omniprediction to multiclass settings with potentially infinite comparator families, achieving sample complexity or regret horizon of approximately ε^-(k+1) for ε-omniprediction in k-class problems.
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.