前言

title: Lifted Proximal Operator Machines

论文百度云链接: https://pan.baidu.com/s/1J2hdhLMp_xW6QcmWRi1-zA
提取码: ersk

提升近端算子机，将非凸问题进行凸化的利器，已用于分析DNN的网络和训练策略等~

摘要

我们提出了一种用于训练前馈神经网络的新优化方法，通过将激活函数重写为等效的近端算子，然后将近端算子以正则项添加到目标函数来近似前馈神经网络，因此称本文提出的方法为提升近端算子机（LPOM）。

LPOM 在所有权重或者激活层中都是块多凸的，这允许我们使用块坐标下降并行更新逐层权重和激活。最值得注意的是，我们只使用激活函数本身，而不是它的导数，从而避免基于梯度方法中的梯度消失或爆炸问题。所以我们的方法适用于各种非递减 Lipschitz 连续激活函数，而且可以是饱和的和不可微的。 LPOM 不比逐层激活需要更多的辅助变量，因此与 SGD方法使用的内存量大致相同。我们也证明了逐层更新权重和激活的收敛性，数据集 MNIST 和 CIFAR-10 上的实验证明了 LPOM 的优势。

一，介绍

前馈深度神经网络 (DNN) 是完全级联的连接层，没有反馈连接。在最近年，随着硬件和数据集规模的进步，前馈 DNN 已成为许多任务的标准，例如图像识别, 语音识别，自然语言理解，并作为Go游戏学习系统的块。

几十年来，训练 DNN 是通过优化一个高度非凸且嵌套的网络权重函数来完成的。训练 DNN 的主要方法是随机梯度下降(SGD)，其有效性由DNN 在各种领域的实际应用中已经得到证明。最近，SGD 的许多变体已被提出，它使用自适应学习率和动量项，例如，Nesterov momentum，AdaGrad，RMSProp 和 Adam。 SGD 及其变体使用少量训练样本来估计全局梯度，使得每次迭代计算复杂度小。此外，估计的梯度是有噪声的，有助于鞍点逃逸。然而，他们也有一些缺点。一个主要问题是梯度消失或爆炸问题，即很多层的梯度指数级的减少或增加。这会导致缓慢或不稳定的收敛，尤其是在非常深的网络中更甚。这个缺陷可以通过使用非饱和激活函数来消除，例如整流线性单元 (ReLU) ，以及网络结构的修改，例如 ResNet。但是，根本问题依然存在。此外，他们无法直接处理不可微的激活函数（例如，二值化神经网络）并且不允许跨层的并行权重更新。有关更多SGD限制的讨论请参考taylor2016training。

SGD 的缺点激发了对训练 DNN 的替代方法研究。最近在训练一个前馈神经网络被表述为带约束的优化问题，其中网络激活作为辅助变量引入，网络配置由分层约束保证。它打破了嵌套函数之间的依赖关系，转变为等式约束，因此可使用许多标准优化方法。许多工作研究了这种方法，不同之处在于如何处理等式约束。carreira2014distributed 将等式约束近似为二次正则项，交替优化网络权重和激活。zeng2018global 提出每层多一个辅助变量块，也通过二次正则项近似等式约束。受乘法器交替方向法启发(ADMM)，taylor2016training等使用了增广拉格朗日方法获得等式约束的精确增强。然而，这两种方法涉及拉格朗日乘数和非线性约束，因此对内存的要求更高，更难优化。ReLU 激活函数等同于一个简单的带约束的凸优化问题，受这一事实的启发，zhang2017convergent 放宽了非线性约束作为正则项，对网络架构和 ReLU 激活函数进行编码。因此，非线性约束不复存在。然而，他们的方法仅限于 ReLU 函数，不适用于其他激活函数。沿着这个思路，askari2018lifted 考虑了更多复杂的凸优化问题并讨论了几种非递减激活函数。然而，他们的方法对权重和激活的更新仍然限于 ReLU 函数。所以他们的方法不能胜过 SGD，只能服务于为 SGD 生成良好的初始化。其实我们已经发现了他们的公式不正确（参见“LPOM 的优势”小节）。

本文做出了以下贡献：

