Research map / Bandits and online learning / Online convex optimization and games

Oracle Efficient Algorithms for Groupwise Regret

ICLR 2024 · Bandits and online learning › Online convex optimization and games · approach: Online learning with feedback graphs · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that a modified sleeping-experts/AdaNormalHedge reduction turns any efficient external-regret learner into an oracle-efficient groupwise (subsequence) regret learner, linear in the number of groups, and validates it on synthetic, medical cost, and Adult income linear regression.

Problem

Online prediction where predictions must have low regret simultaneously on every (possibly intersecting) demographic group subsequence, while existing groupwise-regret algorithms are computationally intractable for large hypothesis classes such as linear models.

Approach

Run one external-regret learner per group subsequence (over the hypothesis class H) and aggregate their policies with AdaNormalHedge over the active subsequences, so only |G|+1 experts are enumerated rather than all (group, hypothesis) pairs; this yields oracle-efficient groupwise regret from any efficient external-regret algorithm.

Key results

• On synthetic data (mean aggregation), the proposed algorithm's regret on the always-on group is about -39.9 versus +0.76 for the baseline, and it has lower regret on every group.
• On Medical Cost data, the algorithm's cumulative loss is about 1.9 units lower than the baseline, against a best-linear-in-hindsight loss of about 4.1.
• On Adult income, the algorithm's cumulative loss is about 14 units lower than the baseline, against a best-linear loss of about 568, a smaller gain than on other datasets.

Measured effects reported in the paper

Surprising findings

• Regret relative to the best linear model in hindsight for each group is often negative, meaning the ensemble beats the best per-group linear model because intersecting groups force mixing of models.
• The baseline's regret grows linearly on intersecting groups even though it has low regret on the full sequence, since the best fixed model differs by group.

Limitations

• Regret bounds for linear regression depend on ||theta||^2 and the algorithm is only efficient when the number of groups is polynomially bounded.
• Experiments are limited to linear regression with a small number of groups (5 synthetic, 3 to 5 real groups per attribute).
• Analysis is for full-information settings; the batch and apple-tasting extensions are only briefly discussed.

Experimental setup

Datasets: Medical Cost dataset Adult income dataset (folktables reconstruction) synthetic data (5 groups, 20-dim features, 100000 individuals)

Benchmarks: Medical Cost dataset Adult income dataset synthetic data

Metrics: groupwise regret cumulative squared loss

Baselines: online ridge regression on full history

Builds on: AdaNormalHedge sleeping experts groupwise regret online ridge regression

Closest papers by meaning

• Group-wise oracle-efficient algorithms for online multi-group learning (NeurIPS 2024 · similarity 0.89)
• From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.87)
• The Relationship Between No-Regret Learning and Online Conformal Prediction (ICML 2025 · similarity 0.86)
• Regret minimization in Linear Bandits with offline data via extended D-optimal exploration. (NeurIPS 2026 · similarity 0.85)
• Stochastic Online Instrumental Variable Regression: Regrets for Endogeneity and Bandit Feedback (AAAI 2025 · similarity 0.85)
• Regret–Oracle Complexity Tradeoffs in Agnostic Online Learning (NeurIPS 2026 · similarity 0.85)