Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction

• URL: http://arxiv.org/abs/2602.17577v1
• Date: Thu, 19 Feb 2026 18:02:03 GMT
• Title: Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction
• Authors: Lunjia Hu, Kevin Tian, Chutong Yang,
• Abstract summary: We study omniprediction in a multiclass setting, where the comparator family $mathcalC$ may be infinite.<n>Our main result is an extension of the recent binary omniprediction algorithm of [OKK25] to the multiclass setting.
• Score: 17.79426749489757
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model [0.688204255655161]
  We study the online unweighted bipartite matching problem in the random arrival order model.<n>Our learning-augmented algorithm achieves $(1-o(1))$-consistency and $(-o(1))$-robustness.
  arXiv  Detail & Related papers  (2025-11-28T17:31:11Z)
• Rate optimal learning of equilibria from data [63.14746189846806]
  We close theoretical gaps in Multi-Agent Imitation Learning (MAIL) by characterizing the limits of non-interactive MAIL and presenting the first interactive algorithm with near-optimal sample complexity.<n>For the interactive setting, we introduce a framework that combines reward-free reinforcement learning with interactive MAIL and instantiate it with an algorithm, MAIL-WARM.<n>We provide numerical results that support our theory and illustrate, in environments such as grid worlds, where Behavior Cloning fails to learn.
  arXiv  Detail & Related papers  (2025-10-10T12:28:35Z)
• Towards Fundamental Limits for Active Multi-distribution Learning [16.639855803241524]
  We develop new algorithms for active multi-distribution learning and establish improved label complexity upper and lower bounds.<n>We show that the bound in the realizable setting is information-theoretically optimal and that the $knu/varepsilon2$ term in the setting is fundamental for proper learners.
  arXiv  Detail & Related papers  (2025-06-21T06:08:58Z)
• Improved Bounds for Swap Multicalibration and Swap Omniprediction [31.959887895880765]
  We show that it is possible to efficiently achieve $O(sqrtT)$ $ell_2$-swap multicalibration error against bounded linear functions.<n>We also establish a $O(varepsilon -3)$ sample complexity of efficiently learning an $varepsilon$-swap omnipredictor for the class of convex and Lipschitz functions.
  arXiv  Detail & Related papers  (2025-05-27T08:29:35Z)
• Omnipredicting Single-Index Models with Multi-Index Models [9.794426212144453]
  We give a learner outputting an omnipredictor that is $varepsilon$-competitive on any matching loss induced by a monotone, Lipschitz link function.<n>Our algorithm requires $approx varepsilon-4$ samples and runs in nearly-linear time, and its sample complexity improves to $approx varepsilon-2$ if link functions are bi-Lipschitz.
  arXiv  Detail & Related papers  (2024-11-20T07:20:49Z)
• Oracle Efficient Online Multicalibration and Omniprediction [15.476402844435704]
  We study omniprediction in the online adversarial setting. We develop a new online multicalibration algorithm that is well defined for infinite benchmark classes $F$. We show upper and lower bounds on the extent to which our rates can be improved.
  arXiv  Detail & Related papers  (2023-07-18T06:34:32Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB)<n>We introduce an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity upper bound matches the lower bound up to a problem-dependent constant factor.<n>We numerically show that the CombGapE algorithm outperforms existing methods significantly in both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  We study contextual bandits with probabilistically triggered arms (C$2$MAB-T) under a variety of smoothness conditions. Under the triggering modulated (TPM) condition, we devise the C$2$-UC-T algorithm and derive a regret bound $tildeO(dsqrtT)$.
  arXiv  Detail & Related papers  (2023-03-30T02:51:00Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  We study learning in contextual bandits with the help of loss predictors. We show that the optimal regret is $mathcalO(minsqrtT, sqrtmathcalETfrac13)$ when $mathcalE$ is known.
  arXiv  Detail & Related papers  (2020-03-04T07:36:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.