本文考虑如下带有大量复杂约束的随机优化问题。

$\begin{array}{ll} \min\limits _{x \in X} & \psi_0(x)=f_0(x) \equiv \mathbb{E}_{\xi}[F(x ; \xi)]+\chi_0(x), \\ \text { s. t. } & f_i(x) \leqslant 0, \quad i=1, \cdots, M . \end{array}$

(1)

其中: $f_0(x):=\mathbb{E}_{\xi}[F(x ; \xi)]$, ξ∈Ξ(概率空间); $X \subseteq \mathbb{R}^d$是凸紧集；χ₀: $X \rightarrow \mathbb{R}$是凸函数；f₀: $X \rightarrow \mathbb{R}$是非凸函数；f_i: $X \rightarrow \mathbb{R}$，i=1, …, M是凸函数; F(·, ξ): $X \rightarrow \mathbb{R}$, $\forall \xi \in \varXi$是可微函数；f_i, i=0, …, M在X上连续可微，M充分大。

期望目标函数在当前的机器学习和数据科学中广泛出现，但常用的都是无约束有限和问题，然而采用约束优化模型的学习问题也在发展，比如基于约束优化的网络结构搜索(NAS)^[1]。该大规模约束优化问题的一大应用是复杂优化问题的近似问题，例如概率约束问题^[2]、robust优化^[3]、极小极大博弈^[4]。以概率约束问题为例，其问题模型是$\min \limits_{x \in X} f_0(x) \text { s. t. } \operatorname{Prob}\left(g\left(x, \xi_i\right) \leqslant 0\right) \geqslant 1-\tau$，其中X是凸紧集，ξ是Ξ上的参数。该问题的困难在于，E[g]可能是非凸函数，即使g对任意ξ是凸函数。一类解法是通过对ξ抽样，用抽样约束组代替概率约束，这称为抽样丢弃法^[2](sampling and discarding approach)。具体地说，这类方法从Ξ中抽取M个独立样本，然后用抽样约束近似概率约束，得到近似的约束优化问题

$\min \limits_{x \in X} f_0(x) . \quad \text { s. t. } \quad g\left(x, \xi_i\right) \leqslant 0 \forall i=1, \cdots, M .$

在一定条件下，可证明M→∞时，近似问题接近于原问题，所以当精度要求较高时M很大^[2]。

针对随机约束优化问题目前已发展了许多算法，这些算法整体上与确定约束优化问题类似，但因目标或约束带有随机信息，所以许多算法都带随机性。因为约束性质和数量的不同，这些算法的类别差异主要体现在约束的处理上。

最简单的处理是投影类方法，这类方法处理约束的思路是每步信息更新后的迭代点投影到可行域内，保持迭代序列可行性。在约束为随机约束或约束个数极多时，每步检查所有约束是否可行以及实现投影计算是非常困难的。所以一些算法^[5-6]引入了随机投影的思想，当约束个数极多时每步迭代只抽样一个约束，然后将迭代点投影到该约束的可行域内。在这一思路基础上，另一种处理方式^[7]是用梯度迭代代替直接投影，它同样每步迭代抽取一个约束，但转而考虑约束的一阶信息，如果约束一阶信息的范数大于给定阈值，则用该信息走一步负梯度方向。

另一类方法是子问题方法，思想是将困难问题转化为一系列的近似简单问题。经典的是二次规划方法^[8]，每步求解当前点的二阶近似，但因为用到二阶信息计算量相对较高。另一种方法是水平集方法^[9-11]，这类方法利用原问题的约束函数和目标函数构造水平集函数，然后将求解原问题转化为求解基于水平集的序列子问题，优势是无需二阶信息，但水平函数的构造相对更复杂，而且只能应用在凸优化问题上，如果目标非凸可以使用ICPP方法^[12]，该方法的子问题为凸约束优化问题，转化后就可以采用已有的凸优化技巧。

第3类方法是罚函数类算法。这一类方法将约束以罚函数的形式加到目标函数上，从而将约束优化转为无约束优化，罚函数的构造区别了这一类算法。最简单的罚函数是L1和L2罚函数，前者是精确罚方法，后者则有光滑性质；另一经典的罚类方法就是增广拉格朗日算法^[13]，此类算法结合了对偶理论，使得罚函数同时具备精确性和光滑性，算法交替更新迭代点和乘子，目标是寻找KKT点。近期针对随机目标优化的增广拉格朗日算法有PDSG^[14]，对凸目标函数，PDSG证明了可以在$\mathcal{O}\left(\epsilon^{-2}\right)$次迭代后找到$\epsilon$近似解。

1 引言

本文提出的算法属于增广拉格朗日算法一类。针对带大规模约束的约束优化问题，基于随机思想和已有的增广拉格朗日算法，提出一个新的随机增广拉格朗日算法，并证明从任意一个初始点出发，该算法能在$\mathcal{O}\left(\epsilon^{-8}\right)$次迭代后找到$\epsilon$-KKT近似点。

1.1 文章贡献

本文的主要贡献有以下3方面：

1) 提出一个原始对偶的随机算法用以解决带大量非线性约束的随机优化问题。该方法是经典增广拉格朗日法的随机改进，其每步采取一阶近似信息更新迭代，并按照约束抽样更新对应乘子。每步的计算复杂度取决于约束抽样数与近似精确度。

2) 建立算法对非凸非光滑目标函数的全局收敛性结果，证明该算法可以在$\mathcal{O}\left(\epsilon^{-8}\right)$次迭代后找到$\epsilon$-KKT近似点。与其他的针对非凸目标的算法不同，不假设约束的非奇异性而仅需要约束是凸的且Lipschitz光滑。

3) 用多分类Neyman Pearson问题验证算法的实际表现。数值结果表明该算法能有效收敛，同时能保证输出迭代点的不可行性的数量级较低。

1.2 标记符号定义

本文所用符号多数均为常用标记符号。使用小写字母x表示向量，黑体的0和1表示全0和全1向量，[M]={1, 2, …, M}表示整数集合，$\mathbb{R}_{++}$表示正实数集，$\|\boldsymbol{x}\|$表示向量x的$\ell_2$范数，$\|z\|_1$是z的$\ell_1$范数，$\|\boldsymbol{x}\|_{\boldsymbol{A}}=\sqrt{\boldsymbol{x}^{\mathrm{T}} \boldsymbol{A x}}$表示基于对称正定矩阵A的椭球范数，[a]₊=max(0, a)，$|\mathcal{I}|$表示集合$\mathcal{I}$的元素个数，ζ_k表示第k次迭代的随机信息，ζ_[k]={ζ₁, …, ζ_k}表示前k次迭代的随机信息，条件期望$\mathbb{E}\left[\cdot \mid \zeta_{[k-1]}\right]=\mathbb{E}_{\zeta_k}\left[\cdot \mid \zeta_{[k-1]}\right]$是已知前k-1次信息对第k次信息的期望，∂χ(x)表示χ在x处的次微分，$D_X:=\sup _{x, y \in X}\|x-y\|$表示集合的直径，d(·，·)表示距离。

2 CSALM

本节提出一个用于解决问题(1)的随机增广拉格朗日方法(composite stochastic augmented Lagrangian method, CSALM)，算法基于问题(1)的非线性增广拉格朗日函数^[15-16]，表示为

$\begin{aligned} & \mathcal{L}_\beta(x, z)=f_0(x)+\chi_0(x)+\Psi_\beta(x, z), \\ & \Psi_\beta(x, z)=\frac{1}{M} \sum\limits_{i=1}^M \psi_\beta\left(f_i(x), z_i\right), \\ & \psi_\beta(u, v)= \begin{cases}u v+\frac{\beta}{2} u^2, & \beta u+v \geqslant 0, \\ -\frac{v^2}{2 \beta}, & \beta u+v<0 .\end{cases} \end{aligned}$

(2)

其中：β>0是罚参数，z是拉格朗日乘子或对偶变量，Ψ是罚函数。式(2)是等式约束增广拉格朗日函数的推广^[15]，其原问题是问题(1)的约束函数乘上系数1/M时的等价问题。

对一般的非凸问题，寻找全局极小点是困难的，如果存在约束则更甚，所以我们的目标是找到KKT点。KKT点作为目标是合理的，当优化问题满足一些约束规范性条件时如LICQ，优化问题就存在KKT点。

定义2.1(KKT点) 称(x^*, z^*)∈$X \times \mathbb{R}_{+}^M$为问题(1)的KKT点，若其满足

$\begin{gathered} 0 \in \nabla f_0\left(x^*\right)+\partial \chi_0\left(x^*\right)+\mathcal{N}_X\left(x^*\right)+ \\ \frac{1}{M} \sum\limits_{i=1}^M z_i^* \nabla f_i\left(x^*\right), \\ f_i\left(x^*\right) \leqslant 0, i=1, \cdots, M, \\ z_i^* f_i\left(x^*\right)=0, i=1, \cdots, M . \end{gathered}$

但因为数值计算的精度问题，精确KKT点一般无法求得或者需要极高的计算量，所以通常寻找$\epsilon$-KKT近似点。

本文设计了寻找问题(1)的$\epsilon$-KKT点算法CSALM，算法假设存在一个$\mathcal{S F O}$(stochastic first order oracle)，即$\forall x$∈X和i∈[M]可以获得$\nabla$f₀(x)基于样本ξ_j的随机近似g_{0, j}=$\nabla$F(x, ξ_j)以及第i个约束的梯度和函数值($\nabla$f_i(x), f_i(x))。在第k次迭代，首先从样本空间和约束集合抽取批量样本$\mathcal{J}_k \subset \Psi$和$\mathcal{I}_k \subset[M]$，然后计算基于$\mathcal{S F O}$的$\nabla$f₀(x^k)的随机近似$g_{0, j}^k=\nabla F\left(x^k, \xi_j\right)$, j∈$\mathcal{J}_k$以及指标集$\mathcal{I}_k$对应约束的梯度和函数值($\nabla$f_i(x), f_i(x)), i∈$\mathcal{I}_k$获得梯度随机近似，

$g_0^k=\frac{1}{J_k} \sum\limits_{j \in \mathcal{J}_k} g_{0, j}^k, J_k=\left|\mathcal{J}_k\right|,$

(3)

$h^k=\frac{1}{I_k} \sum\limits_{i \in \mathcal{I}_k}\left[\beta f_i\left(x^k\right)+z_i^k\right]_{+} \nabla f_i\left(x^k\right), I_k=\left|\mathcal{I}_k\right| .$

(4)

随后基于$g_0^k+h^k$对x^k进行迭代，最后更新$\mathcal{I}_k$对应的对偶变量。

$\begin{aligned} x^{k+1}= & \underset{x \in X}{\arg \min }\left\{\chi_0(x)+\left\langle g_0^k+h^k, x\right\rangle+\right. \\ & \left.\frac{1}{2}\left\|x-x^k\right\|_{D_k}^2\right\} . \end{aligned}$

$z_i^{k+1}=z_i^k+\rho_k \cdot \max \left(-\frac{z_i^k}{\beta}, f_i\left(x^k\right)\right), \quad i \in \mathcal{I}_k .$

整个算法流程详见下列CSALM算法，超参数有罚参β，步长α，乘子更新系数ρ。算法的输出是在T次迭代后，随机取整数R∈[T]，输出x^R+1。

