Group Distributionally Robust Optimization with Flexible Sample Queries

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 O(1/t√∑ⱼ₌₁ᵗ m/rⱼlog m), where rₜ 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)/ε²) 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.