在学习理论的文章中, 算法的样本$ {\bf z} = \{(x_i, y_i)\}_{i = 1}^T $通常是独立同分布的(来自相同分布且相互独立的).在实际问题中, 这一假设往往不成立(具体例子在正文给出).基于非一致抽样下的研究, 较早见于Smale, Zhou^[1]的工作, 主要探讨最小二乘回归下的在线学习. Steinwart等^[2]研究了和支持向量机有关的批量学习. Hu, Zhou^[3]探讨了一般损失函数的非一致在线学习算法, 他们的分析可用于回归和分类等学习问题.本文在非一致分布背景下, 研究在线分位数回归算法, 通过带有阈值$ \epsilon $-pinball损失函数产生稀疏性, 以中位数回归为代表, 得到算法的收敛阶.

假设输入空间$ (X, d) $是$ R^n $中的紧度量空间, 输出空间$ Y\subset R $, 样本空间$ Z = X\times Y $.非一致分布下, 每一学习时刻$ t = 1, 2, \cdots $产生的样本点$ z_t = (x_t, y_t)\in Z $服从联合概率分布$ \rho^{(t)}(x, y), \ (x, y)\in Z, $这里序列$ \{\rho^{(t)}\}_{t = 1, 2, \cdots} $不一定相同.在Smale, Zhou^[1]提出的学习框架下, 假设在$ X $上的边缘分布序列$ \{\rho_X^{(t)}\}_{t = 1, 2, \cdots} $以多项式速度收敛于Hölder空间$ C^s(X)\; (0<s \leq 1) $的对偶空间$ (C^s(X))^* $^{[1, 3]}, Hölder空间$ C^s(X) $是由定义在$ X $上所有连续函数组成的空间, 其范数

$ \left\| f\right\|_{C^s(X)} = \left\| f\right\|_{C(X)}+\left|f\right|_{C^s(X)}, \ \left|f\right|_{C^s(X)}: = \sup \limits_{\substack{x\neq x', \\x, x'\in X}} \frac{\left|f(x)-f(x')\right|}{(d(x, x'))^s}, \ 0\leq s \leq 1. $

定义1.1   称概率分布序列$ \{\rho_X^{(t)}\}_{t = 1, 2, \cdots} $以多项式速度收敛于$ (C^s(X))^* $中的概率分布$ \rho_X $.如果存在$ C>0, b>0 $使得

$ \begin{equation} \left \| \rho_X^{(t)} - \rho_X \right \| _{(C^s(X))^*} \leq Ct^{-b}, t \in\mathbb{N}. \end{equation} $

(1.1)

由对偶空间$ (C^s(X))^* $的定义, 条件$ (1.1) $等价于

$ \begin{equation} \left|\int_Xf(x)d\rho_X^{(t)}-\int_Xf(x)d\rho_X\right|\leq Ct^{-b}\left\| f\right\|_{C^s(X)}, \forall f\in C^s(X), t\in \mathbb{N}, \end{equation} $

(1.2)

指数$ b $衡量不同分布的差异程度, 当$ b = \infty $时, 条件$ (1.1) $是独立同分布.

对于满足衰减条件$ (1.1) $的实际情况已在文献[1, 3]有详细讨论.例如, 真实的抽样分布$ \rho_X $被噪声干扰并且随着时间$ t $增加而噪声水平下降, 那么在不同时刻对应的抽样概率分布$ \{\rho_X^{(t)}\} $收敛于$ \rho_X $.另外, 通过迭代和随机密度核形成的积分算子, 反映了由动力系统诱导出不同分布的表现形式.这些例子都说明研究满足$ (1.1) $衰减的分布是具有实际应用性的.

对于任意的$ 0<\tau<1 $, 定义随机变量$ Y $的$ \tau $分位数函数$ Q(\tau) $为

$ Q(\tau) = \inf\{y:F(y)\geqslant\tau\}, $

其中$ F(y) $是$ Y $的分布函数. Koenker, Bassett^[4]提出线性分位数回归理论, 扩展了经典的最小二乘回归. Koenker^[5]进一步提出分位数回归可提供更多关于因变量的分布信息, 例如:长尾性、厚尾性、多峰性.分位数回归描述因变量的条件分布, 不仅仅分析因变量的条件期望, 并且对不同$ \tau $刻画了概率分布的具体性质.