算法 CSALM(composite stochastic augmented Lagrangian method)
输入：初始点x1∈X, z1=0，罚参数β>0，步长{αk>0}, {ρk∈(0, β)}
输出：xR+1，其中R是从[T]中按均匀分布抽取的随机整数；
1. for k=1 to T do
2.  按概率空间Ξ分布独立抽取样本集$\mathcal{J}_k \subseteq \varXi$，均匀分布独抽取样本集$\mathcal{I}_k \subseteq[M]$
3.  调用一阶信息系统，依据(3)~(4)计算g0k和hk；
4.  更新原始变量x
${x^{k + 1}} = \mathop {\arg \min }\limits_{x \in X} \left\{ {{\chi _0}(x) + \left\langle {g_0^k + {h^k}, x} \right\rangle + \frac{1}{2}x - \left. {{x^k}} \right|_{{D_k}}^2} \right\}.\;\left( 5 \right)$
其中：$\boldsymbol{D}_k=\alpha_k^{-1} \boldsymbol{I}$；
5.  更新对偶变量z
$z_i^{k + 1} = \left\{ {\begin{array}{*{20}{l}} {z_i^k, }&{i \notin {{\cal I}_k}, }\\ {z_i^k + {\rho _k} \cdot \max \left( { - \frac{{z_i^k}}{\beta }, {f_i}\left( {{x^k}} \right)} \right), }&{i \in {{\cal I}_k}.} \end{array}} \right.\;\;\;\left( 6 \right)$
6. End for

当D_k是数量矩阵时，子问题迭代实际是梯度下降的拓展，但更容易处理凸项χ₀(x)。从式(6)可知，CSALM和PDSG^[14]是使用x^k更新对偶变量z^k，而经典增广拉格朗日算法是使用x^k+1，这一改动体现在收敛性证明上。另可观察到，g₀^k+h^k实际是$\mathcal{L}_\beta\left(x^k, z^k\right)$中可微部分的随机梯度，所以该方法其实可类比随机梯度法，从这一角度出发，该方法可以通过应用已有的无约束随机优化的技巧提升理论结果与数值表现，例如动量加速^[17]与方差缩减^[18]。

本文需要如下3个假设，分别是KKT存在假设、f_i的Lipschitz光滑性假设和随机梯度方差有界假设，后两者是随机优化算法中的常见假设。

假设2.1 问题(1)存在KKT点(x^*, z^*)∈$X \times \mathbb{R}_{+}^M$，其满足定义2.1。

假设2.2 {f_i(x), i=0, 1, …, M}在X上是Lipschitz光滑的，

$\begin{gathered} \left\|\nabla f_i(x)-\nabla f_i(y)\right\| \leqslant L\|x-y\|, \forall x, y \in X, \\ i=0, 1, \cdots, M, \Rightarrow \mid f_i(y)-f_i(x)- \\ \left\langle\nabla f_i(x), y-x\right\rangle \left\lvert\, \leqslant \frac{L}{2}\|y-x\|^2\right., i=0, \cdots, M . \end{gathered}$

(7)

其中：L∈$\mathbb{R}_{+}$是光滑系数。

假设2.3 记σ≥0是方差界常数，$\mathcal{S F O}$返回的g_{0, j}^k是无偏且方差有界的

$\begin{gathered} \mathbb{E}\left[g_{0, j}^k \mid \zeta_{[k-1]}\right]=\nabla f_0\left(x^k\right), \forall j \in \mathcal{J}_k, \forall k, \\ \mathbb{E}\left[\left\|g_{0, j}^k-\nabla f_0\left(x^k\right)\right\|^2 \mid \zeta_{[k-1]}\right] \leqslant \sigma^2, \forall j \in \mathcal{J}_k, \forall k, \\ \Rightarrow \mathbb{E}\left[g_0^k \mid \zeta_{[k-1]}\right]=\nabla f_0\left(x^k\right), \forall k, \\ \mathbb{E}\left[\left\|g_0^k-\nabla f_0\left(x^k\right)\right\|^2 \mid \zeta_{[k-1]}\right] \leqslant \frac{\sigma^2}{J_k}, \forall k . \end{gathered}$

基于假设和本文研究问题(1)的设定，可以得到关联f_i，$\nabla$f_i，χ₀，Ψ_β的有界性质。

引理2.1 X是凸紧集，所以$\exists F, G \in \mathbb{R}_{+}$使得

$\begin{gathered} \left|f_i(x)\right| \leqslant F, \left\|\nabla f_i(x)\right\| \leqslant G, \\ \forall x \in X, i=0, 1, \cdots, M . \end{gathered}$

(8)

引理2.2 X是凸紧集且χ₀(x)是正常凸函数，所以$\exists W \in \mathbb{R}$使得

$\chi_0(x) \geqslant W, \quad \forall x \in X$

(9)

引理2.3(引理3.4^[14]) 若i∈[M]是均匀抽样，那么$\forall x \in X, \forall z \in \mathbb{R}^M$有

$\begin{gathered} \mathbb{E}_i\left[\left[\beta f_i(x)+z_i\right]_{+} \nabla f_i(x)\right]=\nabla_x \Psi_\beta(x, z), \\ \mathbb{E}_i\left[\left\|\left[\beta f_i(x)+z_i\right]+\nabla f_i(x)\right\|^2\right] \leqslant 2 \beta^2 F^2 G^2+ \\ \frac{2 G^2}{M}\|z\|^2, \\ \mathbb{E}_i\left[\left\|\left[\beta f_i(x)+z_i\right]_{+} \nabla f_i(x)-\nabla_x \Psi_\beta(x, z)\right\|^2\right] \leqslant \\ 2 \beta^2 F^2 G^2+\frac{2 G^2}{M}\|z\|^2 . \end{gathered}$

则有

$\mathbb{E}\left[h^k \mid \zeta_{[k-1]}\right]=\nabla_x \Psi_\beta\left(x^k, z^k\right),$

(10)

$\begin{gathered} \mathbb{E}\left[\left\|h^k-\nabla_x \Psi_\beta\left(x^k, z^k\right)\right\|^2 \mid \zeta_{[k-1]}\right] \leqslant \\ \frac{2 \beta^2 F^2 G^2+\frac{2 G^2}{M}\left\|z^k\right\|^2}{I_k}. \end{gathered}$

(11)

其中: 由式(8)F, G为常数，$\mathbb{E}_i$是均匀抽样的期望。

3 CSALM收敛性分析

本节的内容是建立算法的收敛性结果。算法的目标是找到满足如下条件的$\epsilon$-KKT点。

定义3.1($\epsilon$-KKT点) $\epsilon$>0为给定求解精度，(x, z)∈$\mathbb{R}^d \times \mathbb{R}_{+}^M$为$\epsilon$-KKT点，若其满足

$\begin{array}{l} {_{R, {\zeta _{[T]}}}}\left[ {{\bf{d}}\left( {\nabla {f_0}(x) + \partial {\chi _0}(x) + \sum\limits_{i = 1}^M {{z_i}} \nabla {f_i}(x) + } \right.} \right.\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left. {\left. {{{\cal N}_X}(x), {\bf{0}}} \right)} \right]\leqslant \epsilon, \end{array}$

(12)

$\mathbb{E}_{R, \zeta_{[T]}}\left[\frac{1}{M} \sum\limits_{i=1}^M\left[f_i(x)\right]_{+}\right] \leqslant \epsilon,$

(13)

$\mathbb{E}_{R, \zeta_{[T]}}\left[\sum\limits_{i=1}^M z_i\left[f_i(x)\right]_{-}\right] \leqslant \epsilon$

(14)

本节将证明在假设2.1~假设2.3下，CSALM算法可以在$\mathcal{O}\left(\epsilon^{-8}\right)$次迭代后找到$\epsilon$-KKT近似点。首先证明乘子z^k和Ψ_β(x, z)的部分性质，然后分别证明梯度(12)、约束违反度(13)、互补松弛违反度(14)的收敛性。

3.1 前置结果

本小节主要证明CSALM算法下拉格朗日乘子z^k的非负性、有界性、Ψ_β(x, z)关于x的Lipschitz光滑性和h^k的方差有界性。非负性是KKT点的性质；有界性是增广拉格朗日算法相对于原始罚函数方法z→∞才收敛的改进优势；Ψ_β(x, z)对x的Lipschitz光滑性要求类比于f₀(x)；h^k的方差有界性类比于g₀^k的方差有界性。后2个结果是为了满足无约束优化问题下建立随机梯度算法收敛性的假设要求。

首先给出z^k的非负性。

引理3.1 对任意k≥1，z^k∈$\mathbb{R}_{+}^M$。

证明 k=1时，z¹=0。k>1时，设z^k∈$\mathbb{R}_{+}^M$，由式(6)和ρ_k∈(0, β)有

$z_i^{k+1} \geqslant z_i^k-\frac{\rho_k}{\beta} z_i^k \geqslant z_i^k-z_i^k=0, \quad \forall i \in[M] .$

由归纳法知结论成立。

然后证明z^k的有界性，首先考虑z^k的单步变化量，其被常数F和更新步长ρ_k控制。

引理3.2 在假设2.2下，∀k∈[T], ∀i∈[M]，有

$\left|z_i^{k+1}-z_i^k\right| \leqslant F \rho_k$

证明 式(8)可知|f(x^k)|≤F。由z^k的更新式(6)得

$\begin{gathered} \left|z_i^{k+1}-z_i^k\right| \leqslant \rho_k\left|\max \left(-\frac{z_i^k}{\beta}, f_i\left(x^k\right)\right)\right|, \\ \forall k \in[T], \forall i \in[M] . \end{gathered}$

(15)

当$f_i\left(x^k\right) \geqslant-\frac{z_i^k}{\beta}$，

$\left|\max \left(-\frac{z_i^k}{\beta}, f_i\left(x^k\right)\right)\right|=\left|f_i\left(x^k\right)\right| \leqslant F .$

(16)

当$f_i\left(x^k\right)<-\frac{z_i^k}{\beta}$，因为z^k非负(引理3.1)，所以

$\left|\max \left(-\frac{z_i^k}{\beta}, f_i\left(x^k\right)\right)\right|=\left|-\frac{z_i^k}{\beta}\right| \leqslant\left|f_i\left(x^k\right)\right| \leqslant F .$

(17)

将式(16)、式(17)代入式(15)结论得证。□

基于z^k的单步变化量，以下给出z^k的有界性结果。

引理3.3 记$\sum\limits_{t = 1}^0 {{\rho _t}} = 0$，假设2.2满足时，∀k∈[T+1], ${\left\| {{z^k}} \right\|_1} \le MF\sum\limits_{t = 1}^{k - 1} {{\rho _t}}$成立。

证明 k=1时，

$\left\|z^1\right\|_1=0=\sum\limits_{t=1}^0 \rho_t=M F \sum\limits_{t=1}^0 \rho_t$

k≥2时，由引理3.2，∀k∈{2, …, T+1},

$\begin{gathered} \left\|z^k\right\|_1=\sum\limits_{i=1}^M\left|z_i^k\right| \leqslant \sum\limits_{i=1}^M\left[\left|z_i^k-z_i^{k-1}\right|+\right. \\ \left.\left|z_i^{k-1}-z_i^{k-2}\right|+\cdots+\left|z_i^2-z_i^1\right|+\left|z_i^1\right|\right] \leqslant \\ \sum\limits_{i=1}^M\left[\sum\limits_{t=1}^{k-1} F \rho_t+0\right]=M F \sum\limits_{t=1}^{k-1} \rho_t \end{gathered}$

(18)

引理得证。□

z^k有界性结果是单步迭代量的累积，其界取决于ρ_k的部分和序列。显然当ρ_k比1/k低阶时，由式(18)可知z^k有界。

利用‖z^k‖₁的有界性，可以推出下述Ψ_β(x, z)关于x的Lipschitz光滑性。

引理3.4 假设2.2满足时，对∀x, y∈X, ∀k∈[T+1]，以下不等式成立:

$\left\|\nabla_x \Psi_\beta\left(x, z^k\right)-\nabla_x \Psi_\beta\left(y, z^k\right)\right\| \leqslant L_k\|x-y\|,$

(19)

其中：${L_k} = \beta {G^2} + \beta FL + LF\sum\limits_{t = 1}^{k - 1} {{\rho _t}}$。

证明 已知

${\nabla _x}{\Psi _\beta }(x,z) = \frac{1}{M}\sum\limits_{i = 1}^M {{{\left[ {\beta {f_i}(x) + {z_i}} \right]}_ + }} \nabla {f_i}(x),{f_i}(x)$是Lipschitz光滑，则∀x, y∈X，

$\begin{aligned} & \left\|\nabla_x \Psi_\beta(x, z)-\nabla_x \Psi_\beta(y, z)\right\| \\ = & \| \frac{1}{M} \sum\limits_{i=1}^M\left[\left[\beta f_i(x)+z_i\right]_{+} \nabla f_i(x)-\right. \\ & {\left.\left[\beta f_i(y)+z_i\right]_{+} \nabla f_i(y)\right] \| } \\ \leqslant & \frac{1}{M} \sum\limits_{i=1}^M \|\left[\beta f_i(x)+z_i\right]_{+} \nabla f_i(x)- \\ & {\left[\beta f_i(y)+z_i\right]_{+} \nabla f_i(y) \| } \\ = & \frac{1}{M} \sum\limits_{i=1}^M \|\left[\left[\beta f_i(x)+z_i\right]_{+}-\left[\beta f_i(y)+z_i\right]_{+}\right] \nabla f_i(x)+ \\ & {\left[\beta f_i(y)+z_i\right]_{+}\left[\nabla f_i(x)-\nabla f_i(y)\right] \| } \\ \leqslant & \frac{1}{M} \sum\limits_{i=1}^M\left[\beta\left|f_i(x)-f_i(y)\right|\left\|\nabla f_i(x)\right\|+\right. \\ & {\left.\left[\beta f_i(y)+z_i\right]_{+} L\|x-y\|\right] } \\ \leqslant & \frac{1}{M} \sum\limits_{i=1}^M\left[\beta G^2\|x-y\|+\right. \\ & \left.\left(\beta F+\left|z_i\right|\right) L\|x-y\|\right] \\ = & \left(\beta G^2+\beta F L+L\|z\|_1 / M\right)\|x-y\| \end{aligned}$

引理3.3代入‖z‖₁中结果得证。第1个和第2个不等号因为三角不等式，第3个不等号是对|f_i(x)-f_i(y)|使用微分中值定理后利用f_i(x)的梯度有界性(8)。

h^k有界方差性质也同样利用z^k的有界性结果。

引理3.5 在假设2.2下，

$\mathbb{E}\left[\left\|h^k-\nabla_x \Psi_\beta\left(x^k, z^k\right)\right\|^2 \mid \zeta_{[k-1]}\right] \leqslant \frac{\sigma_k^2}{I_k}$

(20)

其中：${\sigma _k} = \sqrt {2{\beta ^2}{F^2}{G^2} + 2{F^2}{G^2}{{\left[ {\sum\limits_{t = 1}^{k - 1} {{\rho _t}} } \right]}^2}} ,k \in [T]$。

证明由式(18)可得

$\begin{gathered} \left\|z^k\right\|^2=\sum\limits_{i=1}^M\left|z_i^k\right|^2 \leqslant \sum\limits_{i=1}^M\left[\sum\limits_{t=1}^{k-1} F \rho_t\right]^2 \\ =M F^2\left[\sum\limits_{t=1}^{k-1} \rho_t\right]^2, \forall k \in[T+1] . \end{gathered}$

(21)

将上述不等式代入式(11)就能推知引理成立。□

最后考虑ρ_k的取值。式(19)的Lipschitz系数和式(20)方差界都依赖于ρ_k的部分和，这里给出一组ρ_k的设定，使得这2个系数被固定常数控制。

引理3.6 假设2.2下，取常数ρ>0，令$\rho_k \leqslant \frac{\rho}{\sqrt{T k}}, k \in[T]$，那么以下不等式成立:

$\begin{gathered} \left\|z^k\right\|_1 \leqslant 2 M F \rho, \quad\left\|z^k\right\|^2 \leqslant 4 M F^2 \rho^2, \quad \forall k \in[T+1], \\ L_k \leqslant \beta G^2+\beta F L+2 L F \rho=: L_\beta, \quad \forall k \in[T+1], \\ \sigma_k \leqslant \sqrt{2 \beta^2 F^2 G^2+8 F^2 G^2 \rho^2}=: \sigma_h, \quad \forall k \in[T] . \end{gathered}$

证明 对任意k∈[T+1]，

$\begin{gathered} \sum\limits_{t=1}^{k-1} \rho_t \leqslant \frac{\rho}{\sqrt{T}} \sum\limits_{t=1}^{k-1} \frac{1}{\sqrt{t}} \leqslant \frac{\rho}{\sqrt{T}} \int_{0^{+}}^{k-1} \frac{1}{\sqrt{u}} \mathrm{~d} u= \\ \frac{2 \rho \sqrt{k-1}}{\sqrt{T}} \leqslant 2 \rho \end{gathered}$

结合式(18)~式(21)，推论得证。□

3.2 最优性条件

取点$(\hat{x}, \hat{z})$为

$(\hat{x}, \hat{z})=\left(x^{R+1}, \left(\beta f\left(x^{R+1}\right)+z^{R+1}\right)_{+} / M\right) .$

(22)

其中：(x^R+1, z^R+1)是算法的输出。本节主要内容是证明在$\mathcal{O}\left(\epsilon^{-4}\right)$次迭代后，点$(\hat{x}, \hat{z})$可满足式(12)。整体证明分为3个部分，首先是找到式(12)的一个容易分析的上界，然后分析‖x^k+1-x^k‖的单步下降性，该单步下降性是上界中的项，最后证明收敛性结果。

首先，可以从迭代式(5)、式(6)得到以下结论。

引理3.7 设假设2.2、假设2.3满足，任意步长α_k, ρ_k>0，则对任意k≥1，以下不等式成立：

$\begin{gathered} \mathbb{E}_{\zeta_{[k]}}\left[\mathbf { d } \left(\partial \chi_0\left(x^{k+1}\right)+\nabla f_0\left(x^{k+1}\right)+\right.\right. \\ \left.\left.\nabla_x \Psi_\beta\left(x^{k+1}, z^{k+1}\right)+\mathcal{N}_x\left(x^{k+1}\right), 0\right)\right] \\ \leqslant \mathbb{E}_{\zeta_{[k]}}\left[\left(\frac{1}{\alpha_k}+L+L_k\right)\left\|x^{k+1}-x^k\right\|+\frac{G}{M}\left\|z^{k+1}-z^k\right\|_1\right]+ \\ \mathbb{E}_{\zeta_{[k]}}\left[\left\|\nabla f_0\left(x^k\right)-g_0^k\right\|+\left\|\nabla_x \Psi_\beta\left(x^k, z^k\right)-h^k\right\|\right] . \end{gathered}$

证明 由式(5)的最优性条件，可得∀k≥1, $\exists v^{k+1} \in \mathcal{N}_X\left(x^{k+1}\right), d^{k+1} \in \partial \chi_0\left(x^{k+1}\right)$使得

$d^{k+1}+v^{k+1}+D_k\left(x^{k+1}-x^k\right)+g_0^k+h^k=\mathit{\pmb{0}}$

结合$\mathbf{d}(u+\boldsymbol{A}, \mathit{\pmb{0}}) \leqslant\|u\|+\mathbf{d}(\boldsymbol{A}, \mathit{\pmb{0}})$可以推出

$\begin{aligned} & \mathbb{E}\left[\mathbf{d}\left(\partial \chi_0\left(x^{k+1}\right)+\nabla f_0\left(x^{k+1}\right)+\nabla_x \Psi_\beta\left(x^{k+1}, z^{k+1}\right)+\mathcal{N}_X\left(x^{k+1}\right), 0\right) \mid \zeta_{[k-1]}\right] \\ = & \mathbb{E}\left[\mathbf { d } \left(\nabla f_0\left(x^{k+1}\right)-g_0^k+\nabla_x \Psi_\beta\left(x^{k+1}, z^{k+1}\right)-h^k-\boldsymbol{D}_k\left(x^{k+1}-x^k\right)+\right.\right. \\ & \left.\left.\mathcal{N}_X\left(x^{k+1}\right)-v^{k+1}+\partial \chi_0\left(x^{k+1}\right)-d^{k+1}, 0\right) \mid \zeta_{[k-1]}\right] \\ \leqslant & \mathbb{E}\left[\left\|\nabla f_0\left(x^{k+1}\right)-g_0^k+\nabla_x \Psi_\beta\left(x^{k+1}, z^{k+1}\right)-h^k-\boldsymbol{D}_k\left(x^{k+1}-x^k\right)\right\|+\right. \\ & \left.\mathbf{d}\left(\mathcal{N}_X\left(x^{k+1}\right)-v^{k+1}+\partial \chi_0\left(x^{k+1}\right)-d^{k+1}, 0\right) \mid \zeta_{[k-1]}\right] \\ = & \mathbb{E}\left[\left\|\nabla f_0\left(x^{k+1}\right)-g_0^k+\nabla_x \Psi_\beta\left(x^{k+1}, z^{k+1}\right)-h^k-\boldsymbol{D}_k\left(x^{k+1}-x^k\right)\right\| .\right. \end{aligned}$

因为$\nabla f_0$的Lipschitz连续性和式(19)，所以进一步有

$\begin{aligned} & \mathbb{E}\left[\mathbf{d}\left(\nabla f_0\left(x^{k+1}\right)+\nabla_x \Psi_\beta\left(x^{k+1}, z^{k+1}\right)+\mathcal{N}_x\left(x^{k+1}\right), 0\right) \mid \zeta_{[k-1]}\right] \\ \leqslant & \mathbb{E}\left[\left\|\nabla f_0\left(x^{k+1}\right)+\nabla_x \Psi_\beta\left(x^{k+1}, z^{k+1}\right)-\nabla f_0\left(x^k\right)-\nabla_x \Psi_\beta\left(x^k, z^k\right)\right\| \mid \zeta_{[k-1]}\right]+ \\ & \mathbb{E}\left[\left\|\boldsymbol{D}_k\left(x^{k+1}-x^k\right)\right\|+\left\|\nabla f_0\left(x^k\right)-g_0^k\right\|+\left\|\nabla_x \Psi_\beta\left(x^k, z^k\right)-h^k\right\| \mid \zeta_{[k-1]}\right] \\ \leqslant & \mathbb{E}\left[\left\|\nabla_x \Psi_\beta\left(x^{k+1}, z^{k+1}\right)-\nabla_x \Psi_\beta\left(x^{k+1}, z^k\right)\right\|+\left\|\nabla f_0\left(x^k\right)-g_0^k\right\| \mid \zeta_{[k-1]}\right]+\\ & \mathbb{E}\left[\left.\left(\frac{1}{\alpha_k}+L+L_k\right)\left\|x^{k+1}-x^k\right\|+\left\|\nabla_x \Psi_\beta\left(x^k, z^k\right)-h^k\right\| \right\rvert\, \zeta_{[k-1]}\right] \\ \leqslant & \mathbb{E}\left[\left.\frac{G}{M} \sum\limits_{i=1}^M\left|\left(\beta f_i\left(x^{k+1}\right)+z_i^{k+1}\right)_{+}-\left(\beta f_i\left(x^{k+1}\right)+z_i^k\right)_{+}\right|+\left\|\nabla f_0\left(x^k\right)-g_0^k\right\| \right\rvert\, \zeta_{[k-1]}\right]+ \\ & \mathbb{E}\left[\left.\left(\frac{1}{\alpha_k}+L+L_k\right)\left\|x^{k+1}-x^k\right\|+\left\|\nabla_x \Psi_\beta\left(x^k, z^k\right)-h^k\right\| \right\rvert\, \zeta_{[k-1]}\right] \\ \leqslant & \mathbb{E}\left[\left.\left(\frac{1}{\alpha_k}+L+L_k\right)\left\|x^{k+1}-x^k\right\|+\frac{G}{M} \sum\limits_{i=1}^M\left|z_i^{k+1}-z_i^k\right| \right\rvert\, \zeta_{[k-1]}\right]+ \\ & \mathbb{E}\left[\left\|\nabla f_0\left(x^k\right)-g_0^k\right\|+\left\|\nabla_x \Psi_\beta\left(x^k, z^k\right)-h^k\right\| \mid \zeta_{[k-1]}\right] . \end{aligned}$

第3个不等号因为Ψ_β(x, z)在式(2)中的定义。对上式两端取期望$\mathbb{E}_{\zeta_{[k-1]}}$，可得引理成立。□

接下来估计单次迭代带来的影响。

引理3.8 在假设2.2、假设2.3以及任意步长α_k, ρ_k>0下，∀k≥1有

$\begin{aligned} & \left(\frac{1}{\alpha_k}-\frac{L+L_k}{2}\right) \mathbb{E}_{\zeta_{[k]}}\left[\left\|x^{k+1}-x^k\right\|^2\right] \\ \leqslant & \mathbb{E}_{\zeta_{[k]}}\left[\mathcal{L}_\beta\left(x^k, z^k\right)-\mathcal{L}_\beta\left(x^{k+1}, z^{k+1}\right)+\right. \\ & \frac{F}{M}\left\|z^{k+1}-z^k\right\|_1+2 \alpha_k\left\|g_0^k-\nabla f_0\left(x^k\right)\right\|^2+ \\ & \left.2 \alpha_k\left\|h^k-\nabla_x \Psi_\beta\left(x^k, z^k\right)\right\|^2\right] . \end{aligned}$

证明由$\nabla f_0$和$\nabla_x \Psi_\beta(x, z)$在引理3.3中相对于x的Lipschitz连续性可得

$\begin{array}{l} {f_0}\left( {{x^{k + 1}}} \right) + {\Psi _\beta }\left( {{x^{k + 1}}, {z^k}} \right) \le {f_0}\left( {{x^k}} \right) + {\Psi _\beta }\left( {{x^k}, {z^k}} \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\frac{{L + {L_k}}}{2}{\left\| {{x^{k + 1}} - {x^k}} \right\|^2} + \left\langle {\nabla {f_0}\left( {{x^k}} \right) + } \right.\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left. {{\nabla _x}{\Psi _\beta }\left( {{x^k}, {z^k}} \right), {x^{k + 1}} - {x^k}} \right\rangle \end{array}$

(23)

而同时，根据式(5)的最优性条件，∃d^k+1∈∂χ₀(x^k+1)，对任意的x∈X有

$\left\langle d^{k+1}+g_0^k+h^k+\boldsymbol{D}_k\left(x^{k+1}-x^k\right), x-x^{k+1}\right\rangle \geqslant 0 .$

令上式中的x=x^k可得

$\begin{gathered} \left\langle d^{k+1}, x^k-x^{k+1}\right\rangle+\left\langle g_0^k+h^k, x^k-x^{k+1}\right\rangle- \\ \frac{1}{\alpha_k}\left\|x^{k+1}-x^k\right\|^2 \geqslant 0 . \end{gathered}$

(24)

对于凸部分，利用凸性性质得

$\left\langle d^{k+1}, x^k-x^{k+1}\right\rangle \leqslant \chi_0\left(x^k\right)-\chi_0\left(x^{k+1}\right) .$

(25)

将式(25)代入式(24)然后和式(23)相加，得到

$\begin{gathered} \mathcal{L}_\beta\left(x^{k+1}, z^k\right) \leqslant \mathcal{L}_\beta\left(x^k, z^k\right)+ \\ \left(\frac{L+L_k}{2}-\frac{1}{\alpha_k}\right)\left\|x^{k+1}-x^k\right\|^2+\\ \left\langle\nabla f_0\left(x^k\right)+\nabla_x \Psi_\beta\left(x^k, z^k\right)-g_0^k-h^k, x^{k+1}-x^k\right\rangle . \end{gathered}$

记${\hat x^{k + 1}} = {{\mathop{\rm argmin}\nolimits} _{x \in X}}\left\{ {\left. {{\chi _0}(x) + \left\langle {\nabla {f_0}\left( {{x^k}} \right) + } \right.{\nabla _x}{\Psi _\beta }\left( {{x^k}, {z^k}} \right), x} \right\rangle + \frac{1}{2}\left\| {x - {x^k}} \right\|_{{\mathit{\boldsymbol{D}}_k}}^2} \right\}$，则由投影算子的非扩张性(nonexpansiveness)可得

$\begin{gathered} \left\|\hat{x}^{k+1}-x^{k+1}\right\| \leqslant \alpha_k \| \nabla f_0\left(x^k\right)+ \\ \nabla_x \Psi_\beta\left(x^k, z^k\right)-g_0^k-h^k \| . \end{gathered}$

结合柯西不等式(Cauchy-Schwarz inequality)，可推出

$\begin{aligned} & \mathcal{L}_\beta\left(x^{k+1}, z^k\right) \\ \leqslant & \mathcal{L}_\beta\left(x^k, z^k\right)+\left(\frac{L+\mathcal{L}_k}{2}-\frac{1}{\alpha_k}\right)\left\|x^{k+1}-x^k\right\|^2+ \\ & \left\langle\nabla f_0\left(x^k\right)+\nabla_x \Psi_\beta\left(x^k, z^k\right)-g_0^k-h^k, \hat{x}^{k+1}-x^k\right\rangle+ \\ & \left\langle\nabla f_0\left(x^k\right)+\nabla_x \Psi_\beta\left(x^k, z^k\right)-g_0^k-h^k, x^{k+1}-\hat{x}^{k+1}\right\rangle \\ \leqslant & \mathcal{L}_\beta\left(x^k, z^k\right)+\left(\frac{L+\mathcal{L}_k}{2}-\frac{1}{\alpha_k}\right)\left\|x^{k+1}-x^k\right\|^2+ \\ & \left\langle\nabla f_0\left(x^k\right)+\nabla_x \Psi_\beta\left(x^k, z^k\right)-g_0^k-h^k, \hat{x}^{k+1}-x^k\right\rangle+ \\ & \alpha_k\left\|\nabla f_0\left(x^k\right)+\nabla_x \Psi_\beta\left(x^k, z^k\right)-g_0^k-h^k\right\|^2 . \end{aligned}$

对上述不等式两端取期望$\mathbb{E}_{\zeta_k}\left[\cdot \mid \zeta_{[k-1]}\right]$，然后由假设2.3和引理2.3可推出

$\begin{gathered} \mathbb{E}\left[\mathcal{L}_\beta\left(x^{k+1}, z^k\right) \mid \zeta_{[k-1]}\right] \\ \leqslant \mathbb{E}\left[\mathcal{L}_\beta\left(x^k, z^k\right)+\left(\frac{L+L_k}{2}-\frac{1}{\alpha_k}\right)\left\|x^{k+1}-x^k\right\|^2+\right. \\ \left.\alpha_k\left\|\nabla f_0\left(x^k\right)+\nabla_x \Psi_\beta\left(x^k, z^k\right)-g_0^k-h^k\right\|^2 \mid \zeta_{[k-1]}\right] . \end{gathered}$

另外，由ψ_β(u, v)关于$v \in \mathbb{R}_{+}$的Lipschitz连续性可得

$\begin{aligned} & \mathcal{L}_\beta\left(x^{k+1}, z^k\right) \\ = & \mathcal{L}_\beta\left(x^{k+1}, z^{k+1}\right)+\frac{1}{M} \sum\limits_{i=1}^M\left[\psi_\beta\left(f_i\left(x^{k+1}\right), z_i^k\right)-\right. \\ & \left.\psi_\beta\left(f_i\left(x^{k+1}\right), z_i^{k+1}\right)\right] \\ \geqslant & \mathcal{L}_\beta\left(x^{k+1}, z^{k+1}\right)-\frac{1}{M} \sum\limits_{i=1}^M\left|f_i\left(x^{k+1}\right)\right|\left|z_i^k-z_i^{k+1}\right| \\ \geqslant & \mathcal{L}_\beta\left(x^{k+1}, z^{k+1}\right)-\frac{F}{M}\left\|z^k-z^{k+1}\right\|_1 . \end{aligned}$

将以上2组不等式相加并对两端取期望$\mathbb{E}_{\zeta_{[k-1]}}$，再重新排列即可推知引理成立。□

接下来证明点(22)满足最优性近似(12)。

定理3.1 在假设2.2、假设2.3下，对所有k≥1设定

$\begin{gathered} J_k=k^{\frac{1}{4}}, I_k=\min \left(\left\lceil k^{\frac{3}{4}}\right\rceil, M\right), \beta=T^{\frac{1}{4}}, \\ \alpha_k=\alpha=\frac{T^{-\frac{1}{2}}}{L+G^2+F L+2 L F \rho}=: \frac{T^{-\frac{1}{2}}}{C}, \rho_k=\frac{\rho}{T I_k} . \end{gathered}$

则对任意T≥1，下式成立。

$\begin{gathered} \mathbb{E}_{R, \zeta_{[T]}}\left[\mathbf { d } \left(\partial \chi_0\left(x^{R+1}\right)+\nabla f_0\left(x^{R+1}\right)+\right.\right. \\ \left.\left.\sum\limits_{i=1}^M z_i \nabla f_i\left(x^{R+1}\right)+\mathcal{N}_X\left(x^{R+1}\right), 0\right)\right]=\mathcal{O}\left(T^{-\frac{1}{4}}\right) . \end{gathered}$

其中：$z_i=\frac{1}{M}\left(\beta f_i\left(x^{R+1}\right)+z_i^{R+1}\right)_{+}, i \in[M]$

证明 根据Ψ_β(x, z)的定义和引理3.7，

$\begin{aligned} & \mathbb{E}_{R, \zeta_{[T]}}\left[\mathbf { d } \left(\partial \chi_0\left(x^{R+1}\right)+\nabla f_0\left(x^{R+1}\right)+\right.\right. \\ & \left.\left.\sum\limits_{i=1}^M z_i \nabla f_i\left(x^{R+1}\right)+\mathcal{N}_X\left(x^{R+1}\right), 0\right)\right] \\ = & \frac{1}{T} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\mathbf { d } \left(\partial \chi_0\left(x^{k+1}\right)+\nabla f_0\left(x^{k+1}\right)+\right.\right. \\ & \left.\left.\frac{1}{M} \sum\limits_{i=1}^M\left(\beta f_i\left(x^{k+1}\right)+z_i^{k+1}\right)_{+} \nabla f_i\left(x^{k+1}\right)+\mathcal{N}_X\left(x^{k+1}\right), 0\right)\right] \\ = & \frac{1}{T} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\mathbf { d } \left(\partial \chi_0\left(x^{k+1}\right)+\nabla f_0\left(x^{k+1}\right)+\right.\right. \\ & \left.\left.\nabla_x \Psi_\beta\left(x^{k+1}, z^{k+1}\right)+\mathcal{N}_X\left(x^{k+1}\right), 0\right)\right] \\ \leqslant & \frac{1}{T} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\left(\frac{1}{\alpha_k}+L+L_k\right)\left\|x^{k+1}-x^k\right\|+\right. \\ & \left.\frac{G}{M}\left\|z^{k+1}-z^k\right\| \|_1\right]+\frac{1}{T} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\| \nabla f_0\left(x^k\right)-\right. \\ & \left.g_0^k\|+\| \nabla_x \Psi_\beta\left(x^k, z^k\right)-h^k \|\right] \\ \leqslant & \frac{1}{T} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\left(\frac{1}{\alpha_k}+L+L_\beta\right)\left\|x^{k+1}-x^k\right\|+\right. \\ & \left.\frac{G}{M}\left\|z^{k+1}-z^k\right\| \|_1\right]+\frac{\sigma}{T k^{1 / 8}}+\frac{\sigma_h}{T k^{3 / 8}} . \end{aligned}$

