基于Block Lewis Weights的分布鲁棒线性回归

# 基于块Lewis权重的分布鲁棒线性回归

来源：https://arxiv.org/html/2607.00252

Kumar Kshitij Patel  
数据科学基础研究所，耶鲁大学。邮箱：[email protected] (https://arxiv.org/html/2607.00252v1/[email protected])。本工作部分完成于作者在Simons理论计算研究所担任研究员期间。

###### 摘要

我们提出了一种用于组分布鲁棒（GDR）最小二乘问题的算法。给定 \(m\) 个组、一个参数向量 \(\mathbb{R}^d\) 以及堆叠的设计矩阵和响应 \(\mathbf{A}\) 和 \(\bm{b}\)，我们的算法使用 \(\tilde{O}(\min\{\mathsf{rank}(\mathbf{A}),m\}^{1/3}\varepsilon^{-2/3})\) 次形如 \(\mathbf{A}^{\top}\mathbf{B}\mathbf{A}\)（其中 \(\mathbf{B}\) 为块对角矩阵）的线性系统求解，即可得到 \((1+\varepsilon)\) 倍乘法最优解。我们的技术方法源于一个最近的几何构造——块Lewis权重，它将经验GDR问题与一个精心选择的最小二乘问题以及加速近端方法的应用联系起来。我们的算法在中等精度范围内优于已知的内点方法，并匹配了 \(\ell_\infty\) 回归这一特殊情况下的最新保证。我们还给出了能够平滑地在最小化平均最小二乘损失和分布鲁棒损失之间插值的算法。

###### 目录

1. 1.引言 (https://arxiv.org/html/2607.00252#S1)
   1. 1.1 我们的结果 (https://arxiv.org/html/2607.00252#S1.SS1)
   2. 1.2 先前结果、联系与开放问题 (https://arxiv.org/html/2607.00252#S1.SS2)
   3. 1.3 论文大纲 (https://arxiv.org/html/2607.00252#S1.SS3)
2. 2.技术概述 (https://arxiv.org/html/2607.00252#S2)
   1. 2.1 求解近端子问题 (https://arxiv.org/html/2607.00252#S2.SS1)
      1. 2.1.1 鲁棒情形 (\(p=\infty\))。 (https://arxiv.org/html/2607.00252#S2.SS1.SSS1)
      2. 2.1.2 插值情形 (\(2\leq p<\infty\))。 (https://arxiv.org/html/2607.00252#S2.SS1.SSS2)
   2. 2.2 迭代近端调用 (https://arxiv.org/html/2607.00252#S2.SS2)
   3. 2.3 几近端子问题的几何与块Lewis权重 (https://arxiv.org/html/2607.00252#S2.SS3)
   4. 2.4 分布鲁棒回归算法 (https://arxiv.org/html/2607.00252#S2.SS4)
3. 3.块Lewis权重及其性质 (https://arxiv.org/html/2607.00252#S3)
4. 4.带不精确更新的镜像下降 (https://arxiv.org/html/2607.00252#S4)
5. 5.自定义欧几里得几何下的最优MS加速 (https://arxiv.org/html/2607.00252#S5)
6. 6.最小化分布鲁棒损失 (https://arxiv.org/html/2607.00252#S6)
   1. 6.1 平滑逼近目标 (https://arxiv.org/html/2607.00252#S6.SS1)
   2. 6.2 LogSumExp的微积分 (https://arxiv.org/html/2607.00252#S6.SS2)
   3. 6.3 修正目标的平滑性与拟自和谐性 (https://arxiv.org/html/2607.00252#S6.SS3)
   4. 6.4 算法̃1的分析 (https://arxiv.org/html/2607.00252#S6.SS4)
7. 7.在平均损失与鲁棒损失之间插值 (https://arxiv.org/html/2607.00252#S7)
   1. 7.1 目标的微积分 (https://arxiv.org/html/2607.00252#S7.SS1)
      1. 7.1.1 目标的强凸性 (https://arxiv.org/html/2607.00252#S7.SS1.SSS1)
      2. 7.1.2 目标的光滑性 (https://arxiv.org/html/2607.00252#S7.SS1.SSS2)
   2. 7.2 迭代事实 (https://arxiv.org/html/2607.00252#S7.SS2)
   3. 7.3 近端子问题——微积分、算法、证明 (https://arxiv.org/html/2607.00252#S7.SS3)
      1. 7.3.1 Hessian稳定性 (https://arxiv.org/html/2607.00252#S7.SS3.SSS1)
      2. 7.3.2 近端目标的强凸性及相关性质 (https://arxiv.org/html/2607.00252#S7.SS3.SSS2)
      3. 7.3.3 近端目标的光滑性 (https://arxiv.org/html/2607.00252#S7.SS3.SSS3)
      4. 7.3.4 求解近端子问题 (https://arxiv.org/html/2607.00252#S7.SS3.SSS4)
   4. 7.4 算法 (https://arxiv.org/html/2607.00252#S7.SS4)
8. 8.经验评估 (https://arxiv.org/html/2607.00252#S8)
   1. 8.1 合成异质回归构造 (https://arxiv.org/html/2607.00252#S8.SS1)
      1. 8.1.1 通过凸规划计算鲁棒最优 (https://arxiv.org/html/2607.00252#S8.SS1.SSS1)
      2. 8.1.2 基线方法 (https://arxiv.org/html/2607.00252#S8.SS1.SSS2)
      3. 8.1.3 超参数调优 (https://arxiv.org/html/2607.00252#S8.SS1.SSS3)
      4. 8.1.4 经验行为 (https://arxiv.org/html/2607.00252#S8.SS1.SSS4)
   2. 8.2 真实世界实验：ACS收入 (https://arxiv.org/html/2607.00252#S8.SS2)
9. 参考文献 (https://arxiv.org/html/2607.00252#bib)

## 1 引言

机器学习算法及其训练数据集在过去十年中在规模和复杂性上都大幅增长。这种模型复杂性的增加使得在未观测场景中解释和预测其行为变得具有挑战性。因此，许多涉及社会决策的应用仍然依赖于简单、可解释的模型，如线性回归，通常在特征工程之后。此类应用的例子包括预测全国房价、估算各行业工资、预测各银行贷款金额、预测各组人寿保险费以及预测各社区能源消耗[cohen2024fairness]。在上述应用中，一个共同的安全（有时也是法律）关注点是，不同分布之间模型质量可能存在巨大差异，即对于某些源数据分布，可能输出明显更差的模型[data2014seizing, barocas2016big, hardt2016equality, veale2018fairness, selbst2019fairness, berk2021fairness, corbett2023measure, chouldechova2016fair, kleinberg2018algorithmic, agarwal2019fair, cohen2024fairness, svwz24]。具体来说，考虑拟合一个线性模型 \(\bm{x}\in\mathbb{R}^d\)，用于对 \(m\) 个组的某项任务进行实值预测，其中组 \(i\) 的数据集包含 \(n_i\) 个样本，记为 \(S_i=\{(\bm{a}_i^j,b_i^j)\}_{j\in[n_i]}\)。功利主义或总成本最小化的目标是使各组平均平方预测误差最小，即

\[\displaystyle\min_{\bm{x}\in\mathbb{R}^d}\frac{1}{m}\sum_{i\in[m]}\frac{1}{n_i}\left\|\mathbf{A}_{S_i}\bm{x}-\bm{b}_{S_i}\right\|_2^2\kern 5.0pt,\tag{1.1}\]

其中 \(\mathbf{A}_{S_i}\coloneqq[\bm{a}_i^1\dots\bm{a}_i^{n_i}]^\top\in\mathbb{R}^{n_i\times d}\) 是特征矩阵，\(\bm{b}_{S_i}\coloneqq[b_i^1\dots b_i^{n_i}]^\top\in\mathbb{R}^{n_i}\) 是组 \(i\in[m]\) 的标签向量。由于数据集的固有异质性，通过优化目标 (1.1) 得到的模型可能对某些组特别不利，因为这些组的预测误差可能不成比例地高。为了克服这些局限性，最近的一些工作考虑了以下平等主义或组分布鲁棒优化 (DRO) 目标 [ben2013robust, duchi2016statistics, sagawa2019distributionally, levy2020large, soma2022optimal, aakmrz22, svwz24]：

\[\displaystyle\min_{\bm{x}\in\mathbb{R}^d}\max_{i\in[m]}\frac{1}{n_i}\left\|\mathbf{A}_{S_i}\bm{x}-\bm{b}_{S_i}\right\|_2^2\kern 5.0pt.\tag{1.2}\]

目标1.2 是在所有平衡效用与分布鲁棒性的目标中“最公平”的 [kleinberg2018algorithmic, chouldechova2018frontiers, asadpour2022sequential, chen2022fair, rahmattalabi2019exploring, golrezaei2024online]。由于目标1.2 是一个凸问题，很自然地会应用标准的黑盒优化技术来求解。然而，我们发现现有方法在应用时存在几个挑战：

##### 高效一阶算法具有依赖于几何的收敛速度。
据我们所知，使用高效一阶方法（如次梯度下降）将产生依赖于几何的运行时间。特别地，如果矩阵 \(\mathbf{A}_{S_i}\) 或堆叠矩阵 \(\mathbf{A}\coloneqq[\mathbf{A}_{S_1}^\top\dots\mathbf{A}_{S_M}^\top]^\top\) 条件数很差，那么这将相应地反映在收敛速度中。这是现有结果 [aakmrz22] 和 [svwz24] 的一个缺点。

##### 目标 (1.2) 不是光滑的。
由于该目标是多个连续函数的逐点最大值，在最大值函数变化点处导数未定义。因此，如果没有针对性的分析，对该目标应用次梯度下降将导致迭代复杂度中令人不满意的 \(1/\varepsilon^2\) 依赖性。

##### 极小-极大优化/遗憾最小化方法的迭代复杂度具有 \(1/\varepsilon^2\) 依赖性。
由于问题1.2 是一个极小-极大优化目标，尝试使用博弈论启发的方法也是很自然的，这些方法将每个组的某个预言（如梯度）作为黑箱使用。例如，我们可以将目标1.2 转化为一个重复博弈：最小化玩家（配备无悔算法）与最大化玩家（配备最佳响应预言）之间的博弈。这种方法的主要缺点是，尽管每个组的函数是光滑的，但光滑在线凸优化达到 \(\varepsilon\) 平均后悔的迭代复杂度仍然具有令人不满意的 \(1/\varepsilon^2\) 依赖性（相比之下，光滑凸优化的是 \(1/\varepsilon\)）[soma2022optimal, zhang2024stochastic]。因此，这种方法并不比直接使用次梯度下降优化 (1.2) 更好。

##### 内点方法在 \(m\) 较大时迭代复杂度差。
另一种自然的（可以部分解决前两个问题的）方法，遵循 [boyd2004convex, Section 6.4] 的讨论，是将问题1.2 改写为其 epigraph 形式，并使用内点法 (IPM) 求解所得问题（在此情况下，是一个二次约束线性规划）。不幸的是，这将得到一个迭代复杂度为 \(O(\sqrt{m})\) 的算法，其中每次迭代需要求解形如 \(\mathbf{A}^\top\mathbf{B}\mathbf{A}\)（\(\mathbf{B}\) 为块对角矩阵）的线性系统（参见注释̃1.1）。该算法的朴素实现将具有关于组数的超线性运行时间，这在组数很大时是不可取的。或者，考虑一个例子，我们将每个组复制 \(k\) 次到目标中。新的目标值与原始目标值相同，但内点法的迭代复杂度现在增大到 \(\sqrt{mk}\)。这也提示我们，应寻找一个迭代复杂度基本与 \(m\) 无关的算法。因此，设计一个没有这些缺点的算法需要新颖的思路。

### 1.1 我们的结果

在本文中，我们提出了一种新算法（算法̃1），用于近似优化目标1.2，解决了上述困难。我们在以下定理中陈述算法的迭代复杂度。

###### 定理 1（鲁棒回归）。
令 \( \mathbf{A}_{S_i}\in\mathbb{R}^{n_i\times d} \) 和 \( \bm{b}_{S_i}\in\mathbb{R}^{n_i} \) 对所有 \( i\in[m] \) 成立。将其拼接得到 \( \mathbf{A}\coloneqq[\mathbf{A}_{S_1}^\top\dots\mathbf{A}_{S_M}^\top]^\top\in\mathbb{R}^{n\times d} \) 和 \( \bm{b}\coloneqq[\bm{b}_{S_1}^\top\dots\bm{b}_{S_M}^\top]^\top\in\mathbb{R}^{n} \)，其中 \( n:=\sum_{i\in[m]}n_i \)。设 \( \varepsilon>0 \)。则算法̃1 返回 \( \mathaccent 866{\bm{x}} \) 满足：

\[
\displaystyle\max_{i\in[m]}\frac{1}{\sqrt{n_i}}\left\|\mathbf{A}_{S_i}\mathaccent 866{\bm{x}}-\bm{b}_{S_i}\right\|_2 \leq (1+\varepsilon)\cdot\min_{\bm{x}\in\mathbb{R}^d}\max_{i\in[m]}\frac{1}{\sqrt{n_i}}\left\|\mathbf{A}_{S_i}\bm{x}-\bm{b}_{S_i}\right\|_2\kern 5.0pt,\tag{1.3}
\]

且其运行时间为

\[
O\left(\frac{\min\left\{\mathsf{rank}(\mathbf{A}),m\right\}^{1/3}\left(\log\left(\frac{n\log m}{\varepsilon}\right)^{14/3}+\log\left(m\right)\right)}{\varepsilon^{2/3}}\right)
\]

次形如 \( \mathbf{A}^{\top}\mathbf{B}\mathbf{A} \) 的线性系统求解，其中 \( \mathbf{B} \) 是块对角矩阵，且每个块 \( i \) 的大小为 \( n_i \times n_i \)。

我们在第̃6节中证明定理̃1。我们将定理̃1的保证与其他基线方法在表̃1中进行了比较。

| 算法 | 迭代复杂度 | 每次迭代 |
|------|------------|----------|
| 次梯度下降 | \(\frac{\left\|\bm{x}^{\star}\right\|_{2}\max_{1\leq i\leq m}\tfrac{1}{\sqrt{n_i}}\left\|\mathbf{A}_{S_i}\right\|_{\mathrm{op}}}{\varepsilon^{2}}\) | 计算 \(\nabla f(\bm{x})\) |
| 平滑目标上的Nesterov加速 | \(\frac{\left\|\bm{x}^{\star}\right\|_{2}\left(\max_{1\leq i\leq m}\tfrac{1}{\sqrt{n_i}}\left\|\mathbf{A}_{S_i}\right\|_{\mathrm{op}}\right)^{1/2}}{\varepsilon}\) | 计算 \(\nabla\mathaccent 869{f}_{\beta,\delta}(\bm{x})\) |
| [aakmrz22] | \(\frac{\left\|\bm{x}^{\star}\right\|_{2}\max_{1\leq i\leq m}\tfrac{1}{\sqrt{n_i}}\left\|\mathbf{A}_{S_i}\right\|_{\mathrm{op}}}{\varepsilon}\) | 计算 \(\nabla\mathaccent 869{f}_{\beta,\delta}(\bm{x})\) |
| 带对数障碍的内点法 [boyd2004convex] | \(m^{1/2}\log\left(\frac{1}{\varepsilon}\right)\) | 求解线性系统 \(\mathbf{A}^{\top}\mathbf{B}\mathbf{A}\) |
| 本文（朴素几何） | \(\frac{m^{1/3}}{\varepsilon^{2/3}}\) | 求解线性系统 \(\mathbf{A}^{\top}\mathbf{B}\mathbf{A}\) |
| 带Lewis权重的 \(\ell_\infty\) 回归 [jls21] | \(\frac{\mathsf{rank}\left(\mathbf{A}\right)^{1/3}}{\varepsilon^{2/3}}\) | 求解线性系统 |