我们提出了一种新的公式来训练前馈 DNN，我们称之为提升近端算子机 (LPOM)。 LPOM 是块多凸的，即当剩余的权重和激活是固定时，权重和激活的问题是凸的。相比之下，几乎现有所有的 DNN 训练方法都没有这样的性质。这大大方便了DNN的训练。
相应地，我们应用块坐标下降 (BCD) 来求解 LPOM，其中逐层权重和激活可以并行更新。最值得注意的是，逐层权重或激活的更新仅利用激活函数本身，而不是其导数，从而避免了基于梯度的训练方法中的梯度消失或爆炸问题。此外，LPOM 不需要比逐层激活更多的辅助变量，因此其内存成本接近 SGD。我们进一步证明更新逐层权重或激活的迭代是收敛的。
由于只有激活函数本身参与计算，LPOM 能够处理一般的非递减 Lipschitz 连续激活函数，可以是饱和的（例如 sigmoid 和 tanh）和不可微的（例如 ReLU 和 leaky ReLU）。因此 LPOM 成功地克服了使用大多数现有激活函数时的计算困难。

我们在全连接的 DNN 上实施 LPOM 并在基准数据集MNIST 和 CIFAR-10 中对其进行测试，并获得了满意的结果。在卷积神经网络 (CNN)中，因为我们还没有重新制定池化和跳跃连接，将 LPOM 在 CNN 上的实施留作未来的工作。请注意，现有基于非梯度的方法也首先关注全连接的 DNN。

二，相关工作

在标准的前馈神经网络中，执行分类任务时训练 $n$ 层神经网络的优化问题可以写做：

$\min_{W^i}\ell(\phi(W^{n-1}\phi(\cdots \phi(W^2\phi(W^1X^1)))),L) \tag{1}\label{eq1}$

其中 $X^1 \in \mathbb{R}^{n_1\times m}$ 是批训练样本，$L \in \mathbb{R}^{c\times m}$ 表示对应标签，$n_1$ 是训练样本的维度，$m$ 是批量大小，$c$ 是类的数量，$\{W^i\}_{i=1}^{n-1}$ 是要学习的权重，为简单起见，省略了偏差，$\phi(\cdot)$ 是逐元素激活函数（例如，sigmoid、tanh 和 ReLU)，而 ${\ell}(\cdot,\cdot)$ 是损失函数（例如，最小二乘误差或交叉熵误差）。这里的神经网络被定义为嵌套函数，其中第一层神经网络的函数是$\phi(W^1X^1)$，第 $i$ 层($i=2,\cdots,n$) 函数的形式为 $\phi(W^iX)$，并且 $X$ 是第 $(i-1)$ 层函数的输出。优化 \eqref{eq1} 的常用方法是 SGD，即计算梯度，而网络的所有权重更新使用反向传播，具体通过梯度下降来更新权重。

通过引入逐层激活作为辅助变量块，神经网络的训练可以等价地公式化为等式约束优化问题:

$\begin{align*} &\min_{\{W^i \},\{X^i\} }\ell(X^n,L)\\ &s.t. X^i=\phi(W^{i-1}X^{i-1}),i=2,3\cdots n \end{align*} \tag{2}\label{eq2}$

其中 $X^i$ 是第 $i$ 层的激活，其他层符号与 \eqref{eq1} 中的相同。

问题 \eqref{eq2} 中的约束确保辅助变量 $\{X^i\}_{i=2}^{n}$ 完全匹配网络。与问题\eqref{eq1}相比，问题\eqref{eq2}是有限制的。但由于目标函数没有嵌套，因此更简单，这样的等价表达可能会带来更灵活的优化方法。注意当使用 SGD 解决问题\eqref{eq1}时，它
实际上也是隐含地对问题\eqref{eq2}求解，但需要记录激活 $\{X^i\}_{i=2}^{n}$ 以便计算梯度。

受二次正则方法的启发，carreira2014distributed 提出了辅助坐标（MAC）的方法来求解问题\eqref{eq2}。 MAC使用
二次正则项近似等式约束，并试图求解以下问题：

$\min_{\{W^i\},\{X^i\}}\ell(X^n,L)+\frac{\mu}{2}\sum\limits^n_{i=2}\|X^i-\phi(W^{i-1}X^{i-1})\|^2_F \tag{3}$

其中 $\mu>0$ 是控制约束权重的常数，$|\cdot|_F$ 是 Frobenius 范数。zeng2018global 用新的辅助变量解耦了 \eqref{eq2} 中的非线性激活函数：

$\begin{align*} &\min_{\{W^i \},\{X^i\},\{U^i\}}\ell(X^n,L)\\ &s.t. U^i=W^{i-1}X^{i-1},X^i=\phi(U^i),i=2,3\cdots n \end{align*} \tag{4}\label{eq4}$

这称为 3-splitting 公式。相应地，问题\eqref{eq2} 是 2-splitting 公式。对问题\eqref{eq4}同样适用 MAC 方法，而不是直接求解，可得出他们优化了下面的问题：

