# Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications

arXiv: https://arxiv.org/abs/2108.03837 · HTML: https://mlsanity.com/paper/2108.03837/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 43 references that are in the map.
- First posted on arXiv 9 Aug 2021.

## Builds on (most cited first, 7 of 7)

- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [Advancing subgroup fairness via sleeping experts](https://mlsanity.com/paper/1909.08375/) (2019)
- [Online Learning with Vector Costs and Bandits with Knapsacks](https://mlsanity.com/paper/2010.07346/) (2020)
- [Prediction with Expert Advice: a PDE Perspective](https://mlsanity.com/paper/1904.11401/) (2019)
- [New Potential-Based Bounds for Prediction with Expert Advice](https://mlsanity.com/paper/1911.01641/) (2019)
- [Approachability in unknown games: Online learning meets multi-objective optimization](https://mlsanity.com/paper/1402.2043/) (2014)

## Built on by (most cited first, 27 of 27)

- [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023)
- [Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents](https://mlsanity.com/paper/2306.02704/) (2023)
- [The Relationship between No-Regret Learning and Online Conformal Prediction](https://mlsanity.com/paper/2502.10947/) (2025)
- [Faster Recalibration of an Online Predictor via Approachability](https://mlsanity.com/paper/2310.17002/) (2023)
- [Group-wise oracle-efficient algorithms for online multi-group learning](https://mlsanity.com/paper/2406.05287/) (2024)
- [Oracle Efficient Algorithms for Groupwise Regret](https://mlsanity.com/paper/2310.04652/) (2023)
- [The Scope of Multicalibration: Characterizing Multicalibration via Property Elicitation](https://mlsanity.com/paper/2302.08507/) (2023)
- [In Defense of Defensive Forecasting](https://mlsanity.com/paper/2506.11848/) (2025)
- [Calibeating Made Simple](https://mlsanity.com/paper/2603.22167/) (2026)
- [Repeated Contracting with Multiple Non-Myopic Agents: Policy Regret and Limited Liability](https://mlsanity.com/paper/2402.17108/) (2024)
- [Calibrated Probabilistic Forecasts for Arbitrary Sequences](https://mlsanity.com/paper/2409.19157/) (2024)
- [Calibrated Regression Against An Adversary Without Regret](https://mlsanity.com/paper/2302.12196/) (2023)
- [Learning With Multi-Group Guarantees For Clusterable Subpopulations](https://mlsanity.com/paper/2410.14588/) (2024)
- [Sparsity-Based Interpolation of External, Internal and Swap Regret](https://mlsanity.com/paper/2502.04543/) (2025)
- [Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction](https://mlsanity.com/paper/2602.17577/) (2026)
- [Near-optimal Swap Regret Minimization for Convex Losses](https://mlsanity.com/paper/2602.08862/) (2026)
- [Optimal Deterministic Multicalibration and Omniprediction](https://mlsanity.com/paper/2606.20557/) (2026)
- [Instance-Adaptive Online Multicalibration](https://mlsanity.com/paper/2605.09273/) (2026)
- [Proper Calibeating](https://mlsanity.com/paper/2605.26703/) (2026)
- [Time-Dependent Blackwell Approachability and Application to Absorbing Games](https://mlsanity.com/paper/2303.04956/) (2023)
- [Improved and Oracle-Efficient Online ℓ1-Multicalibration](https://mlsanity.com/paper/2505.17365/) (2025)
- [Multi-Objective textitmin-max Online Convex Optimization](https://mlsanity.com/paper/2510.13560/) (2025)
- [Locally Adaptive Multi-Objective Learning](https://mlsanity.com/paper/2602.14952/) (2026)
- [Prior-Agnostic Incentive-Compatible Exploration](https://mlsanity.com/paper/2602.20465/) (2026)
- [ShakyPrepend: A Multi-Group Learner with Improved Sample Complexity](https://mlsanity.com/paper/2603.07319/) (2026)
- [Blackwell Approachability and Gradient Equilibrium are Equivalent](https://mlsanity.com/paper/2606.27315/) (2026)
- [Sample-Optimal Multi-Group Learning with an ERM Oracle](https://mlsanity.com/paper/2610.15916/) (2026)

## Abstract (arXiv)

We introduce a simple but general online learning framework in which a learner plays against an adversary in a vector-valued game that changes every round. Even though the learner's objective is not convex-concave (and so the minimax theorem does not apply), we give a simple algorithm that can compete with the setting in which the adversary must announce their action first, with optimally diminishing regret. We demonstrate the power of our framework by using it to (re)derive optimal bounds and efficient algorithms across a variety of domains, ranging from multicalibration to a large set of no regret algorithms, to a variant of Blackwell's approachability theorem for polytopes with fast convergence rates. As a new application, we show how to ``(multi)calibeat'' an arbitrary collection of forecasters -- achieving an exponentially improved dependence on the number of models we are competing against, compared to prior work.