(26)

第2个不等式用了假设2.3，引理3.6和$(\mathbb{E}[u])^2 \leqslant \mathbb{E}\left[u^2\right]$对任意随机变量$u \in \mathbb{R}$。注意到，$\mathbb{E}\left[\left\|\nabla_x \Psi_\beta\left(x^k, z^k\right)-h^k\right\|\right] \leqslant \frac{\sigma_h}{k^{3 / 8}}$，在$\left\lceil k^{\frac{3}{4}}\right\rceil$>M时仍成立，因为I_k=M时$h^k=\nabla_x \Psi_\beta\left(x^k, z^k\right)$。

接下来依次分析式(26)的右端项。首先考虑方差项

$\begin{array}{l} \frac{1}{T}\sum\limits_{k = 1}^T {\left( {\frac{\sigma }{{{k^{1/8}}}} + \frac{{{\sigma _h}}}{{{k^{3/8}}}}} \right)} \le \frac{\sigma }{T}\int\limits_{{{\rm{0}}^{\rm{ + }}}}^T {{u^{ - \frac{1}{8}}}} {\rm{d}}u + \frac{{{\sigma _h}}}{T}\int\limits_{{{\rm{0}}^{\rm{ + }}}}^T {{u^{ - \frac{3}{8}}}} {\rm{d}}u = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{{8\sigma }}{{7{T^{1/8}}}} + \frac{{8{\sigma _h}}}{{5{T^{3/8}}}} \end{array}$