在学习理论框架下, $ \rho $是$ Z $上的一个Borel概率测度.给定$ x\in X $时, $ \rho _x(y), y\in Y $是$ \rho $的条件概率分布.分位数回归的目标函数$ f_{\rho, \tau}(x) $在$ x $的值定义为: $ \rho _x(\cdot) $的$ \tau $ -分位数是$ v $, 即存在$ v\in Y $满足

$ \begin{align} \rho_x(\{y\in Y:y\leqslant v\})\geqslant \tau \text{ 且 }\; \rho_x(\{y\in Y:y\geqslant v\})\geqslant 1-\tau. \end{align} $

(1.3)

当$ \tau = \frac{1}{2} $时, 分位数回归就是中位数回归, 中位数回归在分位数回归中占有相当重要的地位.我们知道, 当$ \rho _x(\cdot) $关于中位数对称时, 中位数回归即为条件概率的均值, 对应于经典最小二乘法.一般分位数回归, 对应的损失函数是pinball损失$ V = V^{\tau}:\mathbb{R}\rightarrow \mathbb{R_+} $ (见文献[6]),

$ \begin{align} V^{\tau}(u) = \begin{cases} (1-\tau)u, &u>0, \\ -\tau u, &u\leqslant 0. \end{cases} \end{align} $

(1.4)

为了对分位数回归算法产生稀疏性, 引入阈值$ \epsilon>0 $生成的$ \epsilon $-pinball损失$ V^{\tau}_{\epsilon} $定义为

$ \begin{align} V^{\tau}_{\epsilon}(u) = \begin{cases} (1-\tau)(u-\epsilon), &u>\epsilon, \\ -\tau (u+\epsilon), &u\leqslant -\epsilon, \\ 0, &\text{其它}. \end{cases} \end{align} $

(1.5)

当$ \tau = \frac{1}{2} $, $ V^{\tau}_{\epsilon} $就是$ \epsilon $ -不敏感损失函数.当估计值与真值的偏差小于$ \epsilon $时, 损失为零.当$ \epsilon $比较大时, 导致结果的正确率会略有下降, 但是数据的训练、测试和参数选择速度均会提高, 尤其在大规模数据集上, 这种优势会更加明显. $ \epsilon $-pinball损失函数$ V^{\tau}_{\epsilon} $在支持向量机算法中应用广泛, 因此将$ V^{\tau}_{\epsilon} $和在线学习算法结合研究并给出收敛阶, 具有实际应用价值.

再生核Hilbert空间(RKHS)是由Mercer核$ K:X\times X\rightarrow R $诱导出来的, $ K $是一个连续对称函数, 并且对于任意有限点集$ \{x_1, x_2, \cdots, x_l\}\subset X $生成的矩阵$ (K(x_i, x_j))_{i, j = 1}^l $是半正定的.由函数集$ \{K_x = K(x, \cdot):x\in X\} $张成的完备线性闭包空间RKHS记为$ \mathcal{H}_K $ (Aronszajn, 1950^[7]), 记内积为$ \left<K_x, K_y\right>_K = K(x, y) $.在线算法也称随机梯度下降算法(SGD)与批次算法中样本一次性传给机器不同, 在线算法的训练样本是按时间$ t $顺序依次传送给机器, 对算法不断修正, 提高学习效率.在线算法由于低复杂度, 在流式数据和大规模计算中有广泛的应用.具体可参考文献[8].

定义1.2   与RKHS有关的在线分位数回归算法定义为

$ \begin{align} \begin{split} f_1& = 0, \\ f_{t+1}& = \begin{cases} (1-\lambda_{t}\eta_{t})f_{t}-(1-\tau)\eta_{t}K_{x_t}, &f_t(x_t)-y_t>\epsilon, \\ (1-\lambda_{t}\eta_{t})f_{t}+\tau\eta_{t}K_{x_t}, &f_t(x_t)-y_t\leqslant-\epsilon, \\ (1-\lambda_{t}\eta_{t})f_{t}, &-\epsilon< f_t(x_t)-y_t\leqslant\epsilon, \end{cases} \end{split} \end{align} $