$\begin{align*} &\min_{\{W^i\},\{X^i\},\{U^i\}}\ell(X^n,L)\\ &+\frac{\mu}{2}\sum\limits^n_{i=2}(\|U^i-W^{i-1}X^{i-1}\|^2_F+\|X^i-\phi(U^i)\|^2_F) \end{align*} \tag{5}$

他们采用 BCD 方法来解决上述问题。

taylor2016training 也考虑求解问题\eqref{eq4}。受 ADMM启发，他们在输出层添加了拉格朗日乘子以实现对输出层的等式约束，产生下列问题：

$\begin{align*} &\min_{\{W^i\},\{X^i\},\{U^i\},M}\ell(U^n,L)+\frac{\beta}{2}\|U^n-W^{n-1}X^{n-1}+M\|^2_F\\ &+\sum\limits^{n-1}_{i=2}\frac{\mu_i}{2}(\|U^i-W^{i-1}X^{i-1}\|^2_F+\|X^i-\phi(U^i)\|^2_F) \end{align*} \tag{6}\label{eq6}$

其中 $M$ 是拉格朗日乘子，$\beta>0$ 和 $\mu_i>0$是常数。注意输出层上没有激活函数。所以 \eqref{eq6} 是自适应启发式的 ADMM 算法。 zhang2016efficient 采用了类似的技术，但使用了不同的变量拆分方案：

$\begin{align*} &\min_{\{W^i\},\{X^i\},\{U^i\}}\ell(X^n,L) \\ &s.t. U^{i-1}=X^{i-1},X^i=\phi(W^{i-1}U^{i-1}),i=2,3\cdots n \end{align*} \tag{7}\label{eq7}$

尽管有非线性等式约束，但 ADMM 并不旨在处理该类问题，他们为\eqref{eq7}中的每个约束添加了一个拉格朗日乘数。然后增强的拉格朗日问题如下所示：

$\begin{align*} &\min_{\{W^i\},\{X^i\},\{U^i\},\{A^i\},\{B^i\}}\ell(X^n,L)\\ &+\frac{\mu}{2}\sum\limits^n_{i=2}(\|U^{i-1}-X^{i-1}+A^{i-1}\|^2_F\\ &+\|X^i-\phi(W^{i-1}U^{i-1})+B^{i-1}\|^2_F) \end{align*} \tag{8}$

其中 $A^i$ 和 $B^i$ 是拉格朗日乘子。

与原始应用正则方法和 ADMM 不同，zhang2017convergent 将 ReLU 激活函数解释为一个简单的平滑凸优化问题。即，问题\eqref{eq2} 中的等式约束使用 ReLU 激活函数可以改写为凸优化问题：

$\begin{align*} X^i&=\phi(W^{i-1}X^{i-1})\\ &=max(W^{i-1}X^{i-1},\textbf{0})\\ &=\mathop{argmin}_{U^i\geq 0}\|U^i-W^{i-1}X^{i-1}\|^2_F \end{align*} \tag{9}$

其中 $\textbf{0}$ 是具有适当大小的零矩阵。基于这个观察，他们用以下方式近似激活函数为 ReLU 的问题：

$\begin{align*} &\min_{\{W^i\},\{X^i\}}\ell(X^n,L)+\sum\limits^n_{i=2}\frac{\mu_i}{2}\|X^i-W^{i-1}X^{i-1}\|^2_F\\ &s.t.X^i\geq \textbf{0},i=2,3\cdots n \end{align*} \tag{10}\label{eq10}$

其中正则项对网络结构和激活函数都进行了编码。与基于 MAC 和 ADMM 的方法不同，它确实不包括非线性激活。此外，\eqref{eq10}的主要优势是该问题是块多凸的，即，每个变量块变化时其余的块是固定的。他们提出了一种新的 BCD 方法来求解这个问题，而且经验性的证明了在Caffe框架下基于 SGD 方法ADMM方法的优先级。askari2018lifted 等继承了同样的想法，通过引入更复杂的凸最小化问题，他们可以处理更一般的激活函数，例如 sigmoid、leaky ReLU 和正弦函数等。

三，提升近端算子

在本节中，我们描述了 LPOM 的基本思想及其相对于现有 DNN 训练方法的优势。跟 zhang2017convergent 和 askari2018lifted 一样，LPOM 首先将\eqref{eq2} 中的激活函数表示为凸最小化问题。但是，我们希望这种表示不应仅限于特定激活函数，而且我们希望\eqref{eq2}中的等式约束满足LPOM的KKT条件。

3.1 用近端算子进行重构