此外，引理3.6以及$\beta=T^{\frac{1}{4}}$可知$\sqrt{2 \beta^2 F^2 G^2+8 F^2 G^2 \rho^2}=\mathcal{O}\left(T^{\frac{1}{4}}\right)$因此

$\frac{1}{T} \sum\limits_{k=1}^T\left(\frac{\sigma}{k^{1 / 8}}+\frac{\sigma_h}{k^{3 / 8}}\right) \leqslant \frac{8 \sigma}{7 T^{1 / 8}}+\frac{8 \sigma_h}{5 T^{3 / 8}}=\mathcal{O}\left(T^{-\frac{1}{8}}\right) .$

(27)

然后是z^k+1-z^k项，类似于引理3.2，可以从式(8)和式(6)推出

$\begin{array}{l} \frac{1}{T} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\frac{G}{M}\left\|z^{k+1}-z^k\right\|_1\right] \\ =\frac{G}{T M} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k-1]}}\left[\sum\limits_{i=1}^M \frac{I_k}{M}\left|\rho_k \max \left(-\frac{z_i^k}{\beta}, f_i\left(x^k\right)\right)\right|\right]\\ \leqslant \frac{G}{M T} \sum\limits_{k=1}^T \rho_k I_k F=\frac{G F}{M T} \frac{\rho}{T} T=\frac{G \rho F}{M T}=\mathcal{O}\left(T^{-1}\right) . \end{array}$

(28)

最后考虑‖x^k+1-x^k‖项。由步长α_k和罚参数β的设定可知对任意k≥1有

$\begin{aligned} \frac{1}{\alpha_k} & =T^{\frac{1}{2}}\left(L+G^2+F L+2 L F \rho\right) \\ & \geqslant L+\beta G^2+\beta F L+2 L F \rho=L+L_\beta \\ & \geqslant \frac{L+L_\beta}{2} . \end{aligned}$

因此，记$\alpha_T=\sqrt{\sum_{k=1}^T\left(\frac{1}{\alpha_k}-\frac{L+L_\beta}{2}\right)}$，根据柯西不等式，即对任意${u_k} \ge 0, \sum {{u_k}} {v_k} \le \sqrt {\sum {{u_k}\sum {{u_k}} {v_k}^2} }$，以及对任意随机变量$u \in \mathbb{R}, (\mathbb{E}[u])^2\leqslant \mathbb{E}\left[u^2\right]$，可以推知

$\begin{aligned} & \frac{1}{T} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\left(\frac{1}{\alpha_k}-\frac{L+L_\beta}{2}\right)\left\|x^{k+1}-x^k\right\|\right] \\ \leqslant & \frac{\alpha_T}{T} \sqrt{\sum\limits_{k=1}^T\left(\frac{1}{\alpha_k}-\frac{L+L_\beta}{2}\right)\left[\mathbb{E}_{\zeta_{[k]}}\left[\left\|x^{k+1}-x^k\right\|\right]\right]^2} \\ \leqslant & \frac{\alpha_T}{T} \sqrt{\sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\left(\frac{1}{\alpha_k}-\frac{L+L_\beta}{2}\right)\left\|x^{k+1}-x^k\right\|^2\right]} . \end{aligned}$

同时，利用引理3.8、引理3.6和式(28)可得

$\begin{array}{l} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\left(\frac{1}{\alpha_k}-\frac{L+L_\beta}{2}\right)\left\|x^{k+1}-x^k\right\|^2\right] \\ \leqslant \mathbb{E}_{\zeta_{[T]}}\left[\mathcal{L}_\beta\left(x^1, z^1\right)-\mathcal{L}_\beta\left(x^{T+1}, z^{T+1}\right)\right]+ \\ \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\frac{F}{M}\left\|z^{k+1}-z^k\right\|_1\right]+\sum\limits_{k=1}^T 2 \alpha_k\left(\frac{\sigma^2}{k^{1 / 4}}+\frac{\sigma_h^2}{k^{3 / 4}}\right) \\ \leqslant \mathbb{E}_{\zeta_{[T]}}\left[\mathcal{L}_\beta\left(x^1, z^1\right)-\mathcal{L}_\beta\left(x^{T+1}, z^{T+1}\right)\right]+\\ \frac{F^2 \rho}{M}+\frac{2\left(\frac{4}{3} \sigma^2 T^{\frac{3}{4}}+4 \sigma_h^2 T^{\frac{1}{4}}\right)}{C \sqrt{T}} \end{array}$

其中最后一个不等式还利用了${\alpha _k} = {\left( {C{T^{\frac{1}{2}}}} \right)^{ - 1}},\sum\limits_{k = 1}^T {{k^{ - 1/4}}} \le \int_{{0^ + }}^T {{u^{ - 1/4}}} {\rm{d}}u = \frac{4}{3}{T^{\frac{3}{4}}}$，以及$\sum\limits_{k = 1}^T {{k^{ - 3/4}}} \le \int_{{0^ + }}^T {{u^{ - 3/4}}} {\rm{d}}u = 4{T^{\frac{1}{4}}}$。

考虑项$\mathcal{L}_\beta\left(x^1, z^1\right)-\mathcal{L}_\beta\left(x^{T+1}, z^{T+1}\right)$，首先估计$\mathcal{L}_\beta\left(x^1, z^1\right)V$的上界，因起始对偶点$z^1=\mathit{\pmb{0}}$，所以有

$\begin{aligned} \mathcal{L}_\beta\left(x^1, z^1\right) & =\chi_0\left(x^1\right)+f_0\left(x^1\right)+\frac{\beta}{2 M} \sum\limits_{i=1}^M\left(\left[f_i\left(x^1\right)\right]_{+}\right)^2 \\ & \Rightarrow \mathcal{L}_\beta\left(x^1, z^1\right) \leqslant \chi_0\left(x^1\right)+F+\frac{\beta}{2} F^2 \\ & =\chi_0\left(x^1\right)+F+\frac{F^2}{2} T^{\frac{1}{4}} . \end{aligned}$

然后是$\mathcal{L}_\beta\left(x^{T+1}, z^{T+1}\right)$的下界，由式(2)可得$\psi_\beta(u, v) \geqslant \frac{-v^2}{2 \beta}$，结合式(8)和推论引理3.6得

$\begin{aligned} \mathcal{L}_\beta\left(x^{T+1}, z^{T+1}\right)= & \chi_0\left(x^{T+1}\right)+f_0\left(x^{T+1}\right)+ \\ & \frac{1}{M} \sum\limits_{i=1}^M \psi_\beta\left(f_i\left(x^{T+1}\right), z_i^{T+1}\right) \\ \geqslant & W-F-\frac{1}{M} \sum\limits_{i=1}^M \frac{\left(z_i^{T+1}\right)^2}{2 \beta} \\ \geqslant & W-F-\frac{4 M F^2 \rho^2}{2 \beta M} \\ = & W-F-2 F^2 \rho^2 T^{-\frac{1}{4}} \\ \geqslant & W-F-2 F^2 \rho^2 . \end{aligned}$

所以‖x^k+1-x^k‖项的上界为

$\begin{aligned} & \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\left(\frac{1}{\alpha_k}-\frac{L+L_\beta}{2}\right)\left\|x^{k+1}-x^k\right\|^2\right] \\ \leqslant & \chi_0\left(x^1\right)+W+2 F+2 F^2 \rho^2+\frac{F^2}{2} T^{\frac{1}{4}}+ \\ & \frac{F^2 \rho}{M}+\frac{2\left(\frac{4}{3} \sigma^2 T^{\frac{3}{4}}+4 \sigma_h^2 T^{\frac{1}{4}}\right)}{C \sqrt{T}} . \end{aligned}$