(1.6)

其中$ t $是学习时间, $ \lambda_t>0 $称为正则参数, $ \eta_t>0 $是步长.

在线算法$ (1.6) $中, 正则参数$ \lambda_t $随着学习时间$ t $变化并且$ \lambda_{t+1}\leqslant\lambda_t, \forall \; t\in \mathbb{N} $.当$ \lambda_t\equiv \lambda_1 $时, $ \lambda_t $不会随着步数$ t $变化而变化, 此时称$ (1.6) $为不完全在线算法.

高斯函数在统计学领域, 用于表述正态分布; 在信号处理领域, 用于定义高斯滤波器; 在图像处理领域, 二维高斯核函数常用于高斯模糊; 在数学领域, 主要是用于解决热力方程和扩散方程.高斯核函数作为最常用的径向基函数, 在支持向量机等算法中的应用可以将数据映射到高维甚至无穷维.由于高斯核具有良好的性质和应用广泛, 因此将高斯核应用于以下与中位数回归有关的在线算法$ (1.6) $中.

对于$ f:X\rightarrow \mathbb{R} $的泛化误差定义为

$ \mathcal{E}^\epsilon(f) = \int_ZV^{\tau}_{\epsilon}(y-f(x))d\rho = \int_X\int_YV^{\tau}_{\epsilon}(y-f(x))d\rho_x(y)d\rho_X, $

其中$ f^{V^{\tau}_{\epsilon}}_\rho $是$ \mathcal{E}^\epsilon(f) $在全体可测函数中的极小化值.特别的, 当$ \epsilon = 0 $, 记$ \mathcal{E}(f): = \mathcal{E}^0(f) $, $ f^{V^{\tau}}_\rho: = f^{V^{\tau}_{0}}_\rho $.本文中, $ f^{V^{\tau}}_\rho $是算法$ (1.6) $的目标函数.以下定理提供了算法$ (1.6) $的学习收敛率, 其证明将在2.2节给出.

定理2.1   假设以下假设均成立

1. RKHS $ {\cal H}_K $由高斯函数$ K(x, x') = e^{-\frac{\|x-x'\|^2}{2\sigma^2}}\; , \ \forall\; x, x'\in X, \ \sigma>0 $产生;

2.分位数参数$ \tau = \frac{1}{2} $;

3.正则条件$ f^{V^{\tau}}_\rho = L^r_K(g_\rho) $, 其中$ L^r_K $是紧算子, $ g_\rho\in L^2_{\rho_X}(X) $, $ L_K $是积分算子$ L^2_{\rho_X} $: $ L_Kf(x) = \int_XK(x, v)f(v)d\rho_X(v), \ x\in X $, 成立且$ r>\frac{1}{2} $;

4.关于$ \{\rho^{(t)}_X\} $的多项式收敛条件$ (1.1) $成立;

5. $ \forall\; x\in X $, 条件分布$ \rho_x(\cdot) $是区间$ [f_\rho(x)-1, f_\rho(x)+1] $上的一致分布.

如果$ \lambda_1<\frac{(\|g_\rho\|_{L^2_{\rho_X}})^{\frac{2}{1-2r}}}{2}, \eta_1>0, 0\leq\epsilon\leq\lambda_T^{\frac{2}{s}}, $则有

当$ 1<r\leqslant \frac{3}{2}, \ \ \lambda_T = \lambda_1T^{-\frac{2}{6r+1}}, \eta_T = \eta_1T^{-\frac{4r}{6r+1}} $时,

$ \begin{align} \mathbb{E}_{z_1, z_2, \cdots, z_T}(\|f_{T+1}-f^{V^{\tau}}_\rho\|_K)\leqslant \tilde{C_1}T^{-\min\left\{\frac{2r-1}{6r+1}, \frac{b}{2}-\frac{2}{6r+1}\right\}}. \end{align} $

(2.1)

