用于鲁棒核回归的分布式梯度下降算法

《Journal of Mathematical Analysis and Applications》:Distributed gradient descent algorithm for robust kernel-based regression

【字体: 大 中 小 】 时间:2026年10月01日 来源:Journal of Mathematical Analysis and Applications 1.3

编辑推荐:

   ## 摘要 本文研究了再生核希尔伯特空间(RKHS)框架下带有鲁棒损失函数的梯度下降算法的理论基础。我们引入了一种新的辅助序列用于误差分析,并在回归函数不属于RKHS的情况下改进了先前的收敛结果。在普遍假设条件下,我们建立了分布式鲁棒梯度下降算法在回归函数属于和不属于RKH

  

## 摘要

本文研究了再生核希尔伯特空间(RKHS)框架下带有鲁棒损失函数的梯度下降算法的理论基础。我们引入了一种新的辅助序列用于误差分析,并在回归函数不属于RKHS的情况下改进了先前的收敛结果。在普遍假设条件下,我们建立了分布式鲁棒梯度下降算法在回归函数属于和不属于RKHS两种情况下的最优收敛速率,前提是划分数量不会过大。

## 引言

本文关注非参数回归问题,该问题旨在从给定观测值中估计输入与输出之间未知的底层函数关系。设 $X \subset \mathbb{R}^d$ 为输入变量 $x$ 的紧致度量空间,$Y \subset \mathbb{R}$ 为响应变量 $y$ 的输出空间。它们通过乘积空间 $Z := X \times Y$ 上的未知联合概率测度 $\rho$ 关联起来。在回归分析的大多数应用中,最为重要的是回归函数这一底层函数关系。记 $\rho(\cdot|x)$ 为给定 $x \in X$ 时 $\rho$ 的条件分布。回归(均值)函数定义为

$$f_\rho(x) := \int_Y y \, d\rho(y|x), \quad x \in X.$$

在实践中,传统最小二乘是最广泛使用的回归范式。然而,从鲁棒性角度来看,它并非一个好的选择,因为最小二乘损失不是 Lipschitz 连续的,因此生成的估计量可能受到极少量异常值的严重影响 [5]。为解决缺乏鲁棒性的问题,很自然地会考虑使用鲁棒损失函数来替代最小二乘损失。本文考虑与一类由窗口函数诱导的鲁棒损失函数相关的梯度下降算法 [25]、[26]、[27]。

**定义 1.1** 设 $\sigma > 0$ 为缩放参数。对任意 $u \in \mathbb{R}$,定义

$$\ell_\sigma(u) = G\left(\frac{u}{2\sigma^2}\right).$$

此处窗口函数 $G:[0,\infty) \mapsto \mathbb{R}$ 满足:

(i) $G'_+(0) > 0$,对任意 $w > 0$ 有 $G'(w) > 0$,且 $c_G := \sup_{w \in (0,\infty)} G'(w) < \infty$,其中 $G'_+(0)$ 表示 $G(w)$ 在 $w=0$ 处的右导数。

(ii) 存在常数 $c_p > 0$ 和 $p \geq 0$ 使得 $|G'(w) - G'_+(0)| \leq c_p |w|^p, \forall w > 0$。

通过选择不同的窗口函数,形如 (1.1) 的损失函数可以包含大量常用的鲁棒损失,有关 $\ell_\sigma$ 的具体例子参见 [12]。需要指出的是,满足定义 1.1 的鲁棒损失函数不一定凸。经验研究和理论研究均表明,非凸 $\ell_\sigma$ 损失可以产生比其凸对应物更鲁棒的估计量。最近,[12] 在再生核希尔伯特空间(RKHS)框架下提出了一种带有早停规则的梯度下降算法。回忆 Mercer 核 $K: X \times X \mapsto \mathbb{R}$ 是一个连续的、对称的且非负定的函数。核 $K$ 与 RKHS $(\mathcal{H}_K, \|\cdot\|_K)$ 之间存在一一对应关系,其中 $\mathcal{H}_K$ 是一个带有内积 $\langle \cdot, \cdot \rangle_K$ 的线性函数空间,使得对任意 $x \in X$,$K_x := K(x, \cdot) \in \mathcal{H}_K$,且对任意 $f \in \mathcal{H}_K$ 有 $f(x) = \langle K_x, f \rangle_K$。由于 $X$ 是紧致的,$\mathcal{H}_K$ 是可分的且包含于 $\mathcal{C}(X)$ 中,即 $X$ 上带有范数 $\|f\|_\infty := \sup_{x \in X} |f(x)|$ 的连续函数空间。由 (1.3),对每个 $f \in \mathcal{H}_K$,$\|f\|_\infty \leq \kappa \|f\|_K$,其中 $\kappa := \sup_{x \in X} \sqrt{K(x,x)} < \infty$。