考虑‖x^k+1-x^k‖项。记$C^{\prime}=\chi_0\left(x^1\right)+W+2 F+2 F^2 \rho^2+\frac{F^2 \rho}{M}$，代入$\alpha_k \equiv \alpha=\left(C T^{\frac{1}{2}}\right)^{-1}$，所以‖x^k+1-x^k‖项的上界为

$\begin{array}{l} \frac{1}{T} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\left(\frac{1}{\alpha_k}-\frac{L+L_\beta}{2}\right)\left\|x^{k+1}-x^k\right\|\right] \\ \leqslant \frac{\alpha_T}{T} \sqrt{C^{\prime}+\frac{F^2}{2} T^{\frac{1}{4}}+\frac{2\left(\frac{4}{3} \sigma^2 T^{\frac{3}{4}}+4 \sigma_h^2 T^{\frac{1}{4}}\right)}{C \sqrt{T}}}\\ \leqslant \frac{1}{T} \sqrt{C T^{\frac{3}{2}}} \sqrt{C^{\prime}+\frac{F^2}{2} T^{\frac{1}{4}}+\frac{2\left(\frac{4}{3} \sigma^2 T^{\frac{3}{4}}+4 \sigma_h^2 T^{\frac{1}{4}}\right)}{C \sqrt{T}}} . \end{array}$

其中：$\alpha_T=\sqrt{\sum_{k=1}^T\left(\frac{1}{\alpha_k}-\frac{L+L_\beta}{2}\right)}$。由α_k的定义，有$\frac{1}{\alpha_k}-\frac{L+L_\beta}{2} \geqslant \frac{L+L_\beta}{2}$。利用后者可以进一步得到

$\begin{array}{l} \frac{1}{T} \sum\limits_{k=1}^T \mathbb{E}_{S_{[k]}}\left[\left(\frac{1}{\alpha_k}+L+L_\beta\right)\left\|x^{k+1}-x^k\right\|\right] \\ =\frac{1}{T} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\left(\frac{1}{\alpha_k}-\frac{L+L_\beta}{2}\right)\left\|x^{k+1}-x^k\right\|\right]+ \\ \frac{3 L+3 L_\beta}{2} \frac{1}{T} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\left\|x^{k+1}-x^k\right\|\right] \\ \leqslant \frac{1}{T} \sum\limits_{k=1}^T \mathbb{E}_{S_{[k]}}\left[4\left(\frac{1}{\alpha_k}-\frac{L+L_\beta}{2}\right)\left\|x^{k+1}-x^k\right\|\right] \\ \leqslant \frac{4}{T} \sqrt{C T^{\frac{3}{2}}} \sqrt{C^{\prime}+\frac{F^2}{2} T^{\frac{1}{4}}+\frac{2\left(\frac{4}{3} \sigma^2 T^{\frac{3}{4}}+4 \sigma_h^2 T^{\frac{1}{4}}\right)}{C \sqrt{T}}}\\ =\mathcal{O}\left(T^{-\frac{1}{8}}\right) \end{array}$

(29)

最后一个等式因为$\sigma_h=\mathcal{O}\left(T^{\frac{1}{4}}\right)$。将式(27)~式(29)加到式(26)中，定理得证。□

3.3 约束违反度

该节证明在$\mathcal{O}\left(\epsilon^{-8}\right)$次迭代后，点(22)中的x^R+1满足约束违反度条件(13)

$\mathbb{E}_{R, \zeta_{[T]}}\left[\frac{1}{M} \sum\limits_{i=1}^M\left[f_i\left(x^{R+1}\right)\right]_{+}\right] \leqslant \epsilon .$

分析收敛性前先给出一些需要的性质，分别是Ψ_β(x, z)对x的凸性，Ψ_β(x, z)在可行域内非正性，以及原始对偶解的对偶间隙。

引理3.9 当{f_i, i∈[M]}均为凸函数时，Ψ_β(x, z)对x凸。

证明 Ψ_β的定义如下，

$\begin{gathered} \Psi_\beta(x, z)=\frac{1}{M} \sum\limits_{i=1}^M \psi_\beta\left(f_i(x), z_i\right), \\ \psi_\beta(u, v)= \begin{cases}u v+\frac{\beta}{2} u^2, & \beta u+v \geqslant 0, \\ -\frac{v^2}{2 \beta}, & \beta u+v<0 .\end{cases} \end{gathered}$

因为求和不改变凸性，只需证明对任意i∈[M]，ψ_β(f_i(x), z_i)关于x凸即可。

设v为任意常数，

当βu+v < 0时，ψ_β(u, v)为常数，且

$\psi_\beta(u, v)=-\frac{v^2}{2 \beta}, \nabla_u \psi_\beta(u, v)=0 ;$

当βu+v=0时

$\psi_\beta(u, v)=\frac{u}{2}(v+v+\beta u)=-\frac{v}{2 \beta} \times v=-\frac{v^2}{2 \beta} ;$

当βu+v≥0时，

$\nabla_u \psi_\beta(u, v)=\beta u+v \geqslant 0 .$

所以ψ_β(·, v)与$\nabla_u \psi_\beta(\cdot, v)$都是关于u的单调增函数，所以ψ(·, v)是关于u的凸函数。

设z_i为任意常数，λ₁, λ₂≥0, λ₁+λ₂=1，x₁, x₂∈χ，有

$\begin{aligned} & \quad \lambda_1 \psi_\beta\left(f_i\left(x_1\right), z_i\right)+\lambda_2 \psi_\beta\left(f_i\left(x_2\right), z_i\right) \\ & \stackrel{(1)}{\geqslant} \psi_\beta\left(\lambda_1 f_i\left(x_1\right)+\lambda_2 f_i\left(x_2\right), z_i\right) \\ & \stackrel{(2)}{\geqslant} \psi_\beta\left(f_i\left(\lambda_1 x_1+\lambda_2 x_2\right), z_i\right) \end{aligned}$

(1) 是ψ_β(·, v)凸性，(2)是ψ_β(·, v)对u单调递增和f_i的凸性。引理得证。□

引理3.10 对任意x∈X∩{x|f_i(x)≤0, ∀i∈[M]}，Ψ_β(x, z)≤0。

证明 若βf_i(x)+z_i≥0

$\begin{gathered} \psi_\beta\left(f_i(x), z_i\right)=f_i(x)\left(z_i+\beta f_i(x) / 2\right)= \\ f_i(x)\left(z_i+\beta f_i(x)-\beta f_i(x) / 2\right) \leqslant 0 . \end{gathered}$

若βf_i(x)+z_i < 0，

$\psi_\beta\left(f_i(x), z_i\right)=\frac{-z_i^2}{2 \beta} \leqslant 0$

因此，${\Psi _\beta }(x,z) = \frac{1}{M}\sum\limits_{i = 1}^M {{\psi _\beta }} \left( {{f_i}(x),{z_i}} \right) \le 0$。□

引理3.11 记(x^*, z^*)为满足假设2.1的原始-对偶解，则∀x∈X,

$\psi_0(x) \geqslant \psi_0\left(x^*\right)-\frac{1}{M} \sum\limits_{i=1}^M z_i^* f_i(x)-\frac{L}{2}\left\|x-x^*\right\|^2 .$

证明 由f₀的Lipschitz光滑性可得，对任意x∈X，

$\begin{gathered} f_0(x) \geqslant f_0\left(x^*\right)+\left\langle\nabla f_0\left(x^*\right), x-x^*\right\rangle- \\ \frac{L}{2}\left\|x-x^*\right\|^2 . \end{gathered}$

同时，由x^*的最优性条件

$\begin{gathered} 0 \in \partial \chi_0\left(x^*\right)+\nabla f_0\left(x^*\right)+\mathcal{N}_X\left(x^*\right)+ \\ \frac{1}{M} \sum\limits_{i=1}^M z_i^* \nabla f_i\left(x^*\right), \end{gathered}$

可知存在向量$\boldsymbol{u} \in \mathcal{N}_X\left(x^*\right), d \in \partial \chi_0\left(x^*\right)$使得

$-\boldsymbol{u}-d-\frac{1}{M} \sum\limits_{i=1}^M z_i^* \nabla f_i\left(x^*\right)=\nabla f_0\left(x^*\right)$

将该式代入到光滑性不等式中，并用法锥$\mathcal{N}_X\left(x^*\right)$的定义，约束函数f_i, i∈[M]的凸性，z_i^*≥0, z_i^*f_i(x^*)=0, i∈[M]，和χ₀(x)的凸性，简化结果即可。□

下述引理类似于文献[14]的引理3.3，但两者的区别在于算法CSALM中每次迭代抽取了多个样本，因此这里还是详细给出相应的证明。

引理3.12 算法CSALM对任意确定或随机的向量$z \in \mathbb{R}_{+}^M$，有以下不等式成立：

$\begin{aligned} & -\Psi_\beta\left(x^k, z^k\right)+\frac{1}{M} \sum\limits_{i=1}^M z_i f_i\left(x^k\right)+ \\ & \frac{1}{2 \rho_k I_k} \mathbb{E}\left[\left\|z^{k+1}-z\right\|^2 \mid \zeta_{[k-1]}\right] \leqslant \frac{1}{2 \rho_k I_k}\left\|z^k-z\right\|^2- \\ & \frac{1}{2 \rho_k I_k}\left(\frac{\beta}{\rho_k}-1\right) \mathbb{E}\left[\left\|z^{k+1}-z^k\right\|^2 \mid \zeta_{[k-1]}\right]+ \\ & \mathbb{E}\left[\left\langle z^k-z, \frac{M}{I_k} e_{I_k} \odot \nabla_z \Psi_\beta\left(x^k, z^k\right)-\right.\right. \\ & \left.\left.\nabla_z \Psi_\beta\left(x^k, z^k\right)\right\rangle \mid \zeta_{[k-1]}\right] . \end{aligned}$

其中：⊙代表对应分量相乘。

证明 因为$\nabla_{z_i} \psi_\beta\left(f_i(x), z_i\right)=\max \left(-\frac{z_i}{\beta}, f_i(x)\right)$，所以

$\begin{aligned} \nabla_{z_i} \Psi_\beta(x, z) & =\nabla_{z_i}\left[\frac{1}{M} \sum\limits_{p=1}^M \psi_\beta\left(f_p(x), z_p\right)\right] \\ & =\frac{1}{M} \nabla_{z_i} \psi_\beta\left(f_i(x), z_i\right) \\ & =\frac{1}{M} \max \left(-\frac{z_i}{\beta}, f_i(x)\right) . \end{aligned}$

所以，z的迭代公式(6)可以改写为

$z^{k+1}=z^k+M \rho_k \boldsymbol{e}_{\mathcal{I}_k} \odot \nabla_z \Psi_\beta\left(x^k, z^k\right)$

其中：$\odot: \mathbb{R}^M \times \mathbb{R}^M \rightarrow \mathbb{R}^M$代表对应分量相乘；$\boldsymbol{e}_{\mathcal{I}_k} \mathbb{R}^M\in$记为集合${\mathcal{I}_k}$ _k的指示向量(即对所有$i \in \mathcal{I}_k$，$\boldsymbol{e}_{\mathcal{I}_k}$对应的分量为1，其余分量为0)。因此，

$\begin{aligned} & \frac{1}{I_k \rho_k}\left\langle z^k-z, z^{k+1}-z^k\right\rangle=\left\langle z^k-z, \nabla_z \Psi_\beta\left(x^k, z^k\right)\right\rangle+ \\ & \left\langle z^k-z, \frac{M}{I_k} \boldsymbol{e}_{\tau_k} \odot \nabla_z \Psi_\beta\left(x^k, z^k\right)-\nabla_z \Psi_\beta\left(x^k, z^k\right)\right\rangle \end{aligned}$

记$\mathcal{I}_k^{+}=\left\{i \in[M] \mid \beta f_i\left(x^k\right)+z_i^k \geqslant 0\right\}$, $\mathcal{I}_k^{-}=[M] \backslash \mathcal{I}_k^{+}$。注意到对任意z≥0以及任意$i \in \mathcal{I}_k^{-}, z_i\left(f_i\left(x^k\right)+\frac{z_i^k}{\beta}\right) \leqslant 0$成立，结合Ψ_β(x, z)在式(2)中的定义，所以有

$\begin{aligned} & -\Psi_\beta\left(x^k, z^k\right)+\frac{1}{M} \sum\limits_{i=1}^M z_i f_i\left(x^k\right)+\left\langle z^k-z, \nabla_z \Psi_\beta\left(x^k, z^k\right)\right\rangle \\ = & -\frac{1}{M} \sum\limits_{i \in \mathcal{I}_k^{+}}\left[z_i^k f_i\left(x^k\right)+\frac{\beta}{2}\left[f_i\left(x^k\right)\right]^2\right]+ \\ & \frac{1}{M} \sum\limits_{i \in \mathcal{I}_k^{-}} \frac{\left(z_i^k\right)^2}{2 \beta}+\frac{1}{M} \sum\limits_{i=1}^M z_i f_i\left(x^k\right)+ \\ & \frac{1}{M} \sum\limits_{i \in \mathcal{I}_k^{+}}\left(z_i^k-z_i\right) f_i\left(x^k\right)-\frac{1}{M} \sum\limits_{i \in I_k^{-}}\left(z_i^k-z_i\right) \frac{z_i^k}{\beta} \\ = & -\frac{1}{M} \sum\limits_{i \in \mathcal{I}_k^{+}} \frac{\beta}{2}\left[f_i\left(x^k\right)\right]^2- \\ & \frac{1}{M} \sum\limits_{i \in \mathcal{I}_k^{-}}\left[\frac{\left(z_i^k\right)^2}{2 \beta}-z_i\left(f_i\left(x^k\right)+\frac{z_i^k}{\beta}\right)\right] \\ \leqslant & -\frac{1}{M} \sum\limits_{i \in I_k^{+}} \frac{\beta}{2}\left[f_i\left(x^k\right)\right]^2-\frac{1}{M} \sum\limits_{i \in I_k^{-}} \frac{\left(z_i^k\right)^2}{2 \beta} . \end{aligned}$

