Equal Opportunity in Online Classification with Partial Feedback
summary
Online classification with one-sided feedback (lend/deny), cast to contextual bandits by adding a constant loss for denied cases so the reduction is regret-preserving. Main result: an oracle-efficient algorithm (uses Mini-MONSTER plus a fair cost-sensitive classification oracle) guarantees per-round false-positive gap ≤ gamma + T^-1/4 and regret O(√(T log|H|)) to the best gamma-fair policy; optimal gamma-fair policy needs support ≤2. Matching lower bound shows the fairness–regret tradeoff is tight. Open problems: simultaneous FPR/FNR constraints and other fairness notions.
AI-written summary · about
chapters (7)
- 0:00Problem overview
- 4:56Formalizing the setting
- 7:29Regret in one-sided feedback
- 13:12Defining fairness
- 17:41Fairness and regret algorithm
- 25:55Lower bounds and analysis
- 31:18Open problems and discussion
related talks
48mA Simple Condition for Constant Regret in Online Decision-Making
44mParsimonious Learning-Augmented Algorithms
49mOracle-Efficient Online Learning or: How to Use Non-Robust Optimization for Robust Learning
35mOnline Optimization and Learning Under Long-Term Convex Constraints and Objectives
30mIndividual Statistical Fairness
33mOnline Multivalid Learning: Means, Moments, and Prediction Intervals
01h 15mBridging Stochastic and Adversarial Bandits
58mMemory-Regret Tradeoff for Online Learning