当$ \frac{1}{2}<r\leqslant 1, \ \ \lambda_T = \lambda_1T^{-\frac{1}{3r+2}}, \ \eta_T = \eta_1T^{-\frac{2r+1}{3r+2}} $时,

$ \begin{align} \mathbb{E}_{z_1, z_2, \cdots, z_T}(\|f_{T+1}-f^{V^{\tau}}_\rho\|_{L^2_{\rho_X}})\leqslant \tilde{C}_2T^{-\min\left\{\frac{r}{3r+2}, \frac{b}{2}-\frac{1}{3r+2}\right\}}, \end{align} $

(2.2)

其中$ \tilde{C}_1 $和$ \tilde{C}_2 $是与$ T $无关的常数, 将在证明过程中给出.

注1   该定理反应了中位数回归的在线算法收敛速度, $ (2.1) $式说明了在线算法$ (1.6) $在$ {\cal H}_K $的收敛性, 称为强收敛; 而结果$ (2.2) $称为算法的平均误差.由范数关系$ \|\cdot\|_{L^2_{\rho_X}}\leq \|\cdot\|_{K} $知道本定理结果$ (2.1) $和$ (2.2) $是合理的.虽然本定理是考虑$ \tau = \frac{1}{2} $, 但是从后面的证明过程知道本定理结果可以推广到任意$ 0<\tau<1 $, 只需要修改常数$ \tilde{C}_1 $和$ \tilde{C}_2 $.

注2   在线算法$ (1.6) $的误差估计分为抽样误差和逼近误差两部分, 其中抽样误差是本文的主要贡献, 将在定理2.3中给出; 逼近误差由$ {\cal H}_K $空间的复杂度和数据的分布$ \rho $决定.假设5采用一致分布估计逼近误差.事实上本定理适用于其他更一般的条件分布, 为了简化本定理, 不再进一步讨论.具体可参考文献[2, 3].

注3   当$ b = \infty $, $ (2.1) $和$ (2.2) $式反映了数据抽样$ \bf z $是独立同分布的情况.另外, 我们看到$ \epsilon = 0 $时, 本定理推导出无稀疏性的在线分位数回归算法的收敛阶, 可以通过调节$ \epsilon $的值控制算法的稀疏性同时不影响算法的收敛率.

定义2.2   对于$ \lambda>0 $, 正则化函数$ f^{V^{\tau}_{\epsilon}}_{\lambda}\in \mathcal{H}_K $定义为

$ \begin{align} f^{V^{\tau}_{\epsilon}}_{\lambda}: = {\hbox{arg}} \inf \limits_{f\in \mathcal{H}_K}\left\{\mathcal{E}^\epsilon(f)+\frac{\lambda}{2}\|f\|^2_K\right\}. \end{align} $

(2.3)

逼近误差$ \mathcal{D}(\lambda) $定义为

$ \begin{align} \mathcal{D}(\lambda): = \inf\limits_{f\in \mathcal{H}_K}\left\{\mathcal{E}(f)-\mathcal{E}(f^{V^\tau}_\rho)+\frac{\lambda}{2}\left\|f\right\|^2_K\right\}. \end{align} $

(2.4)

以下定理给出一般分位数回归算法的抽样误差$ f_{T+1}-f^{V^{\tau}_{\epsilon}}_{\lambda_T} $.

定理2.3   如果以下假设成立

1.核函数$ K $与定理2.1相同;

2. $ \{\rho^{(t)}_X\}_{t = 1, 2, \cdots} $以多项式速度收敛到$ (C^s(X))^* $中的$ \rho_X $, 即$ (1.1) $成立;

3.分布$ \{\rho_x:x\in X\} $在$ (C^s(X))^* $中是Lipschitz$ \ s $的, 即存在一个常数$ C_\rho\geqslant 0 $, 使得

$ \begin{align} \|\rho_x-\rho_u\|_{(C^s(Y))^*}\leqslant C_\rho(d(x, u))^s, \ \ \forall\; x, u\in X. \end{align} $

(2.5)

4.逼近误差满足多项式衰减如下

$ \begin{align} \mathcal{D}(\lambda)\leqslant \mathcal{D}_0\lambda^\beta, \ \ 0<\beta\leqslant 1, \mathcal{D}_0>0. \end{align} $

