arXiv:2410.00690v2 宣告类型: replace-cross 摘要：分组分布鲁棒优化（GDRO）的准最小极大样本复杂性已被确定到对数因素 \log(K)，其中 K 是组的数量。在本文中，我们通过一种新颖的稀疏性概念——我们称之为 (\lambda, \beta)-稀疏性——超越了准最小极大视角。简而言之，这种条件意味着在任何参数 \theta 下，存在一个风险至少比其他组的风险大 \lambda 的 \beta 个组的集合。为了找到 \epsilon-近似最优的 \theta，我们通过一种新颖的算法和分析显示，样本复杂性的 \epsilon 依赖项可以从对 K 的线性依赖转变为对较小得多的 \beta 的线性依赖。这一改进得益于睡眠型多臂老虎机领域的最近进展，展示了分组分布鲁棒优化的两玩家零和博弈优化框架与睡眠型多臂老虎机中针对行动的后悔界之间的基本联系。随后，我们展示了通过一种自适应算法，样本复杂性界在对数因素下能够适应最佳的 (\lambda, \beta)-稀疏性条件。我们还展示了如何使用一种计算效率高的方法获得去除了维数的半自适应样本复杂性界。最后，我们在合成数据集和实际数据集上验证了 (\lambda, \beta)-稀疏性条件以及我们算法的改进样本效率的实用性。