面向OLS回归的数据分区分布式草图方法

# 基于数据分区分布式草图构建的OLS回归

来源：https://arxiv.org/html/2607.07888  
\[1\] 机构= 俄克拉荷马大学计算机科学学院，国家 = 美国

标题=基于数据分区分布式草图构建的OLS回归

###### 摘要

本文研究面向普通最小二乘 \(OLS\) 回归的分布式草图构建方法。该方法将大型数据集的多个小型草图分发到多台机器上，分别构建 OLS 估计器并求其平均。与先前考虑对整个数据集进行草图构建的研究不同，我们考虑对分区子集进行草图构建，以进一步降低计算成本。在固定设计设定下，我们刻画了平均化 OLS 估计器的精确超额损失。结果表明，当子集协方差之间的离散度较小时，该损失与已建立的针对整个数据集进行草图构建的损失相当。

###### 关键词：

分布式草图构建\\sep 普通最小二乘回归\\sep 期望超额损失\\sep

## 1 引言

分布式草图构建是一种有效的方法，用于将普通最小二乘 \(OLS\) 回归扩展到大规模数据 (bartlan2023distributed; garg2024distributed; chen2025gpu)。其基本思想是将大数据集的多个小型草图分发到多台机器，每台机器根据收到的草图构建一个 OLS 估计器，然后对所有机器构建的估计器进行平均。在 `bartlan2023distributed` 中，假设每个草图是通过高斯投影从整个数据集映射而来，并刻画了平均化估计器的确切超额损失。然而，这种草图构建机制有一个已知的局限性：映射过程通常计算成本高昂。

本文考虑另一种草图构建机制：每个草图是从整个数据集的某个分区子集映射而来。在这种情况下，随着子集大小减小或等效地随着分布式机器数量增加（这样每台机器持有的子集更小），映射成本会降低。在固定设计设定下，我们也刻画了平均化估计器的确切超额损失。结果表明，当子集协方差之间的离散度较小时，该损失与上述已建立的损失相当。

## 2 预备知识

考虑固定设计设定。令 `x1,...,xn ∈ Rd` 为 `n` 个点的固定集合。令 `yi ∈ R` 为 `xi` 的标签，由 `yi = xi^T α* + εi` 生成，其中 `α* ∈ Rd` 是固定的，`εi` 是独立同分布的随机噪声，满足 `E εi = 0` 和 `Var(εi) = σ^2`，其中 `σ > 0` 为固定值。令 `X = [x1, ..., xn]^T ∈ Rn×d` 为样本矩阵，`Y = [y1, ..., yn]^T ∈ Rn` 为标签向量，`E = [ε1, ..., εn]^T ∈ Rn` 为噪声向量。则上述设定可写为：

`Y = X α* + E.`   (1)

考虑将 `X` 均匀行划分为 `k` 个子矩阵 `X1, ..., Xk ∈ Rp×d`，为方便起见假设 `p k = n`。令 `Y1, ..., Yk ∈ Rp` 和 `E1, ..., Ek ∈ Rp` 分别为 `Y` 和 `E` 的对应行划分，这意味着 `Yi = Xi α* + Ei`。令 `S̃ = {S̃1, ..., S̃k ∈ Rm×n}` 和 `S = {S1, ..., Sk ∈ Rm×p}` 为两组独立随机矩阵，其元素独立同分布，服从 `N(0, 1/m)`。令 `||·||` 表示 `L2` 范数，`Is` 为 `s` 阶单位矩阵。

考虑三个 OLS 估计器。给定 `E`，第一个估计器基于整个数据集构建，即：

`α̂* = arg min_{α∈Rd} ||Xα - Y||^2,`   (2)

给定 `E, S̃`，第二个估计器基于从整个集合映射的草图构建，即：

`β̄ = (1/k) ∑_{i=1}^k β̂_i, 其中 β̂_i = arg min_{α∈Rd} ||S̃_i X α - S̃_i Y||^2.`   (3)

给定 `E, S`，第三个估计器基于从分区子集映射的草图构建，即：

`θ̄ = (1/k) ∑_{i=1}^k θ̂_i, 其中 θ̂_i = arg min_{α∈Rd} ||S_i Xi α - S_i Yi||^2.`   (4)

最后，将回归函数 `α` 在给定 `(X, Y)` 上的平方损失记为：

`L(α) = ||Xα - Y||^2.`   (5)

