优化|优化处理可再生希尔伯特核空间的非参数回归中的协变量偏移

原文：Optimally tackling covariate shift in RKHS-based nonparametric regression. The Annals of Statistics, 51(2), pp.738-761, 2023.​
原文作者：Cong Ma, Reese Pathak, Martin J. Wainwright​
论文解读者：赵进

编者按：

在再生核希尔伯特空间（RKHS）框架下，本文深入研究了非参数回归的协变量转移问题。特别地，其集中讨论了两类主要的协变量转移问题，它们均由源与目标分布间的似然比所定义。当这些似然比受到均匀上界约束时，文章证明，对于一个具有规范化核特征值的广泛RKHS类，精确调整的正则化参数下的核岭回归（KRR）估计函数是极小极大最优的（仅有对数因子的差异）。值得注意的是，除其上确界外，KRR并不依赖于似然比的完整信息。接下来，针对似然比无上界限制但其第二矩有限的更复杂情况，文章提出了一种基于似然比率的有限截断策略的加权KRR估计方法。并且进一步证实，此估计方法在最小最大意义上达到了最优性，仅存在对数级的差异。

1. 问题背景

1.1 协变量转移下的非参数回归

非参数回归的主旨在于依赖于协变量向量$X\in \mathcal{X}$来预测实数值反应$Y$. 对于每一特定的$x$, 均方误差最优的估计器由回归函数$f^{\ast }(x):=\mathbb{E}[Y|X=x]$所描述. 在常规的研究背景中, 我们假设能观察到$n$个独立同分布的样本对 $\{(x_i,y_i){\}}_{i=1}^n$, 其中每个$x_i$是按照分布$P$在$\mathcal{X}$上抽样得到的，随后 $y_i$ 是根据条件概率 $(Y|X=x_i)$ 抽样得到的. 我们始终设定, 对于每一个$i$, 其残差${\omega }_i:=y_i-f^{\ast }(x_i)$是具有方差${\sigma }^2$的次高斯型随机变量.
我们将协变量空间上的分布$P$称为源分布. 在标准设定中, 估计函数$\hat{f}$的性能是根据其$L^2(P)$误差来衡量的：

$$\Vert \hat{f}-f^{\star }{\Vert }_P^2:={\mathbb{E}}_{X\sim P}(\hat{f}(X)-f^{\star }(X){)}^2={\int }_{\mathcal{X}}(\hat{f}(x)-f^{\star }(x){)}^{2}p(x)dx,$$

其中$p$是$P$的密度函数, $L^2(P)$是以$P$为概率测度的$L_2$空间.
在协变量转移下, 我们希望构建一个估计函数$\hat{f}$, 其$L^2(Q)$误差很小. 在此, 目标分布$Q$与源分布$P$不同. 从分析角度来看, 设$q$为$Q$的密度, 我们的目标是找到估计函数$\hat{f}$, 使
$$\Vert \hat{f}-f^{\star }{\Vert }_Q^2:={\mathbb{E}}_{X\sim Q}(\hat{f}(X)-f^{\star }(X){)}^2={\int }_{\mathcal{X}}(\hat{f}(x)-f^{\star }(x){)}^{2}q(x)dx$$
尽可能小. 显然，此问题的难度取决于源分布和目标分布之间的某种差异性.

1.2 源-目标似然比上的条件

我们通过似然比来衡量$L^2(P)$和$L^2(Q)$之间的差异:
$$\rho (x):=\frac{q(x)}{p(x)},$$

我们假设对于任意$x\in \mathcal{X}$, $\rho (x)$存在. 通过对似然比施加不同的条件, 我们可以定义不同的源-目标对 $(P,Q)$, 我们主要关注两种类型:

均匀$B$-有界 对于 $B\ge 1$, 我们称似然比是$B$-有界的, 如果
$$\underset{x\in \mathcal{X}}{\sup }\rho (x)\le B,$$

可以看到, $B=1$表示没有协变量转移的情况, 即$P=Q$.

