我们提出了一种用于群体分布稳健（GDR）最小二乘问题的算法。给定 $m$ 个组、一个参数向量在 $\mathbb{R}^d$ 中，以及堆叠的设计矩阵和响应 $\mathbf{A}$ 和 $\mathbf{b}$，我们的算法能够使用 $\tilde{O}(\min\{\operatorname{rank}(\mathbf{A}),m\}^{1/3}\epsilon^{-2/3})$ 次线性系统求解来获得 $(1+\epsilon)$-倍的最优解。这些线性系统的矩阵形式为 $\mathbf{A}^{\top}\mathbf{B}\mathbf{A}$，其中 $\mathbf{B}$ 为块对角矩阵。
我们的技术方法源于最近的几何构造——块路易斯权重，它将经验 GDR 问题与精心选择的最小二乘问题联系起来，并应用了加速的近端方法。
我们的算法在适度精度范围内优于已知的内点法，并在 $\ell_{\infty}$ 回归的特例中匹配了最先进的保证。我们还提供了算法，能够在最小化平均最小二乘损失和分布稳健损失之间平滑插值。
博主点评： 本文提出的算法展现了群体分布稳健最小二乘问题的新解法，结合几何构造与加速方法，具有重要的理论与实际应用价值。其在精度上的优势和灵活性使得这一研究成果值得深入关注与探索。