求解非凸复合优化问题的随机Douglas-Rachford分裂算法

Stochastic Douglas-Rachford Splitting Algorithm for Solving Non-Convex Composite Optimization Problems

摘要: 本文研究了大规模非凸复合优化问题，该问题的目标函数为非凸的光滑函数与凸(可能是非光滑的)函数之和，其中非凸的光滑函数具有有限和形式。随着大规模非凸复合优化问题在机器学习、图像处理中广泛应用，设计简洁、高效、计算成本低的优化算法来解决大规模非凸复合优化问题已成为当今研究热点之一。求解非凸复合优化问题的一个经典算法是Douglas-Rachford (DR)分裂算法，然而当实际问题规模较大时经典的DR分裂算法计算成本较大。据此本文提出了一种方差缩减的随机DR分裂算法(SDR)，将方差缩减的随机梯度引入到DR分裂算法中，以减小算法的计算成本，并基于Kurdyka-Łojasiewicz (KL)框架对算法的收敛性进行了分析。具体的，我们首先建立了Lyapunov函数的下降性，然后建立了DR价值函数的相对误差界条件，最后利用KL性质证明了算法的全局收敛性。此外，通过将SDR算法用于求解${\ell }_1{\ell }_2$ 稀疏正则化Logistic回归问题，并与PG、Prox-SARAH进行对比，展示了本文所提出算法的优越性。

Abstract: This paper investigates large-scale non-convex composite optimization problems, where the objective function is the sum of a nonconvex smooth function and a convex (possibly nonsmooth) function, with the nonconvex smooth function having a finite sum form. Given the widespread application of large-scale nonconvex composite optimization problems in machine learning and image processing, developing concise, efficient, and low-computational-cost optimization algorithms for solving such problems has become one of the current research hotspots. A classic algorithm for solving non-convex composite optimization problems is the Douglas-Rachford (DR) splitting algorithm. However, the classical DR splitting algorithm incurs significant computational costs when dealing with large-scale practical problems. Accordingly, this paper proposes a variance-reduced stochastic DR splitting algorithm (SDR), incorporating variance reduction stochastic gradients into the DR splitting algorithm to reduce computational costs, and analyzes the convergence of the algorithm based on the Kurdyka-Łojasiewicz (KL) framework. Moreover, we use the SDR algorithm to solve the ${\ell }_1{\ell }_2$ sparse logistic regression problem and compare its performance with PG and Prox-SARAH to show the efficiency of SDR.

1. 引言

近年来，随着大数据时代的到来，涌现出了大量的大规模非凸复合优化问题，其广泛应用于机器学习，图像处理，稀疏优化等领域因此，针对大规模非凸复合优化问题，设计更加高效、简洁、低计算成本的求解算法有着一定的研究意义和应用价值。本文，我们考虑如下形式的大规模非凸复合优化问题

$\underset{x\in {ℝ}^d}{\min }F\left(x\right)=f\left(x\right)+h\left(x\right)={\displaystyle \sum }_{i=1}^N{f}_i\left(x\right)+h\left(x\right).$ (1)

其中$f_i:{ℝ}^d\to ℝ\left(i=1,2,\cdots ,N\right)$ 为连续可微的(可能非凸)，$h:{ℝ}^d\to \left(-\infty ,+\infty \right]$ 为适当下半连续凸函数(可能非光滑)。该复合优化问题有着广泛的应用背景，具体的在机器学习中的二分类${\ell }_1{\ell }_2-$ 正则化逻辑回归问题，其一般形式为

$\underset{x\in {ℝ}^d}{\min }F\left(x\right):=\frac{1}{N}{\displaystyle \sum _{i=1}^N\log \left(1+\exp \left(-b_i{a}_i^{T}x\right)\right)+{\lambda }_1{\Vert x\Vert }_1}+\frac{{\lambda }_2}{2}{\Vert x\Vert }^2,$

其中$a_i\in {ℝ}^d,b_i\in \left\{-1,1\right\},i\in \left\{1,2,\cdots ,N\right\}$ 为样本的特征及相应的标签，${\lambda }_1,{\lambda }_2>0$ 为正则化参数，用以控制所求变量的稀疏性。

1.1. 研究现状

针对复合优化问题(1)的研究已有很多，一个经典的求解算法为邻近梯度算法(proximal gradient, PG)，也称向前向后分裂算法[1]：

$x^{k+1}=\underset{x\in {ℝ}^d}{\arg \min }\left\{h\left(x\right)+f\left(x^k\right)+\langle \nabla f\left(x^k\right),x-x^k\rangle +\frac{1}{2{\alpha }_k}{\Vert x-x^k\Vert }^2\right\}.$

该算法的优点在于充分利用了目标函数光滑部分和非光滑部分的结构，Beck等人研究了在凸或非凸条件下，PG算法在迭代点意义下的收敛性[2]。

为了解决目标函数两部分均不光滑的情况，Douglas和Rachford提出了Douglas-Rachford (DR)分裂算法[3]。虽然在凸的情形下，DR分裂算法[3]已经被充分的研究，但针对问题非凸的情形，相关的理论分析还不是很多。尽管如此，DR分裂算法已经非常成功地应用于各种非凸问题[4]。针对非凸复合优化问题，2015年，Bot等人[5]将惯性近似法和广义DR分裂算法相结合，提出惯性DR分裂算法，其相比于经典DR算法具有更快的收敛速度，更好的适应性，还可以避免局部最优解。2016年，Li等人[6]建立了DR分裂算法在非凸情形下的下降性，并在其满足Kurdyka-Łojasiewicz (KL)性质时证明了算法的全局收敛性。

随着科技迅速发展，实际应用中许多问题的规模通常很大，即问题(1)中N很大的情形。针对这类问题，许多经典的求解算法由于在内循环需要涉及到对光滑部分全梯度的计算，导致了计算成本很高。为降低算法的计算成本，针对光滑优化问题，随机梯度下降算法(SGD) [7]和小批量梯度下降算法(Mini-batch) [8]被提出，其在每一迭代步用一个样本的梯度或小批量样本的梯度近似全梯度的计算。然而，由于方差的引入，算法中的步长参数需要随迭代步不断衰减到0以保证其收敛性，这导致了算法较慢的收敛速度。为提高随机算法的收敛速度，一系列方差缩减的随机梯度被提出，如SAG [9]、SVRG [10]、SASG [11]、SCSG [12]、SARAH [13]、SPIDER [14]等。这一系列随机梯度的技巧被广泛的应用于许多一阶算法，用以实现相关算法计算量的降低。针对本文所关注的大规模非凸复合优化问题，相关的求解算法已有一些，如邻近SGD算法(Proximal SGD)等[15] [16]。此外，方差缩减的随机梯度技术也被用以和邻近梯度算法相结合，如Prox-SARAH [17]等。

1.2. 本文主要内容及结构

本文将方差缩减的随机梯度引入到DR分裂算法中，针对大规模非凸复合优化问题提出随机DR分裂算法，以降低经典DR分裂算法的计算成本，更好的求解大规模优化问题。本文在Kurdyka-Łojasiewicz (KL)框架下，给出算法的收敛性分析。具体的，我们首先建立了Lyapunov函数在前后迭代步的下降性，并建立DR价值函数的相对误差界条件，最后利用KL性质证明了算法的全局收敛性。

本文框架如下，在第二节中，我们将给出本文所涉及到的符号、定义以及相关引理。第三节中，我们提出了求解大规模非凸复合优化问题的随机DR分裂算法，并在KL框架给出了算法的收敛性证明。为了说明所提出算法的优越性，我们在第四节给出了相关的数值实验。在第五节，对本文的工作做出总结。

2. 预备知识

2.1. 基本概念

本节将介绍讨论算法的收敛性所涉及的常用符号、基本定义及性质。首先对本论文所使用的符号做出定义：记${ℝ}^d$ 为d维欧氏空间，$\Vert x\Vert =\sqrt{\langle x,x\rangle }$ 为欧式距离，${\Vert x\Vert }_1={\displaystyle \sum }_{i=1}^d\left|x_i\right|$ 为1范数，对于一个非空闭集$\Omega \subseteq {ℝ}^d$ ，x到集合$\Omega$ 的欧式距离可被定义(2.1.1)为

$\text{dist}\left(x,\Omega \right):=\underset{y\in \Omega }{\inf }\Vert x-y\Vert ,\forall x\in {ℝ}^d,\forall \Omega \in {ℝ}^d.$

定义2.1.2 $\langle u,v\rangle$ 表示向量内积，即

$\langle u,v\rangle =\frac{1}{2}\left({\Vert u+v\Vert }^2-{\Vert u\Vert }^2-{\Vert v\Vert }^2\right).$

定义2.1.3 (L-光滑[18] [19]) 我们称函数$f:{ℝ}^d\to ℝ$ 是L-光滑的，若

$\Vert \nabla f\left(x\right)-\nabla f\left(y\right)\Vert \le L\Vert x-y\Vert ,\forall x,y\in {ℝ}^d.$

定义2.1.4 (凸函数的次微分[19]) 设$f:{ℝ}^d\to ℝ\cup \left\{+\infty \right\}$ 是适当的下半连续函数，对$x\in \text{dom }f$ ，f在点x处的次微分记作$\partial f\left(x\right)$ ，定义为所有满足下述条件的$u\in {ℝ}^d$ 构成的集合

$f\left(y\right)\ge f\left(x\right)+\langle u,y-x\rangle ,\forall y\in {ℝ}^d.$