(2.6)

令

$ \begin{align*} &\lambda_t = \lambda_1t^{-\gamma}, \ \eta_t = \eta_1t^{-\alpha}, \ \ 0<\lambda_1, \eta_1<1, \\ &0<\gamma<\frac{2}{5-\beta}, \ \ \gamma<\alpha<1-\frac{\gamma(3-\beta)}{2}, \ \ \epsilon\leq \lambda^\beta, \end{align*} $

则有

$ \begin{align*} \mathbb{E}_{z_1, z_2, \cdots, z_T}(\|f_{T+1}-f^{V^{\tau}_{\epsilon}}_{\lambda_T}\|^2_K)\leqslant C_{K, \rho, b, \beta}T^{-\theta}, \end{align*} $

其中

$ \begin{align*} \theta: = \min\{2-\gamma(3-\beta)-2\alpha, \alpha-\gamma, b-2\gamma\}, \end{align*} $

$ C_{K, \rho, b, \beta} $是独立于$ T $的一个常数且在证明中给出.

证  本定理的证明借助了Hu, Zhou^[3]的证明思想.以下给出证明的主要步骤, 更详细的过程参见Hu, Zhou^[3]的定理26.证明分为三个步骤.

第一步  存在常数$ \kappa_{2s}>0 $,

$ \begin{align*} |K(x, x)-2K(x, u)+K(u, u)|\leqslant \kappa^2_{2s}(d(x, u))^{2s}, \ \ \forall x, u\in X. \end{align*} $

由$ K(x, x) = K(u, u) = 1 $, 得

$ \begin{align} &|K(x, x)-2K(x, u)+K(u, u)| = 2-2e^{-\frac{\|x-u\|^2}{2\sigma^2}} \leqslant \frac{\|x-u\|^2}{\sigma^2}. \end{align} $

(2.7)

又$ (d(x, u))^{2s} = \|x-u\|^{2s} $, 可令$ s = 1 $, 即存在$ \kappa_{2s} \geqslant \frac{1}{\sigma}>0 $, 使得$ (2.7) $式成立.

第二步  由Ying, Zhou^[8]引理3知

$ \begin{align} \mathbb{E}_{z_t}(\|f_{t+1}-f^{V^\tau_\epsilon}_{\lambda_t}\|^2_K)\leqslant (1-\eta_t\lambda_t)\|f_t-f^{V^\tau_\epsilon}_{\lambda_t}\|^2_K+2\eta_t\Delta_t+\eta^2_t \mathbb{E}_{z_t}\|\partial V^\tau_\epsilon(y_t, f_t(x_t))K_{x_t}+\lambda_tf_t\|^2_K, \end{align} $

(2.8)

其中

$ \begin{align*} \Delta_t = \int_Z\{V^\tau_{\epsilon}(y, f^{V^{\tau}_{\epsilon}}_{\lambda_t}(x))-V^{\tau}_{\epsilon}(y, f_t(x))\}d[\rho^{(t)}-\rho]. \end{align*} $

因此需要估计$ \Delta_t $的上界(参考文献[3]).不难证明存在常数$ C_{V^\tau_\epsilon, \gamma, \alpha}>0 $, 使得$ \|f_t\|_\infty\leqslant \frac{C_{V^\tau_\epsilon, \gamma, \alpha}}{\lambda_t}, \ \ t = 1, 2, \cdots, T+1 $.根据$ V^\tau_\epsilon $关于第二变量的一阶Taylor展开, 可知

$ \begin{align} \Delta_t&\leqslant \left\{(1+\kappa_{2s})\left(\sqrt{\frac{2\|V^\tau_\epsilon\|_\infty}{\lambda_t}} +\frac{C_{V^\tau_\epsilon, \gamma, \alpha}}{\lambda_t}\right)N(\lambda_t)+2C_\rho\tilde{N}(\lambda_t)\right\}\|\rho^{(t)}_X-\rho_X\|_{(C^s(X))^*}\\ &\leqslant B^*_t: = Ct^{-b}\left\{(1+\kappa_{2s})\left(\sqrt{\frac{2\|V^\tau_\epsilon\|_\infty}{\lambda_t}} +\frac{C_{V^\tau_\epsilon, \gamma, \alpha}}{\lambda_t}\right)N(\lambda_t)+2C_\rho\tilde{N}(\lambda_t)\right\}, \end{align} $

