求解DC问题的一类随机优化算法

A Class of Stochastic Optimization Algorithms for Solving DC Problems

摘要: 本文研究的是一类具有有限和形式的DC问题，其目标函数为具有有限和形式的光滑凸函数与连续凸函数之和再减去适当的闭凸函数的形式。传统的邻近DC算法(pDCA)在处理此类问题时，由于每一迭代步都需要对目标函数光滑部分的全梯度进行计算，从而导致计算成本较为昂贵，因此本文将随机梯度SARAH引入到pDCA中，提出了一种基于随机梯度SARAH的随机邻近DC算法(pDCA-SARAH)，并给出了该算法的具体迭代格式，以降低计算成本。在非凸情形下，本文针对pDCA-SARAH算法给出了收敛性及收敛率分析。具体的，本文给出了目标函数在期望意义下的下降量分析以及次线性收敛率的结果。最后，通过将pDCA-SARAH算法用于求解l_1-2正则化最小二乘问题，并与pDCA进行数值比较，展示了本文所提算法的高效性。

Abstract: In this paper, we study a class of DC problems with finite sum form, whose objective function is the sum of smooth convex function and continuous convex function with finite sum form, minus the appropriate closed convex function. When dealing with this kind of problems, the traditional proximal difference-of-convex algorithm (pDCA) needs to calculate the full gradient of the smooth part of the objective function at each iterative step, so the computational cost is expensive. In this paper, stochastic gradient SARAH is introduced into pDCA, a stochastic proximal DC algorithm (pDCA-SARAH) based on stochastic gradient SARAH is proposed, and the specific iterative scheme of the algorithm is given to reduce the computational cost. In the non-convex case, the convergence and convergence rate analysis of pDCA-SARAH algorithm are given in this paper. Specifically, this paper gives the analysis of the decline of the objective function in the sense of expectation and the results of sublinear convergence rate. Finally, the pDCA-SARAH algorithm is applied to solve the l_1-2 regularized least square problem, and compared with pDCA, the efficiency of the proposed algorithm is demonstrated.

1. 引言

优化问题是指在既定约束条件下求解目标函数最值的问题，通过研究优化问题可实现提升效率，降低成本，实现资源最优配置与决策智能化等目的，因而在数学、计算机和金融等领域中至关重要。本文研究的是一类具有有限和形式的DC (difference of convex, DC)问题，具体格式如下所示：

$\underset{x}{\min }G\left(x\right)={\displaystyle \sum _{i=1}^n{f}_i\left(x\right)}+h\left(x\right)-g\left(x\right),$ (1.1)

其中$f_i\left(x\right)\left(i=1,2,\cdots ,n\right)$ 为光滑凸函数，且$\nabla f_i\left(x\right)$ 是Lipschitz连续的，此外$h\left(x\right)$ 是一个连续凸函数，$g\left(x\right)$ 是一个适当的闭凸函数。上述有限和形式的DC问题在许多应用领域都存在广泛应用，如机器学习[1]、压缩感知[2]、logistic回归[3]和二分类问题[4]等。具体的，我们给出如下两个应用实例，其可表述为模型(1.1)的格式。

1) 正则化最小二乘问题[2]

最小二乘问题是一种常用的优化方法，其在高维数据分析、图像处理和金融风险建模等领域具有广泛应用，其中$l_{1-2}$ 正则化最小二乘问题结合了$l_1$ 范数和$l_2$ 范数的优点，通常用于求解一个既稀疏又保持一定稳定性的解。该方法在处理含有异常值或者噪声较大的数据时效果较好，其具体表述为如下优化模型：

$\underset{x\in {ℝ}^n}{\min }{F}_{1-2}\left(x\right):=\frac{1}{2}{\Vert Ax-b\Vert }^2+\lambda \left({\Vert x\Vert }_1-\Vert x\Vert \right)\text{,}$

其中矩阵$A\in {ℝ}^{m\times n}$ ，向量$b\in {ℝ}^m$ ，正则化参数$\lambda >0$ 。

首先设$B=A^{\text{T}}A={\left(b_1{b}_2\cdots b_n\right)}^{\text{T}},C=A^{\text{T}}b={\left(c_1{c}_2\cdots c_n\right)}^{\text{T}}$ ，再令$f\left(x\right)=\frac{1}{2}{\Vert Ax-b\Vert }^2$ ，$h\left(x\right)=\lambda {\Vert x\Vert }_1$ ，$g\left(x\right)=\lambda \Vert x\Vert$ ，$f_i\left(x\right)=\frac{1}{2}{e}_i^{\text{T}}x{b}_{i}x-e_i^{\text{T}}x{c}_i+\frac{1}{2n}{b}^{\text{T}}b$ ，其中$e_i$ 表示第i列为1其余元素皆为0的向量，于是有$f\left(x\right)={\displaystyle \sum _{i=1}^n{f}_i}\left(x\right)$ ，从而上述优化问题可表述为模型(1.1)的格式。

2) 二分类问题[4]

二分类问题在机器学习等领域中，主要用于只有两种可能结果的决策场景，其通过建立一个模型并根据输入变量来预测输出变量的类别。该类问题在特征选择，医学影像分析等领域有着广泛应用，具体表述为如下优化模型：

$\underset{\omega \in {ℝ}^n}{\min }F\left(\omega \right):=\frac{1}{n}{\displaystyle \sum _{i=1}^{n}l}\left(a_i^{\text{T}}\omega ,b_i\right)+\lambda {\Vert \omega \Vert }_1,$

其中${\left\{\left(a_i,b_i\right)\right\}}_{i=1}^n\subset {ℝ}^n\times {\left\{-1,1\right\}}^n$ 是给定的训练数据集，$\lambda >0$ 为正则化参数，$l\left(\cdot ,\cdot \right)$ 是非凸光滑损失函数。具体的，令$f_i\left(x\right)=\frac{1}{n}\cdot l\left(a_i^{\text{T}}\omega ,b_i\right)$ ，$h\left(x\right)=\lambda {\Vert \omega \Vert }_1$ ，$g\left(x\right)=0$ ，则上述优化问题可转化为模型(1.1)的格式。

1.1. 研究现状

DC问题的一个经典求解算法是DCA (Difference of Convex Functions Algorithm)，由Pham Dinh在1985年首次提出[5]，自此学术界对DC问题的研究已接近40年。DCA主要用于求解标准形式的DC规划问题，即目标函数为两个凸函数之差的形式，DC问题的具体格式为

$\min F\left(x\right)=f\left(x\right)-P\left(x\right).$

具体的，DCA的迭代格式为

$x_{k+1}=\arg \underset{x\in {ℝ}^n}{\min }\left\{f\left(x\right)-P\left(x_k\right)-\langle y_k,x-x_k\rangle \right\},$

其中$y_k\in \partial P\left(x_k\right)$ 。DCA的优势在于框架简单、收敛速度快、具有全局收敛性且能够处理大规模问题，但在处理一些DC问题时，有可能会遇到子问题比较复杂，没有显式解的情形，因此需要内部求解器对子问题进行求解。例如，针对如下形式的DC问题

$\min F\left(x\right)=f\left(x\right)+h\left(x\right)-g\left(x\right),$

若采用DCA对其进行求解，则其子问题将表述为

$x_{k+1}\in \arg \underset{x\in {ℝ}^n}{\min }\left\{f\left(x\right)+h\left(x\right)-g\left(x_k\right)-\langle {\xi }^k,x\rangle \right\},$

其中${\xi }^k\in \partial g\left(x_k\right)$ 。由于子问题涉及到对函数$f\left(x\right)+h\left(x\right)$ 的邻近算子的求解，这导致该子问题通常没有显式解，即便函数$f\left(x\right)$ 和$h\left(x\right)$ 的邻近算子是易于求解的。