若$x\notin \text{dom }f$ ，定义f在该点的次微分$\partial f\left(x\right)=\varphi$ 。

定义2.1.5 (DR价值函数) 令$\gamma >0$ ，定义DR价值函数如下

$D_{\gamma }\left(x,z,y\right)=f\left(x\right)+h\left(z\right)-\frac{1}{2\gamma }{\Vert x-z\Vert }^2+\frac{1}{\gamma }\langle y-x,z-x\rangle .$ (2)

再根据定义2.1.2，令$u=y-x$ ，$v=z-x$ ，函数$D_{\gamma }\left(x,z,y\right)$ 可以等价表示为下面公式

$D_{\gamma }\left(x,z,y\right)=f\left(x\right)+h\left(z\right)+\frac{1}{2\gamma }{\Vert 2x-z-y\Vert }^2-\frac{1}{2\gamma }{\Vert y-x\Vert }^2-\frac{1}{\gamma }{\Vert x-z\Vert }^2,$ (3)

再结合$\langle a-b,c-d\rangle =\frac{1}{2}{\Vert a-d\Vert }^2-\frac{1}{2}{\Vert a-c\Vert }^2+\frac{1}{2}{\Vert b-c\Vert }^2-\frac{1}{2}{\Vert b-d\Vert }^2$ ，函数$D_{\gamma }\left(x,z,y\right)$ 可以被表示成以下形式

$D_{\gamma }\left(x,z,y\right)=f\left(x\right)+h\left(z\right)+\frac{1}{2\gamma }{\Vert y-x\Vert }^2-\frac{1}{2\gamma }{\Vert y-z\Vert }^2.$ (4)

2.2. 基本结论

引理 2.2.1 (下降引理[19]) 若函数$f:{ℝ}^d\to ℝ$ 连续可微且L-光滑$\left(L>0\right)$ ，则有

$f\left(y\right)\le f\left(x\right)+\langle \nabla f\left(x\right),y-x\rangle +\frac{L}{2}{\Vert y-x\Vert }^2,\forall x,y\in {ℝ}^d.$

Kurdyka-Łojasiewicz (KL)不等式是证明非凸复合优化问题收敛性的一个重要性质，满足这一性质的函数有很多，如凸函数、幂函数、实解析函数等。记$p:{ℝ}^d\to ℝ\cup \{+\infty \}$ 为正常的下半连续函数。对$-\infty <{\eta }_1<{\eta }_2\le +\infty$ ，定义

$\left[{\eta }_1<p<{\eta }_2\right]:=\left\{x\in {ℝ}^d:{\eta }_1<p\left(x\right)<{\eta }_2\right\}.$

下面，我们给出KL不等式的具体定义。

定义2.2.1 [20] 若存在$\eta \in \left(0,+\infty \right]$ ，$\overline{x}\in \text{dom}\partial f$的邻域U以及连续的凹函数$\phi :\left[0,\eta \right)\to {ℝ}^{+}$ 满足

(i) $\phi \left(0\right)=0$ ；

(iii) $\phi$ 在$\left(0,\eta \right)$ 上是连续函数；

(iii) 对任意的$s\in \left(0,\eta \right)$ ，有${\phi }^{\prime }>0$ ；

(iiii) 对任意的$x\in U\cap \left[p\left(\overline{x}\right)<p<p\left(\overline{x}+\eta \right)\right]$ ，Kurdyka-Łojasiewicz不等式成立，即有

${\phi }^{\prime }\left(p\left(x\right)-p\left(\overline{x}\right)\right)dist\left(0,\partial f\left(x\right)\right)\ge 1.$

此时我们称函数p在点$\overline{x}$ 处具有Kurdyka-Łojasiewicz(KL)性质。

3. 算法及算法的收敛分析

本文将方差缩减的随机梯度算法引入到经典的DR分裂算法中，提出了一种随机DR分裂算法，该算法可以降低经典DR分裂算法的计算成本，更高效的针对于大规模非凸复合优化问题的求解。

在本节中，我们首先给出求解大规模非凸复合优化问题的随机DR算法的迭代格式，然后在KL框架下，给出算法的收敛性分析。具体来说，我们首先建立了Lyapunov函数在前后迭代步的下降性质，并建立DR价值函数的相对误差界条件，最后基于函数之间的关系，我们利用KL性质证明了算法的全局收敛性。

3.1. 随机DR分裂算法

首先我们给出随机DR分裂算法的具体格式。

算法1求解非凸复合优化问题的随机Douglas-Rachford分裂算法

输入：$x^0,y^0\in {ℝ}^d$ ，$\gamma \in \left(0,1\right)$ 。

1：For $k=0,1,2,\cdots ,K-1$ do

2：令$n_k$ 均匀随机从1到N中取值，再随机从梯度$\nabla f_i\left(x_k\right)\left(i=1,2,\cdots ,N\right)$ 中选取$n_k$ 个求平均值并赋值给$g_k$ ，

3：计算$x^{k+1}$ $x^{k+1}=\underset{x\in {ℝ}^d}{\arg \min }\left\{\langle g_k,x-x^k\rangle +\frac{1}{2\gamma }{\Vert x-y^k\Vert }^2\right\},$ (5)

4：计算$z^{k+1}$ $\begin{array}{l}{z}^{k+1}=\underset{z\in {ℝ}^d}{\arg \min }\left\{h\left(z\right)+\frac{1}{2\gamma }{\Vert z-\left(2x^{k+1}-y^k\right)\Vert }^2\right\}\\ =\underset{z\in {ℝ}^d}{\arg \min }\left\{h\left(z\right)+\frac{1}{2\gamma }{\Vert z-x^{k+1}\Vert }^2+\langle z-x^{k+1},g_k\rangle \right\},\end{array}$ (6)

5：计算$y^{k+1}$ $y^{k+1}=y^k+z^{k+1}-x^{k+1},$ (7)

6：End for

根据算法中$x^{k+1},z^{k+1}$ 的迭代子问题，我们可以得到相应的最优性条件：

$0=g_k+\frac{1}{\gamma }\left(x^{k+1}-y^k\right).$ (8)

和

$0\in \partial h\left(z^{k+1}\right)+\frac{1}{\gamma }\left(z^{k+1}-\left(2x^{k+1}-y^k\right)\right).$ (9)

3.2. 收敛性分析

为分析算法的收敛性，我们首先给出一些假设条件。

假设1 (1) $f_i\left(x\right):{ℝ}^d\to ℝ\left(i=1,2,\cdots ,N\right)$ 是Lipschitz连续可微的，Lipschitz常数为$L_i>0$ ，且记$L=\underset{i\in \{1,2,\dots ,N\}}{\max }\left\{L_i\right\}$ 。

(2) $h:{ℝ}^d\to ℝ$ 是适当下半连续凸函数，且在其定义域上是连续的。

(3) 函数G是强制的。

假设2 (梯度方差缩减)存在$\rho \in \left(0,1\right]$ ，$A_i\ge 0\left(i=1,2,3\right)$ 和随机向量${\left\{{\alpha }_k^i\right\}}_{i=1}^s$ 使得以下条件成立：

(1) 梯度估计的均方误差是有界的

${\mathbb{E}}_k{\Vert g_k-\nabla f\left(x^k\right)\Vert }^2\le {\sigma }_k^2+A_1{\mathbb{E}}_k\left[{\Vert x^{k+1}-x^k\Vert }^2\right],$ (10)

${\mathbb{E}}_k\Vert g_k-\nabla f\left(x^k\right)\Vert \le {\xi }_k+A_2{\mathbb{E}}_k\left[\Vert x^{k+1}-x^k\Vert \right].$ (11)

其中${\sigma }_k^2={\displaystyle \sum _{i=1}^S{\Vert {\alpha }_k^i\Vert }^2}$ ，${\xi }_k={\displaystyle \sum _{i=1}^S\Vert {\alpha }_k^i\Vert }$ 。

(2) 序列${\left\{{\sigma }_k^2\right\}}_{k=0}^{\infty }$ 在几何上是衰减的，满足

$\mathbb{E}\left[{\sigma }_{k+1}^2\right]\le \left(1-\rho \right){\sigma }_k^2+A_3\mathbb{E}\left[{\Vert x^{k+1}-x^k\Vert }^2\right].$ (12)

(3) 对于任意序列${\left\{x_k\right\}}_{k=0}^{\infty }$ 满足${\lim }_{k\to \infty }\mathbb{E}\left[{\Vert x_k-x_{k-1}\Vert }^2\right]=0$ ，有下式成立

${\displaystyle \sum _{k=1}^{\infty }\mathbb{E}\left[{\sigma }_k^2\right]}<\infty ,{\displaystyle \sum _{k=1}^{\infty }\mathbb{E}\left[{\xi }_k\right]}<\infty .$ (13)

基于上述算法分析以及相关假设，我们在本节将对随机DR算法的收敛性进行分析。考虑到非凸问题的收敛性分析大部分是基于Kurdyka-Łojasiewicz (KL)框架给出的，本文也采用这一框架对该算法进行收敛性分析。具体的，收敛性框架需要证明以下三个条件成立，包括充分下降性条件、相对误差条件和函数连续性条件。本文我们首先给出了Lyapunov函数在前后迭代步的充分下降性(引理3.2)，并建立DR价值函数的相对误差界条件(引理3.3)，最后本文利用KL性质给出了算法的全局收敛性(定理3.1)。