(2.9)

这里

$ \begin{align*} &N(\lambda) = \sup\left\{|\partial V^\tau_\epsilon(y, f)|:y\in Y, |f|\leqslant \max\left\{C_{V^\tau_\epsilon, \gamma, \alpha}/\lambda, \kappa \sqrt{2\|V^\tau_\epsilon\|_\infty/\lambda}\right\}\right\}, \\ &\tilde{N}(\lambda) = \sup\left\{\|V^\tau_\epsilon(y, f)\|_{C^s(Y)}:y\in Y, |f|\leqslant \max\left\{C_{V^\tau_\epsilon, \gamma, \alpha}/\lambda, \kappa \sqrt{2\|V^\tau_\epsilon\|_\infty/\lambda}\right\}\right\}. \end{align*} $

将估计$ (2.9) $式代入$ (2.8) $式得

$ \begin{align} \mathbb{E}(\|f_{t+1}-f^{V^\tau_\epsilon}_{\lambda_t}\|^2_K)\leqslant (1-\eta_t\lambda_t) \mathbb{E}_{z_1, z_2, \cdots, z_{t-1}}(\|f_t-f^{V^\tau_\epsilon}_{\lambda_t}\|^2_K) +\eta^2_t(N(\lambda_t)+C_{V^\tau_\epsilon, \gamma, \alpha})^2+2\eta_tB^*_t. \end{align} $

(2.10)

第三步  根据$ \|\partial V\|_\infty<\infty $, 知必然存在常数$ C' $, 使得$ N(\lambda)\leqslant C' , \tilde{N}(\lambda)\leqslant C'\lambda $.同时, 注意到当$ \epsilon\leqslant\lambda^\beta $, 可以引用文献[9]中引理3(b), 得到

$ {\cal D}_\epsilon(\lambda): = \inf\limits_{f\in \mathcal{H}_K}\left\{\mathcal{E}(f)-\mathcal{E}(f^{V^\tau_\epsilon}_\rho)+\frac{\lambda}{2}\left\|f\right\|^2_K\right\} \leqslant {\cal D}(\lambda)+2\epsilon\leqslant ({\cal D}_0+2)\lambda^\beta. $

所以用文献[3]定理20的结果, 得到

$ \begin{align*} \|f^{V^\tau_\epsilon}_{\lambda_t}-f^{V^\tau_\epsilon}_{\lambda_{t-1}}\|_K\leqslant 2\sqrt{\mathcal{D}_0+2}\lambda^{\frac{\beta-1}{2}}_1(t-1)^{\frac{\gamma(1-\beta)}{2}-1}\leqslant 4\sqrt{\mathcal{D}_0+2}\lambda^{\frac{\beta-1}{2}}_1t^{\frac{\gamma(1-\beta)}{2}-1}. \end{align*} $

将上述估计插入$ (2.10) $式, 并按$ t = T, \cdots, 1 $顺序进行迭代, 得到本定理结论.

证  将误差$ f_{T+1}-f^{V^{\tau}}_\rho $分解为三项: $ f_{T+1}-f^{V^\tau_\epsilon}_{\lambda_T} $, $ f^{V^\tau_\epsilon}_{\lambda_T}-f^{V^\tau}_{\lambda_T} $和$ f^{V^\tau}_{\lambda_T}-f^{V^{\tau}}_\rho $.

首先, 根据条件5和在文献[10]例6知道, 在正则条件$ f^{V^{\tau}}_\rho = L^r_K(g_\rho) $下

$ \begin{align*} &\|f^{V_{\tau}}_{\lambda_T}-f^{V^{\tau}}_\rho\|_K\leqslant \left(\frac{\lambda_T}{2}\right)^{r-\frac{1}{2}}\|g_\rho\|_{L^2_{\rho_X}}, \ \ \frac{1}{2}<r\leqslant\frac{3}{2}, \\ &\|f^{V_{\tau}}_{\lambda_T}-f^{V^{\tau}}_\rho\|_{L^2_{\rho_X}}\leqslant \left(\frac{\lambda_T}{2}\right)^r\|g_\rho\|_{L^2_{\rho_X}}, \ \ 0<r\leqslant 1. \end{align*} $