${\chi }^2$-有界 实际中, 均匀有界条件往往过于严格, 我们有必要考虑更宽松的条件. 一个放宽的方法是在二阶矩上进行限制. 我们称似然比是$V^2$-时刻有界的, 如果
$${\mathbb{E}}_{X\sim P}\left[{\rho }^2(X)\right]\le V^2.$$

1.3 无权估计与似然加权估计的对比

本文关注基于在再生核定义的希尔伯特空间$\mathcal{H}$上优化的非参数回归方法。希尔伯特范数$\Vert f{\Vert }_{\mathcal{H}}$被用作对解决方案施加“平滑性”的手段，无论是通过向目标函数增加一个惩罚项还是通过明确的约束.

在似然比未知的情况下, 一个直接的方法是简单地计算无权的正则化估计值
$${\hat{f}}_{\lambda }:=\arg \underset{f\in \mathcal{H}}{\min }\left\{\frac{1}{n}\sum _{i=1}^n{\left(f\left(x_i\right)-y_i\right)}^2+\lambda \Vert f{\Vert }_{\mathcal{H}}^2\right\},$$

其中，$\lambda >0$是用户定义的正则化参数。当$\mathcal{H}$是一个再生核希尔伯特空间（RKHS）时，此估计被称为核岭回归（KRR）估计. 这是经验风险最小化的一种形式, 但在协变量转移存在的情境下, 目标涉及对 ${\mathbb{E}}_P[(Y-f(X){)}^2]$ 的经验近似, 而不是 ${\mathbb{E}}_Q[(Y-f(X){)}^2]$.

假如似然比已知，那么一个自然的建议是计算似然比加权的正则化估计，
$${\tilde{f}}_{\lambda }^{\mathrm{rw}}:=\arg \underset{f\in \mathcal{H}}{\min }\left\{\frac{1}{n}\sum _{i=1}^n\rho \left(x_i\right){\left(f\left(x_i\right)-y_i\right)}^2+\lambda \Vert f{\Vert }_{\mathcal{H}}^2\right\}.$$

引入似然比确保了目标现在提供了对期望值${\mathbb{E}}_Q\left[(Y-f(X){)}^2\right]$的无偏估计. 然而, 通过似然比进行重新加权也增加了方差，尤其是在似然比无界的情况下.

1.4 核函数及其特征值

任何RKHS都与一个半正定核函数$\mathcal{K}:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ 相关. Mercer定理保证该核函数具有以下形式的特征展开
$$\mathcal{K}\left(x,x^{\prime }\right)=\sum _{j=1}^{\infty }{\mu }_j{\varphi }_j(x){\varphi }_j\left(x^{\prime }\right).$$

其中, { μ j } j ≥ 1 \left\{\mu_j\right\}_{j \geq 1} {μj​}j≥1​为非负特征值序列, 而 { ϕ j } j ≥ 1 \left\{\phi_j\right\}_{j \geq 1} {ϕj​}j≥1​是在$L^2(Q)$中正交的特征函数.

基于Mercer定理, RKHS范数的平方可以表示为:
$$\Vert f{\Vert }_{\mathcal{H}}^2=\sum _{j=1}^{\infty }\frac{{\theta }_j^2}{{\mu }_j},{\theta }_j={\int }_{\mathcal{X}}f(x){\varphi }_j(x)q(x)dx.$$

因此, 该希尔伯特空间$\mathcal{H}$可以表示为
$$\mathcal{H}:=\left\{f=\sum _{j=1}^{\infty }{\theta }_j{\varphi }_j\mid \sum _{j=1}^{\infty }\frac{{\theta }_j^2}{{\mu }_j}<\infty \right\}.$$

这篇论文的结果要求核函数$\kappa$-均匀有界. 具体来说, 存在一个有限常数$\kappa >0$, 以下条件成立:
$$\underset{x\in \mathcal{X}}{\sup }\mathcal{K}(x,x)\le {\kappa }^2.$$

值得注意的是, 任何在紧致域上连续的核函数自然满足上述条件. 此外, 在实践中广泛使用的许多核，例如高斯核和拉普拉斯核, 都在各自的定义域上满足此条件.

