Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction

Lunjia Hu, Kevin Tian, Chutong Yang
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3593-3634, 2026.

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 Okoroafor et al. (2025) 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-hu26c, title = {Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction}, author = {Hu, Lunjia and Tian, Kevin and Yang, Chutong}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {3593--3634}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/hu26c/hu26c.pdf}, url = {https://proceedings.mlr.press/v336/hu26c.html}, 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 Okoroafor et al. (2025) 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.} }
Endnote
%0 Conference Paper %T Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction %A Lunjia Hu %A Kevin Tian %A Chutong Yang %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-hu26c %I PMLR %P 3593--3634 %U https://proceedings.mlr.press/v336/hu26c.html %V 336 %X 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 Okoroafor et al. (2025) 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.
APA
Hu, L., Tian, K. & Yang, C.. (2026). Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:3593-3634 Available from https://proceedings.mlr.press/v336/hu26c.html.

Related Material