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

Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity

ICML 2025 · Bandits and online learning › Online convex optimization and games · approach: Best-of-both-worlds bandit algorithms · 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.

Introduces (λ,β)-sparsity for group DRO and shows sleeping-bandit-based two-player game algorithms whose sample complexity scales with β instead of K in the leading 1/ε² term, with adaptive and semi-adaptive variants plus experiments on synthetic and Adult data.

Problem

Sample complexity of group distributionally robust optimization (GDRO) is known to be minimax-tight at roughly (G²D²+K)/ε², but practical instances often have large gaps between groups, so the worst-case bound is pessimistic.

Approach

Define (λ,β)-sparsity: at every hypothesis, a set of at most β groups has risks at least λ above all others. The max-player is modeled as a sleeping bandit over only the active (dominant-set) groups, so per-action regret bounds from sleeping bandits reduce the leading-term dependence from K ln K to β ln K.

Key results

• On the Adult dataset (K=10 race×gender groups), SB-GDRO-SA reaches optimality gap below 4e-5 well under 4e5 samples, while SMD-GDRO fails to reach it even after about 1e6 samples.
• Dominant sets discovered by SB-GDRO-SA are smaller than ceil(ln K) within the first 3000 rounds on Adult, showing non-trivial (λ, ln K)-sparsity around the optimum.
• The paper proves a lower bound Omega((G²D²+β)/ε²) for (λ,β)-sparse GDRO, matching the upper bound's dependence on β up to logs.

Measured effects reported in the paper

Surprising findings

• More than 60% of samples drawn by SB-GDRO-SA come from the female Amer-Indian-Eskimo group, which is only 0.3% of the data.

Limitations

• (λ,β)-sparsity is assumed to hold at all θ in Θ, not only near θ*, which the authors note is restrictive
• Fully adaptive algorithm requires covering Θ and is computationally intractable for large n
• Semi-adaptive bound holds only in high-precision regime where ε is much smaller than λ*

Experimental setup

Datasets: Adult

Benchmarks: Adult

Metrics: optimality gap sample complexity dominant set size

Baselines: SMD-GDRO

Builds on: SMD-GDRO SB-EXP3 sleeping bandits EXP3-IX

Closest papers by meaning

• Group Distributionally Robust Optimization with Flexible Sample Queries (NeurIPS 2026 · similarity 0.92)
• Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond (ICML 2024 · similarity 0.91)
• MixMax: Distributional Robustness in Function Space via Optimal Data Mixtures (ICLR 2025 · similarity 0.87)
• On Interpolating Experts and Multi-Armed Bandits (ICML 2024 · similarity 0.87)
• Testing the Feasibility of Linear Programs with Bandit Feedback (ICML 2024 · similarity 0.86)
• Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.86)