mlsanityData to 7 Oct 2026

Group-wise oracle-efficient algorithms for online multi-group learning

arXiv 2406.05287 ↗First posted 7 Jun 2024cs.LG cs.GT stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

We study the problem of online multi-group learning, a learning model in which an online learner must simultaneously achieve small prediction regret on a large collection of (possibly overlapping) subsequences corresponding to a family of groups. Groups are subsets of the context space, and in fairness applications, they may correspond to subpopulations defined by expressive functions of demographic attributes. In contrast to previous work on this learning model, we consider scenarios in which the family of groups is too large to explicitly enumerate, and hence we seek algorithms that only access groups via an optimization oracle. In this paper, we design such oracle-efficient algorithms with sublinear regret under a variety of settings, including: (i) the i.i.d. setting, (ii) the adversarial setting with smoothed context distributions, and (iii) the adversarial transductive setting.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 20 of its 37 references that are in the map. First posted on arXiv 7 Jun 2024.

Builds on

20 of 37 references.

References · 20

  1. 2019Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalizationcited by 1,232
  2. 2017Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairnesscited by 381
  3. 2018Multiaccuracy: Black-Box Post-Processing for Fairness in Classificationcited by 221
  4. 2019Hidden Stratification Causes Clinically Meaningful Failures in Machine Learning for Medical Imagingcited by 215
  5. 2014A Second-order Bound with Excess Lossescited by 91
  6. 2021Smoothed Analysis with Adaptive Adversariescited by 57
  7. 2022Smoothed Online Learning is as Easy as Statistical Learningcited by 50
  8. 2021Multi-group Agnostic PAC Learnabilitycited by 42
  9. 2015The Computational Power of Optimization in Online Learningcited by 38
  10. 2016Efficient Algorithms for Adversarial Contextual Learningcited by 32
  11. 2016Oracle-Efficient Online Learning and Auction Designcited by 32
  12. 2023Multicalibration as Boosting for Regressioncited by 32
8 more
  1. 2023A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learningcited by 29
  2. 2019Advancing subgroup fairness via sleeping expertscited by 28
  3. 2021Online Minimax Multiobjective Optimization: Multicalibeating and Other Applicationscited by 26
  4. 2021Simple and near-optimal algorithms for hidden stratification and multi-group learningcited by 26
  5. 2023Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agentscited by 25
  6. 2022An Algorithmic Framework for Bias Bountiescited by 19
  7. 2022Adaptive Oracle-Efficient Online Learningcited by 7
  8. 2023Oracle Efficient Algorithms for Groupwise Regretcited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 5.

8 papers.

  1. 2025The Relationship between No-Regret Learning and Online Conformal Predictioncited by 13
  2. 2025Panprediction: Optimal Predictions for Any Downstream Task and Losscited by 4
  3. 2026Group-realizable multi-group learning by minimizing empirical riskcited by 2
  4. 2025Improved and Oracle-Efficient Online ℓ1-Multicalibrationcited by 0
  5. 2026Locally Adaptive Multi-Objective Learningcited by 0
  6. 2026ShakyPrepend: A Multi-Group Learner with Improved Sample Complexitycited by 0
  7. 2026A One-Inclusion Graph Approach to Multi-Group Learningcited by 0
  8. 2026The price of multi-group transductive learningcited by 0