Search papers, labs, and topics across Lattice.
This paper extends the binary omniprediction algorithm of [OKK25] to the multiclass setting, addressing the challenge of omniprediction with infinite comparator families. The extension achieves a sample complexity or regret horizon of approximately $\varepsilon^{-(k+1)}$ for $\varepsilon$-omniprediction in a $k$-class problem. The work introduces a novel framework for solving Blackwell approachability problems involving the simultaneous approach of multiple sets via coupled actions.
Forget single-objective optimization—this work cracks omniprediction in multiclass settings, opening the door to algorithms that are robust across diverse loss functions and comparator classes.
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.