针对DCA中子问题不易求解的情形，许多学者进一步将DCA与其他算法相结合，提出了一系列相关算法，如马尔科夫链随机DCA (Markov chain stochastic DCA) [6]、求解球面上四次极小化问题的DCA-Newton (A DCA-Newton method for quartic minimization over the sphere) [7]和邻近DCA (proximal Difference of Convex Functions Algorithm, pDCA) [8]，其中pDCA的迭代格式如下所示：

$\begin{array}{l}{x}_{k+1}=\arg \underset{x\in {ℝ}^n}{\min }\left\{h\left(x\right)+\langle \nabla f\left(x_k\right)-{\xi }^k,x\rangle +\frac{L}{2}{\Vert x-x_k\Vert }^2\right\}\\ \text{ = arg}\underset{x\in {ℝ}^n}{\min }\left\{h\left(x\right)+\frac{L}{2}{\Vert x-\left(x_k-\frac{1}{L}\left(\nabla f\left(x_k\right)-{\xi }^k\right)\right)\Vert }^2\right\}.\end{array}$

其中${\xi }^k\in \partial g\left(x_k\right)$ ，且由于$h\left(x\right)$ 是适当闭凸函数，$x_{k+1}$ 是唯一定义的。pDCA在每一迭代步不仅需要对目标函数中的凹函数部分$-g\left(x\right)$ 做线性优化，还需对目标函数中的光滑凸函数部分$f\left(x\right)$ 做线性化。此时，如果函数$h\left(x\right)$ 的邻近算子便于计算，pDCA的子问题就很容易计算[8]。尽管pDCA中的子问题是易于求解的，但该算法的收敛速度较慢，这是因为当$g\left(x\right)=0$ 时，pDCA便退化为邻近梯度算法，而邻近梯度算法只能达到$O\left(1/k\right)$ 的次线性收敛率，收敛速度较慢。许多学者利用外推技术[9]-[11]实现了pDCA的加速，具体地，Wen等人[11]采用外推技术对pDCA进行加速，提出了带外推的邻近DCA (proximal difference-of-convex algorithm with extrapolation, pDCAe)，该算法的具体迭代格式为

$x_{k+1}=\arg \underset{y\in {ℝ}^n}{\min }\left\{h\left(y\right)+\langle \nabla f\left(y_k\right)-{\xi }^k,y\rangle +\frac{L}{2}{\Vert y-y_k\Vert }^2\right\},$

其中${\xi }^k\in \partial g\left(x_k\right),y_k=x_k+{\beta }_k\left(x_k-x_{k-1}\right),\left\{{\beta }_k\right\}\subseteq \left[0,1\right)$ 且$\underset{k}{\sup }{\beta }_k<1$ 。在适当的假设条件下，pDCAe的全局收敛性以及$O\left(1/k^2\right)$ 的收敛率已被证明[12]。

针对有限和形式的DC问题(1.1)，pDCA在每一迭代步都需要对目标函数光滑部分的梯度$\nabla f_i\left(x\right)\left(i=1,2,\cdots ,n\right)$ 进行计算，这将导致算法的计算相当昂贵。为降低计算成本，许多学者提出了一系列随机梯度算法，如随机梯度下降算法(stochastic gradient descent, SGD) [13]和小批量梯度下降算法(mini-batch gradient descent, Mini-batch) [14]，但由于方差的引入，这类算法为保证收敛性，其迭代步长需要随着迭代的进程衰减至0，这导致算法的收敛速度变慢。为提高随机梯度算法的收敛速度，许多学者提出了一系列方差缩减的随机梯度估计方法，如随机方差缩减梯度算法(stochastic variance reduced gradient, SVRG) [15]、增量梯度算法(incremental gradient method, SAGA) [16]和随机递归梯度算法(stochastic recursive gradient, SARAH) [17]。特别的，SARAH结合了SVRG和SAGA的思想，该算法与SVRG在内循环的更新方式不同，且相较于SAGA不需要存储旧的梯度信息，从而极大降低了存储成本[18]。这一随机梯度的方差随着迭代的进程不断衰减到0，因此迭代步长可以取一个常数，这将使得算法的收敛速度较快。具体的，这类随机梯度算法与确定型一阶算法的收敛速度一致，在强凸情形下可达到期望意义下的线性收敛速度，在凸的情形下可以达到期望意义下的$O\left(1/k\right)$ 次线性收敛率。

1.2. 本文贡献

针对有限和形式的DC问题(1.1)，本文将方差缩减的随机梯度SARAH引入到pDCA中去，提出了一种基于随机梯度SARAH的随机邻近DC算法(pDCA-SARAH)，以降低计算成本。在非凸情形下，本文对算法的收敛性进行了理论分析，并通过数值实验说明了算法的高效性。具体的，本文的主要贡献包括：

在算法上，针对有限和形式的DC问题(1.1)，由于pDCA算法需在每次迭代过程中逐个计算$f_i\left(x\right)$ 的全梯度，从而当数据量n很大时，计算有限和部分的全梯度将会非常昂贵。为降低计算成本，本文将随机梯度SARAH引入到pDCA中，提出了基于SARAH的随机邻近DC算法(pDCA-SARAH)。该算法在每一轮外循环时首先计算一次全梯度，在每一轮内循环中随机抽取小批量的数据来计算随机梯度SARAH，并用随机梯度SARAH来近似全梯度，以实现算法计算成本的降低。

在理论上，本文对pDCA-SARAH算法的收敛性及收敛率进行了分析，并在非凸情形下，详细地给出目标函数在期望意义下的下降量分析和次线性收敛率分析。

在数值上，本文通过将pDCA-SARAH算法应用于$l_{1-2}$ 正则化最小二乘问题的求解中，并通过与传统的pDCA进行比较，验证了本文所提算法理论上的收敛性和高效性。

1.3. 本文框架

本文框架如下，在第二节中，详细介绍了本文所涉及到的符号、定义以及相关引理。第三节中，本文提出了基于SARAH的随机邻近DC算法(pDCA-SARAH)，以解决传统的pDCA在处理形如问题(1.1)时所面临的计算成本昂贵的问题，并给出了pDCA-SARAH算法在期望意义下的下降量分析以及收敛性分析。第四节中，将pDCA-SARAH算法应用于求解$l_{1-2}$ 正则化最小二乘问题来进行数值实验，并与pDCA进行对比，从数值上验证了本文所提出的pDCA-SARAH算法的高效性。第五节中，对本文做出总结。

2. 预备知识

为便于下文研究pDCA-SARAH算法的收敛性，本节将详细介绍本文所涉及到的符号、定义及相关引理。下面首先对本文出现的符号做出定义：记${ℝ}^n$ 为$n$ 维欧几里得空间；$\langle x,y\rangle$ 表示向量内积，其中$x,y\in {ℝ}^n$ ；$\Vert x\Vert =\sqrt{\langle x,x\rangle }$ 为欧式距离；$E[\cdot ]$ 为数学期望。

定义2.1 (凸函数) [19]设函数$f$ 为适当函数，如果$\text{dom }f$ 是凸集，且

$f\left(\theta x+\left(1-\theta \right)y\right)\le \theta f\left(x\right)+\left(1-\theta \right)f\left(y\right),$

对所有的$x,y\in \text{dom }f\text{, 0}\le \theta \le \text{1}$ 都成立，则称$f$ 是凸函数。

定义2.2 (凸函数的次微分) [19]设$f:{ℝ}^n\to ℝ\cup \left\{+\infty \right\}$ 为适当下半连续凸函数，定义域为$\text{dom }f:=\left\{x\in {ℝ}^n|f\left(x\right)<+\infty \right\}$ ，$x$ 为定义域$\text{dom }f$ 中的一点。若向量$u\in {ℝ}^n$ 满足

