# Group Distributionally Robust Optimization with Flexible Sample Queries

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 49 references that are in the map.
- First posted on arXiv 21 May 2025.

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

- [Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization](https://mlsanity.com/paper/1911.08731/) (2019)
- [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)
- [DoReMi: Optimizing Data Mixtures Speeds Up Language Model Pretraining](https://mlsanity.com/paper/2305.10429/) (2023)
- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Group Robust Preference Optimization in Reward-free RLHF](https://mlsanity.com/paper/2405.20304/) (2024)
- [Generative models improve fairness of medical classifiers under distribution shifts](https://mlsanity.com/paper/2304.09218/) (2023)
- [Distributionally Robust Optimization: A Review](https://mlsanity.com/paper/1908.05659/) (2019)
- [Stable Prediction across Unknown Environments](https://mlsanity.com/paper/1806.06270/) (2018)
- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [Minimax Regret Optimization for Robust Machine Learning under Distribution Shift](https://mlsanity.com/paper/2202.05436/) (2022)
- [Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2212.13669/) (2022)
- [Distributionally Robust Optimization via Ball Oracle Acceleration](https://mlsanity.com/paper/2203.13225/) (2022)
- [Minimax Optimal Algorithms for Adversarial Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1911.11122/) (2019)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [To Cool or not to Cool? Temperature Network Meets Large Foundation Models via DRO](https://mlsanity.com/paper/2404.04575/) (2024)
- [Multiarmed Bandits With Limited Expert Advice](https://mlsanity.com/paper/1306.4653/) (2013)
- [Adaptation to Easy Data in Prediction with Limited Advice](https://mlsanity.com/paper/1807.00636/) (2018)
- [Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity](https://mlsanity.com/paper/2410.00690/) (2024)
- [Fast rates for prediction with limited expert advice](https://mlsanity.com/paper/2110.14485/) (2021)
- [Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2302.09267/) (2023)
- [Efficient Stochastic Approximation of Minimax Excess Risk Optimization](https://mlsanity.com/paper/2306.00026/) (2023)
- [Lasso Bandit with Compatibility Condition on Optimal Arm](https://mlsanity.com/paper/2406.00823/) (2024)
- [Efficient Online-Bandit Strategies for Minimax Learning Problems](https://mlsanity.com/paper/2105.13939/) (2021)
- [Constant regret for sequence prediction with limited advice](https://mlsanity.com/paper/2210.02256/) (2022)
- [Minimax Optimal Reinforcement Learning with Quasi-Optimism](https://mlsanity.com/paper/2503.00810/) (2025)

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

- [StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Models](https://mlsanity.com/paper/2604.15416/) (2026)
- [Communication-Efficient Agnostic Federated Learning via Faster Convergence and Compression](https://mlsanity.com/paper/2609.36610/) (2026)

## Abstract (arXiv)

Group distributionally robust optimization (GDRO) aims to develop models that perform well across m distributions simultaneously. Existing GDRO algorithms can only process a fixed number of samples per iteration, either 1 or m, and therefore can not support scenarios where the sample size varies dynamically. To address this limitation, we investigate GDRO with flexible sample queries and cast it as a two-player game: one player solves an online convex optimization problem, while the other tackles a prediction with limited advice (PLA) problem. Within such a game, we propose a novel PLA algorithm, constructing appropriate loss estimators for cases where the sample size is either 1 or not, and updating the decision using follow-the-regularized-leader. Then, we establish the first high-probability regret bound for non-oblivious PLA. Building upon the above approach, we develop a GDRO algorithm that allows an arbitrary and varying sample size per round, achieving a high-probability optimization error bound of Oleft(frac1t√sumj=1t fracmrjlog mright), where rt denotes the sample size at round t. This result demonstrates that the optimization error decreases as the number of samples increases and implies a consistent sample complexity of O(mlog (m)/ε2) for any fixed sample size r∈[m], aligning with existing bounds for cases of r=1 or m. We validate our approach on synthetic binary and real-world multi-class datasets.