我们假设激活函数 $\phi$ 是非递减的，那么$\phi^{-1}(x)=\{y|x=\phi(y)\}$是一个凸集，$\phi^{-1}(x)$ 是 $\{y\}$ 单例当且仅当 $\phi$ 在 $\phi(y)$ 处是严格增加的。我们要构建一个目标函数 $h(x,y)$，由 $y$ 参数化，使得它的最小值正好是 $x=\phi(y)$。因此，我们可以通过最小化 $h(x,y)$ 替换约束 $x=\phi(y)$ ，可以将约束作为正则添加到DNN损失中。

优化问题更新变量的基本操作有两种：梯度更新和近端算子。我们正在构造的优化问题和近端算子如下所示：

$\textrm{prox}_f(y)=\mathop{argmin}_xf(x)+\frac{1}{2}(x-y)^2 \tag{11}\label{eq11}$

我们考虑使用近端算子来构造优化问题。定义

$f(x)=\int^x_0(\phi^{-1}(y)-y)dy$

注意 $f(x)$ 定义明确，即使 $\phi^{-1}(y)$ 对于某些介于 0 和 $x$ 之间的 $y$ 来说不是唯一的。无论如何，$\phi^{-1}$、$f$ 和 $g$（稍后定义）不会显式用于我们的计算。很容易证明问题\eqref{eq11}的优化条件是 $0\in (\phi^{-1}(x)-x) + (x-y)$。所以\eqref{eq11} 的解正好是 $x=\phi(y)$。

请注意 $f(x)$ 是单位变量函数。对于矩阵 $X=(X_{kl})$，我们定义$f(X)=(f(X_{kl}))$。然后
以下最小化问题的优化性条件：

$\mathop{argmin}_{X^i}\mathbf{1}^\top f(X^i)\mathbf{1}+\frac{1}{2}\|X^i-W^{i-1}X^{i-1}\|^2_F \tag{12}\label{eq12}$

其中 $\mathbf{1}$ 是全为1的列向量，是

$\mathbf{0}\in\phi^{-1}(X^i)-W^{i-1}X^{i-1} \tag{13}$

其中 $\phi^{-1}(X^i)$ 也是按元素定义的。所以
\eqref{eq12} 的优化解是

$X^i=\phi(W^{i-1}X^{i-1}) \tag{14}\label{eq14}$

这正是问题\eqref{eq2} 中的约束。所以我们自然地将问题\eqref{eq2} 近似为：

$\begin{align*} &\min_{\{W^i\},\{X^i\}}\ell(X^n,L)\\ &+\sum\limits^n_{i=2}\mu_i\bigg (\mathbf{1}^\top f(X^i)\mathbf{1}+\frac{1}{2}\|X^i-W^{i-1}X^{i-1}\|^2_F \bigg) \end{align*} \tag{15}$

然而，$\{X^i\}_{i=2}^{n-1}$ 的优化条件是：

$\begin{align*} \mathbf{0}\in &\mu_i(\phi^{-1}(X^i)-W^{i-1}X^{i-1})\\ &+\mu_{i+1}(W^i)^\top (W^iX^i-X^{i+1}),i=2\cdots, n-1 \end{align*} \tag{16}\label{eq16}$

我们可以清楚地看到问题\eqref{eq2}的等式约束\eqref{eq14}不满足以上条件。

为了使等式约束 \eqref{eq14}满足逼近问题的最优性条件，我们需要将 \eqref{eq16} 修改为

$\begin{align*} \mathbf{0}\in &\mu_i(\phi^{-1}(X^i)-W^{i-1}X^{i-1})\\ &+\mu_{i+1}(W^i)^\top (\phi(W^iX^i)-X^{i+1}),i=2\cdots, n-1 \end{align*} \tag{17}\label{eq17}$

这对应于以下问题：

$\begin{align*} &\min_{\{W^i\},\{X^i\}}\ell(X^n,L)+\sum\limits^n_{i=2}\mu_i\bigg (\mathbf{1}^\top f(X^i)\mathbf{1}\\ &+\mathbf{1}^\top g(W^{i-1}X^{i-1})\mathbf{1} +\frac{1}{2}\|X^i-W^{i-1}X^{i-1}\|^2_F \bigg) \end{align*} \tag{18}\label{eq18}$

其中

$\int^x_0(\phi(y)-y)dy$

$g(X)$ 是在矩阵 $X$ 逐元素定义的， $f(x)$ 和 $g(x)$的一些有代表性的激活函数显示在表1。 \eqref{eq18} 是我们提出的 LPOM ，其中强调下 $g$ 的引入非常重要且不明显。

3.2 LPOM优势

将 \eqref{eq18} 中 LPOM 的目标函数表示为 $F(W,X)$。那么我们有下面的定理：

定理1
假设 $\ell(X^n, L)$ 在 $X^n$ 中是凸的并且 $\phi$ 是
非递减的。那么 $F(W,X)$ 是块多凸，也就是，如果所有其他变量块都是固定的，每个 $X^i$ 和 $W^i$ 都是凸的。