$f\left(y\right)\ge f\left(x\right)+u^{\text{T}}\left(y-x\right),\forall y\in \text{dom }f\text{,}$

则称u为函数f在点x处的一个次梯度。进一步地，函数f在点x处的次微分记作$\partial f\left(x\right)$ ，定义为所有满足上述条件的向量u所构成的集合，即

$\partial f\left(x\right)=\left\{u|u\in {ℝ}^n,f\left(y\right)\ge f\left(x\right)+u^{\text{T}}\left(y-x\right),\forall y\in \text{dom }f\right\}.$

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

定义2.3 (梯度利普希兹连续) [20]对于可微函数$f$ ，若对任意的$x,y\in \text{dom }f$ ，存在常数$L>0$ ，使其满足不等式

$\Vert \nabla f\left(x\right)-\nabla f\left(y\right)\Vert \le L\Vert x-y\Vert \text{,}$

则称函数f是梯度利普希兹连续的，简记为L-光滑，其中L为Lipschitz常数。

引理2.1 [20]对定义在凸集上的可微函数f，f是凸函数的充要条件为

$f\left(y\right)\ge f\left(x\right)+\nabla f{\left(x\right)}^{\text{T}}\left(y-x\right),\forall x,y\in \text{dom }f.$

引理2.2 (下降引理) [21]若$f:{ℝ}^n\to ℝ$ 连续可微且L-光滑(L > 0)，则f满足如下不等式：

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

3. 算法及收敛性分析

3.1. 基于SARAH的随机邻近DC算法

本文主要研究的是一类具有有限和形式的DC问题，该问题的具体格式如下所示：

$\underset{x}{\min }G\left(x\right)={\displaystyle \sum _{i=1}^n{f}_i\left(x\right)}+h\left(x\right)-g\left(x\right),$

其中$f_i\left(x\right)\left(i=1,2,\cdots ,n\right)$ 为光滑凸函数，且$\nabla f_i\left(x\right)$ 是Lipschitz连续的，此外$h\left(x\right)$ 是一个连续凸函数，$g\left(x\right)$ 是一个适当的闭凸函数。求解该类问题的一个经典算法是pDCA，但由于pDCA每一迭代步都需要计算$f_i\left(x\right)\left(i=1,2,\cdots ,n\right)$ 的全梯度，因此针对大规模DC问题，若采用pDCA则计算成本较为昂贵，故本文在pDCA中引入随机梯度SARAH来降低计算成本。下面给出基于SARAH的随机邻近DC算法(pDCA-SARAH)的迭代格式。

基于SARAH的随机邻近DC算法(pDCA-SARAH)

$fors=0\text{, 1, }\cdots \text{, }S-1\text{ do}$

$x_{s+1}^0=x_s^{\text{T}}$

$V_{s+1}^0={\displaystyle \sum _{i=1}^n\nabla f_i\left({\widehat{x}}_s\right)}$

$fort=\text{0, 1, }\cdots \text{, }T-1\text{ do}$

随机选取小批量$I_b\subset \left\{1,2,\cdots ,n\right\},\left|I_b\right|=b$

$V_{s+1}^t=\frac{1}{b}{\displaystyle \sum _{i\in I_b}\left(\nabla f_i\left(x_{s+1}^t\right)-\nabla f_i\left(x_{s+1}^{t-1}\right)\right)+V_{s+1}^{t-1}}$

$x_{s+1}^{t+1}=\arg \underset{x}{\min }\left\{h\left(x\right)+\langle V_{s+1}^t-{\xi }_{s+1}^t,x-x_{s+1}^t\rangle +\frac{1}{2\alpha }{\Vert x-x_{s+1}^t\Vert }^2\right\}$

end

${\widehat{x}}_{s+1}=x_{s+1}^{\text{T}}$

end

输出：$x_{\alpha }$ 从${\left\{{\left\{x_{s+1}^{t+1}\right\}}_{t=0}^T\right\}}_{s=0}^{S-1}$ 随机均匀选择

注：在算法中，第s轮外循环输出的x更新值为$x_s^{\text{T}}$ ，并将其赋值给第s + 1轮外循环中x的初始值，即$x_{s+1}^0=x_s^{\text{T}}$ 。然后在第s + 1轮外循环中进行T轮内循环，在其中第t轮内循环，由$\frac{1}{b}{\displaystyle \sum _{i\in I_b}\left(\nabla f_i\left(x_{s+1}^t\right)-\nabla f_i\left(x_{s+1}^{t-1}\right)\right)+V_{s+1}^{t-1}}$ 得到随机梯度$V_{s+1}^t$ ，以此来近似全梯度并更新$x_{s+1}^t$ 。

3.2. 算法收敛性及收敛率分析

本节将对pDCA-SARAH算法的收敛性以及收敛率进行分析。为了便于分析pDCA-SARAH算法的收敛性，当选取全梯度进行计算时，本文记pDCA-SARAH算法的子问题对应的精确解为

${\overline{x}}_{s+1}^{t+1}=\arg \underset{x}{\min }\left\{h\left(x\right)+\langle \nabla F\left(x_{s+1}^t\right)-{\zeta }_{s+1}^t,x-x_{s+1}^t\rangle +\frac{1}{2\alpha }{\Vert x-x_{s+1}^t\Vert }^2\right\}.$

此外，本文需要对优化问题的目标函数做出如下假设：

假设1：有限和部分的$f_i\left(x\right)\left(i=1,2,\cdots ,n\right)$ 为光滑凸函数；

假设2：$\nabla f_i\left(x\right)\left(i=1,2,\cdots ,n\right)$ 是Lipschitz连续的；

假设3：$h\left(x\right)$ 是一个连续凸函数，$g\left(x\right)$ 是一个适当的闭凸函数。

在进行收敛分析之前，首先需要证明引理3.1与3.2。具体地，引理3.1给出了目标函数在前后迭代点处，期望意义下的下降量分析。

引理3.1 (目标函数期望意义下的下降量)当假设1~3成立时，令$\left\{x_s^t\right\}$ 是由pDCA-SARAH算法所产生的迭代序列，则有如下所示不等式成立：

