ABSTRACT

Based on the regularized risk function model (SRM) of machine learning (ML), this paper combines the bundle method for solving non-smooth functions, presents an algorithm for solving empirical risk function model. The objective function is approximated by the cut-plane model, and the step size is obtained by the inexact line search. Under appropriate assumptions, the global convergence and convergence speed of the algorithm are analyzed.

Keywords:Machine Learning, Bundle Methods, Risk Minimization, Global Convergence

基于正则化风险函数模型的束方法

覃嘉，李艳妮

广西大学数学与信息科学学院，广西 南宁

收稿日期：2019年7月4日；录用日期：2019年7月19日；发布日期：2019年7月26日

摘 要

本文在机器学习(ML)的正则化风险函数模型(SRM)的基础上，结合求解非光滑函数的束方法，提出了一种求解经验风险函数模型的算法，用割平面模型去近似目标函数，用非精确线搜索去获得步长，在适当的假设下，分析了算法的全局收敛和收敛速度。

关键词 :机器学习，束方法，风险最小化，全局收敛

Copyright © 2019 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

本文主要考虑以下最优化问题(文 [1] ):

$\underset{w}{\min }J\left(w\right):=\lambda \Omega \left(w\right)+R_{emp}\left(w\right),$ (1.1)

其中， $R_{emp}\left(w\right):=\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}l\left(x_i,y_i,w\right)}$ 是经验风险函数。 $x_i\in X\subseteq R^d$ 是训练实例， $y_i\in Y$ 是相应的标签。l是一个凸的损失函数，用来衡量y与通过w产生的预测值之间的差异，例如， $l\left(x,y,w\right)={\left(\langle w,x\rangle -y\right)}^2$ ，其中 $\langle \cdot ，\cdot \rangle$ 定义为标准的欧几里得内积。最后， $\Omega \left(w\right)$ 是一个凸函数且作为正则化项，而 $\lambda \ge 0$ 是正则化参数。特别的， $\Omega \left(w\right)$ 是可微的且易于计算。与之相反的，经验风险函数项 $R_{emp}\left(w\right)$ 通常是不可微的，而且它的计算代价总是很大的(文 [2] )。

目前，各种各样的机器学习问题都可以描述成一类最小化正则风险函数问题，具体地，不同的机器学习算法会形成不同的风险函数和正则化项，例如：线性支持向量机(SVMs)，逻辑回归，条件随机场(CRFs)等等。因而研究此类凸优化问题具有重要的理论和现实意义。本文在束方法的基础上，结合一类BMRM算法，对BMRM算法的精确线搜索进行改进，推广到非精确的情形，给出一个改进的BMRM算法来求解正则化风险函数问题，在一定条件下，证明算法的全局收敛性。

2. 基础知识

机器学习问题建立在最优化基础理论上，为了更好的研究机器学习，下面将简要介绍与最优化理论相关的基本概念和一些重要结论，次梯度和束方法等。先介绍一些记号，其中：序列或者集合元素的索引记在下标，如 $u_1,u_2$ 。向量u的第i个分量记为 $u^{\left(i\right)}$ ， $\left[k\right]$ 表示集合 $\left\{1,2,\cdots ,k\right\}$ ， $L_p$ 范数定义为： $\Vert u_p\Vert ={\left({\displaystyle \underset{i=1}{\overset{d}{\sum }}{\left|u^{\left(i\right)}\right|}^p}\right)}^{1/p}$ ，这里的 $p\ge 1$ ，然后使用 $\Vert \cdot \Vert$ 来定义 ${\Vert \cdot \Vert }_2$ 。

次梯度(文 [3] )：对于一类非光滑的凸函数，次梯度是对于梯度的一个近似，假设 $w^{\prime }$ 是凸函数J上的一点， $s^{\prime }$ 是J在点 $w^{\prime }$ 处的次梯度，当且仅当：

对任意的w，有 $J\left(w\right)\ge J\left(w^{\prime }\right)+\langle w-w^{\prime },s^{\prime }\rangle$ 成立 (2.1)