2. 对有界似然比的分析

2.1 无权核岭回归接近最优

在这一节中, 首先推导出在协变量转移下的核岭回归估计函数的一系列上界. 结合之后的分析, 这些界限将证实对于具有有界似然比的协变量转移, KRR估计是仅相差对数项的最小最大优的.

定理1 考虑一个均匀$B$-有界的似然比, 在一个$\kappa$-均匀有界核的希尔伯特空间上的协变量转移回归问题. 那么, 对于任意的 $\lambda \ge 10{\kappa }^2/n$, 核岭回归估计 ${\hat{f}}_{\lambda }$ 满足以下界限
$$\Vert \widehat{f_{\lambda }}-f^{\star }{\Vert }_Q^2\le \underset{{\mathbf{b}}_{\lambda }^2(B)}{\underbrace{4\lambda B{\Vert f^{\star }\Vert }_{\mathcal{H}}^2}}+\underset{{\mathbf{v}}_{\lambda }(B)}{\underbrace{80{\sigma }^{2}B\frac{\log n}{n}\sum _{j=1}^{\infty }\frac{{\mu }_j}{{\mu }_j+\lambda B}}},$$

概率至少为 $1-28\frac{{\kappa }^2}{\lambda }{e}^{-\frac{n\lambda }{16{\kappa }^2}}-n^{-10}.$

该上界主要包含两项. 首项${\mathbf{b}}_{\lambda }^2(B)$描述了KRR估计的平方偏差, 此偏差随着正则化参数$\lambda$和似然比界$B$的增加而成比例增长. 其次,${\mathbf{v}}_{\lambda }(B)$刻画了KRR估计器的估计方差, 它在$\lambda$的增长下呈现减小的趋势, 从而暗示$\lambda$在调控偏差与方差之间的平衡中起到了核心作用.

接下来进一步分析导致最优${\lambda }^{\ast }(B)$的平衡过程. 对于具有规则特征值的核, 这一过程可以更容易地理解. 对于给定的目标误差$\delta >0$, 考虑描述第一个低于${\delta }^2$的特征值的指标$d(\delta )$, 即 d ( δ ) : = min ⁡ { j ≥ 1 ∣ μ j ≤ δ 2 } d(\delta) := \min\{j\geq1 | \mu_j\leq\delta^2\} d(δ):=min{j≥1∣μj​≤δ2}. 特征值序列被称为正则的，如果
$$\sum _{j=d(\delta )+1}^{\infty }{\mu }_j\le cd(\delta ){\delta }^2,$$

对某常数$c$成立. 正则特征值核的包括有限秩核以及特征值在多项式或指数层面上呈现逐渐衰减的核, 这些核广泛应用于实际中. 对于带有正则特征值的核函数, 我们可以证明存在常数$c^{\prime }$使得
$$\Vert {\hat{f}}_{\lambda }-f^{\star }{\Vert }_Q^2\le c^{\prime }\left\{{\delta }^2{\Vert f^{\star }\Vert }_{\mathcal{H}}^2+{\sigma }^{2}B\frac{d(\delta )\log n}{n}\right\},{\delta }^2=\lambda B.$$

2.2 带有协变量偏移的正则核的下界

上一节我们为非加权的KRR估计建立了上界. 这一节我们证明对于具有正则特征值的核, 非加权KRR估计函数所实现的界是极小极大最优的.

定理2 对于任意的$B\ge 1$, 存在一对似然比为$B$-有界的分布$(P,Q)$, 以及在$L^2(Q)$中的一组正交基 { ϕ j } j ≥ 1 \{\phi_j\}_{j \geq 1} {ϕj​}j≥1​$使得对于任意的正则核特征值序列$ { μ j } j ≥ 1 \{\mu_j\}_{j \geq 1} {μj​}j≥1​, 有
$$\underset{\hat{f}}{\inf }\underset{f^{\star }\in {\mathcal{B}}_{\mathcal{H}}(1)}{\sup }\mathbb{E}[\Vert \hat{f}-f^{\star }{\Vert }_Q^2]\ge c\underset{\delta >0}{\inf }\left\{{\delta }^2+{\sigma }^{2}B\frac{d(\delta )}{n}\right\}.$$