给定从 $\rho$ 独立抽取的观测集 $D = \{z_i = (x_i, y_i)\}_{i=1}^{|D|}$,其中 $|D|$ 为 $D$ 的基数。为简化起见,我们假设 $|D| \geq 3$。带有鲁棒损失函数 $\ell_\sigma$ 的梯度下降算法由以下更新过程定义(见 [12]):

**定义 1.2** 鲁棒核回归的梯度下降算法定义为 $f_{1,D} = 0$,对 $t = 1, 2, \cdots, T$,

$$f_{t+1,D} = f_{t,D} - \frac{\eta_t}{|D|} \sum_{i=1}^{|D|} G'\left(\xi_{t,D}(z_i)\right)(f_{t,D}(x_i) - y_i) K_{x_i},$$

其中 $\eta_t > 0$ 为步长,$\xi_{t,D}(z_i) := \frac{(y_i - f_{t,D}(x_i))^2}{\sigma^2}$。缩放参数 $\sigma$ 在估计精度和鲁棒性之间起到权衡作用,需要根据样本量调整 $\sigma$ 值以执行均值回归 [7]、[8]、[9]、[12]。在实践中,缩放参数 $\sigma$ 通常通过基于交叉验证的合适后验策略选择。特别是,[12] 表明,通过适当选择缩放参数 $\sigma$ 和早停规则 $T \in \mathbb{N}$,在满足某些正则性假设的情况下,(1.5) 经过 $T$ 次迭代后的输出可以逼近 $f_\rho$。然而,由于每次迭代中梯度的计算涉及所有训练样本,梯度下降算法 (1.5) 在处理大规模数据集时会面临可扩展性问题。这促使我们在本文研究分布式核梯度下降算法。通过分而治之的方法,我们将给定数据集 $D$ 划分为 $m$ 个不相等的等大小子集 $D_1, D_2, \cdots, D_m$。在每个子集 $D_j$ 上,使用梯度下降算法 (1.5) 计算局部估计量 $f_{t+1,D_j}$。分布式核回归鲁棒梯度下降算法的最终输出为

$$\overline{f}_{t+1,D} = \frac{1}{m} \sum_{j=1}^m f_{t+1,D_j}.$$

这一过程虽然简单,但在第二阶段通过实现并行计算从而具备计算效率,并通过最小化相互信息通信来保持数据安全性和隐私。因此,分布式学习已受到相当多的研究,参见 [4]、[13]、[14]、[15]、[16]、[17]、[18]、[19]、[20]、[21]、[28]、[31] 及其中的参考文献。然而,上述研究均基于最小二乘回归或谱方法,对带有鲁棒代理损失的分布式算法的理论理解仍然有限。

本文的主要目的是在广泛的估计精度度量范围内建立鲁棒核梯度下降算法的紧密误差界。我们的主要贡献有两方面:第一,我们改进了 [12] 中当 $f_\rho$ 不属于 $\mathcal{H}_K$ 时对算法 (1.5) 推导的收敛结果。第二,在 [12] 中相同的假设下,我们证明了分布式算法 (1.6) 在划分数量 $m$ 不过大的情况下,对 $f_\rho \in \mathcal{H}_K$ 和 $f_\rho \notin \mathcal{H}_K$ 两种情况均可保持最优速率。

本文的其余部分组织如下。第 2 节给出一些符号并陈述主要结果。第 3 节给出将在主要定理证明中起关键作用的一些预备引理。第 4 节和第 5 节分别对算法 (1.5) 和 (1.6) 进行误差分析。最后,第 6 节总结我们的主要结论。

## 假设与主要结果

我们首先给出一些符号和假设,以便精确陈述主要结果。

设 $\rho_X$ 为 $\rho$ 在 $X$ 上的边缘分布。全文中我们假设边缘分布 $\rho_X$ 是非退化的。设 $\mathcal{L}^2_{\rho_X}$ 为关于 $\rho_X$ 平方可积函数的希尔伯特空间。记 $\|\cdot\|_\rho$ 为由内积 $\langle f, g \rangle_\rho := \int_X f(x) g(x) \, d\rho_X(x)$ 在空间 $\mathcal{L}^2_{\rho_X}$ 中诱导的范数。Mercer 核 $K$ 在 $\mathcal{L}^2_{\rho_X}$(或 $\mathcal{H}_K$)上定义了一个积分算子 $L_K$,即