则在 $w^{\prime }$ 处所有的次梯度组成的集合叫做次微分，记为 ${\partial }_{w}J\left(w^{\prime }\right)$ 。

切平面模型(CPM) (文 [4] )：

给定点 $w_0,w_1,\cdots ,w_{t-1}$ 处的次梯度 $s_1,s_2,\cdots ,s_t$ ，产生一系列分段线性下界来迫近J：

$J\left(w\right)\ge J_t^{CP}\left(w\right):=\underset{1\le i\le t}{\max }\left\{J\left(w_{i-1}\right)+\langle w-w_{i-1},s_i\rangle \right\}.$ (2.2)

迭代点 $w_t$ 的更新：

$w_t:=\underset{w}{\arg \min }{J}_t^{CP}\left(w\right).$ (2.3)

切平面模型(CPM)的模型迭代过程不断改进分段线性下界 $J^{CP}$ ，且使整个模型逐步逼近J的最小值。

邻近束方法(Proximal Bundle Methods) (文 [5] )：

虽然切平面模型是收敛的，但是当新的迭代点与上一个迭代点距离较大时，切平面模型收敛速度很慢。为了改进切平面模型的不稳定性，邻近束方法通过增加一个邻近函数来改进下一个点的选取，其中，一般选取 $\frac{1}{2}{\Vert \cdot \Vert }^2$ 作为邻近函数：

$w_t:=\underset{w}{\arg \min }\left\{\frac{{\zeta }_t}{2}{\Vert w-{\hat{w}}_{t-1}\Vert }^2+J_t^{CP}\left(w\right)\right\}.$ (2.4)

这里 ${\hat{w}}_{t-1}$ 是最近的邻近中心， ${\zeta }_t$ 是正邻近项参数。但是，这样的改进会使束方法需要对参数进行仔细地调整。

3. 一个新的最小化正则风险函数算法(BMRM)

结合次梯度和邻近束方法，文章 [6] 提出了一种新的机器学习凸优化算法：BMRM算法。在求解一类机器学习问题(1.1)时，对于每一次迭代t，BMRM算法都会构建下界 $R_t^{CP}$ 来近似经验风险函数 $R_{emp}$ ，而新的迭代点 $w_t$ 则由最小化 $J_t$ 更新， $J_t$ 由 $R_t^{CP}$ 与正则项 $\Omega$ 组成。这是BMRM算法和邻近束方法的最大不同。

实际上，BMRM算法不涉及邻近中心，进一步，BMRM算法甚至不包括邻近项。

BMRM算法具体如下：

算法1 (BMRM算法)

步骤1：输入及初始化： $\epsilon \ge 0,w_0,t:=0$

步骤2：循环： $t:=t+1$ ，计算：

$\begin{array}{l}{a}_t\in {\partial }_{\omega }{R}_{emp}\left(w_{t-1}\right),\\ b_t:=R_{emp}\left(w_{t-1}\right)-\langle w_{t-1},a_t\rangle ,\end{array}$

步骤3：(更新模型) $R_t^{CP}:=\underset{1\le i\le t}{\max }\left\{\langle w,a_i\rangle +b_i\right\}$

步骤4：(迭代点更新) $w_t:=\underset{w}{\arg \min }{J}_t\left(w\right):=\lambda \Omega \left(w\right)+R_t^{CP}(w)$

步骤5： ${\epsilon }_t:=\underset{0\le i\le t}{\min }J\left(w_i\right)-J_t(wt)$

步骤6：直到 ${\epsilon }_t\le \epsilon$ ，返回 $w_t$

与邻近束方法相比较，BMRM算法有两点不同：

a) BMRM算法是用一个分段线性下界来接近 $R_{emp}\left(w\right)$ 而不是 $J\left(w\right)$ 。

b) 在邻近束方法中，邻近项( $\frac{\zeta }{2}{\Vert w-{\hat{w}}_t\Vert }^2$ )被正则化项 $\Omega \left(w\right)$ 替代，因此，就不需要调整邻近参数了。