证明：
$F(W,X)$ 可以简化为

$\begin{align*} &F(W,X)=\ell(X^n,L)+\sum\limits^n_{i=2}\mu_i\bigg (\mathbf{1}^\top \tilde{f}(X^i)\mathbf{1}\\ &+\mathbf{1}^\top \tilde{g}(W^{i-1}X^{i-1})\mathbf{1} +\langle X^i,W^{i-1}X^{i-1}\rangle \bigg) \end{align*} \tag{19}$

其中 $\tilde{f}(x)=\int_0^x \phi^{-1}(y) dy$ 和 $\tilde{g}(x)=\int_0^x \phi(y) dy$。因为 $\phi$ 和 $\phi^{-1}$ 是非递减的，所以 $\tilde{f}(x)$ 和 $\tilde{g}(x)$ 是凸的。很容易验证 $\mathbf{1}^\top\tilde{g}(W^{i-1}!X^{i-1})\mathbf{1}$ 当 $W^{i-1}$ 固定时在 $X^{i-1}$ 中是凸的，当 $X^{i-1}$ 固定时在 $W^{i-1}$ 中是凸的。$F(W,X)$ 中的剩余项 $\langle X^{i},W^{i-1}X^{i-1}\rangle$ 当其他两个块固定时，在一个块中是线性的。证明完成。

由于子问题的凸性，定理1允许使用高效的 BCD 算法求解 LPOM，并保证可以得到更新 $X^i$ 和 $W^i$ 的最佳解决方案。相反，正则项方法和基于 ADMM 的方法中的子问题都是非凸的。

与基于 ADMM 的方法相比，LPOM 除了 $\{X^i\}_{i=2}^{n}$ 不需要拉格朗日乘子和更多的辅助变量。此外，我们还设计了精致的算法，这样求解 LPOM 也无需额外的变量。所以 LPOM 的变量数比基于 ADMM 的方法少，因此大大节省了内存。实际上，它的内存成本接近于 SGD。

与正则项方法相比，LPOM 的优化条件更简单。例如，LPOM 中的 $\{X^i\}_{i=2}^{n-1}$ 和 $\{W^i\}_{i=1}^{n-1}$ 优化条件是 \eqref{eq17} 和

$(\phi(W^iX^i)-X^{i+1})(X^i)^\top\!=0,\; i=1,2\cdots n-1 \tag{20}$

而那些用于 MAC 的优化条件是

