Online Multivalid Learning: Means, Moments, and Prediction Intervals
summary
Provides algorithms that guarantee group-conditional uncertainty in an adversarial online setting: multi-calibration and 1−δ prediction-interval coverage for every group in a possibly huge, overlapping family, with error α = O(1/√T) and dependence on groups like √log|G| (or √d if each example lies in ≤d groups). Key tools are the minimax theorem, a smooth softmax surrogate plus Taylor bounds, and constructive procedures (a simple grid-randomized strategy for multi-calibration and an ellipsoid+knapsack oracle LP for intervals). Guarantees hold with high probability and run in polynomial time, though the interval solver is practically heavy.
AI-written summary · about
chapters (7)
- 0:00Start
- 1:40Accuracy and Uncertainty
- 2:45Uncertainties and Subpopulations
- 6:27Strong Can Uncertainty Guarantees Be?
- 8:46tributional Assumptions
- 25:44diction Interval Multivalidity
- 27:49iving Prediction Interval Guarantees
related talks
48mOnline Adversarial Multicalibration And (Multi)Calibeating
50mA Multi-Group Approach To Algorithmic Fairness
37mEfficient Algorithms for Reliable Machine Learning
01h 21mMulticalibration: Towards Fair Decision Making
59mTesting Assumptions of Learning Algorithms
47mA Multi-Group Perspective on Fairness
42mBypassing the Impossibility of Online Learning Thresholds: Unbounded Losses and Transductive Priors
36mQuantifying uncertainty in Machine Learning predictions