$\begin{array}{l}E\left[G\left(x_{s+1}^{t+1}\right)\right]\le E\left[G\left(x_{s+1}^t\right)\right]+\left(\frac{L}{2}-\frac{1}{2\alpha }+\theta \right)\cdot E\left[{\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2\right]\\ +\frac{1}{2\theta }E\left[{\Vert \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t\Vert }^2\right]-\left(\frac{1}{2\alpha }-\theta \right)E\left[{\Vert {\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\Vert }^2\right],\end{array}$

其中$\alpha >0$ 为迭代步长，$\theta >0$ 为常数。

证明。一方面，令$F\left(x\right)={\displaystyle \sum _{i=1}^n{f}_i\left(x\right)}$ ，由于$\nabla f_i\left(x\right)\left(i=1,2,\cdots ,n\right)$ 是Lipschitz连续的，于是根据引理2.2 (下降引理)可得不等式(3.1)成立：

$F\left(x_{s+1}^{t+1}\right)\le F\left(x_{s+1}^t\right)+\langle \nabla F\left(x_{s+1}^t\right),x_{s+1}^{t+1}-x_{s+1}^t\rangle +\frac{L}{2}{\Vert x_{s+1}^{t+1}-x_{s+1}^t\Vert }^2.$ (3.1)

另一方面，因为函数h(x)为凸函数，从而根据引理2.1可得，对$\forall x,y\in \text{dom }h$ 有$h\left(y\right)\ge h\left(x\right)+\langle \partial h\left(x\right),y-x\rangle$ ，所以可以推导出如下两不等式，即

$h\left(x_{s+1}^{t+1}\right)\le h\left({\overline{x}}_{s+1}^{t+1}\right)+\langle {\xi }_{s+1}^{t+1},x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle ,\forall {\xi }_{s+1}^{t+1}\in \partial h\left(x_{s+1}^{t+1}\right),$ (3.2)

和

$h\left({\overline{x}}_{s+1}^{t+1}\right)\le h\left(x_{s+1}^t\right)+\langle {\overline{\xi }}_{s+1}^{t+1},{\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\rangle ,\forall {\overline{\xi }}_{s+1}^{t+1}\in \partial h\left({\overline{x}}_{s+1}^{t+1}\right).$ (3.3)

下面对不等式(3.2)、(3.3)进一步处理。首先针对不等式(3.2)，根据算法的最优性条件可得

$0\in \partial h\left(x_{s+1}^{t+1}\right)+V_{s+1}^t-{\zeta }_{s+1}^t+\frac{1}{\alpha }\left(x_{s+1}^{t+1}-x_{s+1}^t\right),$

因此可对不等式(3.2)中的$\langle {\xi }_{s+1}^{t+1},x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle$项做如下变换(其中${\xi }_{s+1}^{t+1}\in \partial h\left(x_{s+1}^{t+1}\right)$ )：

$\begin{array}{l}\langle {\xi }_{s+1}^{t+1},x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle \\ =\langle -V_{s+1}^t+{\zeta }_{s+1}^t-\frac{1}{\alpha }\left(x_{s+1}^{t+1}-x_{s+1}^t\right),x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle \\ =\langle -V_{s+1}^t+{\zeta }_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle -\frac{1}{\alpha }\langle x_{s+1}^{t+1}-x_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle \\ =\langle -V_{s+1}^t+{\zeta }_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle +\frac{1}{\alpha }\langle x_{s+1}^t-x_{s+1}^{t+1},x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle .\end{array}$

接着对上述变换结果做进一步的化简，由于

$\langle a-b,c-d\rangle =\frac{1}{2}\left({\Vert a-d\Vert }^2-{\Vert a-c\Vert }^2+{\Vert b-c\Vert }^2-{\Vert b-d\Vert }^2\right)$ ,

从而其中的$\langle x_{s+1}^t-x_{s+1}^{t+1},x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle$项可以转化为

$\langle x_{s+1}^t-x_{s+1}^{t+1},x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle =\frac{1}{2}\left({\Vert x_{s+1}^t-{\overline{x}}_{s+1}^{t+1}\Vert }^2-{\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2-{\Vert x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\Vert }^2\right),$

再将该式代入上述变换结果，可得

$\begin{array}{l}\langle {\xi }_{s+1}^{t+1},x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle =\frac{1}{2\alpha }\left({\Vert x_{s+1}^t-{\overline{x}}_{s+1}^{t+1}\Vert }^2-{\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2-{\Vert x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\Vert }^2\right)\\ +\langle -V_{s+1}^t+{\zeta }_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle .\end{array}$ (3.4)

类似地，对于不等式(3.3)，由算法的最优性条件可得

$0\in \partial h\left({\overline{x}}_{s+1}^{t+1}\right)+\nabla F\left(x_{s+1}^t\right)-{\zeta }_{s+1}^t+\frac{1}{\alpha }\left({\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\right),$

从而可化简不等式(3.3)得到

$\langle \partial h\left({\overline{x}}_{s+1}^{t+1}\right),{\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\rangle =\langle -\nabla F\left(x_{s+1}^t\right)+{\zeta }_{s+1}^t,{\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\rangle -\frac{1}{\alpha }{\Vert {\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\Vert }^2.$ (3.5)

下面分别将(3.4)式代入(3.2)式，(3.5)式代入(3.3)式，则有如下两个不等式成立：

$h\left(x_{s+1}^{t+1}\right)\le h\left({\overline{x}}_{s+1}^{t+1}\right)+\langle -V_{s+1}^t+{\zeta }_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle +\frac{1}{2\alpha }\left({\Vert x_{s+1}^t-{\overline{x}}_{s+1}^{t+1}\Vert }^2-{\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2-{\Vert x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\Vert }^2\right);$

$h\left({\overline{x}}_{s+1}^{t+1}\right)\le h\left(x_{s+1}^t\right)+\langle -\nabla F\left(x_{s+1}^t\right)+{\zeta }_{s+1}^t,{\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\rangle -\frac{1}{\alpha }{\Vert {\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\Vert }^2.$

对上面两不等式求和并整理，具体过程为

$\begin{array}{l}h\left(x_{s+1}^{t+1}\right)\le h\left(x_{s+1}^t\right)+\langle -V_{s+1}^t+{\zeta }_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle +\langle -\nabla F\left(x_{s+1}^t\right)+{\zeta }_{s+1}^t,{\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\rangle \\ +\frac{1}{2\alpha }\left({\Vert x_{s+1}^t-{\overline{x}}_{s+1}^{t+1}\Vert }^2-{\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2-{\Vert x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\Vert }^2\right)-\frac{1}{\alpha }{\Vert {\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\Vert }^2\\ =h\left(x_{s+1}^t\right)+\langle -V_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle +\langle {\zeta }_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle +\langle -\nabla F\left(x_{s+1}^t\right),{\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\rangle \\ +\langle {\zeta }_{s+1}^t,{\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\rangle -\frac{1}{2\alpha }\left({\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2+{\Vert x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\Vert }^2+{\Vert x_{s+1}^t-{\overline{x}}_{s+1}^{t+1}\Vert }^2\right)\\ =h\left(x_{s+1}^t\right)+\langle -V_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle +\langle -\nabla F\left(x_{s+1}^t\right),{\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\rangle +\langle {\zeta }_{s+1}^t,x_{s+1}^{t+1}-x_{s+1}^t\rangle \\ -\frac{1}{2\alpha }\left({\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2+{\Vert x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\Vert }^2+{\Vert x_{s+1}^t-{\overline{x}}_{s+1}^{t+1}\Vert }^2\right),\end{array}$

从而可以得到不等式(3.6)成立：

$\begin{array}{l}h\left(x_{s+1}^{t+1}\right)\le h\left(x_{s+1}^t\right)-\frac{1}{2\alpha }\left({\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2+{\Vert x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\Vert }^2+{\Vert x_{s+1}^t-{\overline{x}}_{s+1}^{t+1}\Vert }^2\right)\\ +\langle -V_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle +\langle -\nabla F\left(x_{s+1}^t\right),{\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\rangle +\langle {\zeta }_{s+1}^t,x_{s+1}^{t+1}-x_{s+1}^t\rangle .\end{array}$ (3.6)

此外，又因为$g\left(x\right)$ 是凸函数，所以根据引理2.1可以得到

$g\left(x_{s+1}^t\right)+\langle {\zeta }_{s+1}^t,x_{s+1}^{t+1}-x_{s+1}^t\rangle \le g\left(x_{s+1}^{t+1}\right).$ (3.7)

接着再对(3.1)式、(3.6)式与(3.7)式求和，得到不等式(3.8)如下所示：

$\begin{array}{l}F\left(x_{s+1}^{t+1}\right)+h\left(x_{s+1}^{t+1}\right)+g\left(x_{s+1}^t\right)+\langle {\zeta }_{s+1}^t,x_{s+1}^{t+1}-x_{s+1}^t\rangle \\ \le F\left(x_{s+1}^t\right)+\langle \nabla F\left(x_{s+1}^t\right),x_{s+1}^{t+1}-x_{s+1}^t\rangle +h\left(x_{s+1}^t\right)+\frac{L}{2}{\Vert x_{s+1}^{t+1}-x_{s+1}^t\Vert }^2\\ +\langle -V_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle +\langle -\nabla F\left(x_{s+1}^t\right),{\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\rangle +\langle {\zeta }_{s+1}^t,x_{s+1}^{t+1}-x_{s+1}^t\rangle \\ -\frac{1}{2\alpha }\left({\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2+{\Vert x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\Vert }^2+{\Vert x_{s+1}^t-{\overline{x}}_{s+1}^{t+1}\Vert }^2\right)+g\left(x_{s+1}^{t+1}\right),\end{array}$ (3.8)

化简(3.8)式中$\langle \nabla F\left(x_{s+1}^t\right),x_{s+1}^{t+1}-x_{s+1}^t\rangle +\langle -V_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle +\langle -\nabla F\left(x_{s+1}^t\right),{\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\rangle$，具体为

$\begin{array}{l}\langle \nabla F\left(x_{s+1}^t\right),x_{s+1}^{t+1}-x_{s+1}^t\rangle +\langle -V_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle +\langle -\nabla F\left(x_{s+1}^t\right),{\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\rangle \\ =\langle \nabla F\left(x_{s+1}^t\right),x_{s+1}^{t+1}-x_{s+1}^t\rangle -\langle \nabla F\left(x_{s+1}^t\right),{\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\rangle +\langle -V_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle \\ =\langle \nabla F\left(x_{s+1}^t\right),x_{s+1}^{t+1}-x_{s+1}^t-{\overline{x}}_{s+1}^{t+1}+x_{s+1}^t\rangle +\langle -V_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle \\ =\langle \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle ,\end{array}$

设$G\left(x\right)=F\left(x\right)+h\left(x\right)-g\left(x\right)$ ，将上述化简结果代入不等式(3.8)，则可以得到

$\begin{array}{l}G\left(x_{s+1}^{t+1}\right)\le G\left(x_{s+1}^t\right)+\frac{L}{2}{\Vert x_{s+1}^{t+1}-x_{s+1}^t\Vert }^2+\langle \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle \\ -\frac{1}{2\alpha }\left({\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2+{\Vert x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\Vert }^2+{\Vert x_{s+1}^t-{\overline{x}}_{s+1}^{t+1}\Vert }^2\right),\end{array}$

其中$\alpha$ 是步长，则有$\alpha >0$ ，故$\frac{1}{2\alpha }{\Vert x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\Vert }^2>0$ ，于是放缩该不等式可以得到

$\begin{array}{l}G\left(x_{s+1}^{t+1}\right)\le G\left(x_{s+1}^t\right)+\frac{L}{2}{\Vert x_{s+1}^{t+1}-x_{s+1}^t\Vert }^2+\langle \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle \\ -\frac{1}{2\alpha }\left({\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2+{\Vert x_{s+1}^t-{\overline{x}}_{s+1}^{t+1}\Vert }^2\right).\end{array}$

根据上述不等式，可得$G\left(x_{s+1}^{t+1}\right)$ 的期望满足如下不等式：

$\begin{array}{l}E\left[G\left(x_{s+1}^{t+1}\right)\right]\le E\left[G\left(x_{s+1}^t\right)\right]+E\left[\langle \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle \right]\\ +\left(\frac{L}{2}-\frac{1}{2\alpha }\right)E\left[{\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2\right]-\frac{1}{2\alpha }E\left[{\Vert {\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\Vert }^2\right].\end{array}$ (3.9)

下面处理不等式(3.9)，首先由$\langle a,b\rangle \le \frac{L}{2}{\Vert a\Vert }^2+\frac{1}{2L}{\Vert b\Vert }^2$ 与$\langle a,b\rangle =\langle b,a\rangle$ 可得

$\langle \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle =\frac{\theta }{2}{\Vert x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\Vert }^2+\frac{1}{2\theta }{\Vert \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t\Vert }^2.$ (3.10)

进一步化简(3.10)式，针对其中的项$\frac{\theta }{2}{\Vert x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\Vert }^2$ ，根据范数的三角不等式，即$\Vert a+b\Vert \le \Vert a\Vert +\Vert b\Vert ,\forall a,b\in {ℝ}^n$ ，可以得到

${\Vert a+b\Vert }^2\le {\left(\Vert a\Vert +\Vert b\Vert \right)}^2={\Vert a\Vert }^2+2\Vert a\Vert \cdot \Vert b\Vert +{\Vert b\Vert }^2\le 2{\Vert a\Vert }^2+2{\Vert b\Vert }^2,$

于是有

$\frac{\theta }{2}{\Vert x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\Vert }^2=\frac{\theta }{2}{\Vert x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}+x_{s+1}^t-x_{s+1}^t\Vert }^2\le \theta {\Vert x_{s+1}^{t+1}-x_{s+1}^t\Vert }^2+\theta {\Vert x_{s+1}^t-{\overline{x}}_{s+1}^{t+1}\Vert }^2.$

再将该不等式代入(3.10)式，可以得到

$\langle \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t,x_{s+1}^{t+1}-{\overline{x}}_{s+1}^{t+1}\rangle \le \theta {\Vert x_{s+1}^{t+1}-x_{s+1}^t\Vert }^2+\theta {\Vert x_{s+1}^t-{\overline{x}}_{s+1}^{t+1}\Vert }^2+\frac{1}{2\theta }{\Vert \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t\Vert }^2.$

将上述不等式代入不等式(3.9)，则可得不等式(3.11)，即

$\begin{array}{l}E\left[G\left(x_{s+1}^{t+1}\right)\right]\le E\left[G\left(x_{s+1}^t\right)\right]+\left(\frac{L}{2}-\frac{1}{2\alpha }+\theta \right)\cdot E\left[{\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2\right]\\ +\frac{1}{2\theta }E\left[{\Vert \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t\Vert }^2\right]-\left(\frac{1}{2\alpha }-\theta \right)E\left[{\Vert {\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\Vert }^2\right],\end{array}$ (3.11)

引理3.1证毕。

为了证明pDCA-SARAH算法的收敛性，我们还需要对该算法中采用的随机梯度的方差进行估计，具体见引理3.2。

引理3.2当假设1~3成立时，令$\left\{x_s^t\right\}$ 是由pDCA-SARAH算法所产生的迭代序列，则有

$E\left[{\Vert \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t\Vert }^2\right]\le E\left[{\Vert \nabla F\left(x_{s+1}^0\right)-V_{s+1}^0\Vert }^2\right]+\frac{L^2}{b}{\displaystyle \sum _{i=0}^{t-1}E\left[{\Vert x_{s+1}^{i+1}-x_{s+1}^i\Vert }^2\right]},$

其中b是随机抽取的小批量数据集的长度，$L>0$ 为Lipschitz常数。

证明。首先对(3.11)式中$E\left[{\Vert \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t\Vert }^2\right]$ 做进一步处理，具体过程为

$\begin{array}{l}E\left[{\Vert \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t\Vert }^2\right]\\ =E\left[{\Vert \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right)+\nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1}+V_{s+1}^{t-1}-V_{s+1}^t\Vert }^2\right]\end{array}$

$\begin{array}{l}=E\left[{\Vert \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right)\Vert }^2\right]+E\left[{\Vert \nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1}\Vert }^2\right]+E\left[{\Vert V_{s+1}^{t-1}-V_{s+1}^t\Vert }^2\right]\\ +2E[\langle \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right),\nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1}\rangle +\langle \nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1},V_{s+1}^{t-1}-V_{s+1}^t\rangle \\ +\langle \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right),V_{s+1}^{t-1}-V_{s+1}^t\rangle ].\end{array}$

从而可得(3.12)式，即

$\begin{array}{l}E\left[{\Vert \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t\Vert }^2\right]\\ =E\left[{\Vert \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right)\Vert }^2\right]+E\left[{\Vert \nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1}\Vert }^2\right]+E\left[{\Vert V_{s+1}^{t-1}-V_{s+1}^t\Vert }^2\right]\\ +2E[\langle \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right),\nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1}\rangle +\langle \nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1},V_{s+1}^{t-1}-V_{s+1}^t\rangle \\ +\langle \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right),V_{s+1}^{t-1}-V_{s+1}^t\rangle ].\end{array}$ (3.12)

对(3.12)式的项：$\text{2}E\left[\langle \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right),\nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1}\rangle +\langle \nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1},V_{s+1}^{t-1}-V_{s+1}^t\rangle \right]$ ，根据$V_{s+1}^{t-1}-V_{s+1}^t=\nabla F\left(x_{s+1}^{t-1}\right)-\nabla F\left(x_{s+1}^t\right)$ 与$\langle a,b\rangle =\langle b,a\rangle$ ，可将该项化简为

$\begin{array}{l}\text{2}E\left[\langle \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right),\nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1}\rangle +\langle \nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1},V_{s+1}^{t-1}-V_{s+1}^t\rangle \right]\\ =2E\left[\langle \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right),\nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1}\rangle -\langle \nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1},\nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right)\rangle \right]\\ =2E\left[\langle \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right),\nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1}\rangle -\langle \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right),\nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1}\rangle \right]\\ =0.\end{array}$

类似的，化简等式(3.12)中的另一项$2E\left[\langle \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right),V_{s+1}^{t-1}-V_{s+1}^t\rangle \right]$ ，具体过程为

$\begin{array}{l}2E\left[\langle \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right),V_{s+1}^{t-1}-V_{s+1}^t\rangle \right]\\ =2E\left[\langle \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right),\nabla F\left(x_{s+1}^{t-1}\right)-\nabla F\left(x_{s+1}^t\right)\rangle \right]\\ =-2E\left[\langle \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right),\nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right)\rangle \right]\\ =-2E{\left[\Vert \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right)\Vert \right]}^2.\end{array}$

