mlsanityData to 7 Oct 2026

Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction

arXiv 2602.17577 ↗First posted 19 Feb 2026cs.DS cs.LG stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

Omniprediction is a learning problem that requires suboptimality bounds for each of a family of losses L against a family of comparator predictors C. We initiate the study of omniprediction in a multiclass setting, where the comparator family 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) ≈ 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.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 26 of its 47 references that are in the map. First posted on arXiv 19 Feb 2026.

Builds on

26 of 47 references.

References · 26

  1. 2017On Calibration of Modern Neural Networkscited by 4,860
  2. 2014Convex Optimization: Algorithms and Complexitycited by 569
  3. 2019Beyond temperature scaling: Obtaining well-calibrated multiclass probabilities with Dirichlet calibrationcited by 359
  4. 2021Calibrating Predictions to Decisions: A Novel Approach to Multi-Class Calibrationcited by 79
  5. 2021Omnipredictorscited by 71
  6. 2022A Characterization of Multiclass Learnabilitycited by 66
  7. 2022Loss Minimization through the Lens of Outcome Indistinguishabilitycited by 61
  8. 2023U-Calibration: Forecasting for an Unknown Agentcited by 46
  9. 2023High-Dimensional Prediction for Sequential Decision Makingcited by 41
  10. 2023Oracle Efficient Online Multicalibration and Omnipredictioncited by 36
  11. 2025Near-Optimal Algorithms for Omnipredictioncited by 33
  12. 2023Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibrationcited by 31
14 more
  1. 2021Online Minimax Multiobjective Optimization: Multicalibeating and Other Applicationscited by 26
  2. 2022A Characterization of List Learnabilitycited by 22
  3. 2014The Sample Complexity of Learning Linear Predictors with the Squared Losscited by 16
  4. 2024On Computationally Efficient Multi-Class Calibrationcited by 16
  5. 2025Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Lossescited by 14
  6. 2024From Fairness to Infinity: Outcome-Indistinguishable (Omni)Prediction in Evolving Graphscited by 13
  7. 2025High dimensional online calibration in polynomial timecited by 12
  8. 2025High-Dimensional Calibration from Swap Regretcited by 12
  9. 2014Approachability in unknown games: Online learning meets multi-objective optimizationcited by 10
  10. 2013The PAV algorithm optimizes binary proper scoring rulescited by 8
  11. 2024Omnipredicting Single-Index Models with Multi-Index Modelscited by 7
  12. 2025Generalized and Unified Equivalences between Hardness and Pseudoentropycited by 5
  13. 2025Calibration through the Lens of Indistinguishabilitycited by 4
  14. 2017Approachability with Constraintscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Testable and Actionable Calibration for Full Swap Regretcited by 1
  2. 2026Optimal Recalibration of an Online Predictorcited by 1
  3. 2026Fast Rates for Swap-Agnostic Learning of Proper Lossescited by 0