mlsanityData to 7 Oct 2026

Group Distributionally Robust Optimization with Flexible Sample Queries

arXiv 2505.15212 ↗First posted 21 May 2025cs.LG math.OCcited by 2

Not on the map. Why?

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.

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

Builds on

27 of 49 references.

References · 27

  1. 2019Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalizationcited by 1,232
  2. 2019Agnostic Federated Learningcited by 451
  3. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  4. 2023DoReMi: Optimizing Data Mixtures Speeds Up Language Model Pretrainingcited by 385
  5. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 334
  6. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  7. 2024Group Robust Preference Optimization in Reward-free RLHFcited by 94
  8. 2023Generative models improve fairness of medical classifiers under distribution shiftscited by 90
  9. 2019Distributionally Robust Optimization: A Reviewcited by 75
  10. 2018Stable Prediction across Unknown Environmentscited by 55
  11. 2022On-Demand Sampling: Learning Optimally from Multiple Distributionscited by 39
  12. 2022Minimax Regret Optimization for Robust Machine Learning under Distribution Shiftcited by 31
15 more
  1. 2022Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyondcited by 16
  2. 2022Distributionally Robust Optimization via Ball Oracle Accelerationcited by 14
  3. 2019Minimax Optimal Algorithms for Adversarial Bandit Problem with Multiple Playscited by 11
  4. 2024Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyondcited by 11
  5. 2024To Cool or not to Cool? Temperature Network Meets Large Foundation Models via DROcited by 11
  6. 2013Multiarmed Bandits With Limited Expert Advicecited by 7
  7. 2018Adaptation to Easy Data in Prediction with Limited Advicecited by 7
  8. 2024Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsitycited by 5
  9. 2021Fast rates for prediction with limited expert advicecited by 4
  10. 2023Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyondcited by 4
  11. 2023Efficient Stochastic Approximation of Minimax Excess Risk Optimizationcited by 4
  12. 2024Lasso Bandit with Compatibility Condition on Optimal Armcited by 4
  13. 2021Efficient Online-Bandit Strategies for Minimax Learning Problemscited by 2
  14. 2022Constant regret for sequence prediction with limited advicecited by 2
  15. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Modelscited by 4
  2. 2026Communication-Efficient Agnostic Federated Learning via Faster Convergence and Compressioncited by 0