再将上述两项的化简结果代入(3.12)式，整理后可得如下不等式：

$E\left[{\Vert \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t\Vert }^2\right]\le E\left[{\Vert \nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1}\Vert }^2\right]+E\left[{\Vert V_{s+1}^{t-1}-V_{s+1}^t\Vert }^2\right]-E{\left[\Vert \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right)\Vert \right]}^2,$

其中$-E{\left[\Vert \nabla F\left(x_{s+1}^t\right)-\nabla F\left(x_{s+1}^{t-1}\right)\Vert \right]}^2<0$ ，则可以由放缩法得到不等式(3.13)成立，即

$E\left[{\Vert \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t\Vert }^2\right]\le E\left[{\Vert \nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1}\Vert }^2\right]+E\left[{\Vert V_{s+1}^{t-1}-V_{s+1}^t\Vert }^2\right].$ (3.13)

此外，根据pDCA-SARAH算法梯度更新公式$V_{s+1}^t=\frac{1}{b}{\displaystyle \sum _{i\in I_b}\left(\nabla f_i\left(x_{s+1}^t\right)-\nabla f_i\left(x_{s+1}^{t-1}\right)\right)}+V_{s+1}^{t-1}$ 可得

$V_{s+1}^{t-1}-V_{s+1}^t=V_{s+1}^{t-1}-\left(\frac{1}{b}{\displaystyle \sum _{i\in I_b}\left(\nabla f_i\left(x_{s+1}^t\right)-\nabla f_i\left(x_{s+1}^{t-1}\right)\right)}+V_{s+1}^{t-1}\right)=-\frac{1}{b}{\displaystyle \sum _{i\in I_b}\left(\nabla f_i\left(x_{s+1}^t\right)-\nabla f_i\left(x_{s+1}^{t-1}\right)\right)},$

