提出高效算法解决分组分布鲁棒线性回归问题
Distributionally Robust Linear Regression With Block Lewis Weights
- 基于块莱维斯权重构造等价优化问题
- 仅需约 $\widetilde{O}(\min\{\mathsf{rank}(\mathbf{A}),m\}^{1/3}\varepsilon^{-2/3})$ 次线性系统求解
- 适用于中等精度场景，适合关注鲁棒性的机器学习研究者
我们提出一种求解分组分布鲁棒（GDR）最小二乘问题的算法。给定 $m$ 个组、参数向量 $\R^d$，以及堆叠的设计矩阵和响应 $\mathbf{A}$ 与 $\mathbf{b}$，该算法通过 $\widetilde{O}(\min\{\mathsf{rank}(\mathbf{A}),m\}^{1/3}\varepsilon^{-2/3})$ 次形如 $\mathbf{A}^{ op}\mathbf{B}\mathbf{A}$ 的线性系统求解，获得 $(1+\varepsilon)$-乘法最优解，其中 $\mathbf{B}$ 为块对角矩阵。技术核心是利用最近提出的几何构造——块莱维斯权重，将经验 GDR 问题转化为一个精心设计的最小二乘问题，并结合加速近端方法。该算法在中等精度下优于已知内点法，且在 $\l_{\infty}$ 回归这一特例中达到当前最优保证。此外，我们还给出了可在平均最小二乘损失与分布鲁棒损失之间平滑插值的算法。
原文摘要 · Abstract (English)
We present an algorithm for the group distributionally robust (GDR) least squares problem. Given $m$ groups, a parameter vector in $\mathbb{R}^d$, and stacked design matrices and responses $\mathbf{A}$ and $\mathbf{b}$, our algorithm obtains a $(1+\varepsilon)$-multiplicative optimal solution using $\widetilde{O}(\min\{\mathsf{rank}(\mathbf{A}),m\}^{1/3}\varepsilon^{-2/3})$ linear-system-solves of matrices of the form $\mathbf{A}^{\top}\mathbf{B}\mathbf{A}$ for block-diagonal $\mathbf{B}$. Our technical methods follow from a recent geometric construction, block Lewis weights, that relates the empirical GDR problem to a carefully chosen least squares problem and an application of accelerated proximal methods. Our algorithm improves over known interior point methods for moderate accuracy regimes and matches the state-of-the-art guarantees for the special case of $\ell_{\infty}$ regression. We also give algorithms that smoothly interpolate between minimizing the average least squares loss and the distributionally robust loss.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。