Research map / Bandits and online learning / Online convex optimization and games
Group-wise oracle-efficient algorithms for online multi-group learning
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.
Designs oracle-efficient online multi-group learning algorithms (FTPL-based, via a joint group-hypothesis optimization oracle) achieving sublinear group-wise regret in smoothed, i.i.d., and transductive settings.
Problem
Online multi-group learning where the family of groups is too large to enumerate; the learner must achieve small regret on every (possibly overlapping) group subsequence while accessing groups and hypotheses only through optimization oracles.
Approach
Extends the adversary-moves-first min-max framework by using a follow-the-perturbed-leader strategy for the group-hypothesis player, which implicitly maintains a distribution over G x H and is approximated by repeatedly calling a joint (G,H) optimization oracle; also sparsifies FTPL distributions and simplifies the per-round min-max game to a 2-variable LP. Uses GFTPL with perturbation matrices fo
Key results
- Oracle-efficient algorithm achieves E[Reg_T(H,g)] = O(sqrt(dT log T / sigma) + alpha T) for all groups g in G under sigma-smooth contexts, with poly(T) oracle calls.
- Under gamma-approximability, GFTPL variant achieves O(sqrt(T_g) max{gamma, log|H||G|, sqrt(N log|H||G|)} + alpha T) group-wise regret for finite H and G.
- Transductive setting gives group-wise regret O(sqrt(T_g) T^{1/4}) (up to log factors) when N <= T.
Limitations
- Group-specific o(T_g) regret not achieved for infinite H and G (stated open problem).
- The sigma-smooth result has sigma-dependence that is not optimal (the FTPL variant gives sigma^{-1/4} dependence per remark).
- Oracle is approximate and alternating-maximization instantiation only guarantees a local saddle point.
Experimental setup
Metrics: multi-group regret group-wise regret bounds
Baselines: Multi-group online learning via specialists (Blum-Mansour-style reduction) Oracle-efficient multi-group algorithm with enumeration of G Oracle-efficient smoothed online learning algorithms (Haghtalab et al.)
Builds on: adversary-moves-first framework follow-the-perturbed-leader generalized follow-the-perturbed-leader ListUpdate (multi-group batch learning) specialists / sleeping experts
Closest papers by meaning
- Oracle Efficient Algorithms for Groupwise Regret (ICLR 2024 · similarity 0.89)
- The Relationship Between No-Regret Learning and Online Conformal Prediction (ICML 2025 · similarity 0.87)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.85)
- Replicable Online Learning (NeurIPS 2025 · similarity 0.85)
- Multi-group Learning for Hierarchical Groups (ICML 2024 · similarity 0.85)
- A Simple and Optimal Approach for Universal Online Learning with Gradient Variations (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.