则有${\Vert V_{s+1}^{t-1}-V_{s+1}^t\Vert }^2={\Vert \frac{1}{b}{\displaystyle \sum _{i\in I_b}\left(\nabla f_i\left(x_{s+1}^t\right)-\nabla f_i\left(x_{s+1}^{t-1}\right)\right)}\Vert }^2$ ，又因$\nabla f_i\left(x_{s+1}^t\right)$ 是Lipschitz连续的，故有

$E\left[{\Vert V_{s+1}^{t-1}-V_{s+1}^t\Vert }^2\right]=E\left[{\Vert \frac{1}{b}{\displaystyle \sum _{i\in I_b}\left(\nabla f_i\left(x_{s+1}^t\right)-\nabla f_i\left(x_{s+1}^{t-1}\right)\right)}\Vert }^2\right]\le \frac{L^2}{b}E\left[{\Vert x_{s+1}^t-x_{s+1}^{t-1}\Vert }^2\right]$ .

再将不等式$E\left[{\Vert V_{s+1}^{t-1}-V_{s+1}^t\Vert }^2\right]\le \frac{L^2}{b}E\left[{\Vert x_{s+1}^t-x_{s+1}^{t-1}\Vert }^2\right]$ 代入(3.13)式，于是有

$E\left[{\Vert \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t\Vert }^2\right]\le E\left[{\Vert \nabla F\left(x_{s+1}^{t-1}\right)-V_{s+1}^{t-1}\Vert }^2\right]+\frac{L^2}{b}E\left[{\Vert x_{s+1}^t-x_{s+1}^{t-1}\Vert }^2\right],$

进一步的，以此类推，可以得到不等式

$E\left[{\Vert \nabla F\left(x_{s+1}^t\right)-V_{s+1}^t\Vert }^2\right]\le E\left[{\Vert \nabla F\left(x_{s+1}^0\right)-V_{s+1}^0\Vert }^2\right]+\frac{L^2}{b}{\displaystyle \sum _{i=0}^{t-1}E\left[{\Vert x_{s+1}^{i+1}-x_{s+1}^i\Vert }^2\right]}.$ (3.14)

引理3.2证毕。

基于引理3.1以及引理3.2，本文给出了pDCA-SARAH算法的次线性收敛率结果。为便于衡量pDCA-SARAH算法的收敛速度，我们定义DC问题的广义邻近梯度映射为$G_{\eta }\left(x_{s+1}^t\right)={\overline{x}}_{s+1}^{t+1}-x_{s+1}^t$ 。下面，我们给出pDCA-SARAH算法的次线性收敛率结果。

定理3.1 (次线性收敛率)当假设1~3成立时，令$\left\{x_s^t\right\}$ 是由pDCA-SARAH算法所产生的迭代序列，则有如下所示不等式成立：

