← 研踪 PaperTrailarXiv:2505.15212 · v2
Group Distributionally Robust Optimization with Flexible Sample Queries
首次提交 2025-05-21 15:41
版本更新 2026-11-02 18:24
雷达观测 2026-11-04 23:42
摘要
Group distributionally robust optimization (GDRO) aims to learn models that perform well across $m$ distributions simultaneously. Existing methods either (i) query $m$ samples per round, which imposes strict implementation requirements, or (ii) query only a single sample per round, which requires many rounds to converge and therefore leads to long runtime. To avoid these limitations, we introduce a novel setting called \emph{flexible sample queries} (FSQ), which allows the number of samples that can be queried to vary across rounds. Under the FSQ setting, we cast GDRO as a two-player game: one performs non-oblivious online convex optimization, while the other tackles a non-oblivious prediction with limited advice (PLA) problem. In this game, the first player updates its decision using follow-the-regularized-leader with stochastic gradients. For the second player, we develop a new PLA method equipped with an adaptive exploration strategy that can leverage an arbitrary per-round sample size. We then establish the \emph{first} high-probability regret bound for non-oblivious PLA. By integrating these components, we develop an anytime GDRO algorithm that supports FSQ, and derive 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_j$ is the sample size at round $j$. This result demonstrates that the optimization error decreases as the per-round sample sizes increase, and implies the same near-optimal sample complexity of $O(m\log (m)/ε^2)$ for any fixed sample size $r\in[m]$.
作者备注：Accepted at NeurIPS 2026
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-02 18:24 · 最新观测版本
Group Distributionally Robust Optimization with Flexible Sample Queries
Group distributionally robust optimization (GDRO) aims to learn models that perform well across $m$ distributions simultaneously. Existing methods either (i) query $m$ samples per round, which imposes strict implementation requirements, or (ii) query only a single sample per round, which requires many rounds to converge and therefore leads to long runtime. To avoid these limitations, we introduce a novel setting called \emph{flexible sample queries} (FSQ), which allows the number of samples that can be queried to vary across rounds. Under the FSQ setting, we cast GDRO as a two-player game: one performs non-oblivious online convex optimization, while the other tackles a non-oblivious prediction with limited advice (PLA) problem. In this game, the first player updates its decision using follow-the-regularized-leader with stochastic gradients. For the second player, we develop a new PLA method equipped with an adaptive exploration strategy that can leverage an arbitrary per-round sample size. We then establish the \emph{first} high-probability regret bound for non-oblivious PLA. By integrating these components, we develop an anytime GDRO algorithm that supports FSQ, and derive 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_j$ is the sample size at round $j$. This result demonstrates that the optimization error decreases as the per-round sample sizes increase, and implies the same near-optimal sample complexity of $O(m\log (m)/ε^2)$ for any fixed sample size $r\in[m]$.
查看此版本解读 →查看此版本原文 ↗