另外，由式(6)可得

$\begin{aligned} & \mathbb{E}\left[\left\|z^{k+1}-z^k\right\|^2 \zeta_{[k-1]}\right] \\ = & \frac{I_k}{M}\left[\sum\limits_{i \in \mathcal{I}_k^{+}}\left(\rho_k f_i\left(x^k\right)\right)^2+\sum\limits_{i \in \mathcal{I}_k^{-}}\left(\frac{\rho_k z_i^k}{\beta}\right)^2\right] \\ = & \frac{I_k \rho_k^2}{M \beta}\left[\sum\limits_{i \in \mathcal{I}_k^{+}} \beta\left(f_i\left(x^k\right)\right)^2+\sum\limits_{i \in \mathcal{I}_k^{-}} \frac{\left(z_i^k\right)^2}{\beta}\right] . \end{aligned}$

结合以上3组(不)等式，根据

$\begin{gathered} \left\langle z^k-z, z^{k+1}-z^k\right\rangle= \\ \frac{1}{2}\left[\left\|z^{k+1}-z\right\|^2-\left\|z^k-z\right\|^2-\left\|z^{k+1}-z^k\right\|^2\right]. \end{gathered}$

引理得证。□

基于引理3.12，可以得到以下重要结论。

定理3.2 在假设2.1~假设2.3以及任意步长{α_k>0, k∈[T]}下，下列不等式

$\begin{array}{l} \mathbb{E}\left[\left(\left.\psi_0\left(x^k\right)+\frac{1}{M} \sum\limits_{i=1}^M z_i f_i\left(x^k\right) \right\rvert\, \zeta_{[k-1]}\right)\right]+ \\ \mathbb{E}\left[\left.\frac{1}{2 \alpha_k}\left\|x^{k+1}-x\right\|^2+\frac{1}{2 \rho_k I_k}\left\|z^{k+1}-z\right\|^2 \right\rvert\, \zeta_{[k-1]}\right] \\ \leqslant \mathbb{E}\left[\psi_0(x)+\Psi_\beta\left(x, z^k\right)+\frac{1}{2}\left(\frac{1}{\alpha_k}+L\right)\right.\\ \left.\left\|x^k-x\right\|^2 \mid \zeta_{[k-1]}\right]+\mathbb{E}\left[\left.\frac{1}{2 \rho_k I_k}\left\|z^k-z\right\|^2 \right\rvert\, \zeta_{[k-1]}\right]+ \\ \alpha_k\left(\sigma^2+G^2+2 \beta^2 F^2 G^2+\frac{2 G^2}{M} \mathbb{E}\left[\left\|z^k\right\|^2 \mid \zeta_{[k-1]}\right]\right)- \\ \frac{1}{2 \rho_k I_k}\left(\frac{\beta}{\rho_k}-1\right) \mathbb{E}\left[\left\|z^{k+1}-z^k\right\|^2 \mid \zeta_{[k-1]}\right]-\\ \mathbb{E}\left[ {\left\langle {{x^k} - x, \left( {g_0^k + {h^k}} \right) - \left( {\nabla {f_0}\left( {{x^k}} \right) + } \right.} \right.} \right.\\ \left.\left.\left.\nabla_x \Psi_\beta\left(x^k, z^k\right)\right)\right\rangle \mid \zeta_{[k-1]}\right]+\\ \mathbb{E}\left[\left\langle z^k-z, \frac{M}{I_k} e_{I_k} \odot \nabla_z \Psi_\beta\left(x^k, z^k\right)-\right.\right. \\ \left.\left.\nabla_z \Psi_\beta\left(x^k, z^k\right)\right\rangle \mid \zeta_{[k-1]}\right]+ \\ \mathbb{E}\left[\chi_0\left(x^k\right)-\chi_0\left(x^{k+1}\right) \mid \zeta_{[k-1]}\right] . \end{array}$

对任意x∈X, $z \in \mathbb{R}_{+}^M$成立。

证明 由式(5)的最优性条件可得，∃d^k+1∈χ₀(x^k+1)，使得

$\begin{array}{l} \left\langle {{d^{k + 1}} + g_0^k + {h^k} + {{\bf{D}}_k}\left( {{x^{k + 1}} - {x^k}} \right), x - {x^{k + 1}}} \right\rangle \ge 0, \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\forall x \in X. \end{array}$

(30)

下面将不等式左端拆为4项，依次分析。

对内积项$\left\langle g_0^k, x-x^{k+1}\right\rangle$，根据杨氏不等式和式(7)，

$\begin{aligned} & \mathbb{E}\left[\left\langle g_0^k, x^{k+1}-x\right\rangle \mid \zeta_{[k-1]}\right] \\ = & \mathbb{E}\left[\left\langle g_0^k, x^{k+1}-x^k\right\rangle+\left\langle g_0^k, x^k-x\right\rangle \mid \zeta_{[k-1]}\right] \\ \geqslant & \mathbb{E}\left[-\frac{1}{4 \alpha_k}\left\|x^{k+1}-x^k\right\|^2-\alpha_k\left\|g_0^k\right\|^2+\right. \\ & \left\langle\nabla f_0\left(x^k\right), x^k-x\right\rangle+\left\langle g_0^k-\nabla f_0\left(x^k\right), \right. \\ & \left.\left.x^k-x\right\rangle \mid \zeta_{[k-1]}\right] \\ \geqslant & \mathbb{E}\left[-\frac{1}{4 \alpha_k}\left\|x^{k+1}-x^k\right\|^2-\alpha_k\left(\sigma^2+G^2\right)+\right. \\ & f_0\left(x^k\right)-f_0(x)-\frac{L}{2}\left\|x^k-x\right\|^2+ \\ & \left.\left\langle g_0^k-\nabla f_0\left(x^k\right), x^k-x\right\rangle \mid \zeta_{[k-1]}\right] . \end{aligned}$

(31)

第2个不等号还用到了依据假设2.3和式(8)得到的下列不等式

$\begin{aligned} \mathbb{E}\left[\left\|g_0^k\right\|^2 \zeta_{[k-1]}\right]= & \mathbb{E}\left[\left\|g_0^k-\nabla f_0\left(x^k\right)\right\|^2 \zeta_{[k-1]}\right]+ \\ & \mathbb{E}\left[\left\|\nabla f_0\left(x^k\right)\right\|^2 \zeta_{[k-1]}\right] \leqslant \sigma^2+G^2 \end{aligned}$

对内积项〈h^k, x-x^k+1〉，根据Ψ_β在x上的凸性和杨氏不等式，可以得到类似的估计，

$\begin{aligned} & \mathbb{E}\left[\left\langle h^k, x^{k+1}-x\right\rangle \mid \zeta_{[k-1]}\right] \\ = & \mathbb{E}\left[\left\langle h^k, x^{k+1}-x^k\right\rangle \mid \zeta_{[k-1]}\right]+ \\ & \mathbb{E}\left[\left\langle h^k, x^k-x\right\rangle \mid \zeta_{[k-1]}\right] \\ \geqslant & \mathbb{E}\left[-\frac{1}{4 \alpha_k}\left\|x^{k+1}-x^k\right\|^2+\left\langle\nabla_x \Psi_\beta\left(x^k, z^k\right), x^k-x\right\rangle-\right. \\ & \left.\alpha_k\left\|h^k\right\|^2+\left\langle h^k-\nabla_x \Psi_\beta\left(x^k, z^k\right), x^k-x\right\rangle \mid \zeta_{[k-1]}\right] \\ \geqslant & \mathbb{E}\left[-\frac{1}{4 \alpha_k}\left\|x^{k+1}-x^k\right\|^2+\Psi_\beta\left(x^k, z^k\right)-\Psi_\beta\left(x, z^k\right)-\right. \\ & \left.\alpha_k\left\|h^k\right\|^2+\left\langle h^k-\nabla_x \Psi_\beta\left(x^k, z^k\right), x^k-x\right\rangle \mid \zeta_{[k-1]}\right] . \end{aligned}$

由引理2.3和对任意向量$\left\{u^i\right\}, \left\|\sum_{i=1}^M u^i\right\|^2 \leqslant M \sum_{i=1}^M\left\|u^i\right\|^2$，可知

$\mathbb{E}\left[\left\|h^k\right\|^2 \mid \zeta_{[k-1]}\right] \leqslant 2 \beta^2 F^2 G^2+\frac{2 G^2}{M}\left\|z^k\right\|^2$

所以

$\begin{aligned} \mathbb{E} & {\left[\left\langle h^k, x^{k+1}-x\right\rangle \mid \zeta_{[k-1]}\right] } \\ \geqslant & \mathbb{E}\left[\left.-\frac{1}{4 \alpha_k}\left\|x^{k+1}-x^k\right\|^2 \right\rvert\, \zeta_{[k-1]}\right]+ \\ & \mathbb{E}\left[\left\langle h^k-\nabla_x \Psi_\beta\left(x^k, z^k\right), x^k-x\right\rangle \mid \zeta_{[k-1]}\right]+ \\ & \mathbb{E}\left[\Psi_\beta\left(x^k, z^k\right)-\Psi_\beta\left(x, z^k\right) \mid \zeta_{[k-1]}\right]+ \\ & \mathbb{E}\left[\left.-\alpha_k\left(2 \beta^2 F^2 G^2+\frac{2 G^2}{M}\left\|z^k\right\|^2\right) \right\rvert\, \zeta_{[k-1]}\right] . \end{aligned}$

(32)

对内积项$\left\langle\boldsymbol{D}_k\left(x^{k+1}-x^k\right), x^{k+1}-x\right\rangle$，取期望得

$\begin{aligned} & \mathbb{E}\left[\left\langle\boldsymbol{D}_k\left(x^{k+1}-x^k\right), x^{k+1}-x\right\rangle \mid \zeta_{[k-1]}\right] \\ = & \frac{1}{2} \mathbb{E}\left[\left\|x^{k+1}-x\right\|_{D_k}^2-\left\|x^k-x\right\|_{D_k}^2+\right. \\ & \left.\left\|x^{k+1}-x^k\right\|_{D_k}^2 \mid \zeta_{[k-1]}\right] . \end{aligned}$

(33)

对式(30)两端取期望$\mathbb{E}\left[\cdot \mid \zeta_{[k-1]}\right]$，并加上式(31)~式(33)可得

$\begin{aligned} & \mathbb{E} {\left[f_0\left(x^k\right)-f_0(x)+\Psi_\beta\left(x^k, z^k\right)-\Psi_\beta\left(x, z^k\right) \mid \zeta_{[k-1]}\right]+} \\ & \mathbb{E}\left[\left.\frac{1}{2 \alpha_k}\left\|x^{k+1}-x\right\|^2 \right\rvert\, \zeta_{[k-1]}\right] \\ & \leqslant \frac{1}{2} \mathbb{E}\left[\left.\left(L+\frac{1}{\alpha_k}\right)\left\|x^k-x\right\|^2 \right\rvert\, \zeta_{[k-1]}\right]+ \\ & \alpha_k\left(\sigma^2+G^2+2 \beta^2 F^2 G^2+\frac{2 G^2}{M} \mathbb{E}\left[\left\|z^k\right\|^2 \mid \zeta_{[k-1]}\right]\right)- \\ & \mathbb{E}\left[\left\langle x^k-x, \left(g_0^k+h^k\right)-\left(\nabla f_0\left(x^k\right)+\right.\right.\right. \\ &\left.\left.\left.\nabla_x \Psi_\beta\left(x^k, z^k\right)\right)\right\rangle \mid \zeta_{[k-1]}\right]- \\ & \mathbb{E}\left[\left\langle d^{k+1}, x^{k+1}-x\right\rangle \mid \zeta_{[k-1]}\right] . \end{aligned}$

(34)

考虑项〈d^k+1,x^k+1-x〉，因为d^k+1∈∂χ₀(x^k+1)，所以由 χ₀的凸性

$\begin{gathered} 0 \geqslant\left\langle d^{k+1}, x^{k+1}-x\right\rangle \geqslant \chi_0\left(x^{k+1}\right)-\chi_0(x) \\ \Leftrightarrow \chi_0\left(x^k\right)-\chi_0\left(x^{k+1}\right) \geqslant \chi_0\left(x^k\right)-\chi_0(x) . \end{gathered}$

(35)

式(35)加在式(34)上得到

$\begin{aligned} & \mathbb{E}\left[\psi_0\left(x^k\right)-\psi_0(x)+\Psi_\beta\left(x^k, z^k\right)-\Psi_\beta\left(x, z^k\right)+\right. \\ & \left.\left.\frac{1}{2 \alpha_k}\left\|x^{k+1}-x\right\|^2 \right\rvert\, \zeta_{[k-1]}\right] \\ & \leqslant \frac{1}{2} \mathbb{E}\left[\left.\left(L+\frac{1}{\alpha_k}\right)\left\|x^k-x\right\|^2 \right\rvert\, \zeta_{[k-1]}\right]+ \\ & \quad \alpha_k\left(\sigma^2+G^2+2 \beta^2 F^2 G^2+\frac{2 G^2}{M} \mathbb{E}\left[\left\|z^k\right\|^2 \mid \zeta_{[k-1]}\right]\right)- \\ & \quad \mathbb{E}\left[\left\langle x^k-x, \left(g_0^k+h^k\right)-\left(\nabla f_0\left(x^k\right)+\right.\right.\right. \\ & \left.\left.\left.\quad \nabla_x \Psi_\beta\left(x^k, z^k\right)\right)\right\rangle \mid \zeta_{[k-1]}\right]+\\ &\mathbb{E}\left[\chi_0\left(x^k\right)-\chi_0\left(x^{k+1}\right) \mid \zeta_{[k-1]}\right] \end{aligned}$

(36)

结合引理3.12和式(36)，重排后即可得到结论。□

