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

arXiv: https://arxiv.org/abs/2410.00690 · HTML: https://mlsanity.com/paper/2410.00690/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 30 references that are in the map.
- First posted on arXiv 1 Oct 2024.

## Builds on (most cited first, 13 of 13)

- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Fairness risk measures](https://mlsanity.com/paper/1901.08665/) (2019)
- [Fighting Bandits with a New Kind of Smoothness](https://mlsanity.com/paper/1512.04152/) (2015)
- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [Active Sampling for Min-Max Fairness](https://mlsanity.com/paper/2006.06879/) (2020)
- [Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2212.13669/) (2022)
- [Optimal Multi-Distribution Learning](https://mlsanity.com/paper/2312.05134/) (2023)
- [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023)
- [Near-optimal Per-Action Regret Bounds for Sleeping Bandits](https://mlsanity.com/paper/2403.01315/) (2024)

## Built on by (most cited first, 5 of 5)

- [Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry](https://mlsanity.com/paper/2411.05198/) (2024)
- [Group Distributionally Robust Optimization with Flexible Sample Queries](https://mlsanity.com/paper/2505.15212/) (2025)
- [Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise](https://mlsanity.com/paper/2602.21039/) (2026)
- [Structured Credal Learning](https://mlsanity.com/paper/2603.14070/) (2026)
- [Distributionally Robust Set Representation Learning Under Inference-Time Element Corruption](https://mlsanity.com/paper/2605.30089/) (2026)

## Abstract (arXiv)

The minimax sample complexity of group distributionally robust optimization (GDRO) has been determined up to a log(K) factor, where K is the number of groups. In this work, we venture beyond the minimax perspective via a novel notion of sparsity that we dub (λ, β)-sparsity. In short, this condition means that at any parameter θ, there is a set of at most β groups whose risks at θ all are at least λ larger than the risks of the other groups. To find an ε-optimal θ, we show via a novel algorithm and analysis that the ε-dependent term in the sample complexity can swap a linear dependence on K for a linear dependence on the potentially much smaller β. This improvement leverages recent progress in sleeping bandits, showing a fundamental connection between the two-player zero-sum game optimization framework for GDRO and per-action regret bounds in sleeping bandits. We next show an adaptive algorithm which, up to log factors, gets a sample complexity bound that adapts to the best (λ, β)-sparsity condition that holds. We also show how to get a dimension-free semi-adaptive sample complexity bound with a computationally efficient method. Finally, we demonstrate the practicality of the (λ, β)-sparsity condition and the improved sample efficiency of our algorithms on both synthetic and real-life datasets.