对 `β̄` 的确切超额损失已有研究。我们将刻画 `θ̄` 的确切损失并进行适当比较。与先前研究类似，我们关注 `p > d+1` 的情形，并假设几乎必然所有数据矩阵满秩且 `Xi^T Xi` 可逆。在刻画中一个有用的量为：

`D = (1/k^2) ∑_{i=1}^k ∑_{j=1}^k D_{ij}, 其中 D_{ij} = tr[ (Xi^T Xi) (Xj^T Xj)^{-1} ].`   (6)

该量可视为子集协方差的一种离散度度量，值越小通常意味着离散度越小。显然当 `k=1` 时（即 `Xi = X`），`D = d`。以下引理给出一个紧的下界。

###### 引理 2.1.

几乎必然有 `D ≥ d`，当所有 `i ≠ j` 满足 `Xi^T Xi = Xj^T Xj` 时取等号。

该量还与几个众所周知的度量相关联，这丰富了其解释。为方便起见，假设所有子矩阵中心化，使得 `Xi^T Xi` 是子集 `i` 的（未缩放）样本协方差。

一个联系是经典的 Stein 损失 (dey1985estimation) 或等价地 Burg 矩阵散度 (kulis2009low)。子集 `i` 和 `j` 的样本协方差之间的标准散度定义为：

`BD(i,j) = D_{ij} - d - log det[ (Xi^T Xi) (Xj^T Xj)^{-1} ].`   (7)

我们可以定义所有子集上的平均 Burg 散度为：

`BD = (1/k^2) ∑_{i,j=1}^k BD(i,j) = D - d - (1/k^2) log det ∏_{i,j=1}^k (Xi^T Xi) (Xj^T Xj)^{-1}.`   (8)

这意味着 `D` 是平均 Burg 散度的主导项，较小的 `D` 通常意味着较小的散度。反之，当平均 Burg 散度为零时（当且仅当每个 `BD(i,j)=0`，等价于所有子集具有相同的样本协方差），根据引理 2.1，`D` 达到其最小值 `d`。

另一个联系是流行的杠杆分数 (bharadwaj2023fast)。令 `A^r` 表示给定矩阵 `A` 的第 `r` 行。对于子集 `i`，其第 `r` 个点的标准杠杆分数为：

`L_{i,r} = (X_i^r) (Xi^T Xi)^{-1} (X_i^r)^T,`   (9)

它指定了点 `r` 在子集 `i` 中偏离其他点的程度。类似地，我们可以写出：

`D_{ij} = ∑_{r=1}^p L_{ir,j}, 其中 L_{ir,j} = (X_i^r) (Xj^T Xj)^{-1} (X_i^r)^T.`   (10)

与 `L_{i,r}` 相比，项 `L_{ir,j}` 可视为相对杠杆分数，它指定了点 `r` 偏离子集 `j` 中点的程度。那么 `D_{ij}` 是子集 `i` 的总相对杠杆分数（相对于子集 `j`），而 `D` 是描述子集之间偏离的平均相对分数。

## 3 主要结果

我们首先回顾关于 `β̄` 的一个已知结果。

###### 定理 3.1 (bartlan2023distributed)。

给定 `E`，对于 `m > d+1`：

`E_{S̃|E}[ L(β̄) ] - L(α̂*) = (1/k) * (L(α̂*)/(m-d-1)) * d.`   (11)

我们对 `θ̄` 的结果如下。

###### 定理 3.3.

在固定设计设定下，对于 `p ≥ m > d+1`：

`E_{S,E}[ L(θ̄) ] - E_E[ L(α̂*) ] = (σ^2/k) * ((n - k d)/(m - d - 1)) * D + σ^2 (D - d) := B_θ.`   (13)

我们有三个观察。首先，如果 `k=1`，则 `B_θ = B_β`，这是预期的，因为 `θ̄` 没有进行分区。其次，如果 `D` 接近 `d`，则 `B_θ ≤ B_β`，这表明如果子集协方差离散度较小（这在数据独立同分布采样时可能常见），`θ̄` 可能优于 `β̄`。第三，如果 `D` 远离 `d`，则 `B_θ ≥ B_β`，这表明如果子集协方差离散度较大（这可能发生在数据来自异质源时），`θ̄` 可能表现更差。

这些观察表明，`D` 与 `d` 之间的差距是 `θ̄` 性能的重要指标。为了更具体地了解这一差距，我们可以进一步引入 `X` 的随机性。