进一步，考虑存在有效的精确线搜索时，BMRM算法可以实现更快速的收敛，所以，结合线搜索的BMRM算法如下(文 [4] )：

算法2 (结合精确线搜索的BMRM算法)

步骤1：输入及初始化： $\epsilon \ge 0,\theta \in \left(0,1\right],w_0^b,w_0^c:=w_0^b,t:=0$

步骤2：循环： $t:=t+1$ ，计算：

$\begin{array}{l}{a}_t\in {\partial }_{\omega }{R}_{emp}\left(w_{t-1}^c\right),\\ b_t:=R_{emp}\left(w_{t-1}^c\right)-\langle w_{t-1}^c,a_t\rangle ,\end{array}$

步骤3：(更新模型) $R_t^{CP}:=\underset{1\le i\le t}{\max }\left\{\langle w,a_i\rangle +b_i\right\}$

步骤4： $w_t:=\underset{w}{\arg \min }{J}_t\left(w\right):=\lambda \Omega \left(w\right)+R_t^{CP}(w)$

步骤5：(线搜索)

$\begin{array}{l}{\eta }_t:=\underset{\eta \in R}{\arg \min }J\left(w_{t-1}^b+\eta \left(w_t-w_{t-1}^b\right)\right)\\ w_t^b:=w_{t-1}^b+{\eta }_t\left(w_t-w_{t-1}^b\right)\\ w_t^c:=\left(1-\theta \right)w_t^b+\theta w_t\end{array}$

步骤6： ${\epsilon }_t:=\underset{0\le i\le t}{\min }J\left(w_t^b\right)-J_t(wt)$

直到 ${\epsilon }_t\le \epsilon$ ，返回 $w_t^b$ 。

注意到，对所有的t，如果设 ${\eta }_t=1$ ，则算法2可以简化为算法1，且两个算法使用相同的终止准则.值得注意的是，带线搜索的BMRM算法并不能应用于结构化的机器学习问题，例如：最大边际马尔科夫网络问题。

4. 改进的非精确线搜索BMRM算法

在机器学习的优化问题中，算法2中的精确线搜索往往需要计算很多的函数值和梯度值，这样的话会产生较大的计算代价，特别是当迭代点离最优点比较远的时候，精确线搜索往往不是最有效和合理的。所以，对于许多像问题(1.1)的机器学习凸优化问题，非精确线搜索既能保证目标函数具有可接受的下降量，又能使最终形成的迭代序列收敛，以下将考虑非精确线搜索和BMRM算法的结合。

算法3 (结合非精确线搜索的BMRM算法)

步骤1：输入及初始化： $\epsilon \ge 0,\theta \in \left(0,1\right],w_0^b,w_0^c:=w_0^b,t:=0$

步骤2：循环： $t:=t+1$ ，计算：

$\begin{array}{l}{a}_t\in {\partial }_{\omega }{R}_{emp}\left(w_{t-1}^c\right),\\ b_t:=R_{emp}\left(w_{t-1}^c\right)-\langle w_{t-1}^c,a_t\rangle ,\end{array}$

步骤3：(更新模型) $R_t^{CP}:=\underset{1\le i\le t}{\max }\left\{\langle w,a_i\rangle +b_i\right\}$

步骤4： $w_t:=\underset{w}{\arg \min }{J}_t\left(w\right):=\lambda \Omega \left(w\right)+R_t^{CP}(w)$

步骤5：(线搜索)内循环： $m:=0,\beta \in \left(0,1\right),\sigma \in \left(0,0.5\right)$

$\begin{array}{l}\text{if}J\left(w_{t-1}^b+{\beta }^m\left(w_t-w_{t-1}^b\right)\right)\le J\left(w_{t-1}^b\right)+\sigma {\beta }^m\left(a_t+\lambda {\Omega }^{\prime }\left(w\right)\right)\left(w_t-w_{t-1}^b\right)\\ {\eta }_t={\beta }^m\\ m:=m+1\end{array}$

步骤6：更新点列：

