Group Distributionally Robust Optimization with Flexible Sample Queries
Authors:
- Haomin BaiHBHaomin Bai
- Dingzhi YuDYDingzhi Yu
- Shuai LiSLShuai Li
- Haipeng LuoHLHaipeng Luo
- Lijun ZhangLZLijun Zhang
Preprint
Abstract
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\left(\frac{1}{t}\sqrt{\sum_{j=1}^t \frac{m}{r_j}\log m}\right)$, where $r_t$ 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(m\log (m)/ε^2)$ for any fixed sample size $r\in[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.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Learning models with uniform performance via distributionally robust optimizationThe Annals of Statistics, 2021
- Federated learning with adaptive communication compression under dynamic bandwidth and unreliable networksInformation Sciences, 2020
- Multi-armed Bandit with Additional ObservationsProceedings of the ACM on Measurement and Analysis of Computing Systems, 2018
- A survey on concept drift adaptationACM Computing Surveys, 2014
- Impact of HbA1c Measurement on Hospital Readmission Rates: Analysis of 70,000 Clinical Database Patient RecordsBioMed Research International, 2014
- Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven ProblemsOperations Research, 2010
- Robust Stochastic Approximation Approach to Stochastic ProgrammingSIAM Journal on Optimization, 2009
- Dependent rounding and its applications to approximation algorithmsJournal of the ACM, 2006
- The Nonstochastic Multiarmed Bandit ProblemSIAM Journal on Computing, 2002
- On Tail Probabilities for MartingalesThe Annals of Probability, 1975