提出稀疏性新概念，显著降低群体鲁棒优化的样本需求。
Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
- 引入(λ, β)稀疏性，仅需关注少数高风险群体。
- 样本复杂度从依赖K降至依赖更小的β，理论优势明显。
- 算法自适应稀疏性，适合群体差异明显的实际场景。
群体分布鲁棒优化（GDRO）的极小极大样本复杂度已确定，误差项含$\log(K)$因子，其中$K$为群体数。本文通过引入新稀疏性概念$(λ, β)$-稀疏性，突破传统极小极大视角：在任意参数$θ$下，至多$β$个群体的风险比其余群体高出至少$λ$。针对寻找$ε$-最优$θ$的问题，我们设计新算法并分析，使$ε$相关项的依赖关系由$K$线性变为$β$线性，显著提升效率。该结果基于睡眠老虎机最新进展，揭示了GDRO零和博弈框架与每动作后悔界之间的深层联系。进一步提出自适应算法，其样本复杂度可逼近最优$(λ, β)$-稀疏条件，且可实现维度无关的半自适应高效方法。实验验证了$(λ, β)$-稀疏性的实用性及算法在合成与真实数据集上的样本效率优势。
原文摘要 · Abstract (English)
The minimax sample complexity of group distributionally robust optimization (GDRO) has been determined up to a $\log(K)$ factor, where $K$ is the number of groups. In this work, we venture beyond the minimax perspective via a novel notion of sparsity that we dub $(λ, β)$-sparsity. In short, this condition means that at any parameter $θ$, there is a set of at most $β$ groups whose risks at $θ$ all are at least $λ$ larger than the risks of the other groups. To find an $ε$-optimal $θ$, we show via a novel algorithm and analysis that the $ε$-dependent term in the sample complexity can swap a linear dependence on $K$ for a linear dependence on the potentially much smaller $β$. This improvement leverages recent progress in sleeping bandits, showing a fundamental connection between the two-player zero-sum game optimization framework for GDRO and per-action regret bounds in sleeping bandits. We next show an adaptive algorithm which, up to log factors, gets a sample complexity bound that adapts to the best $(λ, β)$-sparsity condition that holds. We also show how to get a dimension-free semi-adaptive sample complexity bound with a computationally efficient method. Finally, we demonstrate the practicality of the $(λ, β)$-sparsity condition and the improved sample efficiency of our algorithms on both synthetic and real-life datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。