$\begin{array}{l}{w}_t^b:=w_{t-1}^b+{\eta }_t\left(w_t-w_{t-1}^b\right)\\ w_t^c:=\left(1-\theta \right)w_t^b+\theta w_t\end{array}$

步骤7： ${\epsilon }_t:=\underset{0\le i\le t}{\min }J\left(w_t^b\right)-J_t(wt)$

直到 ${\epsilon }_t\le \epsilon$ ，返回 $w_t^b$ 。

在证明算法3的收敛性之前，先介绍相关引理。

定义4.1 (Fenchel对偶) 定义 $\Omega :W\to R$ 是一个在凸集W上的凸函数，则 $\Omega$ 的对偶 ${\Omega }^{\ast }$ 定义为：

${\Omega }^{\ast }\left(\mu \right):=\underset{w\in W}{\sup }\langle w,\mu \rangle -\Omega \left(w\right).$

定理4.1 定义 $A=\left[a_1,\cdots ,a_t\right]$ 的列向量为(次)梯度， $b=\left[b_1,\cdots ,b_t\right]$ ，则问题：

$w_t:=\underset{w\in R^d}{\arg \min }\left\{J_t\left(w\right):=\underset{1\le i\le t}{\max }\langle w,a_i\rangle +b_i+\lambda \Omega \left(w\right)\right\}$ (4.1)

的对偶问题为：

${\alpha }_t=\underset{\alpha \in R^t}{\arg \max }\left\{J_t^{\ast }\left(\alpha \right):=-\lambda {\Omega }^{\ast }\left(-{\lambda }^{-1}A\alpha \right)+{\alpha }^{\text{T}}b|\alpha \ge 0,{\Vert \alpha \Vert }_1=1\right\}$ (4.2)

此外， $w_t$ 和 ${\alpha }_t$ 之间有对偶关系式 $w_t\text{=}\partial {\Omega }^{\ast }\left(-{\lambda }^{-1}A{\alpha }_t\right)$ 。

证明：首先将(4.1)式改写成一个带约束的最优化问题：

$\begin{array}{l}\underset{w,\xi }{\min }\lambda \Omega \left(w\right)+\xi \\ \text{st}.\xi \ge \langle w,a_i\rangle +b_i\end{array}$

式中 $i=1,2,\cdots ,t$ 。通过引入非负的拉格朗日乘子 $\alpha$ 和元素都是1的t维向量 $1_t$ ，相应的拉格朗日函数可以写成：