接下来, 关于第二项$ f^{V^\tau_\epsilon}_{\lambda_T}-f^{V^\tau}_{\lambda_T} $的估计, 由Hu, Xiang等^[11]性质1知

$ \begin{align*} \|f^{V^\tau_\epsilon}_{\lambda_T}-f^{V^\tau}_{\lambda_T}\|_K\leq C_\rho\epsilon^s\lambda_T^{-1} = C_\rho\lambda^{-1}_1\epsilon^sT^\gamma. \end{align*} $

关于第一项$ f_{T+1}-f^{V^\tau_\epsilon}_{\lambda_T} $的估计需要借助定理2.3.逐条验证定理2.3的条件1–4, 显然在定理2.1的条件下, 定理2.3的条件1–2成立.

注意到$ \|f^{V^{\tau}}_\rho\|_K\leqslant \|g_\rho\|_{L^2_{\rho_X}} $和$ \|f^{V^{\tau}}_\rho\|_{C^s(X)}\leqslant (1+\kappa_{2s})\|f_\rho\|_K $, $ \rho_x, \rho_u $均为均匀分布, 则$ \forall\; x, u\in X, g\in C^s(Y) $, 有

$ \begin{align*} \left|\int_Yg(y)d(\rho_x-\rho_u)\right|& = \frac{1}{2}\left|\int^{f_\rho(x)+1}_{f_\rho(x)-1}g(y)dy-\int^{f_\rho(u)+1}_{f_\rho(u)-1}g(y)dy\right|\\ &\leqslant \|g\|_{C(Y)}|f_\rho(x)-f_\rho(u)|\\ &\leqslant \|g\|_{C(Y)}(1+\kappa_2)\|g_\rho\|_{L^2_{\rho_X}}(d(x, u)). \end{align*} $

Lipschitz $ s $连续条件$ (2.5) $, 其中$ C_\rho = (1+\kappa_{2s})\|g_\rho\|_{L^2_{\rho_X}} $.即定理2.3的条件3满足.

关于定理2.3的条件4, 因为正则指数$ r\geqslant\frac{1}{2} $, $ \ f^{V^\tau}_\rho\in{\cal H}_K $, 所以$ {\cal D}(\lambda)\leqslant \lambda\|f^{V^\tau_\rho}\|_K^2, $即$ (2.6) $式成立且$ \beta = 1 $, $ {\cal D}_0 = \|f^{V^\tau}_\rho\|_K^2 $.综上, 可得

$ \mathbb{E}_{z_1, z_2, \cdots, z_T}(\|f_{T+1}-f^{V^{\tau}_{\epsilon}}_{\lambda_T}\|^2_K)\leqslant C_{K, \rho, b, \beta}T^{-\theta^*}, $

这里$ \theta^*: = \min\{2-2\gamma-2\alpha, \alpha-\gamma, b-2\gamma\}. $

根据以上推导得到

$ \begin{align} & \mathbb{E}_{z_1, z_2, \cdots, z_T}(\|f_{T+1}-f^{V^\tau}_\rho\|_K)\\ \leqslant& \mathbb{E}_{z_1, z_2, \cdots, z_T}(\|f_{T+1}-f^{V^{\tau}_{\epsilon}}_{\lambda_T}\|_K)+ \|f^{V^\tau_\epsilon}_{\lambda_T}-f^{V^\tau}_{\lambda_T}\|_K +\|f^{V^\tau}_{\lambda_T}-f^{V^{\tau}}_\rho\|_K\\ \leqslant& \sqrt{C_{K, \rho, b, \beta}}T^{-\frac{\theta^*}{2}}+C_\rho\lambda^{-1}_1\epsilon^sT^\gamma+\lambda^{r-\frac{1}{2}}_T\|g_\rho\|_{L^2_{\rho_X}}, \ \ 1<r\leqslant \frac{3}{2}, \end{align} $