与2.1节末的结果相比, 我们观察到当选择合适的正则化参数$\lambda$时, KRR 估计函数实现了极小极大最优 (仅相差对数项).

3. 对无界似然比的分析

到目前为止，我们的分析都基于$B$-有界的似然比. 但实际上似然比往往是无界的. 以一个简单的单变量例子为证，假设目标分布$Q$是标准正态分布$\mathcal{N}(0,1)$, 而源分布$P$为 $\mathcal{N}(0,0.9)$. 不难发现, 随着$|x|$趋于无穷，似然比 $\rho (x)$也趋于无穷。在1.2节中我们提到，用似然加权估计器的一个担忧是它们可能导致方差的大幅膨胀, 特别是乘以可能无界的似然比$\rho (x)$. 因此, 我们考虑将$\rho (x)$截断: 更具体地说, 对于给定的${\tau }_n>0$, 我们定义截断后的似然比为
$${\rho }_{{\tau }_n}(x):=\{\begin{array}{ll}\rho (x)& \text{ if }\rho (x)\le {\tau }_n\\ {\tau }_n& \text{ otherwise }\end{array}$$

并定义截断加权KRR估计函数:
$${\hat{f}}_{\lambda }^{\mathrm{rw}}:=\arg \underset{f\in \mathcal{H}}{\min }\left\{\frac{1}{n}\sum _{i=1}^n{\rho }_{{\tau }_n}\left(x_i\right){\left(f\left(x_i\right)-y_i\right)}^2+\lambda \Vert f{\Vert }_{\mathcal{H}}^2\right\},$$

其中$\lambda >0$和 ${\tau }_n$待定.
在核的特征函数均匀有界时, 我们对估计函数进行了分析. 核特征函数均匀有界指
$${\Vert {\varphi }_j\Vert }_{\infty }:=\underset{x\in \mathcal{X}}{\sup }\left|{\varphi }_j(x)\right|\le 1\forall j=1,2,\dots$$

关于截断加权KRR估计函数的定理涉及核复杂性函数 $\Psi (\delta ,\mu )={\sum }_{j=1}^{\infty }\min \left\{{\delta }^2,{\mu }_j{\Vert f^{\star }\Vert }_{\mathcal{H}}^2\right\}$, 并适用于任意满足不等式 $\mathcal{M}(\delta )<\frac{{\delta }^2}{2}$ 的解 ${\delta }_n>0$, 其中:
$$\mathcal{M}(\delta ):=c_0\sqrt{\frac{{\sigma }^2{V}^2{\log }^3(n)}{n}\Psi (\delta ,\mu )}.$$

定理3 考虑均匀有界的特征函数的核, 以及满足${\mathbb{E}}_P[\rho (x{)}^2]\le V^2$的源-目标分布. 进一步假设噪声的方差满足 ${\sigma }^2\le {\kappa }^2\Vert f^{\star }{\Vert }_{\mathcal{H}}^2$. 那么, 有截断阈值${\tau }_n=\sqrt{n{V}^2}$ 和正则化参数$\lambda {\Vert f^{\star }\Vert }_{\mathcal{H}}^2\ge {\delta }_n^2/3$的估计函数 ${\hat{f}}_{\lambda }^{rw}$ 有上界:
$$\Vert {\hat{f}}_{\lambda }^{\mathrm{rw}}-f^{\star }{\Vert }_Q^2\le {\delta }_n^2+3\lambda {\Vert f^{\star }\Vert }_{\mathcal{H}}^2,$$

其概率为$1-n^{-10}$.

参考文献

[1] Cong Ma, Reese Pathak, Martin J. Wainwright “Optimally tackling covariate shift in RKHS-based nonparametric regression,” The Annals of Statistics, Ann. Statist. 51(2), 738-761, (April 2023)