$E\left[{\Vert G_{\eta }\left({\tilde{x}}_{s+1}\right)\Vert }^2\right]=\frac{1}{k}{\displaystyle \sum _{s=0}^{S-1}{\displaystyle \sum _{t=0}^{T-1}E\left[{\Vert {\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\Vert }^2\right]}}\le \frac{2\alpha }{k\left(1-2\alpha \theta \right)}E\left[G\left({\tilde{x}}_0\right)-G^{\ast }\right],$

其中$k=ST$ ，表示总迭代次数，$\alpha >0$ 为迭代步长，$\theta >0$ 为常数。

证明。将不等式(3.14)代入不等式(3.11)，则有

$\begin{array}{l}E\left[G\left(x_{s+1}^{t+1}\right)\right]\le E\left[G\left(x_{s+1}^t\right)\right]+\frac{1}{2\theta }E\left[{\Vert \nabla F\left(x_{s+1}^0\right)-V_{s+1}^0\Vert }^2\right]+\frac{L^2}{2\theta b}{\displaystyle \sum _{i=0}^{t-1}E\left[{\Vert x_{s+1}^{i+1}-x_{s+1}^i\Vert }^2\right]}\\ +\left(\frac{L}{2}-\frac{1}{2\alpha }+\theta \right)E\left[{\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2\right]-\left(\frac{1}{2\alpha }-\theta \right)E\left[{\Vert {\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\Vert }^2\right].\end{array}$

因为pDCA-SARAH算法的梯度更新公式为$V_{s+1}^t=\frac{1}{b}{\displaystyle \sum _{i\in I_b}\left(\nabla f_i\left(x_{s+1}^t\right)-\nabla f_i\left(x_{s+1}^{t-1}\right)\right)}+V_{s+1}^{t-1}$ ，且该算法的第s + 1轮外循环中初始点的全梯度记作$V_{s+1}^{\text{0}}$ ，即$\nabla F\left(x_{s+1}^{\text{0}}\right)=V_{s+1}^{\text{0}}$ ，于是有${\Vert \nabla F\left(x_{s+1}^0\right)-V_{s+1}^0\Vert }^2=0$ 成立，因此可以更新上述不等式得到

$\begin{array}{l}E\left[G\left(x_{s+1}^{t+1}\right)\right]\le E\left[G\left(x_{s+1}^t\right)\right]+\frac{L^2}{2\theta b}{\displaystyle \sum _{i=0}^{t-1}E\left[{\Vert x_{s+1}^{i+1}-x_{s+1}^i\Vert }^2\right]}\\ +\left(\frac{L}{2}-\frac{1}{2\alpha }+\theta \right)E\left[{\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2\right]-\left(\frac{1}{2\alpha }-\theta \right)E\left[{\Vert {\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\Vert }^2\right].\end{array}$ (3.15)

下面针对不等式(3.15)中的项：$\frac{L^2}{2\theta b}{\displaystyle \sum _{i=0}^{t-1}E\left[{\Vert x_{s+1}^{i+1}-x_{s+1}^i\Vert }^2\right]}+\left(\frac{L}{2}-\frac{1}{2\alpha }+\theta \right)E\left[{\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2\right]$ ，进行$t=0,1,\cdots ,T-1$ 的累和，得到的结果如下所示：

$\begin{array}{l}{\displaystyle \sum _{t=0}^{T-1}\left\{\frac{L^2}{2\theta b}{\displaystyle \sum _{i=0}^{t-1}E\left[{\Vert x_{s+1}^{i+1}-x_{s+1}^i\Vert }^2\right]}+\left(\frac{L}{2}-\frac{1}{2\alpha }+\theta \right)E\left[{\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2\right]\right\}}\\ =\left(\frac{T{L}^2}{2\theta b}+\frac{L}{2}-\frac{1}{2\alpha }+\theta \right)\cdot \left({\displaystyle \sum _{i=0}^{t-1}E\left[{\Vert x_{s+1}^{i+1}-x_{s+1}^i\Vert }^2\right]}\right)+\left(\frac{L}{2}-\frac{1}{2\alpha }+\theta \right)E\left[{\Vert x_{s+1}^{T-1}-x_{s+1}^T\Vert }^2\right].\end{array}$

只要满足$\frac{T{L}^2}{2\theta b}+\frac{L}{2}-\frac{1}{2\alpha }+\theta \le 0,\frac{L}{2}-\frac{1}{2\alpha }+\theta <0$ ，则有如下不等式成立：

$\frac{L^2}{2\theta b}{\displaystyle \sum _{i=0}^{t-1}E\left[{\Vert x_{s+1}^{i+1}-x_{s+1}^i\Vert }^2\right]}+\left(\frac{L}{2}-\frac{1}{2\alpha }+\theta \right)E\left[{\Vert x_{s+1}^t-x_{s+1}^{t+1}\Vert }^2\right]<0,$

从而可以化简不等式(3.15)得到

$\left(\frac{1}{2\alpha }-\theta \right)E\left[{\Vert {\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\Vert }^2\right]\le E\left[G\left(x_{s+1}^t\right)\right]-E\left[G\left(x_{s+1}^{t+1}\right)\right].$

类似的，对上述不等式进行$t=0,1,\cdots ,T-1$ 的累和，可以得到不等式(3.16)。即

$\left(\frac{1}{2\alpha }-\theta \right){\displaystyle \sum _{t=0}^{T-1}E\left[{\Vert {\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\Vert }^2\right]]}\le E\left[G\left(x_{s+1}^0\right)\right]-E\left[G\left(x_{s+1}^T\right)\right].$ (3.16)

接着再对不等式(3.16)进行$s=0,1,\cdots ,S-1$ 的累和，其中右式的累和结果为

$E\left[G\left({\tilde{x}}_0\right)-G^{\ast }\right]=E\left[G\left(x_1^0\right)\right]-E\left[G\left(x_1^T\right)\right]+E\left[G\left(x_2^0\right)\right]-E\left[G\left(x_2^T\right)\right]+\cdots +E\left[G\left(x_S^0\right)\right]-E\left[G\left(x_S^T\right)\right],$

将其记作$E\left[G\left({\tilde{x}}_0\right)-G^{\ast }\right]$ ，因此不等式(3.16)的累和结果为

$\left(\frac{1}{2\alpha }-\theta \right){\displaystyle \sum _{s=0}^{S-1}{\displaystyle \sum _{t=0}^{T-1}E\left[{\Vert {\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\Vert }^2\right]}}\le E\left[G\left({\tilde{x}}_0\right)-G^{\ast }\right].$

令$k=ST,E\left[{\Vert G_{\eta }\left({\tilde{x}}_{s+1}\right)\Vert }^2\right]=\frac{1}{k}{\displaystyle \sum _{s=0}^{S-1}{\displaystyle \sum _{t=0}^{T-1}E\left[{\Vert {\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\Vert }^2\right]}}$，结合上述累和结果可得

$E\left[{\Vert G_{\eta }\left({\tilde{x}}_{s+1}\right)\Vert }^2\right]=\frac{1}{k}{\displaystyle \sum _{s=0}^{S-1}{\displaystyle \sum _{t=0}^{T-1}E\left[{\Vert {\overline{x}}_{s+1}^{t+1}-x_{s+1}^t\Vert }^2\right]}}\le \frac{2\alpha }{k\left(1-2\alpha \theta \right)}E\left[G\left({\tilde{x}}_0\right)-G^{\ast }\right].$

定理3.1证毕，说明pDCA-SARAH算法在期望意义下是收敛的。

4. 数值实验

在本节中，我们将本文所提出的pDCA-SARAH算法用于求解$l_{1-2}$ 正则化最小二乘问题，并将该算法与pDCA进行比较，说明本文所提算法的高效性。本节所有的实验均在64位PC上使用Matlab 2016a进行的，该PC配备有2.7 GHz和8 G RAM。

本节主要考虑如下所示的$l_{1-2}$ 正则化最小二乘问题：

$\underset{x\in {ℝ}^n}{\min }{F}_{1-2}\left(x\right):=\frac{1}{2}{\Vert Ax-b\Vert }^2+\lambda \left({\Vert x\Vert }_1-\Vert x\Vert \right)\text{,}$ (4.1)

其中$A\in {ℝ}^{m\times n}\text{, }b\in {ℝ}^m$ 且正则化参数$\lambda >0$ 。为将问题(4.1)转化成本文所研究的具有有限和形式的DC问题(1.1)，首先令$f\left(x\right)=\frac{1}{2}{\Vert Ax-b\Vert }^2,h\left(x\right)=\lambda {\Vert x\Vert }_1,g\left(x\right)=\lambda \Vert x\Vert ,$ 通过对$f\left(x\right)$ 简单的整理，便可以得到

$f\left(x\right)=\frac{1}{2}{\Vert Ax-b\Vert }^2=\frac{1}{2}{\left(Ax-b\right)}^{\text{T}}\left(Ax-b\right)=\frac{1}{2}\left(x^{\text{T}}{A}^{\text{T}}Ax-2x^{\text{T}}{A}^{\text{T}}b+b^{\text{T}}b\right)$

进一步，我们令$B=A^{\text{T}}A={\left(b_1{b}_2\cdots b_n\right)}^{\text{T}},C=A^{\text{T}}b={\left(c_1{c}_2\cdots c_n\right)}^{\text{T}},$ 将其代入上式，可得

$f\left(x\right)=\frac{1}{2}\left(x^{T}Bx-2x^{T}C+b^{T}b\right),$

其中$B\in {ℝ}^{n\times n},C\in {ℝ}^n$ ，$b^{\text{T}}b$ 为一常数。

进一步的，令$b_i\left(i=1,2,\cdots ,n\right)$ 是由矩阵B第i行构成的行向量，$c_i\left(i=1,2,\cdots ,n\right)$ 为矩阵C的第i行对应元素，$e_i\left(i=1,2,\cdots ,n\right)$ 为第i列为1且其余元素皆为0的行向量，并设

$f_i\left(x\right)=\frac{1}{2}{e}_i^{\text{T}}x{b}_{i}x-e_i^{\text{T}}x{c}_i+\frac{1}{2n}{b}^{\text{T}}b$ ,

于是有$f\left(x\right)={\displaystyle \sum _{i=1}^n{f}_i\left(x\right)}$ 成立，从而问题(4.1)可以转化为具有有限和形式的DC问题(1.1)。

为了衡量算法的收敛程度，下面给出相对误差[22]的定义为

$e\left(k\right):=\frac{F_{1-2}\left(x^k\right)-F_{1-2}^{\min }}{F_{1-2}\left(x^0\right)-F_{1-2}^{\min }},$

其中$F_{1-2}\left(x^k\right)$ 与$F_{1-2}\left(x^0\right)$ 分别为目标函数$F_{1-2}\left(x\right)$ 在$x^k$ 与$x^0$ 处的函数值，$F_{1-2}^{\min }$ 为最小函数值。接着令$T\left(k\right)$ 为得到$x^k$ 的总计算时间，从而定义每个时间歩长下的最小相对误差为

$E\left(t\right):=\min \left\{e\left(k\right)|k\in \left\{i|T\left(i\right)\le t\right\}\right\}.$

当最小相对误差$E\left(t\right)$ 越接近0时，目标函数$F_{1-2}\left(x\right)$ 越接近最优解。

针对数值实验的参数设置，首先随机生成矩阵$A\in {ℝ}^{m\times n}$ ，向量$b\in {ℝ}^m$ ，并控制变量，依次选取正则化参数$\lambda =0.5$ 与$\lambda =0.3$ ，用于比较不同正则化参数条件下pDCA-SARAH算法和pDCA的数值效果。针对问题规模设置，本节考虑如下四个三元数组：

$\left(n,m,s\right)=\left(3000,900,180\right);\left(n,m,s\right)=\left(5000,1500,300\right);$

$\left(n,m,s\right)=\left(8000,2400,480\right);\left(n,m,s\right)=\left(10000,3000,600\right).$

对以上四个数组$\left(n,m,s\right)$ 分别生成10组独立实验并计算出每组的平均最小相对误差，以此来比较pDCA与pDCA-SARAH算法的数值效果。此外，我们统一规定两算法的外循环最大迭代次数为10,000，并根据问题规模$\left(n,m,s\right)$ 分别设置最大迭代时间为100秒、300秒、700秒和1000秒。其次设置pDCA-SARAH算法内循环迭代次数为2，每轮内循环随机抽取的小批量数据个数为3。

针对不同的正则化参数$\lambda$ 与问题规模$\left(n,m,s\right)$ ，分别将最小相对误差$E\left(t\right)={10}^{-6}$ 时，pDCA与pDCA-SARAH算法迭代所用时长记录在表1与表2中。从表中不难看出，当正则化参数$\lambda$ 确定时，对本文所规定的四组不同的问题规模$\left(n,m,s\right)$ ，就两算法的最小相对误差$E\left(t\right)$ 达到相同阈值$1\times {10}^{-6}$ 所需的迭代时间而言，pDCA-SARAH算法均比pDCA短，且问题规模越大，pDCA-SARAH算法的优势便越显著，这说明了pDCA-SARAH算法在处理大规模DC问题时的优越性。

Table 1. When $\lambda =0.5,E\left(t\right)={10}^{-6}$ , comparison between two algorithms with respect to iteration times in problem (4.1)

表1. $\lambda =0.5,E\left(t\right)={10}^{-6}$ 时，问题(4.1)中两算法迭代时间对比

案例	问题规模			迭代时间(秒)
	n	m	s	pDCA	pDCA-SARAH
1	3000	900	180	99.02	89.12
2	5000	1500	300	255.32	232.79
3	8000	2400	480	664.42	622.51
4	10,000	3000	600	982.70	836.98

Table 2. When $\lambda =0.3,E\left(t\right)={10}^{-6}$ , comparison between two algorithms with respect to iteration times in problem (4.1)

表2. $\lambda =0.3,E\left(t\right)={10}^{-6}$ 时，问题(4.1)中两算法迭代时间对比

案例	问题规模			迭代时间(秒)
	n	m	s	pDCA	pDCA-SARAH
1	3000	900	180	85.88	79.27
2	5000	1500	300	267.69	227.04
3	8000	2400	480	672.10	606.27
4	10000	3000	600	907.02	837.88

此外，针对不同问题规模$\left(n,m,s\right)$ 与正则化参数$\lambda$ ，我们还在图1和图2中给出了pDCA与pDCA-SARAH算法的迭代收敛结果。具体的，图1给出了正则化参数$\lambda =0.5$ 时，pDCA与pDCA-SARAH算法最小相对误差$E\left(t\right)$ 的下降比较，从图中可知pDCA-SARAH算法的收敛速度比pDCA更快。类似的，针对正则化参数$\lambda =0.3$ 的情形，由图2亦可以得出上述结论。因此，在处理大规模DC问题时，就达到相同最小相对误差$E\left(t\right)$ 所需时间而言，pDCA-SARAH算法要优于pDCA。

Figure 1. When $\lambda =0.5$ , comparison of relative error reduction E(t) in pDCA and pDCA-SARAH algorithms

图1. $\lambda =0.5$ 时，pDCA与pDCA-SARAH算法最小相对误差E(t)下降比较

Figure 2. When $\lambda =0.3$ , comparison of relative error reduction E(t) in pDCA and pDCA-SARAH algorithms

图2. $\lambda =0.3$ 时，pDCA与pDCA-SARAH算法最小相对误差E(t)下降比较

5. 总结

本文将随机梯度SARAH与pDCA相结合，提出基于SARAH的随机邻近DC算法(pDCA-SARAH)，并将其应用于求解一类具有有限和形式的DC问题。

首先，本文提出pDCA-SARAH算法，该算法通过在内循环中抽取小批量的数据来计算随机梯度，并以此来近似全梯度，以实现计算成本的降低。其次，本文对pDCA-SARAH算法的收敛性及收敛率进行了分析，并在非凸情形下，详细地给出了目标函数在期望意义下的下降量分析和次线性收敛率分析。最后，通过数值实验，验证了pDCA-SARAH算法在处理大规模DC问题时的高效性。