(2.11)

$ \begin{align} & \mathbb{E}_{z_1, z_2, \cdots, z_T}(\|f_{T+1}-f^{V^\tau}_\rho\|_{L^2_{\rho_X}})\\ \leqslant& \mathbb{E}_{z_1, z_2, \cdots, z_T}(\|f_{T+1}-f^{V^{\tau}_{\epsilon}}_{\lambda_T}\|_{L^2_{\rho_X}})+ \|f^{V^\tau_\epsilon}_{\lambda_T}-f^{V^\tau}_{\lambda_T}\|_{L^2_{\rho_X}}+\|f^{V^\tau}_{\lambda_T}-f^{V^{\tau}}_\rho\|_{L^2_{\rho_X}}\\ \leqslant& \mathbb{E}_{z_1, z_2, \cdots, z_T}(\|f_{T+1}-f^{V^{\tau}_{\epsilon}}_{\lambda_T}\|_{K})+ \|f^{V^\tau_\epsilon}_{\lambda_T}-f^{V^\tau}_{\lambda_T}\|_{K}+\|f^{V^\tau}_{\lambda_T}-f^{V^{\tau}}_\rho\|_{L^2_{\rho_X}}\\ \leqslant& \sqrt{C_{K, \rho, b, \beta}}T^{-\frac{\theta^*}{2}}+C_\rho\lambda^{-1}_1\epsilon^sT^\gamma+\lambda^r_T\|g_\rho\|_{L^2_{\rho_X}}, \ \ \frac{1}{2}<r\leqslant 1. \end{align} $

(2.12)

当$ 1<r\leqslant \frac{3}{2} $时, 将$ \lambda_T = \lambda_1T^{-\frac{2}{6r+1}}, \eta_T = \eta_1T^{-\frac{4r}{6r+1}}, \epsilon = \lambda_T ^{\frac{2}{s}} $代入$ (2.11) $式得

$ \begin{align*} \mathbb{E}_{z_1, z_2, \cdots, z_T}(\|f_{T+1}-f_\rho\|_K)&\leqslant \sqrt{C_{K, \rho, b, \beta}}T^{-\frac{\theta^*}{2}}+C_\rho\lambda_1T^{-\frac{2}{6r+1}}+\lambda^{r-\frac{1}{2}}_1\|g_\rho\|_{L^2_{\rho_X}}T^{-\frac{2r-1}{6r+1}}\\ &\leqslant \tilde{C_1}T^{-\min\left\{\frac{2r-1}{6r+1}, \frac{b}{2}-\frac{2}{6r+1}\right\}}, \end{align*} $

其中$ \tilde C_1: = \sqrt{C_{K, \rho, b, \beta}}+C_\rho\lambda_1+\lambda^{r-\frac{1}{2}}_1\|g_\rho\|_{L^2_{\rho_X}} $.结论$ (2.1) $式成立.

当$ \frac{1}{2}<r\leqslant 1 $时, 将$ \lambda_T = \lambda_1T^{-\frac{1}{3r+2}}, \eta_T = \eta_1T^{-\frac{2r+1}{3r+2}} $代入$ (??) $式得

$ \begin{align*} \mathbb{E}_{z_1, z_2, \cdots, z_T}(\|f_{T+1}-f_\rho\|_{L^2_{\rho_X}})&\leqslant \sqrt{C_{K, \rho, b, \beta}}T^{-\frac{\theta^*}{2}}+C_\rho\lambda_1T^{-\frac{1}{3r+2}}+\lambda^r_1\|g_\rho\|_{L^2_{\rho_X}}T^{-\frac{r}{3r+2}}\\ &\leqslant \tilde{C_2}T^{-\min\left\{\frac{r}{3r+2}, \frac{b}{2}-\frac{1}{3r+2}\right\}}, \end{align*} $

其中$ \tilde C_2: = \sqrt{C_{K, \rho, b, \beta}}+C_\rho\lambda_1+\lambda^{r}_1\|g_\rho\|_{L^2_{\rho_X}} $.结论$ (2.2) $式成立.