设$D_{\gamma }\left(x^k,z^k,y^k\right),D_{\gamma }\left(x^{k+1},z^{k+1},y^{k+1}\right)$ 分别为函数$D_{\gamma }$ 第k次和第$k+1$ 次的迭代步，在下述引理中，我们将给出该函数前后迭代步的关系。

引理3.1 若假设1与假设2成立，${\left\{\left(x^k,z^k,y^k\right)\right\}}_{k\in \mathbb{N}}$ 是由随机DR算法生成的序列。对于任意$k\in \mathbb{N}$ ，我们有

$\begin{array}{l}\mathbb{E}\left[D_{\gamma }\left(x^{k+1},z^{k+1},y^{k+1}\right)-D_{\gamma }\left(x^k,z^k,y^k\right)\right]\\ \le \left(\frac{1}{2\theta }+4+3\gamma \right)\left[{\sigma }_k^2+A_1\left(\mathbb{E}\left[{\Vert x^{k+1}-x^k\Vert }^2\right]\right)\right]+\left(4+3\gamma \right)\left[{\sigma }_{k-1}^2+A_1\left(\mathbb{E}\left[{\Vert x^k-x^{k-1}\Vert }^2\right]\right)\right]\\ +\left(4L^2+3\gamma L^2\right){\Vert x^k-x^{k-1}\Vert }^2-\left(\frac{1}{2\gamma }-\frac{L}{2}-\frac{\theta }{2}-4\right){\Vert x^{k+1}-x^k\Vert }^2.\end{array}$

证明：针对$D_{\gamma }\left(x^{k+1},z^{k+1},y^{k+1}\right)-D_{\gamma }\left(x^k,z^k,y^k\right)$ ，做如下处理

$\begin{array}{l}{D}_{\gamma }\left(x^{k+1},z^{k+1},y^{k+1}\right)-D_{\gamma }\left(x^k,z^k,y^k\right)\\ =\left(D_{\gamma }\left(x^{k+1},z^k,y^k\right)-D_{\gamma }\left(x^k,z^k,y^k\right)\right)+\left(D_{\gamma }\left(x^{k+1},z^{k+1},y^k\right)-D_{\gamma }\left(x^{k+1},z^k,y^k\right)\right)\\ \text{ +}\left(D_{\gamma }\left(x^{k+1},z^{k+1},y^{k+1}\right)-D_{\gamma }\left(x^{k+1},z^{k+1},y^k\right)\right)\text{. }\end{array}$

由公式(4)可得：

$\begin{array}{l}{D}_{\gamma }\left(x^{k+1},z^k,y^k\right)-D_{\gamma }\left(x^k,z^k,y^k\right)\\ =f\left(x^{k+1}\right)+\frac{1}{2\gamma }{\Vert y^k-x^{k+1}\Vert }^2-\left[f\left(x^k\right)+\frac{1}{2\gamma }{\Vert y^k-x^k\Vert }^2\right].\end{array}$ (14)

由$f_i\left(i\in \left\{1,2,\cdots ,N\right\}\right)$ 的梯度Lipschitz连续性和引理2.2.1可知

$f\left(x^{k+1}\right)-f\left(x^k\right)\le \langle \nabla f\left(x^k\right),x^{k+1}-x^k\rangle +\frac{L}{2}{\Vert x^{k+1}-x^k\Vert }^2.$ (15)

结合公式(2)~(4)，(14)，(15)可以计算化简得出

$\begin{array}{l}{D}_{\gamma }\left(x^{k+1},z^k,y^k\right)-D_{\gamma }\left(x^k,z^k,y^k\right)\\ \le \frac{1}{2\gamma }{\Vert y^k-x^{k+1}\Vert }^2-\frac{1}{2\gamma }{\Vert y^k-x^{k+1}+x^{k+1}-x^k\Vert }^2+\langle \nabla f\left(x^k\right),x^{k+1}-x^k\rangle +\frac{L}{2}{\Vert x^{k+1}-x^k\Vert }^2\\ =-\frac{1}{\gamma }\langle y^k-x^{k+1},x^{k+1}-x^k\rangle -\frac{1}{2\gamma }{\Vert x^{k+1}-x^k\Vert }^2+\langle \nabla f\left(x^k\right),x^{k+1}-x^k\rangle +\frac{L}{2}{\Vert x^{k+1}-x^k\Vert }^2,\end{array}$

其中等式是由${\Vert a+b\Vert }^2={\Vert a\Vert }^2+2\langle a,b\rangle +{\Vert b\Vert }^2$ 得到的。又由(8)可以得到以下不等式

$\begin{array}{l}{D}_{\gamma }\left(x^{k+1},z^k,y^k\right)-D_{\gamma }\left(x^k,z^k,y^k\right)\\ \le \langle \nabla f\left(x^k\right)-g_k,x^{k+1}-x^k\rangle -\left(\frac{1}{2\gamma }-\frac{L}{2}\right){\Vert x^{k+1}-x^k\Vert }^2.\end{array}$ (16)

利用$\langle a,b\rangle \le \frac{1}{2\beta }{\Vert a\Vert }^2+\frac{\beta }{2}{\Vert b\Vert }^2\left(\beta >0\right)$ 可得到

$\begin{array}{l}{D}_{\gamma }\left(x^{k+1},z^k,y^k\right)-D_{\gamma }\left(x^k,z^k,y^k\right)\\ \le \frac{1}{2\beta }{\Vert \nabla f\left(x^k\right)-g_k\Vert }^2-\left(\frac{1}{2\gamma }-\frac{L}{2}-\frac{\beta }{2}\right){\Vert x^{k+1}-x^k\Vert }^2.\end{array}$ (17)

接下来处理z的前后迭代步关系。首先根据公式(3)可得

$\begin{array}{l}{D}_{\gamma }\left(x^{k+1},z^{k+1},y^k\right)-D_{\gamma }\left(x^{k+1},z^k,y^k\right)\\ =h\left(z^{k+1}\right)+\frac{1}{2\gamma }{\Vert z^{k+1}-\left(2x^{k+1}-y^k\right)\Vert }^2-\frac{1}{\gamma }{\Vert x^{k+1}-z^{k+1}\Vert }^2\\ -\left[h\left(z^k\right)+\frac{1}{2\gamma }{\Vert z^k-\left(2x^{k+1}-y^k\right)\Vert }^2-\frac{1}{\gamma }{\Vert x^{k+1}-z^k\Vert }^2\right],\end{array}$

进一步结合迭代步(6)和(7)，有下式成立

$D_{\gamma }\left(x^{k+1},z^{k+1},y^k\right)-D_{\gamma }\left(x^{k+1},z^k,y^k\right)\le -\frac{1}{\gamma }{\Vert y^{k+1}-y^k\Vert }^2+\frac{1}{\gamma }{\Vert x^{k+1}-z^k\Vert }^2.$ (18)

下面处理$\frac{1}{\gamma }{\Vert x^{k+1}-z^k\Vert }^2$ 这一项。由(8)可得