$\begin{align*} &(X^i-\phi(W^{i-1}X^{i-1}))\\ &+(W^i)^\top[(\phi(W^iX^i)-X^{i+1})\circ\phi^{'}(W^iX^i)]=\mathbf{0}\\ &i=2,\cdots n-1 \end{align*} \tag{21}$

和

$\begin{align*} [(\phi(W^iX^i)-X^{i+1})\circ\phi^{'}(W^iX^i)](X^i)^\top=\mathbf{0},i=1,\cdots n-1 \end{align*} \tag{22}$

其中 $\circ$ 表示逐元素乘法。我们可以看到 MAC 的优化条件有额外的 $\phi’(W^iX^i)$，这是非线性的。zeng2018global 的优化条件可以在补充材料中找到，他们也还有一个额外的 $\phi’(U^i)$。这可能意味着 MAC 和 zeng2018global 的解集更复杂，更大。所以LPOM 可能更容易找到良好解决方案。

与凸优化重构方法相比，LPOM 可处理更一般的激活函数。注意 zhang2017convergent 只考虑了 ReLU。虽然 askari2018lifted 声称他们的公式可以处理一般的激活函数，其求解方法还是仅限于 ReLU。此外 askari2018lifted 关于$\{X^i\}_{i=2}^{n-1}$ 和 $\{W^i\}_{i=1}^{n-1}$的优化条件推导是有误的，也就是：

$\begin{align*} \mathrm{0}\in&\mu_i(\phi^{-1}(X^i)-W^{i-1}X^{i-1})-\mu_{i+1}(W^i)^\top X^{i+1}\\ &i=2,\dots n-1 \end{align*}$

相应地，$X^{i+1}(X^i)^\top=\mathbf{0},\,i=1,\cdots,n-1,$，很明显，等式约束\eqref{eq14} 不满足以上条件。此外，不知何故 askari2018lifted 不管激活函数是什么，都添加了额外的约束 $X^i\geq \mathbf{0}$，所以他们的重构不能很好地近似原始 DNN \eqref{eq2}，这可能解释为什么 askari2018lifted 得不到好的结果。实际上，它们只能为 SGD 提供良好的初始化。

与基于梯度的方法（例如 SGD）相比，LPOM 可以使用任何非递减 Lipschitz 连续激活而没有数值求解，包括饱和（例如，sigmoid 和 tanh）和不可微分的（例如，ReLU 和 leaky ReLU），并且可以逐层并行更新权重和激活。相反，基于梯度的方法只能使用有限的激活函数，例如 ReLU， leaky ReLU 和 softplus，以避免梯度消失或爆炸问题，并且在计算时无法并行化梯度和激活。

四，求解LPOM

多亏了块多凸性性质(定理1)，LPOM可以用BCD求解。即，我们通过固定所有其他变量块来更新 $X^i$ 或 $W^i$。可以使用小批量训练数据来进行优化问题的求解，解决 LPOM 的整个算法总结在算法1，下面我们给出更多的细节。

4.1 更新$\{X^i\}^n_{i=2}$

我们先介绍串行更新的方法 $\{X^i\}_{i=2}^n$，将 $\{X^i\}_{i=2}^{n}$ 从 $i=2$ 接连不断地更新到 $n$，就像 DNN 的前馈过程一样。当 $i=2,\cdots,n-1$ 时，在 $\{W^i\}_{i=1}^{n-1}$ 和 $\{X^j\}_{j=2,j\neq i}^n$ 固定时，问题 \eqref{eq18}可以化为：

$\begin{align*} &\min_{X^i}\mu_i\bigg(\mathbf{1}^\top f(X^i)\mathbf{1}+\frac{1}{2}\|X^i-W^{i-1}X^{i-1}\|^2_F \bigg)\\ &+\mu_{i+1}\bigg(\mathbf{1}^\top g(W^iX^i)\mathbf{1}+\frac{1}{2}\|X^{i+1}-W^iX^i\|^2_F \bigg) \end{align*} \tag{23}$

优化条件是：

$\begin{align*} &\mathbf{0}\in \mu_i(\phi^{-1}(X^i)-W^{i-1}X^{i-1})\\ &+\mu_{i+1}((W^i)^\top(\phi(W^iX^i)-X^{i+1})) \end{align*} \tag{24}$

所以用下面迭代方法更新 $X^i$ 直到收敛：

$X^{i,t+1}=\phi\bigg(W^{i-1}X^{i-1}-\frac{\mu_{i=1}}{\mu_i}(W^i)^\top(\phi(W^iX^{i,t})-X^{i+1}) \bigg) \tag{25}$

其中上标 $t$ 为迭代次序。收敛分析如下：

定理2
假设 $|\phi’(x)|\leq\gamma$，如果 $\rho<1$，则迭代是收敛的并且收敛速率是线性的，其中

$\rho=\frac{\mu_{i+1}}{\mu_i}\gamma^2\sqrt{\| |(W^i)^\top||W^i| \|_1\| |(W^i)^\top| |W^i|\|_\infty}$

证明可以在补充材料中找到。在上面式子中，$|A|$ 是一个矩阵，其元素是 $A$ 的绝对值，$|\cdot|_1$ 和 $|\cdot|_{\infty}$ 分别是矩阵 1-范数（largest absolute column sum）和矩阵 $\infty$-范数（largest absolute row sum）。

当考虑 $X^n$ 时，问题\eqref{eq18} 简化为

$\min_{X^n}\ell(X^n,L)+\mu_n\bigg(\mathbf{1}^\top f(X^i)\mathbf{1}+\frac{1}{2}\|X^n-W^{n-1}X^{n-1}\|^2_F \bigg) \tag{26}$

优化条件是：

$\mathbf{0}\in\frac{\partial\ell(X^n,L)}{\partial X^n}+\mu_n(\phi^{-1}(X^n)-W^{n-1}X^{n-1}) \tag{27}$

所以用下面迭代来更新 $X^n$ 直到收敛

$X^{n,t+1}=\phi\bigg(W^{n-1}X^{n-1}-\frac{1}{\mu_n}\frac{\partial\ell(X^{n,t},L)}{\partial X^n} \bigg) \tag{28}$

收敛分析如下所示：

定理3
假设 $|\phi’(x)|\leq\gamma$ 和 $\bigg|\big(\frac{\partial^2\ell(X,L)}{\partial X_{kl}\partial X_{pq}}\big)\bigg|_1\leq\eta$。如果 $\tau < 1$，则迭代收敛，收敛率为线性，其中 $\tau=\frac{\gamma\eta}{\mu_n}$。

证明也可以在补充材料中找到。如果 ${\ell}(X^n,L)$ 是最小二乘误差，即 ${\ell}(X^n,L)=\frac{1}{2}|X^n-L|_F^2$，然后 $\bigg|\bigg|\big(\frac{\partial^2\ell(X,L)}{\partial X_{kl}\partial X_{pq}}\big)\bigg|\bigg|_1 = 1 $。所以我们得到 $\mu_n>\gamma$。

上面的串行更新程序可以很容易地更改为并行更新：每个 $X^i$ 都使用最新的其他 $X^j, j\neq i$ 的信息来更新。

4.2 更新$\{W^i\}^{n-1}_{i=1}$

$\{W^i\}_{i=1}^{n-1}$ 可以完全并行更新，当 $\{X^i\}_{i=2}^{n}$ 是固定的，问题 \eqref{eq18}化为：

$\begin{align*} \min_{W^i}\mathbf{1}^\top g(W^iX^i)\mathbf{1}+\frac{1}{2}\|W^iX^i-X^{i+1}\|^2_F\\ i=1\cdots n-1 \end{align*} \tag{29}\label{eq29}$

上述问题可以并行求解。 \eqref{eq29} 可以写做：

$\min_{W^i}\mathbf{1}^\top\tilde{g}(W^iX^i)\mathbf{1}-\langle X^{i+1},W^iX^i \rangle\tag{30} \label{eq30}$

其中，如前所述 $\tilde{g}(x)=\int_0^x \phi(y)dy$。假设 $\phi(x)$ 是 $\beta$-Lipschitz 连续的，这对于几乎所有使用的激活函数都是成立的。然后 $\tilde{g}(x)$ 是 $\beta$-平滑的：

$|\tilde{g}^{'}(x)-\tilde{g}^{'}(y)|=|\phi(x)-\phi(y)|\leq\beta|x-y| \tag{31}$

问题 \eqref{eq30} 可以通过APG的局部线性化 $\hat{g}(W)=\tilde{g}(WX)$ 求解。然而，$\hat{g}(W)$ 梯度的Lipschitz 常数，即 $\beta|X|_2^2$，可能非常大，因此收敛可能很慢。下面我们提出一个 APG 的改进版本，专为解决问题\eqref{eq30} 而设计的高效算法。

考虑以下问题：

$\min_xF(x)\equiv\varphi(Ax)+h(x) \tag{32}\label{eq32}$

其中 $\varphi(y)$ 和 $h(x)$ 都是凸的。而且，$\varphi(y)$ 是 $L_\varphi$-平滑的：$|\nabla\varphi(x)-\nabla \varphi(y)| \leq L_\varphi|x-y|,\forall x,y.$ 我们假设下面的问题：

$x_{k+1}=\mathop{argmin}_x\langle\nabla\varphi(Ay_k),A(x-y_k) \rangle +\frac{L_\varphi}{2}\|A(x-y_k)\|^2+h(x) \tag{33}\label{eq33}$

对任何给定的 $y_k$ 很容易求解，我们提出用算法2求解 \eqref{eq32}，那么我们有下面的定理：

定理4
如果我们使用算法2来求解问题\eqref{eq32}，则收敛速度至少为 $O(k^{-2})$：

$F(x_k)\!-\!F(x^*)\!+\!\frac{L_\varphi}{2}\|z_k\|^2\!\leq\!\frac{4}{k^2}\!\left(\!F(x_1)\!-\!F(x^*)\!+\!\frac{L_\varphi}{2}\|z_1\|^2\!\right)$

其中，
$z_k=A[\theta_{k-1}x_{k-1}-x_k+(1-\theta_{k-1})x^]$，且 $x^$ 是问题\eqref{eq32}的任意优化解。

证明也可以在补充材料中找到。

通过用问题\eqref{eq30}实例化问题\eqref{eq32}，子问题\eqref{eq33} 变为：

$\begin{align*} W^{i,t+1}&=\mathop{argmin}_W\langle\phi(Y^{i,t}X^i),(W-Y^{i,t})X^i\rangle\\ &+\frac{\beta}{2}\|(W-Y^{i,t})X^i||^2_F-\langle X^{i+1}-WX^i\rangle \end{align*} \tag{34}$

这是一个最小二乘问题，解是：

$W^{i,t+1}=Y^{i,t}-\frac{1}{\beta}(\phi(Y^{i,t}X^i)-X^{i+1})(X^i)^{+} \tag{35}$

其中 $(X^i)^{+}$ 是 $X^i$ 的伪逆，$Y^{i,t}$ 是算法2中的 $y_k$。

如果 $\phi(x)$ 严格递增且递增率 $\frac{\phi(y)-\phi(x)}{y-x}\, (y\neq x)$ 的下界为 $\alpha>0$，那么 $\tilde{g}(x)$ 是强凸的，并且收敛是线性的，这里我们省略详情。

五，实验

在本节中，我们通过与 SGD 和两种基于非梯度的方法askari2018lifted 及 taylor2016training 进行比较来评估 LPOM。其他基于非梯度的方法不为分类任务训练完全连接的前馈神经网络（例如，使用跳跃连接，训练自动编码器，以及学习哈希等)，所以我们不能将它们包括在内进行比较。为简单起见，我们使用最小二乘损失函数和 ReLU 激活函数（使用 ReLU 的另一个原因是它可以产生更高的精度，尽管 LPOM 可以没有数值困难的用其他激活函数参与计算）除非另有说明。与 askari2018lifted 不同，我们不对权重 $\{W^i\}_{i=1}^{n-1}$ 使用任何正则化。我们对 LPOM 和 SGD 使用相同的输入和随机运行初始化。我们用 LPOM 的 MATLAB 实现而不优化代码，使用基于 Caffe 的 SGD 求解器。对于 Caffe 求解器，我们修改demo代码，仔细调参实现最好的精度。对于 askari2018lifted 和 taylor2016training，我们引用他们的论文的结果。

5.1 与SGD比较

我们对两个数据集进行实验，即 MNIST 和 CIFAR-10。对于 MNIST 数据集，我们使用 $28\times28=784$ 个原始像素作为输入，它包括 60,000 张训练图像和 10,000 张测试图像，不使用预处理或数据增强。LPOM和SGD，在每个epoch中都用所有训练样本运行一次。性能取决于网络结构的选择。与 zeng2018global 一样，我们实现了一个784-2048-2048-2048-10 前馈神经网络。对于 LPOM，我们只需在 \eqref{eq18} 中设置 $\mu_i=20$。我们在 LPOM 和 SGD 上都运行 100 个周期的，固定批量大小为 100。训练和测试精度如图1(a) 和 (b)，可以看到两种方法的训练精度都约等于 $100\%$。然而，LPOM 的测试准确性略优于 SGD（$98.2\%$ vs. $98.0\%$）。

对于 CIFAR-10 数据集，在 zeng2018global 中我们实现 3072-4000-1000-4000-10 前馈神经网络。我们通过分别减去训练数据集中红色、绿色和蓝色通道的均值来标准化彩色图像，不使用预处理或数据扩充。对于 LPOM，我们设置 \eqref{eq18} 中的 $\mu_i=100$。在 LPOM 和 SGD 上运行 100 个 epochs，批量大小为 100。训练和测试准确度如图1 (c) 和 (d) 所示，可以看到SGD和LPOM的训练精度是约等于 $100\%$。但是，LPOM 的测试精度优于SGD（$52.5\%$ 对 $47.5\%$）。

5.2 与其他非梯度方法比较

我们用 MNIST 数据集上相同结构的网络与 askari2018lifted 中的结果进行比较。在实际计算中askari2018lifted 只用了 ReLU 激活函数，与 askari2018lifted 一样，我们在 LPOM 上运行 17 个 epochs，固定批量大小为 100，设置 $\mu_i=20$。使用 60,000 张训练图像和 10,000 张测试图像，不要使用预处理或数据增强。这两种方法的测试精度示于表2，可以看到带 ReLU 的 LPOM 表现很大差距的优于askari2018lifted 的方法，这符合我们在“LPOM 的优点”小节的描述。

按照 taylor2016training 中数据集和网络架构的设置，我们在 SVHN 数据集上测试 LPOM，设置 $\mu_i=20$。 SGD、taylor2016training 和 LPOM 的测试精度如表3所示。可以看到 LPOM 优于 SGD 和 taylor2016training。
如 taylor2016training 中所述，他们基于 ADMM 的方法和 SGD 的测试精度分别约为 $96.5\%$ 和 $95.0\%$。然而，LPOM 可以在相同的设置下达到 $98.3\%$ 的测试精度。
这进一步验证了LPOM的优势。

六，总结

在这项工作中，我们提出了 LPOM 来训练全连接前馈神经网络，使用近端运算符 LPOM 将神经网络转化为一个新的分块多凸模型，转换适用于一般非递减 Lipschitz 连续激活函数。我们自然地提出了块坐标下降算法，保障每个子问题收敛的情况下求解。 LPOM 可以并行解决，相比分层激活，无需更多辅助变量。实验结果表明 LPOM 在完全连接的神经网络比 SGD，askari2018lifted 和 taylor2016training 效果更好。未来的工作包括将 LPOM 扩展到训练卷积和递归神经网络并应用 LPOM 到网络压缩。

重要文献

Lifted neural networks
Deep residual learning for image recognition