Online Adversarial Multicalibration And (Multi)Calibeating
summary
A unifying framework called online minimax multi-objective optimization converts many adversarial online goals into a zero-sum surrogate game and yields efficient algorithms that provably achieve multi-calibration, prediction-interval multi-validity, multi-group no-regret assignment and calibeating. Key tools are a softmax surrogate, telescoping the surrogate loss, and playing the min-max equilibrium each round. Bounds guarantee the max-coordinate loss ≤ average adversary-moves-first value plus O(√(log D / T)); discretization adds a 1/R error. Algorithms are constructive and attain optimal dependence on parameters.
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:50Two motivating online adversarial problems
- 1:16What do/should reported uncertainty estimates mean?
- 2:29Marginal Guarantees.
- 6:03Mean Multicalibration
- 7:59Prediction Interval Multivalidity
- 9:26Multi-Group Optimal Assignment
- 14:10A Simple Unifying Framework: "Online Minimax Multiobjective Optimization"
- 16:25An Interlude: Zero Sum Games
- 17:58Can we just solve zero sum games?
- 24:34We can achieve this.
- 31:50Instantiating the Generic Framework
- 39:45Can combine compatible constraints! Combining multigroup regret and calibration
related talks
33mOnline Multivalid Learning: Means, Moments, and Prediction Intervals
01h 21mMulticalibration: Towards Fair Decision Making
01h 11mA Theory of Multi-objective Machine Learning
55mLearning Minimax Estimators Via Online Learning
47mA Multi-Group Perspective on Fairness
45mMulticalibration, Universal Adaptability and Causality
37mOmnipredictors
50mA Multi-Group Approach To Algorithmic Fairness