该注记表明，当 `k` 较小或 `n ≫ max(k, d)` 时，差距可能较小；特别地，当 `k=1` 时 `E[D] = d`，这与上述结果一致。另一个有趣的实验是将阶次代入 `B_θ - B_β`，得到：

`E_X[ B_β - B_θ ] = σ^2 d * (F(k; n, d, m) + 1),`   (14)

其中 `F(k; n, d, m) = (n-d)/(m-d-1) k - (1/k) * ((n - k d)/(m - d - 1)) * ((n-(d+1))/(n - k(d+1))) - (n-(d+1))/(n - k(d+1))` 是关于 `k` 的函数。通过标准分析（检查函数导数），可以证明 `F` 呈倒 U 形。这意味着，随着 `k` 增加，`θ̄` 和 `β̄` 之间的性能差距可能先增大后减小。我们的数值结果证实了这一点。

最后，我们推导出 `θ̄` 超额损失的一个高概率界。其证明见附录 B，主要依赖于使用随机矩阵的经典奇异值界来界定 `(Xi^T Si^T Si Xi)^{-1}`。

给定估计器 `α̂`，令 `L_o(α̂) = E_Y ||X α̂ - Y||` 表示其样本外超额损失，其中 `Y` 和 `α̂` 分别由独立的标签噪声 `E_Y` 和 `E_α̂` 构建。我们的结果如下。

将 `B_θ'` 与 `B_θ` 比较，我们看到它们具有相同的第二项。对于 `B_θ`，第一项是 `σ^2 D * (p-d)/(m-d-1)`，当 `m ≫ d` 时主要由 `σ^2 D * (p/m)` 主导。对于 `B_θ'`，忽略对数项，第一项近似为：

`σ^2 D * (Γ(p,m,k,δ) - 1) ≈ σ^2 D * ( (√m + √p)^2 / (√m - √d)^2 - 1 ),`   (16)

当 `p ≫ m ≫ d` 时，它也主要由 `σ^2 D * (p/m)` 主导。这表明 `B_θ'` 可以是 `B_θ` 的高概率代理，这意味着期望超额损失能够代表典型的分布式草图构建性能。

## 4 定理 3.3 的证明

给定 `E`，令估计器 `α` 在 `(Xi, Yi)` 上的平方损失为：

`L_i(α) = ||Xi α - Yi||^2.`   (17)

令 `ᾱ` 为平均估计器，定义为：

`ᾱ = (1/k) ∑_{i=1}^k α̂_i, 其中 α̂_i = arg min_α L_i(α).`   (18)

令 `Ê_i` 为与 `α̂_i` 在 `(Xi, Yi)` 上相关联的残差，即：

`Ê_i = Yi - Xi α̂_i.`   (19)

注意 `Ê_i` 不同于 `Ei`，并且在给定 `Ei` 时是固定的。最后，回忆 `S = {S1, ..., Sk}` 并令 `SX = {S1 X1, ..., Sk Xk}`。由于每个集合中的元素相互独立，任何仅依赖于 `Si` 的变量 `Gi` 满足 `E_S[Gi] = E_{Si}[Gi]` 和 `E_{SX}[Gi] = E_{Si Xi}[Gi]`。没有下标的期望继承前一个期望的下标。

### 4.1 路线图

一个基本观察是 `E_{S|E}[θ̂_i] = α̂_i` (Claim 4.1)。在此基础上，我们证明 (Claim 4.2)：

`E_E[ L(α̂*) ] = (n - d) σ^2 且 E_E[ L_i(α̂_i) ] = (p - d) σ^2.`   (20)

前者建立了 Remark 3.2，并蕴含另一个重要刻画 (Claim 4.3)：

`E_{S,E}[ L(θ̄) ] - E_E[ L(α̂*) ] = E_{S,E} || X (θ̄ - α̂*) ||^2.`   (21)

为了评估右边，我们首先固定 `E` 并证明 (Claim 4.4)：

`E_{S|E} || X θ̄ - X α̂* ||^2 = E || X θ̄ - X ᾱ ||^2 + || X ᾱ - X α̂* ||^2 = (1/k^2) ∑_{i=1}^k E || X (θ̂_i - α̂_i) ||^2 + || X ᾱ - X α̂* ||^2,`   (22)

其中第一个等式来自 `E_{S|E}[θ̄] = ᾱ` (Claim 4.1)，第二个来自 `E_{S|E}[θ̂_i] = α̂_i`。进一步，

`E_{S|E} || X (θ̂_i - α̂_i) ||^2` ...