$$L_K(f) := \int_X f(x) K_x \, d\rho_X(x), \quad f \in \cdots$$

## 预备引理

在给出主要结果证明之前,我们先给出一些有用的引理。设 $k, t \in \mathbb{N}$。记

$$\pi_{t,k}^t(L) := \prod_{j=k}^t (I - G'_+(0) \eta_j L), \quad k \leq t, \quad \pi_{t,t+1}^t(L) := I,$$

对任意算子 $L: \mathcal{H} \mapsto \mathcal{H}$,其中 $\mathcal{H}$ 是希尔伯特空间,$I$ 表示 $\mathcal{H}$ 上的恒等算子。定义函数 $F_t: \mathbb{R} \mapsto \mathbb{R}$ 为

$$F_t(u) := \sum_{k=1}^t G'_+(0) \eta_k \pi_{k+1}^t(u).$$

利用 (1.5) 的迭代关系,可以容易地看出梯度下降算法可以改写为 $f_{1,D} = 0$,对 $t = 1, 2, \cdots, T$,

$$f_{t+1,D} = F_t(L_{K,D}) f_{\rho,D} + \sum_{k=1}^t \eta_k \pi_{k+1}^t(L_{K,D}) E_{k,D},$$

其中 $f_{\rho,D} := \frac{1}{|D|} \sum \cdots (x_i \cdots)$。

## 单数据集的误差分析

证明定理 2.1 的关键是误差分解。此处使用的策略与 [12] 中依赖于迭代关系的策略不同。相反,为呈现误差分解,我们需要引入一种新的辅助序列。序列 $\{g_{t,D}\}_t$ 定义为 $g_{1,D} = 0$,对 $t = 1, 2, \cdots, T$,

$$g_{t+1,D} := F_t(L_{K,D}) L_{K,D} f_\rho.$$

由三角不等式,我们有

$$\|L_K^\nu (f_{T+1,D} - f_\rho)\|_K \leq \|L_K^\nu (f_{T+1,D} - g_{T+1,D})\|_K + \|L_K^\nu (g_{T+1,D} - f_\rho)\|_K.$$

在本节中,我们将分别估计这两项。

### 总误差

### 分布式方法的误差分析

本节致力于对分布式梯度下降算法 (1.6) 的误差进行界定。类似于 [14, Proposition 4],我们有

$$\mathbb{E}\left[\|L_K^\nu (\overline{f}_{T+1,D} - f_\rho)\|_K^2\right] \leq \frac{1}{m^2} \sum_{j=1}^m \mathbb{E}\left[\|L_K^\nu (f_{T+1,D_j} - f_\rho)\|_K^2\right] + \frac{1}{m} \sum_{j=1}^m \|L_K^\nu (\mathbb{E}[f_{T+1,D_j}] - f_\rho)\|_K^2.$$

### 定理 2.2 的证明

设 $\lambda = |D|^{-\frac{1}{2r+\gamma}}$。由条件 (2.4),可以看出对每个固定的 $j \in \{1, 2, \cdots, m\}$,$|D_j| = \frac{|D|}{m} = |D|^{1-\xi} > |D|^{\frac{1}{2r+\gamma}}$。这保证了 $\lambda = |D_j|^{-\beta}$,其中 $\beta = \frac{1}{(2r+\gamma)(1-\xi)} \in (0,1)$。由引理 3.3,对任意 $0 < \delta < 1$,以至少 $1 - \delta/4$ 的置信度,

$$\Omega_{D_j} \leq C_2 \left(\frac{(2r+\gamma)(1-\xi)}{(2r+\gamma)(1-\xi)-1}\right) \log \frac{1}{6\delta}.$$

由 (2.4),$\cdots$

## 结论与讨论

本文聚焦于鲁棒核回归分布式梯度下降的理论分析,并在广泛的估计精度度量范围内推导了紧密的风险界。与我们工作最相关的前序工作是 [12],该文在 $f_\rho \in \mathcal{H}_K$ 时建立了算法 (1.5) 在 $\mathcal{L}^2_{\rho_X}$-范数和 RKHS 范数下的最优速率,但当正则性条件 (2.2) 在 $0 < r < 1/2$ 下满足(即 $f_\rho \notin \mathcal{H}_K$)时,仅获得了次优速率。我们的第一个结果,推论 2.1 改进了 $\cdots$

## 致谢

作者感谢匿名审稿人提出的建设性意见和建议,这些意见和建议显著提高了本文的质量。

通鸿志
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号