在定理3.1的基础上，可以得到关于$\sum\limits_{k = 1}^T {{\mathbb{E}_{{\zeta _{[k]}}}}} {I_k}\left[ {{{\left\| {{z^{k + 1}} - {z^k}} \right\|}^2}} \right]$的估计。

引理3.13 在假设2.1~假设2.3下，对任意k≥1令

$\begin{aligned} & J_k=\left\lceil k^{\frac{1}{4}}\right\rceil, I_k=\min \left(\left\lceil k^{\frac{3}{4}}\right\rceil, M\right), \beta=T^{\frac{1}{4}}, \\ & \alpha_k=\alpha=\frac{T^{-\frac{1}{2}}}{L+G^2+F L+2 L F \rho}=\frac{T^{-\frac{1}{2}}}{C}, \\ & \rho \in\left(0, \frac{1}{2}\right), \rho_k=\frac{\rho}{T I_k} . \end{aligned}$

则对任意T≥1，下列不等式成立:

$\begin{aligned} & \sum\limits_{k=1}^T I_k \mathbb{E}_{\xi_{[k]}}\left[\left\|z^{k+1}-z^k\right\|^2\right] \\ & \leqslant 4 \rho^2\left[\frac{C\left\|x^1-x^*\right\|^2}{2}+\frac{\sigma^2+G^2+8 G^2 F^2 \rho^2}{C}\right] T^{-\frac{7}{4}}+ \\ & 4 \rho^2\left[L D_X^2+\frac{\left\|z^*\right\|^2}{2 \rho}+\frac{2 F^2 G^2}{C}\right] T^{-\frac{5}{4}}+ \\ & 4 \rho^2\left[X_0\left(x^1\right)-W\right] T^{-\frac{4}{5}} . \end{aligned}$

证明 令定理3.1中(x, z)=(x^*, z^*)、引理3.11中x=x^k、引理3.10中(x, z)=(x^*, z^k)，加和可得

$\begin{aligned} \mathbb{E} & {\left[\left.\frac{1}{2 \alpha_k}\left\|x^{k+1}-x^*\right\|^2+\frac{1}{2 \rho_k I_k}\left\|z^{k+1}-z^*\right\|^2 \right\rvert\, \zeta_{[k-1]}\right] } \\ \leqslant & \mathbb{E}\left[\frac{1}{2}\left(\frac{1}{\alpha_k}+2 L\right)\left\|x^k-x^*\right\|^2+\right. \\ & \left.\left.\frac{1}{2 \rho_k I_k}\left\|z^k-z^*\right\|^2 \right\rvert\, \zeta_{[k-1]}\right]+\alpha_k\left(\sigma^2+G^2+\right. \\ & \left.2 \beta^2 F^2 G^2+\frac{2 G^2}{M} \mathbb{E}\left[\left\|z^k\right\|^2 \mid \zeta_{[k-1]}\right]\right)- \\ & \frac{1}{2 \rho_k I_k}\left(\frac{\beta}{\rho_k}-1\right) \mathbb{E}\left[\left\|z^{k+1}-z^k\right\|^2 \mid \zeta_{[k-1]}\right]- \\ & \mathbb{E}\left[\left\langle x^k-x^*, \left(g_0^k+h^k\right)-\left(\nabla f_0\left(x^k\right)+\right.\right.\right. \\ & \left.\left.\left.\nabla_x \Psi\left(x^k, z^k\right)\right)\right\rangle \mid \zeta_{[k-1]}\right]+ \\ & \mathbb{E}\left[\left\langle z^k-z^*, \frac{M}{I_k} e_{I_k} \odot \nabla_z \Psi\left(x^k, z^k\right)-\right.\right. \\ & \left.\left.\nabla_z \Psi\left(x^k, z^k\right)\right\rangle \mid \zeta_{[k-1]}\right]+ \\ & \mathbb{E}\left[\chi_0\left(x^k\right)-\chi_0\left(x^{k+1}\right) \mid \zeta_{[k-1]}\right] . \end{aligned}$

代入g₀^k, h^k的无偏性和引理3.6得

$\begin{aligned} \mathbb{E} & {\left[\left.\frac{1}{2 \alpha_k}\left\|x^{k+1}-x^*\right\|^2+\frac{1}{2 \rho_k I_k}\left\|z^{k+1}-z^*\right\|^2 \right\rvert\, \zeta_{[k-1]}\right] } \\ \leqslant & \mathbb{E}\left[\frac{1}{2}\left(\frac{1}{\alpha_k}+2 L\right)\left\|x^k-x^*\right\|^2+\right. \\ & \left.\left.\frac{1}{2 \rho_k I_k}\left\|z^k-z^*\right\|^2 \right\rvert\, \zeta_{[k-1]}\right]+ \\ & \alpha_k\left(\sigma^2+G^2+2 \beta^2 F^2 G^2+8 G^2 F^2 \rho^2\right)- \\ & \frac{1}{2 \rho_k I_k}\left(\frac{\beta}{\rho_k}-1\right) \mathbb{E}\left[\left\|z^{k+1}-z^k\right\|^2 \mid \zeta_{[k-1]}\right] \end{aligned}$

不等式两端取期望$\mathbb{E}_{\zeta_{[k-1]}}[\cdot]$，求k=1到T的累加和，由设定α_k≡α, $\rho_k I_k \equiv \frac{\rho}{T}$, $\beta=T^{\frac{1}{4}}$得

$\begin{aligned} & \sum\limits_{k=1}^T \frac{T}{2 \rho}\left(\frac{T^{\frac{5}{4}} I_k}{\rho}-1\right) \mathbb{E}_{\zeta_{[k]}}\left[\left\|z^{k+1}-z^k\right\|^2\right] \\ \leqslant & \mathbb{E}_{\zeta_{[r]}}\left[\frac{\left\|x^1-x^*\right\|^2}{2 \alpha}+L \sum\limits_{k=1}^T\left\|x^k-x^*\right\|^2+\right. \\ & \left.\frac{T}{2 \rho}\left\|z^1-z^*\right\|^2\right]+T \alpha\left(\sigma^2+G^2+2 T^{\frac{1}{2}} F^2 G^2+\right. \\ & \left.8 G^2 F^2 \rho^2\right)+\sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\chi_0\left(x^{k+1}\right)-\chi_0\left(x^k\right)\right] \\ \leqslant & {\left[\frac{C\left\|x^1-x^*\right\| 2}{2}+\frac{\sigma^2+G^2+8 G^2 F^2 \rho^2}{C}\right] T^{\frac{1}{2}}+} \\ & {\left[L D_X^2+\frac{z^{* 2}}{2 \rho}+\frac{2 F^2 G^2}{C}\right] T+} \\ & \mathbb{E}_{\zeta_{[T]}}\left[\chi_0\left(x^1\right)-\chi_0\left(x^{T+1}\right)\right] . \end{aligned}$

其中：$D_X<+\infty$。已知$\rho<\frac{1}{2}$，所以$1<\frac{1}{2 \rho} \leqslant\frac{T^{\frac{5}{4}} I_k}{2 \rho}$，因而

$\begin{array}{l} & \sum\limits_{k=1}^T \frac{T^{\frac{5}{4}} I_k}{2 \rho} \mathbb{E}_{\zeta_{[k]}}\left[\left\|z^{k+1}-z^k\right\|^2\right] \\ \leqslant & \sum\limits_{k=1}^T\left(\frac{T^{\frac{5}{4}} I_k}{\rho}-1\right) \mathbb{E}_{\zeta_{[k]}}\left[\left\|z^{k+1}-z^k\right\|^2\right] \\ \leqslant & 2 \rho\left[\frac{C\left\|x^1-x^*\right\|^2}{2}+\frac{\sigma^2+G^2+8 G^2 F^2 \rho^2}{C}\right] T^{-\frac{1}{2}}+ \\ & 2 \rho\left[L D_X^2+\frac{\left\|z^*\right\|^2}{2 \rho}+\frac{2 F^2 G^2}{C}\right]+ \\ & 2 \rho\left[X_0\left(x^1\right)-W\right] . \end{array}$

最后证明在$\mathcal{O}\left(\epsilon^{-8}\right)$次迭代后，算法输出x^R+1在期望意义下满足式(13)。

定理3.3 在假设2.1~假设2.3下，按照引理3.13设定参数α_k, ρ_k, β, I_k。则对任意T≥1，下列等式成立:

$\mathbb{E}_{R, 5_{[r]}}\left[\frac{1}{M} \sum\limits_{i=1}^M\left[f_i\left(x^{R+1}\right)\right]_{+}\right]=\mathcal{O}\left(T^{-\frac{1}{8}}\right) .$

证明 首先，对任意实数$u \in \mathbb{R}_{+}$, $v \in \mathbb{R}$, $[v]_{+} \leqslant|\max \{-u, v\}|$。因此由引理3.1可知，对任意分量i∈[M]以及任意k≥1，成立

$\left[f_i\left(x^{k+1}\right)\right]_{+} \leqslant\left|\max \left\{-\frac{z_i^{k+1}}{\beta}, f_i\left(x^{k+1}\right)\right\}\right|$

由z^k的更新公式(6)，得

$\begin{aligned} & \mathbb{E}\left[ {\frac{1}{M}\left\| {{{\left[ {f\left( {{x^{k + 1}}} \right)} \right]}_ + }} \right\|\left| {{\zeta _{[k - 1]}}} \right.} \right] \\ = & {\left[\left.\mathbb{E}\left[\frac{1}{M} \sum\limits_{i=1}^M\left[f_i\left(x^{k+1}\right)\right]_{+}^2\right]^{\frac{1}{2}}\right|\zeta_{[k-1]}\right] } \\ \leqslant & \mathbb{E}\left[\left.\frac{1}{M}\left[\sum\limits_{i=1}^M\left|\max \left\{-\frac{z_i^{k+1}}{\beta}, f_i\left(x^{k+1}\right)\right\}\right|^2\right]^{\frac{1}{2}}\right|\zeta_{[k-1]}\right] \\ = & \frac{1}{M} E\left[\left.\left(\mathbb{E}\left[\left.\frac{M}{\rho_{k+1}^2 I_{k+1}}\left\|z^{k+2}-z^{k+1}\right\|^2 \right\rvert\, \zeta_{[k]}\right]\right)^{\frac{1}{2}} \right\rvert\, \zeta_{[k-1]}\right] \\ \leqslant & \frac{1}{M}\left(\mathbb{E}\left[\left.\mathbb{E}\left[\left.\frac{M}{\rho_{k+1}^2 I_{k+1}}\left\|z^{k+2}-z^{k+1}\right\|^2 \right\rvert\, \zeta_{[k]}\right] \right\rvert\, \zeta_{[k-1]}\right]\right)^{\frac{1}{2}} \\ = & \frac{1}{M}\left(\mathbb{E}{ }_{\zeta_k, \zeta_{k+1}}\left[\left.\frac{M}{\rho_{k+1}^2 I_{k+1}}\left\|z^{k+2}-z^{k+1}\right\|^2 \right\rvert\, \zeta_{[k-1]}\right]\right)^{\frac{1}{2}} . \end{aligned}$

第2个不等号因为对任意随机变量$u \in \mathbb{R}$, $(\mathbb{E}(u))^2 \leqslant \mathbb{E}\left(u^2\right)$。再次利用$(\mathbb{E}(u))^2 \leqslant \mathbb{E}\left(u^2\right)$，对上述不等式两端取期望$\mathbb{E}_{\zeta_{[k-1]}}$可得

$\begin{aligned} & \mathbb{E}_{\zeta_{[k]}}\left[\frac{1}{M}\left\|\left[f\left(x^{k+1}\right)\right]_{+}\right\|\right] \\ \leqslant & \frac{1}{M} \mathbb{E}_{\zeta_{[k-1]}}\left[\left(\mathbb{E}_{\zeta_k \cdot \zeta_{k+1}}\left[\left.\frac{M}{\rho_{k+1}^2 I_{k+1}}\left\|z^{k+2}-z^{k+1}\right\|^2 \right\rvert\, \zeta_{[k-1]}\right]\right)^{\frac{1}{2}}\right] \\ \leqslant & \frac{1}{M}\left(\mathbb{E}_{\zeta_{[k-1]}}\left[\mathbb{E}_{\zeta_k \cdot \zeta_{k+1}}\left[\left.\frac{M}{\rho_{k+1}^2 I_{k+1}}\left\|z^{k+2}-z^{k+1}\right\|^2 \right\rvert\, \zeta_{[k-1]}\right]\right]\right)^{\frac{1}{2}} \\ = & \frac{1}{M}\left(\mathbb{E}_{\zeta_{[k+1]}}\left[\frac{M}{\rho_{k+1}^2 I_{k+1}}\left\|z^{k+2}-z^{k+1}\right\|^2\right]\right)^{\frac{1}{2}} . \end{aligned}$

因为$\sqrt{.}$是凹函数，且对任意$z \in \mathbb{R}^M$, ‖z‖₁≤M‖z‖，所以

$\begin{array}{l} \mathbb{E}_{R, \zeta_{[T]}}\left[\frac{1}{M}\left\|\left[f\left(x^{R+1}\right)\right]_{+}\right\|_1\right] \\ \leqslant \sqrt{M} \mathbb{E}_{R, \zeta_{[T]}}\left[\frac{1}{M}\left\|\left[f\left(x^{R+1}\right)\right]_{+}\right\|\right] \\ =\frac{\sqrt{M}}{T} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\frac{1}{M}\left\|\left[f\left(x^{k+1}\right)\right]_{+}\right\|\right] \\ \leqslant \frac{\sqrt{M}}{M} \frac{1}{T} \sum\limits_{k=1}^T\left(\mathbb{E}_{\zeta_{[k+1]}}\left[\frac{M}{\rho_{k+1}^2 I_{k+1}}\left\|z^{k+2}-z^{k+1}\right\|^2\right]\right)^{\frac{1}{2}}\\ \leqslant \frac{\sqrt{M}}{M}\left(\frac{1}{T} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k+1]}}\left[\frac{M}{\rho_{k+1}^2 I_{k+1}}\left\|z^{k+2}-z^{k+1}\right\|^2\right]\right)^{\frac{1}{2}} \\ =\left(\frac{1}{T} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k+1]}}\left[\frac{T^2 I_{k+1}}{\rho^2}\left\|z^{k+2}-z^{k+1}\right\|^2\right]\right)^{\frac{1}{2}} \end{array}$

