提出可动态调整采样数的鲁棒优化方法,提升模型在多分布下的泛化性能。
Group Distributionally Robust Optimization with Flexible Sample Queries
- 将问题建模为双玩家博弈,设计新算法适应任意采样规模。
- 理论证明优化误差随样本量增加而降低,达到最优样本复杂度。
- 适用于样本量不固定的场景,适合追求鲁棒性的实际应用。
群体分布鲁棒优化(GDRO)旨在使模型在 $m$ 个分布上同时表现良好。现有算法每轮仅能处理固定数量样本(1 或 $m$),无法支持动态变化的样本规模。为此,本文将 GDRO 与灵活采样查询结合,建模为两玩家博弈:一玩家求解在线凸优化,另一玩家解决有限建议预测(PLA)问题。在此框架下,提出一种新型 PLA 算法,针对样本数为 1 或非 1 的情况构造合适损失估计器,并使用跟随正则化领导者进行更新。进一步建立了首个非盲式 PLA 的高概率后悔界。基于此,构建了支持每轮任意且可变样本数的 GDRO 算法,实现高概率优化误差界 $O\left(\frac{1}{t}\sqrt{\sum_{j=1}^t \frac{m}{r_j}\log m}\right)$,其中 $r_t$ 表示第 $t$ 轮的样本数。结果表明优化误差随样本量增大而减小,且对任意固定样本大小 $r\in[m]$,样本复杂度为 $O(m\log(m)/ε^2)$,与 $r=1$ 或 $r=m$ 的已有结果一致。在合成二分类及真实世界多分类数据集上验证了方法有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。