$\{\begin{array}{l}L\left(w,\xi ,\alpha \right)=\lambda \Omega \left(w\right)+\xi -{\alpha }^{\text{T}}\left(\xi 1_t-A^{\text{T}}w-b\right)\\ \alpha \ge 0\end{array}$ (4.3)

式中， $\alpha \ge 0$ 表示向量 $\alpha$ 的每一个分量都是非负的，对 $\xi$ 求导可得： $1-{\alpha }^{\text{T}}{1}_t=0$ 。此外，对变量w最小化L意味着求解问题：

${\max }_w\langle w,-{\lambda }^{-1}A\alpha \rangle -\Omega \left(w\right)={\Omega }^{\ast }\left(-{\lambda }^{-1}A\alpha \right).$

把上述两项插回到(4.3)式中，就可以消除了原始变量 $\xi$ 和w。得证。

推论4.1 当 $\Omega \left(w\right)=\frac{1}{2}{\Vert w\Vert }_2^2$ 时，即取二次正则项的时候，(4.2)式可以写成：

${\alpha }_t=\underset{\alpha \in R^t}{\arg \max }\left\{-\frac{1}{2\lambda }{\alpha }^{\text{T}}{A}^{\text{T}}A\alpha +{\alpha }^{\text{T}}b|\alpha \ge 0,{\Vert \alpha \Vert }_1=1\right\}$

5. 收敛性分析

接下来证明结合非精确线搜索的BMRM算法具有较好的收敛速度。事实上，对于求解非光滑优化问题，水平束方法收敛速度为 $O\left(1/{\epsilon }^2\right)$ 。本文将证明，对于求解具有非光滑损失函数的正则化风险函数问题，算法3将具有 $O\left(1/\epsilon \right)$ 的收敛速度。更具体的说，我们将证明以下收敛性：

假设 ${\max }_{u\in {\partial }_w{R}_{emp}\left(w\right)}\Vert u\Vert \le G$ ，而对于正则化项 $\Omega \left(w\right)$ 有 $\Vert {\partial }_{\mu }^2{\Omega }^{\ast }\left(\mu \right)\Vert \le H^{\ast }$ ，本文将证明在上述假设下，算法具有 $O\left(1/\epsilon \right)$ 收敛速度，即算法将在 $O\left(1/\epsilon \right)$ 的迭代次数中，得到其 $\epsilon$ -最优解。

在以下的证明过程中，我们使用了类似于文 [7] 的技术：

定理5.1 假设 ${\max }_{u\in {\partial }_w{R}_{emp}\left(w\right)}\Vert u\Vert \le G$ 对于所有的 $w\in domJ$ 成立，且 $\Vert {\partial }_{\mu }^2{\Omega }^{\ast }\left(\mu \right)\Vert \le H^{\ast }$ 对于所有的 $\mu \in \left\{-{\lambda }^{-1}{\displaystyle \underset{i=1}{\overset{t+1}{\sum }}{\alpha }_i{\alpha }_i}\right\}$ 成立，这里 ${\alpha }_i\ge 0$ ，且对 $\forall i$ 有 ${\displaystyle \underset{i=1}{\overset{t+1}{\sum }}{\alpha }_i}=1$ 成立，即，存在：

${\epsilon }_t-{\epsilon }_{t+1}\ge \frac{{\epsilon }_t}{2}\min \left(1,\frac{\lambda {\epsilon }_t}{4G^2{H}^{\ast }}\right).$

证明：定理5.1的证明参考文献 [4] 。

定理5.2 假设对于所有的w有 $J\left(w\right)\ge 0$ ，在定理5.1成立的条件下，可以证明算法1的收敛性。即对任

意的 $\epsilon <\frac{4G^2{H}^{\ast }}{\lambda }$ ，算法会在至多：

$n\le {\log }_2\frac{\lambda J\left(0\right)}{G^2{H}^{\ast }}+\frac{8G^2{H}^{\ast }}{\lambda \epsilon }-1$

步后，收敛到所需精度。

证明：定理5.2的证明参考文献 [4] 。

在证明算法3收敛性之前先介绍相关引理。

引理5.1 $J_{t+1}\left(w_t\right)=\lambda \Omega \left(w_t\right)+\langle w_t,a_{t+1}\rangle +b_{t+1}$ 。

证明：由 $w_t^b$ 和 $w_t$ 与 $w_{t-1}^b$ 的关系，且 $w_t^c$ 是 $w_t$ 和 $w_t^b$ 的凸组合，此外，根据 $a_{t+1}$ 和 $b_{t+1}$ 的定义，得到 $J\left(w_t^c\right)=J_{t+1}\left(w_t^c\right)$ 。因此有：

$J\left(w_t^c\right)=J_{t+1}\left(w_t^c\right)\text{=}\lambda \Omega \left(w_t^c\right)+\langle a_{t+1},w_t^c\rangle +b_{t+1}\ge J\left(w_t^b\right).$ (5.1)

因为 $\Omega$ 是凸的，所以：

$\Omega \left(\left(1-\theta \right)w_t^b+\theta w_t\right)\le \left(1-\theta \right)\Omega \left(w_t^b\right)+\theta \Omega \left(w_t\right),$

即：

$\theta \left(\Omega \left(w_t^b\right)-\Omega \left(w_t\right)\right)\le \Omega \left(w_t^b\right)-\Omega \left(w_t^c\right),$

上式两边乘以 $\lambda$ ，然后加上 $\theta R_{emp}\left(w_t^b\right)$ 和减去 $\theta R_t\left(w_t\right)$ 得：

$\begin{array}{l}\lambda \theta \Omega \left(w_t^b\right)\text{+}\theta R_{emp}\left(w_t^b\right)-\lambda \theta \Omega \left(w_t\right)-\theta R_t\left(w_t\right)\\ \le \lambda \Omega \left(w_t^b\right)+R_{emp}\left(w_t^b\right)-\lambda \Omega \left(w_t^c\right)-\left(1-\theta \right)R_{emp}\left(w_t^b\right)-\theta R_t\left(w_t\right),\end{array}$

结合算法3的步骤7：

$\theta {\epsilon }_t\le J\left(w_t^b\right)-\lambda \Omega \left(w_t^c\right)-\left(1-\theta \right)R_{emp}\left(w_t^b\right)-\theta R_t\left(w_t\right),$ (5.2)

联立(5.1)和(5.2)：

$\langle a_{t+1},w_t^c\rangle +b_{t+1}\ge J\left(w_t^b\right)-\lambda \Omega \left(w_t^c\right)\ge \left(1-\theta \right)R_{emp}\left(w_t^b\right)+\theta R_t\left(w_t\right)+\theta {\epsilon }_t$

由 $w_t^c=\left(1-\theta \right)w_t^b+\theta w_t$ 可得：

$\left(1-\theta \right)\langle a_{t+1},w_t^b\rangle +\theta \langle a_{t+1},w_t\rangle +b_{t+1}\ge J\left(w_t^b\right)-\lambda \Omega \left(w_t^c\right)\ge \left(1-\theta \right)R_{emp}\left(w_t^b\right)+\theta R_t\left(w_t\right)+\theta {\epsilon }_t,$

化简得：

$\left(1-\theta \right)\left(\langle a_{t+1},w_t^b\rangle -R_{emp}\left(w_t^b\right)\right)+\theta \left(\langle a_{t+1},w_t\rangle -R_t\left(w_t\right)\right)+b_{t+1}\ge J\left(w_t^b\right)-\lambda \Omega \left(w_t^c\right)\ge \theta {\epsilon }_t.$ (5.3)

因为 $\langle w_t^b,a_{t+1}\rangle +b_{t+1}$ 是凸函数 $R_{emp}$ 的泰勒近似，所以有：

$R_{emp}\left(w_t^b\right)\ge \langle w_t^b,a_{t+1}\rangle +b_{t+1}$ (5.4)

把(5.4)带入(5.3)，得到：

$\left(1-\theta \right)\left(-b_{t+1}\right)+\theta \left(\langle w_t^b,a_{t+1}\rangle -R_t\left(w_t\right)\right)+b_{t+1}\ge \theta {\epsilon }_t$

两边除以 $\theta >0$ ，得到：

$\langle w_t^b,a_{t+1}\rangle +b_{t+1}\ge R_t\left(w_t\right)+{\epsilon }_t$

又：

$R_{t+1}\left(w_t\right)=\max \left(\langle w_t,a_{t+1}\rangle +b_{t+1},R_t\left(w_t\right)\right)=\langle w_t,a_{t+1}\rangle +b_{t+1}$

$J_{t+1}\left(w_t\right)=\lambda \Omega \left(w_t\right)+R_{t+1}(wt)$

故： $J_{t+1}\left(w_t\right)=\lambda \Omega \left(w_t\right)+\langle w_t,a_{t+1}\rangle +b_{t+1}.$

引理5.2 ${\epsilon }_t-{\epsilon }_{t+1}\ge J_{t+1}\left(w_{t\text{+}1}\right)-J_t\left(w_t\right)$ 。

证明：

$\begin{array}{c}{\epsilon }_t-{\epsilon }_{t+1}=J\left(w_t^b\right)-J_t\left(w_t\right)-J\left(w_{t+1}^b\right)+J_{t+1}\left(w_{t+1}\right)\\ =J\left(w_t^b\right)-J\left(w_{t+1}^b\right)+J_{t+1}\left(w_{t+1}\right)-J_t\left(w_t\right)\\ \ge J_{t+1}\left(w_{t+1}\right)-J_t\left(w_t\right).\end{array}$

引理5.3 令 ${\alpha }_t$ 如定理4.1中的定义， $\bar{A}:=\left[a_1,\cdots ,a_{t+1}\right]$ 和 $\bar{b}:=\left[b_1,\cdots ,b_{t+1}\right]$ ，则在定理5.1里下述条件成立 ${\max }_{u\in {\partial }_w{R}_{emp}\left(w\right)}\Vert u\Vert \le G$ 情况下，下式成立：

${\left[-{\alpha }_t,1\right]}^{\text{T}}{\bar{A}}^{\text{T}}\bar{A}\left[-{\alpha }_t,1\right]\le 4G^2.$

证明：首先，有对偶关系 ${\partial }_w\lambda \Omega \left(w_t\right)=-A{\alpha }_t$ ，且(4.2)在第t迭代时， ${\alpha }_t\ge 0$ 和 ${\Vert {\alpha }_t\Vert }_1=1$ ，随后，因为 ${\partial }_w\lambda \Omega \left(w_t\right)$ 在 $a_{t^{\prime }}\in {\partial }_w{R}_{emp}\left(w_{t^{\prime }}^c\right),\forall t^{\prime }\le t$ 的凸包里面，因此 $\Vert {\partial }_w\lambda \Omega \left(w_t\right)\Vert \le G$ ，接下来，由Cauchy-Schwarz不等式得：

$\begin{array}{c}{\left[-{\alpha }_t,1\right]}^{\text{T}}{\bar{A}}^{\text{T}}\bar{A}\left[-{\alpha }_t,1\right]={\Vert {\partial }_w\lambda \Omega \left(w_t\right)+a_{t+1}\Vert }^2\\ ={\Vert {\partial }_w\lambda \Omega \left(w_t\right)\Vert }^2+2{\partial }_w\lambda \Omega {\left(w_t\right)}^{\text{T}}{a}_{t+1}+{\Vert a_{t+1}\Vert }^2\\ \le 4G^2.\end{array}$

引理5.4 对满足以下递推条件： $c>0$ 是一个常数，当 $t\ge 1$ 时

${\rho }_t-{\rho }_{t+1}\ge c{\left({\rho }_t\right)}^2$

的非负序列 $\langle {\rho }_1,{\rho }_2,\cdots \rangle$ ，有当整数 $t\ge 1$ 时：

${\rho }_t\le \frac{1}{c\left(t-1+\frac{1}{{\rho }_{1}c}\right)}.$

此外，当 $t\ge \frac{1}{c\rho }-\frac{1}{{\rho }_{1}c}+1$ 时：总有 ${\rho }_t\le \rho$ 成立。

证明：此引理通过归纳法易得，参考文献 [8] 。

定理 5.3 在定理5.1成立条件下，算法3收敛到任意 $\epsilon <4G^2{H}^{\ast }/\lambda$ 精度需要：

$n\le \frac{8G^2{H}^{\ast }}{\lambda \epsilon }$ 步。

证明：对于 $\epsilon <\frac{4G^2{H}^{\ast }}{\lambda }$ ，结合定理5.1及其证明过程，易知：

${\epsilon }_t-{\epsilon }_{t\text{+}1}\ge \frac{\lambda {\epsilon }_t^{\text{2}}}{8G^2{H}^{\ast }}$

又由引理5.4可知 ${\epsilon }_t\le \frac{1}{c\left(t-1+\frac{1}{{\epsilon }_{1}c}\right)}$ ，这里 $c=\frac{\lambda }{8G^2{H}^{\ast }}$ 。令 $\frac{1}{c\left(t-1+\frac{1}{{\epsilon }_{1}c}\right)}=\epsilon$ ，假设 ${\epsilon }_1>0$ ，然后

解出n，有：

$n\le \frac{1}{c\epsilon }=\frac{8G^2{H}^{\ast }}{\lambda \epsilon }.$

文章引用

覃 嘉,李艳妮. 基于正则化风险函数模型的束方法
The Bundle Methods Based on the Regularized Risk Minimization Model[J]. 应用数学进展, 2019, 08(07): 1243-1250. https://doi.org/10.12677/AAM.2019.87144

参考文献