第2个等号代入了步长设定$\rho_k=\frac{\rho}{T I_k}$。而根据引理3.13，可以得到

$\begin{aligned} & \frac{1}{T} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k+1]}}\left[\frac{T^2 I_{k+1}}{\rho^2}\left\|z^{k+2}-z^{k+1}\right\|^2\right] \\ \leqslant & \frac{1}{T} \sum\limits_{k=1}^{T+1} \mathbb{E}_{\zeta_{[k]}}\left[\frac{T^2 I_k}{\rho^2}\left\|z^{k+1}-z^k\right\|^2\right] \\ \leqslant & \frac{T}{\rho^2} \times 4 \rho^2\left[\frac{C\left\|x^1-x^*\right\|^2}{2}+\right. \\ & \left.\frac{\sigma^2+G^2+8 G^2 F^2 \rho^2}{C}\right](T+1)^{-\frac{7}{4}}+ \\ & \frac{T}{\rho^2} \times 4 \rho^2\left[L D_X^2+\frac{\left\|z^*\right\|^2}{2 \rho}+\frac{2 F^2 G^2}{C}\right](T+1)^{-\frac{5}{4}}+ \\ & \frac{T}{\rho^2} \times 4 \rho^2\left[\chi_0\left(x^1\right)-W\right](T+1)^{-\frac{5}{4}} \\ \leqslant & 4 T^{-\frac{3}{4}}\left[\frac{C\left\|x^1-x^*\right\|^2}{2}+\frac{\sigma^2+G^2+8 G^2 F^2 \rho^2}{C}\right]+ \\ & 4 T^{-\frac{1}{4}}\left[L D_X^2+\frac{\left\|z^*\right\|^2}{2 \rho}+\frac{2 F^2 G^2}{C}\right]+ \\ & 4 T^{-\frac{1}{4}}\left[\chi_0\left(x^1\right)-W\right] . \end{aligned}$

结合上述2组不等式，利用对任意a, b≥0, $\sqrt{a+b} \leqslant \sqrt{a}+\sqrt{b}$，可推知定理成立。□

3.4 互补松弛条件

这一节将证明，在$\mathcal{O}\left(\epsilon^{-4}\right)$次迭代后，点(22)满足式(14)。

定理3.4 在定理3.1的条件下，对任意T≥1，下列不等式成立：

$\begin{gathered} \mathbb{E}_{R, \zeta_{[T]}}\left[\frac{1}{M} \sum\limits_{i=1}^M\left(\beta f_i\left(x^{R+1}\right)+z_i^{R+1}\right)_{+}\left[f_i\left(x^{R+1}\right)\right]_{-}\right] \\ =\mathcal{O}\left(T^{-\frac{1}{4}}\right) . \end{gathered}$

证明 由定义可得

$\begin{aligned} & \frac{\left|z_i^k\right|^2}{4 \beta} \geqslant\left(\beta f_i\left(x^k\right)+z_i^k\right)_{+}\left[f_i\left(x^k\right)\right]- \\ & = \begin{cases}-\left(\beta f_i\left(x^k\right)+z_i^k\right) f_i\left(x^k\right), & 0>f_i\left(x^k\right) \geqslant-\frac{z_i^k}{\beta}, \\ 0, & \text { else. }\end{cases} \end{aligned}$

其中不等式利用了$-u(b u+a) \leqslant \frac{a^2}{4 b}$, $\forall u \in \mathbb{R}$,$b \in \mathbb{R}_{++}$。类似于引理3.3，可得对任意分量i∈[M]以及任意k∈[T+1]，$\left|z_i^k\right| \leqslant F \rho$。进而可得

$\begin{gathered} \sum\limits_{i=1}^M \mathbb{E}_{\zeta_{[k-1]}}\left[\left(\beta f_i\left(x^k\right)+z_i^k\right)+\left[f_i\left(x^k\right)\right]_{-}\right] \\ \leqslant \sum\limits_{i=1}^M \mathbb{E}_{\zeta_{[k-1]}}\left[\frac{\left|z_i^k\right|^2}{4 \beta}\right] \leqslant \frac{M F^2 \rho^2}{4 \beta} \end{gathered}$

因此，根据$\beta=T^{\frac{1}{4}}$

$\begin{aligned} & \mathbb{E}_{R, \zeta_{[T]}}\left[\frac{1}{M} \sum\limits_{i=1}^M\left(\beta f_i\left(x^{R+1}\right)+z_i^{R+1}\right)+\left[f_i\left(x^{R+1}\right)\right]_{-}\right] \\ = & \frac{1}{T} \sum\limits_{k=1}^T \mathbb{E}_{\zeta_{[k]}}\left[\frac { 1 } { M } \sum _ { i = 1 } ^ { M } \left(\beta f_i\left(x^{k+1}\right)+\right.\right. \\ & \left.\left.z_i^{k+1}\right)_{+}\left[f_i\left(x^{k+1}\right)\right]_{-}\right] \\ \leqslant & \frac{1}{T} \sum\limits_{k=1}^T \frac{F^2 \rho^2}{4 \beta}=\frac{F^2 \rho^2}{4 \beta}=\mathcal{O}\left(T^{-\frac{1}{4}}\right) . \end{aligned}$

定理得证。□

基于定理3.1、定理3.3和定理3.4，可以得到算法CSALM的迭代复杂度如下。

引理3.14 在引理3.13的条件下，对任意精度$\epsilon$∈(0, 1)，算法CSALM在迭代$T=\mathcal{O}\left(\epsilon^{-8}\right)$次后，点(22)是问题(1)的$\epsilon$-KKT点

证明 利用定理3.1、定理3.3、定理3.4和$T=\mathcal{O}\left(\epsilon^{-8}\right)$，可得到

$\begin{aligned} & \mathbb{E}_{R, \zeta_{[T]}}\left[\mathbf { d } \left(d \nabla f_0\left(x^{R+1}\right)+\partial \chi_0\left(x^{R+1}\right)+\right.\right. \\ & \left.\left.\quad \sum\limits_{i=1}^M z_i \nabla f_i\left(x^{R+1}\right)+\mathcal{N}_X\left(x^{R+1}\right), 0\right)\right] \leqslant \epsilon, \\ & \mathbb{E}_{R, \zeta_{[T]}}\left[\frac{1}{M} \sum\limits_{i=1}^M\left[f_i\left(x^{R+1}\right)\right]_{+}\right] \leqslant \epsilon, \\ & \mathbb{E}_{R, \zeta_{[T]}}\left[\sum\limits_{i=1}^M z_i\left[f_i\left(x^{R+1}\right)\right]_{-}\right] \leqslant \epsilon^2 \leqslant \epsilon . \end{aligned}$

其中：$z=\frac{1}{M}\left(\beta f\left(x^{R+1}\right)+z^{R+1}\right)_{+} \in \mathbb{R}_{+}^M$, f=(f₁, …, f_M)。对照定义3.1可知结论成立。□

4 数值实验

为检验算法的实际表现，本节测试CSALM算法在多分类NPC问题(multi-class neyman pearson classification, mNPC) 上的数值表现。mNPC旨在最小化一类的分类损失，同时控制其他类的分类损失。设训练集有M个类，每类所有样本记为$\mathcal{D}_m$，每类对应参数$x_m \in \mathbb{R}^d$, m=1, …, M，对未知类别的ξ，预测分类的方式为$\arg \max \limits_m x_m^T \xi$, m=1, 2, …, M，若要第m类预测精度较高，则要求$x_m^T \xi-x_l^T \xi, \forall m \neq l, \xi \in \mathcal{D}_m$的值尽可能大。因为所有类别同时极大化是矛盾的，所以mNPC问题取一样本类为目标，其他类则构建约束，以非降函数ϕ作为损失，再加入L1正则项λ‖x‖₁，最终带正则的mNPC问题表示为

$\begin{gathered} \min\nolimits_{\| \mathbf{x}_m \mid \leqslant \lambda, m=1, \cdots, M} \frac{1}{\left|\mathcal{D}_1\right|} \sum\limits_{l>1} \sum\limits_{\xi \in \mathcal{D}_1} \phi\left(\boldsymbol{x}_1^{\mathrm{T}} \xi-\boldsymbol{x}_l^{\mathrm{T}} \xi\right)+ \\ \lambda\|x\|_1, \\ \text { s. t. } \frac{1}{\left|\mathcal{D}_m\right|} \sum\limits_{l \neq m} \sum\limits_{\xi \in \mathcal{D}_m} \phi\left(\boldsymbol{x}_m^{\mathrm{T}} \xi-\boldsymbol{x}_l^{\mathrm{T}} \xi\right) \leqslant r_m, \\ m=2, 3, \cdots, M . \end{gathered}$

其中：r_m是其他约束的控制损失。

本文的问题设定是约束个数M极大，但常见的机器学习数据集类别数通常较少，而类别较多的数据集的单类规模过大如imagenet，所以使用LIBSVM的数据集mnist、covtype作为测试数据集，数据集的类数分别为M=10、M=7。mnist数据集使用数字1的类别作为目标，covtype数据集使用标签为1的类别作为目标。所有数据集均使用ϕ(x)=1/(1+exp(x))作为损失函数，并取r_m=0.5(M-1), ∀m=2, …, M作为误差界。

本文使用ICPP算法^[12]作为对比算法。mNPC问题的目标函数和约束函数均可视作离散的期望函数，对目标和约束均为期望函数的优化问题，如果对目标和约束都采用随机信息，ICPP算法能以$\mathcal{O}\left(\epsilon^{-6}\right)$的迭代复杂度求解，若约束是一般函数无期望函数结构，在使用随机目标信息和确定约束信息时，ICPP算法能以$\mathcal{O}\left(\epsilon^{-4}\right)$)的迭代复杂度求解。因为本文的研究问题设定约束为一般函数，故将与采用随机目标信息、确定约束信息的ICPP算法对比。

实验的具体设定因数据集和算法的理论设定有所不同。执行CSALM算法时，因为M极小，所以实际执行时，每次迭代使用的约束数量一般取1~3，而非设定的按迭代次数增长$I_k=\min \left(\left\lceil k^{3 / 4}\right\rceil, M\right)$，另外实际使用的算法步长α_k为下降步长而非固定步长，这是为了算法执行后期的数值稳定。具体而言，对mnist数据集：CSALM算法的设定为迭代次数T=500，步长α_k=0.05/k^1/4，罚参β=5，正则项λ=0.05，乘子步长ρ=0.1，目标函数的批量大小$J_k=\left\lceil k^{1 / 4}\right\rceil$，约束个数I_k=1；对covtype数据集：迭代次数T=1 000，步长α_k=0.01/k^1/4，罚参β=50，正则项λ=0.01，乘子步长ρ=0.001，目标函数的批量大小$J_k=\left\lceil k^{1 / 4}\right\rceil$，约束个数I_k=1。

执行ICPP时，算法设定不变，循环输出略有不同。ICPP算法是内外循环算法，在原算法框架中，内循环的输出点是所有内循环点的加权平均，实现时直接采用内循环的最后一次迭代点作为循环输出。具体的算法设定上，对mnist数据集：外循环K=10，内循环T=26，正则项λ=0.05，每次均使用所有约束的信息M=9，t₀=2，强凸项参数μ₀=1.5，连续性参数M_f=M/2；对covtype数据集：外循环K=10，内循环T=45，正则项λ=0.05，每次均使用所有约束的信息M=6，t₀=2，强凸项参数μ₀=1.5，连续性参数M_f=M/2。

实验前，数据集均进行了预处理。对mnist，因为样本是灰度图像，特征全为0~255的正整数，故所有特征按特征归一化到[0, 1]区间；对covtype：前10种特征中除第5种特征外按特征归一化到[0, 1]区间，第5种特征因为含负样本故归一化到[-1, 1]区间，其他特征不变。实验时对所有算法和数据集，算法乘子初始化为0，实验的初始点均为x₀=0，所有实验均运行在Windows 10，CPU intel i7-11700，内存128 GB的机器上，matlab版本为R2022a。CSALM和ICPP算法均在mnist、covtype数据集上各运行了10次，取数值平均后实验结果如下。

所有实验中计算时间单位为s，使用tic、toc工具测量。在函数损失实验结果中，函数指ϕ(x)不包括正则项，在不可行性实验结果中，不可行性是所有违反约束的约束违反值的算数平均。约束不可行性数据有处理，因为在对数图中0无法表示，为有效显示，将mnist的不可行性结果中小于10^-7的值替换为10^-7，将ICPP的不可行性结果中小于10^-7的结果替换为10^-7。ICPP算法的数值结果仅记录外循环点。

由图 1~图 4的结果可以看出，主要特点是CSALM下降快，ICPP不可行性低。对mnist数据集，函数值方面CSALM算法初期下降显著快于ICPP，但最终值二者接近，不可行性方面CSALM和ICPP整体接近且均有可行点出现，但整个过程CSALM的波动较大，原因可能是每次只抽样1个约束太少。对covtype数据集，CSALM显著快于ICPP，约束不可行性则显著高于ICPP，且两算法均没有可行点，原因可能是函数值快速下降和约束不可行性低值稳定在本次实验里是相背的要求，而ICPP在covtype上的参数设置得偏向于控制不可行性，最终导致ICPP下降慢于CSALM。

5 结论

针对大规模约束的非凸非光滑问题，本文提出一个基于增广拉格朗日的随机算法，该算法每步使用随机信息进行迭代更新，使得计算量与问题规模解耦。在约束凸光滑且Lipschitz光滑的假设下，证明该算法可从任意初始可行点出发找到$\epsilon$-KKT近似点。多分类Neyman-Pearson问题的数值实验表明该算法可以在实际问题中获得优秀的数值表现。