$\{\begin{array}{l}0=g_k+\frac{1}{\gamma }\left(x^{k+1}-y^k\right),\\ 0=g_{k-1}+\frac{1}{\gamma }\left(x^k-y^{k-1}\right).\end{array}$

因此有

$y^k-y^{k-1}=x^{k+1}-x^k+\gamma \left(g_k-g_{k-1}\right)$ (19)

所以

$\begin{array}{l}\Vert y^k-y^{k-1}\Vert \\ \le \Vert x^{k+1}-x^k\Vert +\gamma \Vert g_k-g_{k-1}\Vert \\ =\Vert x^{k+1}-x^k\Vert +\gamma \Vert g_k-\nabla f\left(x^k\right)+\nabla f\left(x^k\right)-\nabla f\left(x^{k-1}\right)+\nabla f\left(x^{k-1}\right)-g_{k-1}\Vert \\ \le \Vert x^{k+1}-x^k\Vert +\gamma \Vert g_k-\nabla f\left(x^k\right)\Vert +\gamma \Vert \nabla f\left(x^{k-1}\right)-g_{k-1}\Vert +\gamma L\Vert x^k-x^{k-1}\Vert \text{. }\end{array}$ (20)

其中最后一个不等式利用公式$\Vert x+y\Vert \le \Vert x\Vert +\Vert y\Vert$ 和定义2.1.3。进而可得

$\begin{array}{l}{\Vert y^k-y^{k-1}\Vert }^2\le {\Vert x^{k+1}-x^k\Vert }^2+{\gamma }^2{\Vert g_k-\nabla f\left(x^k\right)\Vert }^2+{\gamma }^2{\Vert g_{k-1}-\nabla f\left(x^{k-1}\right)\Vert }^2\\ +{\gamma }^2{L}^2{\Vert x^k-x^{k-1}\Vert }^2\text{+2}\gamma \langle x^{k+1}-x^k,g_k-\nabla f\left(x^k\right)\rangle \\ +\text{2}\gamma \langle x^{k+1}-x^k,g_{k-1}-\nabla f\left(x^{k-1}\right)\rangle +\text{2}\gamma \langle x^{k+1}-x^k,L\left(x^k-x^{k-1}\right)\rangle \\ +2{\gamma }^2\langle g_k-\nabla f\left(x^k\right),g_{k-1}-\nabla f\left(x^{k-1}\right)\rangle \\ +2{\gamma }^2\langle g_k-\nabla f\left(x^k\right),L\left(x^k-x^{k-1}\right)\rangle \\ +2{\gamma }^2\langle g_{k-1}-\nabla f\left(x^{k-1}\right),L\left(x^k-x^{k-1}\right)\rangle .\end{array}$

进一步利用不等式$2\langle a,b\rangle \le {\Vert a\Vert }^2\text{+}{\Vert b\Vert }^2$ 可得

$\begin{array}{c}{\Vert y^k-y^{k-1}\Vert }^2\le \left(1+3\gamma \right){\Vert x^{k+1}-x^k\Vert }^2+\left(\gamma +3{\gamma }^2\right){\Vert g_k-\nabla f\left(x^k\right)\Vert }^2\\ +\left(\gamma +3{\gamma }^2\right){\Vert g_{k-1}-\nabla f\left(x^{k-1}\right)\Vert }^2+\left(\gamma L^2+3{\gamma }^2{L}^2\right){\Vert x^k-x^{k-1}\Vert }^2.\end{array}$ (21)

由不等式${\Vert a+b+c\Vert }^2\le 3{\Vert a\Vert }^2\text{+3}{\Vert b\Vert }^2+3{\Vert c\Vert }^2$ 可得

$\begin{array}{l}{\Vert g_k-g_{k-1}\Vert }^2={\Vert g_k-\nabla f\left(x^k\right)+\nabla f\left(x^{k-1}\right)-g_{k-1}+\nabla f\left(x^{k-1}\right)-\nabla f\left(x^k\right)\Vert }^2\\ \le 3{\Vert g_k-\nabla f\left(x^k\right)\Vert }^2+3{\Vert \nabla f\left(x^{k-1}\right)-g_{k-1}\Vert }^2+3{\Vert \nabla f\left(x^{k-1}\right)-\nabla f\left(x^k\right)\Vert }^2.\end{array}$ (22)

结合公式(7)，(19)~(21)可得

$\begin{array}{l}\frac{1}{\gamma }{\Vert x^{k+1}-z^k\Vert }^2=\frac{1}{\gamma }{\Vert x^{k+1}-x^k\Vert }^2+\frac{1}{\gamma }{\Vert x^k-z^k\Vert }^2+\frac{2}{\gamma }\langle x^{k+1}-x^k,x^k-z^k\rangle \\ \le \frac{1}{\gamma }{\Vert x^{k+1}-x^k\Vert }^2+\left(\frac{1}{\gamma }+3\right){\Vert x^{k+1}-x^k\Vert }^2+\left(1+3\gamma \right){\Vert g_k-\nabla f\left(x^k\right)\Vert }^2\\ +\left(1+3\gamma \right){\Vert g_{k-1}-\nabla f\left(x^{k-1}\right)\Vert }^2+\left(L^2+3\gamma L^2\right){\Vert x^k-x^{k-1}\Vert }^2\\ +\frac{2}{\gamma }\langle x^{k+1}-x^k,x^k-x^{k+1}-\gamma \left(g_k-g_{k-1}\right)\rangle \\ \le \frac{1}{\gamma }{\Vert x^{k+1}-x^k\Vert }^2+\left(\frac{1}{\gamma }+3\right){\Vert x^{k+1}-x^k\Vert }^2+\left(1+3\gamma \right){\Vert g_k-\nabla f\left(x^k\right)\Vert }^2\\ +\left(1+3\gamma \right){\Vert g_{k-1}-\nabla f\left(x^{k-1}\right)\Vert }^2+\left(L^2+3\gamma L^2\right){\Vert x^k-x^{k-1}\Vert }^2-\frac{2}{\gamma }{\Vert x^{k+1}-x^k\Vert }^2\\ \text{ +}2\langle x^k-x^{k+1},g_k-g_{k-1}\rangle \text{. }\end{array}$

结合该式和不等式$2\langle a,b\rangle \le {\Vert a\Vert }^2\text{+}{\Vert b\Vert }^2$ ，公式(22)可得

$\begin{array}{l}\frac{1}{\gamma }{\Vert x^{k+1}-z^k\Vert }^2\le 4{\Vert x^{k+1}-x^k\Vert }^2+\left(4+3\gamma \right){\Vert g_k-\nabla f\left(x^k\right)\Vert }^2+\left(4+3\gamma \right){\Vert g_{k-1}-\nabla f\left(x^{k-1}\right)\Vert }^2\\ +\left(4L^2+3\gamma L^2\right){\Vert x^k-x^{k-1}\Vert }^2.\end{array}$

利用该式和公式(18)可推出

$\begin{array}{l}{D}_{\gamma }\left(x^{k+1},z^{k+1},y^k\right)-D_{\gamma }\left(x^{k+1},z^k,y^k\right)\\ \le -\frac{1}{\gamma }{\Vert y^{k+1}-y^k\Vert }^2+4{\Vert x^{k+1}-x^k\Vert }^2+\left(4+3\gamma \right){\Vert g_k-\nabla f\left(x^k\right)\Vert }^2\\ +\left(4+3\gamma \right){\Vert g_{k-1}-\nabla f\left(x^{k-1}\right)\Vert }^2+\left(4L^2+3\gamma L^2\right){\Vert x^k-x^{k-1}\Vert }^2.\end{array}$ (23)

最后处理y的前后迭代步关系。根据(2)可得

$D_{\gamma }\left(x^{k+1},z^{k+1},y^{k+1}\right)-D_{\gamma }\left(x^{k+1},z^{k+1},y^k\right)=\frac{1}{\gamma }\langle y^{k+1}-y^k,z^{k+1}-x^{k+1}\rangle .$

再由公式(7)整理可得

$D_{\gamma }\left(x^{k+1},z^{k+1},y^{k+1}\right)-D_{\gamma }\left(x^{k+1},z^{k+1},y^k\right)=\frac{1}{\gamma }{\Vert y^{k+1}-y^k\Vert }^2.$ (24)

所以结合$x,z,y$ 的前后迭代步关系，即公式(17) (23) (24)可以得证函数$D_{\gamma }$ 的前后迭代步的关系，即

$\begin{array}{l}{D}_{\gamma }\left(x^{k+1},z^{k+1},y^{k+1}\right)-D_{\gamma }\left(x^k,z^k,y^k\right)\\ \le \left(\frac{1}{2\beta }+4+3\gamma \right){\Vert \nabla f\left(x^k\right)-g_k\Vert }^2+\left(4+3\gamma \right){\Vert g_{k-1}-\nabla f\left(x^{k-1}\right)\Vert }^2\\ +\left(4L^2+3\gamma L^2\right){\Vert x^k-x^{k-1}\Vert }^2-\left(\frac{1}{2\gamma }-\frac{L}{2}-\frac{\beta }{2}-4\right){\Vert x^{k+1}-x^k\Vert }^2.\end{array}$ (25)

此时由于使用了随机梯度，所以接下来对公式(25)左右两边同时求期望，并利用假设2，可得

$\begin{array}{l}\mathbb{E}\left[D_{\gamma }\left(x^{k+1},z^{k+1},y^{k+1}\right)-D_{\gamma }\left(x^k,z^k,y^k\right)\right]\\ \le \left(\frac{1}{2\beta }+4+3\gamma \right)\left[{\sigma }_k^2+A_1\left(\mathbb{E}\left[{\Vert x^{k+1}-x^k\Vert }^2\right]\right)\right]\\ +\left(4+3\gamma \right)\left[{\sigma }_{k-1}^2+A_1\left(\mathbb{E}\left[{\Vert x^k-x^{k-1}\Vert }^2\right]\right)\right]\\ +\left(4L^2+3\gamma L^2\right){\Vert x^k-x^{k-1}\Vert }^2-\left(\frac{1}{2\gamma }-\frac{L}{2}-\frac{\beta }{2}-4\right){\Vert x^{k+1}-x^k\Vert }^2,\end{array}$ (26)

得证。

为了得到算法的下降性，本文定义如下的Lyapunov函数

$T^{k+1}=D_{\gamma }\left(x^{k+1},z^{k+1},y^{k+1}\right)+a{\sigma }_{k+1}^2+b{\sigma }_k^2+c{\Vert x^{k+1}-x^k\Vert }^2,$

其中$a,b,c$ 的取值分别为

$a=\frac{b+\frac{1}{2\beta }+4+3\gamma }{\rho }=\frac{\left(4+3\gamma \right)\left(1+\rho \right)\cdot 2\beta +\rho }{2\beta {\rho }^2},b=\frac{4+3\gamma }{\rho },c=4L^2+3\gamma L^2+\frac{4+3\gamma }{\rho }{A}_1.$

引理3.2 若假设1与假设2成立，${\left\{\left(x^k,z^k,y^k\right)\right\}}_{k\in \mathbb{N}}$ 是由随机DR算法生成的序列，步长$\gamma$ 满足$\gamma \in \left(0,\frac{\sqrt{B^2+\frac{24\left({\rho }^2+\rho +1\right)A_1}{{\rho }^2}}-B}{48\left({\rho }^2+\rho +1\right)A_1}\cdot {\rho }^2\right)$ ，其中$B=L+\beta +8+\left(\frac{9\rho +8}{{\rho }^2}+\frac{1}{\beta }+8\right)A_1$ 。对于任意$k\in \mathbb{N}$ ，我们有

$\mathbb{E}\left[T^{k+1}\right]\le \mathbb{E}\left[T^k\right]-B_1\mathbb{E}{\Vert x^{k+1}-x^k\Vert }^2,$

其中$B_1=\frac{1}{2\gamma }-\frac{L}{2}-\frac{\beta }{2}-4-a{A}_1-\left(\frac{1}{2\beta }+4+3\gamma \right)A_1>0$ 。

证明：由引理3.1和函数T的定义可得到以下不等式

$\begin{array}{l}\mathbb{E}\left[T^{k+1}\right]=\mathbb{E}\left[D_{\gamma }\left(x^{k+1},z^{k+1},y^{k+1}\right)\right]+a{\sigma }_{k+1}^2+b{\sigma }_k^2+c\mathbb{E}{\Vert x^{k+1}-x^k\Vert }^2\\ \le \mathbb{E}\left[D_{\gamma }\left(x^k,z^k,y^k\right)\right]+a{\sigma }_k^2+b{\sigma }_{k-1}^2+c\mathbb{E}{\Vert x^k-x^{k-1}\Vert }^2\\ -\left(\frac{1}{2\gamma }-\frac{L}{2}-\frac{\beta }{2}-4-a{A}_1-\left(\frac{1}{2\beta }+4+3\gamma \right)A_1\right)\mathbb{E}{\Vert x^{k+1}-x^k\Vert }^2\\ =\mathbb{E}\left[T^k\right]-B_1\mathbb{E}{\Vert x^{k+1}-x^k\Vert }^2,\end{array}$ (27)

由于$\gamma$ 满足$\gamma \in \left(0,\frac{\sqrt{B^2+\frac{24\left({\rho }^2+\rho +1\right)A_1}{{\rho }^2}}-B}{48\left({\rho }^2+\rho +1\right)A_1}\cdot {\rho }^2\right)$ ，其中$B=L+\beta +8+\left(\frac{9\rho +8}{{\rho }^2}+\frac{1}{\beta }+8\right)A_1$ ，所以$B_1=\frac{1}{2\gamma }-\frac{L}{2}-\frac{\beta }{2}-4-a{A}_1-\left(\frac{1}{2\beta }+4+3\gamma \right)A_1>0$ ，得证。

本文将基于KL框架分析算法的收敛性，上文已得到充分下降性，接下来我们要证明相对误差条件。

引理3.3 若假设1和假设2成立，令$\left\{\left(x^{k+1},z^{k+1},y^{k+1}\right)\right\}$ 是由随机DR算法生成的序列，那么存在${\omega }^{k+1}\in \partial D_{\gamma }\left(x^{k+1},z^{k+1},y^{k+1}\right)$ ，使得

$E\Vert {\omega }^{k+1}\Vert \le \left(2L+\frac{1}{\gamma }+2A_2\right)E\Vert x^{k+1}-x^k\Vert +\left(A_2+\frac{2}{\gamma }\right)E\Vert x^{k+2}-x^{k+1}\Vert +2E{\xi }_k+E{\xi }_{k+1}.$

证明：令

$\{\begin{array}{l}{\omega }_x^{k+1}=\nabla f\left(x^{k+1}\right)-\frac{1}{\gamma }\left(y^{k+1}-x^{k+1}\right)\\ {\omega }_z^{k+1}=\frac{1}{\gamma }\left(2x^{k+1}-y^k-z^{k+1}\right)+\frac{1}{\gamma }\left(y^{k+1}-z^{k+1}\right)\\ {\omega }_y^{k+1}=\frac{1}{\gamma }\left(z^{k+1}-x^{k+1}\right).\end{array}$

则我们有${\omega }^{k+1}=\left({\omega }_x^{k+1},{\omega }_z^{k+1},{\omega }_y^{k+1}\right)\in \partial D_{\gamma }\left(x^{k+1},z^{k+1},y^{k+1}\right)$ 。由公式(12)与定义2.1.3可得

$\begin{array}{l}\Vert {\omega }_x^{k+1}\Vert =\Vert \nabla f\left(x^{k+1}\right)-\frac{1}{\gamma }\left(y^{k+1}-x^{k+1}\right)\Vert \\ =\Vert \nabla f\left(x^{k+1}\right)-\nabla f\left(x^k\right)+\nabla f\left(x^k\right)-g_k+g_k-\frac{1}{\gamma }\left(y^{k+1}-x^{k+1}\right)\Vert \\ \le L\Vert x^{k+1}-x^k\Vert +\Vert \nabla f\left(x^k\right)-g_k\Vert +\frac{1}{\gamma }\Vert y^{k+1}-y^k\Vert \text{. }\end{array}$

结合公式(19)整理可得

$\Vert {\omega }_x^{k+1}\Vert \le L\Vert x^{k+1}-x^k\Vert +\frac{1}{\gamma }\Vert x^{k+2}-x^{k+1}\Vert +\Vert \nabla f\left(x^k\right)-g_k\Vert +\Vert g_{k+1}-g_k\Vert .$ (28)

整理可得

$\begin{array}{l}\Vert {\omega }_z^{k+1}\Vert =\frac{1}{\gamma }\Vert y^{k+1}-y^k\Vert \\ \le \frac{1}{\gamma }\Vert x^{k+1}-x^k\Vert +\Vert g_{k+1}-g_k\Vert .\end{array}$ (29)

针对${\omega }_y^{k+1}$ ，有

$\begin{array}{l}\Vert {\omega }_y^{k+1}\Vert =\frac{1}{\gamma }\Vert y^{k+1}-y^k\Vert \\ \le \frac{1}{\gamma }\Vert x^{k+2}-x^{k+1}\Vert +\Vert g_{k+1}-g_k\Vert ,\end{array}$ (30)

其中不等式是由公式(19)得到的。由公式(28)，(29)，(30)可得

$\begin{array}{l}\Vert {\omega }^{k+1}\Vert \le \left(L+\frac{1}{\gamma }\right)\Vert x^{k+1}-x^k\Vert +\frac{2}{\gamma }\Vert x^{k+2}-x^{k+1}\Vert +\Vert \nabla f\left(x^k\right)-g_k\Vert +\Vert g_{k+1}-g_k\Vert \\ \le \left(L+\frac{1}{\gamma }\right)\Vert x^{k+1}-x^k\Vert +\frac{2}{\gamma }\Vert x^{k+2}-x^{k+1}\Vert +\Vert \nabla f\left(x^k\right)-g_k\Vert \\ +\Vert g_{k+1}-\nabla f\left(x^{k+1}\right)+\nabla f\left(x^{k+1}\right)-\nabla f\left(x^k\right)+\nabla f\left(x^k\right)-g_k\Vert \\ \le \left(2L+\frac{1}{\gamma }\right)\Vert x^{k+1}-x^k\Vert +2\Vert \nabla f\left(x^k\right)-g_k\Vert \\ +\Vert \nabla f\left(x^{k+1}\right)-g_{k+1}\Vert +\frac{2}{\gamma }\Vert x^{k+2}-x^{k+1}\Vert .\end{array}$

对上式左右两边同时求期望可得

$\begin{array}{l}E\Vert {\omega }^{k+1}\Vert \le \left(2L+\frac{1}{\gamma }\right)E\Vert x^{k+1}-x^k\Vert +2E\Vert \nabla f\left(x^k\right)-g_k\Vert \\ +E\Vert \nabla f\left(x^{k+1}\right)-g_{k+1}\Vert +\frac{2}{\gamma }E\Vert x^{k+2}-x^{k+1}\Vert \\ \le \left(2L+\frac{1}{\gamma }+2A_2\right)E\Vert x^{k+1}-x^k\Vert \\ +\left(A_2+\frac{2}{\gamma }\right)E\Vert x^{k+2}-x^{k+1}\Vert +2E{\xi }_k+E{\xi }_{k+1},\end{array}$

其中第二个不等式是由公式(11)得到的。相对误差界条件得证。

为便于收敛性分析，我们用$S\left({\mu }^0\right)$ 表示由初始值${\mu }^0$ 产生的序列${\left\{{\mu }^k=\left(x^k,y^k,z^k\right)\right\}}_{k\in \mathbb{N}}$ 的聚点集。

$S\left({\mu }^0\right):=\left\{x*|存在一个子列{\left\{{\mu }^{k_j}\right\}}_{j=0}^{\infty }使得\underset{j\to \infty }{lim}{\mu }^0=\overline{\mu }\right\}.$

命题3.1 假设1，2成立，令${\left\{{\mu }^k=\left(x^k,y^k,z^k\right)\right\}}_{k\in \mathbb{N}}$ 是由随机DR分裂算法所生成的迭代序列，且该序列有界，其初始点为${\mu }^0=\left(x^0,y^0,z^0\right)$ 。则可以得到以下结论：

(1) ${\lim }_{k\to \infty }E\left[T_k\right]={\lim }_{k\to \infty }E\left[D_{\gamma }\left({\mu }^k\right)\right]={\lim }_{k\to \infty }E\left[F\left(y^k\right)\right]=F^{*}$ ，其中$F^{*}\in \left[F,\infty \right)$ ；

(2) ${\lim }_{k\to \infty }E\left[dist(0,\partial D_{\gamma }\left({\mu }^k\right))\right]=0$ ；

(3) 对于所有的$\overline{\mu }=\left(\overline{x},\overline{y},\overline{z}\right)\in S\left({\mu }^0\right)$ 有集合$S\left({\mu }^0\right)\ne \varphi$ 和$E\left[dist\left(0,\partial D_{\gamma }\left(\overline{\mu }\right)\right)\right]=0$ ；

(4) $\text{dist}\left({\mu }^k,S\left({\mu }^0\right)\right)\stackrel{a.s.}{\to }0$，当$k\to \infty$ ；

(5) $S\left({\mu }^0\right)$ 是几乎处处紧的且联通的；

(6) 对于所有的$\overline{\mu }\in S\left({\mu }^0\right)$ ，有$E\left[D_{\gamma }\left(\overline{\mu }\right)\right]=F^{*}$ 。

证明：(1) 根据引理3.2，我们知道$E\left[T_k\right]$ 是收敛的且${\lim }_{k\to \infty }E\left[{\Vert x^{k+1}-x^k\Vert }^2\right]=0$ 。进而我们能得到${\lim }_{k\to \infty }E\left[{\Vert x^{k+1}-x^k\Vert }^2\right]=0$ ，${\lim }_{k\to \infty }E\left[{\Vert z^{k+1}-y^{k+1}\Vert }^2\right]=0$ ，根据$x^{k+1}$ 的更新，我们有$z^{k+1}-z^k=x^{k+1}-x^k+x^{k-1}-x^k+y^{k+1}-y^k$ ，进而可推导出${\lim }_{k\to \infty }E\left[{\Vert z^{k+1}-z^k\Vert }^2\right]=0$ 。同理我们可以得到${\lim }_{k\to \infty }E\left[{\Vert {\mu }^{k+1}-{\mu }^k\Vert }^2\right]=0$ 。所以我们可以推出

${\lim }_{k\to \infty }E\left[T_k\right]={\lim }_{k\to \infty }E\left[D_{\gamma }\left({\mu }^k\right)\right]={\lim }_{k\to \infty }E\left[F\left(y^k\right)\right]=F^{*}.$

(2) 通过引理3.3，我们可以推导出$w_k\in \partial D_{\gamma }\left({\mu }^k\right)$ ，存在一个常数$b_2$ 使得

$E\left[\Vert w^k\Vert \right]\le \left(2L+\frac{1}{\gamma }+2A_2\right)E\Vert x^k-x^{k-1}\Vert +\left(A_2+\frac{2}{\gamma }\right)E\Vert x^{k+1}-x^k\Vert +2E{\xi }_{k-1}+E{\xi }_k.$

由于${\lim }_{k\to \infty }E\left[{\Vert x^{k+1}-x^k\Vert }^2\right]=0$ ，易得${\lim }_{k\to \infty }E\left[\Vert y^k-y^{k-1}\Vert \right]={\lim }_{k\to \infty }E\left[\Vert y^{k+1}-y^k\Vert \right]=0$ 。

又因为假设2，故我们有${\lim }_{k\to \infty }E\left[dist\left(0,\partial D_{\gamma }\left({\mu }^k\right)\right)\right]=0$ 。

(3) 对任意$\overline{\mu }=\left(\overline{x},\overline{y},\overline{z}\right)\in S\left({\mu }^0\right)$ ，让${\left\{{\mu }^{k_j}\right\}}_{j=0}^{\infty }$ 为${\left\{{\mu }^k\right\}}_{k=0}^{\infty }$ 的收敛到$\overline{\mu }$ 的子序列，我们有${\lim }_{j\to \infty }h\left(z^{k_j+1}\right)=h\left(\overline{z}\right)$ 。根据f的连续性，我们可以得到${\lim }_{j\to \infty }{D}_{\gamma }\left({\mu }^{k_j}\right)=D_{\gamma }\left(\overline{\mu }\right)$ 。根据引理3.3和上面对(2)的分析我们得到了$w^{k_j}\in \partial D_{\gamma }\left({\mu }^{{}_{k_j}}\right)$ 和${\lim }_{j\to \infty }E\left[\Vert w^{k_j}\Vert \right]=0$ ，通过进一步利用次微分的闭性，我们有${\lim }_{j\to \infty }E\left[\Vert w^{k_j}\Vert \right]=E\left[dist\left(0,\partial D_{\gamma }\left(\overline{\mu }\right)\right)\right]=0$ 。

(4)和(5)对于任意满足$\Vert {\mu }^k-{\mu }^{k-1}\Vert \stackrel{a.s.}{\to }0,k\to \infty$条件的序列成立。这一结论可由[20, Lemma 5, Remark 5]和[21, Lemma 4.3 (5) (6)]证到。

(6)从(1)的证明中，我们得到了${\lim }_{k\to \infty }E\left[D_{\gamma }\left({\mu }^k\right)\right]=F^{*}$ ，则可以推导出对任意收敛于$\overline{\mu }\in S\left({\mu }^0\right)$ 的序列${\left\{{\mu }^{k_j}\right\}}_{j=0}^{\infty }$ 都满足${\lim }_{k\to \infty }E\left[D_{\gamma }\left({\mu }^k\right)\right]=F^{*}$ 。因为函数f的连续性以及${\lim }_{j\to \infty }h\left(z^{k_j+1}\right)=h\left(\overline{z}\right)$ ，我们有${\lim }_{j\to \infty }E\left[D_{\gamma }\left({\mu }^{k_j}\right)\right]=E\left[D_{\gamma }\left(\overline{\mu }\right)\right]=E\left[F\left(\overline{y}\right)\right]$ ，所以，这可以推导出$D_{\gamma }$ 在$S\left({\mu }^0\right)$ 上的期望为常数。

充分下降性和相对误差条件已被建立，接下来我们要证明随机DR分裂算法在KL性质下的全局收敛性。对于任意满足p阶矩$\left(p\ge 1\right)$ 有限的随机变量X，我们定义${\left|X\right|}_p={\left(\mathbb{E}\left[X^p\right]\right)}^{1/p},p\ge 1$ 。则我们可以得到${\left|X\right|}_p\le {\left|X\right|}_q,\forall \text{1}\le p\le q$ 。

引理3.4 [21] 在假设1，假设2成立的条件下，令${\left\{{\mu }^k=\left(x^k,z^k,y^k\right)\right\}}_{k\in \mathbb{N}}$ 是由随机DR分裂算法产生的序列，如果序列${\left\{{\mu }^k\right\}}_{k\in \mathbb{N}}$ 是有界的，并且函数$D_{\gamma }^{}$ 是一个半代数函数，假设$D_{\gamma }^{}$ 满足$\phi (t)=a{t}^{1-\theta }$ 的KL性质，即存在$k_0>0$ ，使得

${\phi }^{\prime }\left(E\left[D_{\gamma }^k-F_k^{*}\right]\right)E\left[dist\left(0,\partial D_{\gamma }^k\right)\right]\ge 1,k>k_0.$

其中${\left\{F_k^{*}\right\}}_{k=0}^{\infty }$ 是收敛到$\mathbb{E}\left[D_{\gamma }\left(\overline{\mu }\right)\right]$ 的非递减序列。

定理3.1 (随机DR分裂算法的全局收敛)在假设1，假设2成立的条件下，令${\left\{{\mu }^k=\left(x^k,z^k,y^k\right)\right\}}_{k\in \mathbb{N}}$ 是由随机DR分裂算法产生的序列且假设其有界。假设$D_{\gamma }^k$ 满足KL性质，则${\displaystyle \sum _{k=0}^{\infty }E\Vert x^{k+1}-x^k\Vert }<\infty$ 成立，且算法全局收敛。

证明：由$D_{\gamma }^k$ 满足KL性质可知，存在常数$k_1>0$ 和函数$\phi (x)=a{x}^{1-\theta },\theta \in \left(0,1\right)$ 满足

$\phi \text{'}\left(\mathbb{E}\left[D_{\gamma }^k-F_k^{\ast }\right]\right)\mathbb{E}\left[dist\left(0,\partial D_{\gamma }^k\right)\right]\ge 1,$

其中${\left\{F_k^{\ast }\right\}}_{k\in {\rm N}}$ 是一个收敛到$\mathbb{E}\left[D_{\gamma }\left(\overline{\mu }\right)\right]$ 的非减序列，$\overline{\mu }$ 为序列${\left\{{\mu }^k=\left(x^k,y^k,z^k\right)\right\}}_{k\in \mathbb{N}}$ 的子列的极限点。当$\theta \in \left(0,\frac{1}{2}\right)$ 时，$D_{\gamma }^k$ 满足指数为$\frac{1}{2}$ 时的KL性质。因此只需分析$\theta \in \left[\frac{1}{2},1\right)$ 的情况。

由假设2可得

$\mathbb{E}\left[{\xi }_k\right]=\mathbb{E}\left[{\displaystyle \sum _{i=1}^s\Vert {\alpha }_k^i\Vert }\right]\le \sqrt{s}{\left(\mathbb{E}{\left[{\displaystyle \sum _{i=1}^s\Vert {\alpha }_k^i\Vert }\right]}^2\right)}^{1/2}\le \sqrt{s}{\left(\mathbb{E}\left[{\sigma }_k^2\right]\right)}^{1/2}=\sqrt{s}{\left|{\sigma }_k\right|}_2.$

由上式以及性质2.2.1，还有$\left\{F_s^{*}\right\}$ 的非减性整理KL不等式可得

$\begin{array}{l}E\left[dist\left(0,\partial D_{\gamma }^k\right)\right]\\ \le \left(A_2+\frac{2}{\gamma }\right)E\Vert x^{k+1}-x^k\Vert +B_{2}E\Vert x^k-x^{k-1}\Vert +2E{\xi }_{k-1}+E{\xi }_k\\ \le \left(A_2+\frac{2}{\gamma }\right)E{\left|x^{k+1}-x^k\right|}_2+B_{2}E{\left|x^k-x^{k-1}\right|}_2+2\sqrt{s}{\left|{\sigma }_{k-1}\right|}_2+\sqrt{s}{\left|{\sigma }_k\right|}_2,\end{array}$ (31)

其中$B_2=2L+\frac{1}{\gamma }+2A_2$ 。

在$\rho \in \left(0,1\right)$ 时有以下不等式成立

$\begin{array}{l}{\left|{\sigma }_k\right|}_2\le \sqrt{\left(1-\rho \right){\left|{\sigma }_{k-1}\right|}_2^2+A_3{\left|x^k-x^{k-1}\right|}_2^2}\\ \le \sqrt{\left(1-\rho \right)}{\left|{\sigma }_{k-1}\right|}_2+\sqrt{A_3}{\left|x^k-x^{k-1}\right|}_2\\ \le \left(1-\frac{\rho }{2}\right){\left|{\sigma }_{k-1}\right|}_2+\sqrt{A_3}{\left|x^k-x^{k-1}\right|}_2,\end{array}$

其中第二步是由不等式$\sqrt{x+y}\le \sqrt{x}+\sqrt{y}$ 得到。进而可以推出以下不等式

${\left|{\sigma }_{k-1}\right|}_2\le \frac{2\sqrt{A_3}}{\rho }{\left|x^k-x^{k-1}\right|}_2+\frac{2}{\rho }\left({\left|{\sigma }_{k-1}\right|}_2-{\left|{\sigma }_k\right|}_2\right),{\left|{\sigma }_k\right|}_2\le \frac{2\sqrt{A_3}}{\rho }{\left|x^{k+1}-x^k\right|}_2+\frac{2}{\rho }\left({\left|{\sigma }_k\right|}_2-{\left|{\sigma }_{k+1}\right|}_2\right).$

由此将上式左右两边分别乘$2\sqrt{s}$ ，$\sqrt{s}$ 作为系数可以计算得到

$2\sqrt{s}{\left|{\sigma }_{k-1}\right|}_2\le \frac{4\sqrt{s{A}_3}}{\rho }{\left|x^k-x^{k-1}\right|}_2+\frac{4\sqrt{s}}{\rho }\left({\left|{\sigma }_{k-1}\right|}_2-{\left|{\sigma }_k\right|}_2\right),$ (32)

$\sqrt{s}{\left|{\sigma }_k\right|}_2\le \frac{2\sqrt{s{A}_3}}{\rho }{\left|x^{k+1}-x^k\right|}_2+\frac{2\sqrt{s}}{\rho }\left({\left|{\sigma }_k\right|}_2-{\left|{\sigma }_{k+1}\right|}_2\right).$ (33)

所以综合公式(31)，(32)，(33)可以计算得出此不等式

$\begin{array}{l}\mathbb{E}\left[dist\left(0,\partial D_{\gamma }^k\right)\right]\le \left(B_2+\frac{4\sqrt{s{A}_3}}{\rho }\right){\left|x^k-x^{k-1}\right|}_2+\left(A_2+\frac{2}{\gamma }+\frac{2\sqrt{s{A}_3}}{\rho }\right){\left|x^{k+1}-x^k\right|}_2\\ +\frac{4\sqrt{s}}{\rho }\left({\sigma }_{k-1}^2-{\sigma }_k^2\right)+\frac{2\sqrt{s}}{\rho }\left({\sigma }_k^2-{\sigma }_{k+1}^2\right).\end{array}$

我们定义一个新的序列$C_k$

$\begin{array}{l}{C}_k:=\left(B_2+\frac{4\sqrt{s{A}_3}}{\rho }\right){\left|x^k-x^{k-1}\right|}_2+\left(A_2+\frac{2}{\gamma }+\frac{2\sqrt{s{A}_3}}{\rho }\right){\left|x^{k+1}-x^k\right|}_2\\ +\frac{4\sqrt{s}}{\rho }\left({\sigma }_{k-1}^2-{\sigma }_k^2\right)+\frac{2\sqrt{s}}{\rho }\left({\sigma }_k^2-{\sigma }_{k+1}^2\right).\end{array}$

记$M=\max \left\{\left(B_2+\frac{4\sqrt{s{A}_3}}{\rho }\right),\left(A_2+\frac{2}{\gamma }+\frac{2\sqrt{s{A}_3}}{\rho }\right)\right\}$ ，则有

$C_k\le M\left[{\left|x^{k+1}-x^k\right|}_2+{\left|x^k-x^{k-1}\right|}_2+\left({\sigma }_{k-1}^2-{\sigma }_k^2\right)+\left({\sigma }_k^2-{\sigma }_{k+1}^2\right)\right].$ (34)

定义函数$\phi \left(t\right)=a{t}^{1-\theta },\theta \in \left[\frac{1}{2},1\right)$ 。对于所有的$k\ge k_1$ ，$D_{\gamma }^k$ 满足KL不等式，所以

$\begin{array}{l}\phi \text{'}\left(\mathbb{E}\left[D_{\gamma }^k-F_k^{\ast }\right]\right)=a\left(1-\theta \right){\left(\mathbb{E}\left[D_{\gamma }^k-F_k^{\ast }\right]\right)}^{-\theta }\\ \Rightarrow {\left(\mathbb{E}\left[D_{\gamma }^k-F_k^{\ast }\right]\right)}^{\theta }\le a\left(1-\theta \right)C_k.\end{array}$

而对于所有的$k\ge k_2$ ，结合假设2可知存在常数$c>0$ 满足以下不等式

$\begin{array}{l}{\left(\mathbb{E}\left[a{\sigma }_k^2+b{\sigma }_{k-1}^2+c{\Vert x^k-x^{k-1}\Vert }^2\right]\right)}^{\theta }\le O\left({\left(\Vert x^{k+1}-x^k\Vert +\Vert x^k-x^{k-1}\Vert +{\sigma }_{k-1}^2\right)}^{\theta }\right)\\ \le c{C}_k.\end{array}$

又因为${\left(a+b\right)}^{\theta }\le a^{\theta }+b^{\theta },\theta \in \left[\frac{1}{2},1\right)$ ，因此可以得到对于所有的$k\ge k_3=\max \left\{k_1,k_2\right\}$ ，以下不等式成立

$\begin{array}{l}{\left(\mathbb{E}\left[T_{\gamma }^k-F_k^{*}\right]\right)}^{\theta }=(\mathbb{E}[D_{\gamma }\left(x^k,z^k,y^k\right)+a{\sigma }_k^2+b{\sigma }_{k-1}^2+c{\Vert x^k-x^{k-1}\Vert }^2{-F_k^{*}])}^{\theta }\\ \le {\left(\mathbb{E}\left[D_{\gamma }^k-F_k^{\ast }\right]\right)}^{\theta }+{\left(\mathbb{E}\left[a{\sigma }_k^2+b{\sigma }_{k-1}^2+c{\Vert x^k-x^{k-1}\Vert }^2\right]\right)}^{\theta }\\ \le a\left(1-\theta \right)C_k+c{C}_k.\end{array}$

进而可以得到以下不等式

${\left(\mathbb{E}\left[T_{\gamma }^k-F_k^{*}\right]\right)}^{\theta }\le ad\left(1-\theta \right)C_k,\forall k>k_2,$ (35)

其中d满足$ad\left(1-\theta \right)\ge a\left(1-\theta \right)+c$ 。定义函数$\varphi \left(t\right)=ad{t}^{1-\theta },\theta \in \left[\frac{1}{2},1\right)$ ，由(35)可得

${\varphi }^{\prime }\left(\mathbb{E}\left(T^k-F_k^{*}\right)\right)\ge C_k^{-1}.$

对于所有的$k\in \mathbb{N}$ ，我们定义${\Delta }_{k,k+1}=\varphi \left(\mathbb{E}\left[T_{\gamma }^k-F_k^{\ast }\right]\right)-\varphi \left(\mathbb{E}\left[T_{\gamma }^{k+1}-F_{k+1}^{\ast }\right]\right).$

由函数$\varphi$ 的凹性可得

$\begin{array}{l}{\Delta }_{k,k+1}\ge {\varphi }^{\prime }\left(\mathbb{E}\left[T_{\gamma }^k-F_k^{\ast }\right]\right)\left(\mathbb{E}\left[T_{\gamma }^{k+1}-T_{\gamma }^k+F_k^{\ast }-F_{k+1}^{\ast }\right]\right)\\ \ge {\varphi }^{\prime }\left(\mathbb{E}\left[T_{\gamma }^k-F_k^{\ast }\right]\right)\mathbb{E}\left[T_{\gamma }^{k+1}-T_{\gamma }^k\right]\\ \ge \frac{B_1\mathbb{E}{\Vert x^{k+1}-x^k\Vert }^2}{C_k}\text{. }\end{array}$

综合上式和(34)，整理可得以下不等式

$9\mathbb{E}{\Vert x^{k+1}-x^k\Vert }^2\le \frac{9M}{B_1}{\Delta }_{k,k+1}\left[{\left|x^{k+1}-x^k\right|}_2+{\left|x^k-x^{k-1}\right|}_2+\frac{4\sqrt{s}}{\rho M}\left({\sigma }_{k-1}^2-{\sigma }_k^2\right)+\frac{2\sqrt{s}}{\rho M}\left({\sigma }_k^2-{\sigma }_{k+1}^2\right)\right].$ 又因为$\mathbb{E}X\le \sqrt{\mathbb{E}{X}^2}$ ，并且对于任意的$u,v\ge 0$ ，$2\sqrt{uv}\le u+v$ ，因此对上式左右两边同时开根号可得，对于所有的$k\ge k_3=\max \left\{k_1,k_2\right\}$ ，

$\begin{array}{l}3{\left|x^{k+1}-x^k\right|}_2\le \frac{9M}{4B_1}{\Delta }_{k,k+1}+{\left|x^{k+1}-x^k\right|}_2+{\left|x^k-x^{k-1}\right|}_2\\ +\frac{4\sqrt{s}}{\rho M}\left({\sigma }_{k-1}^2-{\sigma }_k^2\right)+\frac{2\sqrt{s}}{\rho M}\left({\sigma }_k^2-{\sigma }_{k+1}^2\right).\end{array}$

化简可得

$\begin{array}{l}2{\left|x^{k+1}-x^k\right|}_2\le \frac{9M}{4B_1}{\Delta }_{k,k+1}+{\left|x^k-x^{k-1}\right|}_2\\ +\frac{4\sqrt{s}}{\rho M}\left({\sigma }_{k-1}^2-{\sigma }_k^2\right)+\frac{2\sqrt{s}}{\rho M}\left({\sigma }_k^2-{\sigma }_{k+1}^2\right).\end{array}$

最后对上式左右两边同时累加化简可以得到

$\begin{array}{c}{\displaystyle \sum _{k\ge k_3}{\left|x^{k+1}-x^k\right|}_2}\le \frac{9M}{4B_1}\left[\varphi \left(T_{k_3}-F_{k_3}^{*}\right)-\varphi \left(T_{\infty }-F_{\infty }^{*}\right)\right]+{\left|x^{k_3}-x^{k_3-1}\right|}_2\\ +\frac{4\sqrt{s}}{\rho M}\left({\sigma }_{k_3-1}^2-{\sigma }_{\infty }^2\right)+\frac{2\sqrt{s}}{\rho M}\left({\sigma }_{k_3}^2-{\sigma }_{\infty }^2\right)\\ <\infty .\end{array}$

因此可以得到

${\displaystyle \sum _{k\ge k_3}E\Vert x^{k+1}-x^k\Vert }={\displaystyle \sum _{k\ge k_3}{\left|x^{k+1}-x^k\right|}_1}\le {\displaystyle \sum _{k\ge k_3}{\left|x^{k+1}-x^k\right|}_2}<\infty .$

进而可知序列${\left\{x^k\right\}}_{k\in \mathbb{N}}$ 柯西收敛。

由公式(20)可得

$\Vert y^{k+1}-y^k\Vert \le \Vert x^{k+2}-x^{k+1}\Vert +\gamma \Vert g_{k+1}-\nabla f\left(x^{k+1}\right)\Vert +\gamma \Vert \nabla f\left(x^k\right)-g_k\Vert +\gamma L\Vert x^{k+1}-x^k\Vert .$

对上式左右两边同时求期望可得

$\begin{array}{c}E\Vert y^{k+1}-y^k\Vert \le E\Vert x^{k+2}-x^{k+1}\Vert +\gamma E\Vert g_{k+1}-\nabla f\left(x^{k+1}\right)\Vert \\ +\gamma E\Vert \nabla f\left(x^k\right)-g_k\Vert +\gamma LE\Vert x^{k+1}-x^k\Vert \\ \le \left(\gamma A_2+1\right)E\Vert x^{k+2}-x^{k+1}\Vert +\left(\gamma A_2+\gamma L\right)E\Vert x^{k+1}-x^k\Vert \\ +\gamma E\left[{\xi }_{k+1}\right]+\gamma E\left[{\xi }_k\right].\end{array}$

又因为${\displaystyle \sum _{k\ge k_3}E\Vert x^{k+1}-x^k\Vert }<\infty$ ，对上式左右两边同时累和可得

$\begin{array}{c}{\displaystyle \sum _{k\ge k_3}E\Vert y^{k+1}-y^k\Vert }\le \left(\gamma A_2+1\right){\displaystyle \sum _{k\ge k_3}E\Vert x^{k+2}-x^{k+1}\Vert }+\left(\gamma A_2+\gamma L\right){\displaystyle \sum _{k\ge k_3}E\Vert x^{k+1}-x^k\Vert }\\ +\gamma {\displaystyle \sum _{k\ge k_3}E\left[{\xi }_{k+1}\right]}+\gamma {\displaystyle \sum _{k\ge k_3}E\left[{\xi }_k\right]}\\ <\infty .\end{array}$

由公式(7)可得

$\begin{array}{c}\Vert z^{k+1}-z^k\Vert =\Vert y^{k+1}-y^k+x^{k+1}-y^k+y^{k-1}-x^k\Vert \\ \le \Vert y^{k+1}-y^k\Vert +\Vert y^k-y^{k-1}\Vert +\Vert x^{k+1}-x^k\Vert .\end{array}$

由对上式左右两边同时求期望并累和可得

$\begin{array}{c}{\displaystyle \sum _{k\ge k_3}E\Vert z^{k+1}-z^k\Vert }={\displaystyle \sum _{k\ge k_3}E\Vert y^{k+1}-y^k+x^{k+1}-y^k+y^{k-1}-x^k\Vert }\\ \le {\displaystyle \sum _{k\ge k_3}E\Vert y^{k+1}-y^k\Vert }+{\displaystyle \sum _{k\ge k_3}E\Vert y^k-y^{k-1}\Vert }+{\displaystyle \sum _{k\ge k_3}E\Vert x^{k+1}-x^k\Vert }\\ <\infty .\end{array}$

所以，序列$\left\{x^k\right\},\left\{y^k\right\},\left\{z^k\right\}\left(k\in \mathbb{N}\right)$ 均柯西收敛。因此算法生成序列$\left\{\left(x^k,z^k,y^k\right)\right\}$ $\left(k\in \mathbb{N}\right)$ 柯西收敛，即该算法全局收敛。

4. 数值实验

本节，我们应用本文提出的随机DR分裂算法(SDR)来求解稀疏Logistic回归问题，并将该算法与经典的邻近梯度算法PG以及Prox-SARAH进行比较，以阐述本文所提出的算法的高效性。

首先，我们考虑带有$l_1{l}_2$ 正则化的稀疏Logistic回归模型，如今已被广泛应用于二分类问题。该模型的具体表述如下：

$\underset{x\in {ℝ}^d}{\min }F\left(x\right):=\frac{1}{N}{\displaystyle \sum }_{i=1}^N\log \left(1+\exp \left(-b_i{a}_i^{T}x\right)\right)+{\lambda }_1{\Vert x\Vert }_1+\frac{{\lambda }_2}{2}{\Vert x\Vert }^2\text{,}$

其中$a_i\in {ℝ}^d,b_i\in \left\{-1,1\right\},i\in \left\{1,2,\cdots ,N\right\}$ 为样本的特征以及相应的标签，${\lambda }_1,{\lambda }_2>0$ 为正则化参数，用以控制变量的稀疏性。通过令$f\left(x\right)=\frac{1}{N}{\displaystyle \sum }_{i=1}^N\log \left(1+\exp \left(-b_i{a}_i^{T}x\right)\right),$ $h\left(x\right)={\lambda }_1{\Vert x\Vert }_1+\frac{{\lambda }_2}{2}{\Vert x\Vert }^2$ ，上述稀疏Logistic回归问题即可转化为问题(1)。

在实验中，我们随机生成特征矩阵$A=\left(a_1,a_2,\cdots ,a_N\right)\in {ℝ}^{d\times N}$ ，并计算出对应的标签$b={\left(b_1,b_2,\cdots ,b_N\right)}^{\text{T}}\in {ℝ}^N$ ，稀疏正则化参数设置为${\lambda }_1={\lambda }_2={10}^{-5}$ 。针对问题规模，本文选择样本量为$N=1000$ 和$N=1500$ ，以及$d=50$ 和$d=100$ 。两两组合共构成4种不同的数据规模设置，以对比分析算法在不同规模下的性能表现。此外，我们将算法的最大迭代次数统一设置为20,000，并以相对误差$\frac{F(x)-F\left(x^{*}\right)}{F\left(x^{*}\right)}\le 2\times {10}^{-4}$ 作为算法的停机准则，其中$F\left(x^{*}\right)$ 为最小的函数值。

数值实验结果见下图1，针对不同的样本规模，我们提出的算法SDR总是能够在规定的最大迭代次数内达到收敛，且收敛所用的时间远少于PG和Prox-SARAH，收敛速度最快。此外，可以看到当数据规模增大时，算法达到收敛需要的时间也显著增大，而对比而言，SDR因规模增大而增加的时间也是最少的，充分展示了我们所提出的算法的优越性。

Figure 1. Comparison of SDR, PG and Prox-SARAH under different data scales

图1. 不同数据规模下SDR算法与PG、Prox-SARAH算法对比

5. 总结

针对大规模非凸复合优化问题，本文将方差缩减的随机梯度算法引入到DR分裂算法中，提出随机DR分裂算法，可以更高效，更稳定的解决大规模优化问题，降低算法的计算成本，并在KL不等式的前提下，证明随机DR分裂算法的全局收敛性。具体地，我们首先建立Lyapunov函数在算法前后迭代步的下降性，再建立DR价值函数的相对误差界条件，并最终基于KL性质建立算法的全局收敛性。此外，通过数值实验，验证了随机DR分裂算法(SDR)的优越性。