英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

非凸和非光滑优化的非精确近端梯度方法

摘要

在机器学习研究中，近似梯度方法在解决各种非光滑正则化优化问题上很受欢迎。当精确求解近端算子很耗费时间，或者近端算子没有分析解时，非精确的近端梯度方法是非常重要的。然而，现有的非精确近端梯度方法仅考虑凸问题。非凸近端梯度方法的知识非常有限。为了解决这个难题，本文首先提出了三种非精确的近端梯度算法，包括基本方法和Nesterov加速方法。之后，我们为基本方法和Nesterov加速方法提供理论分析。理论结果显示我们的非精确的近端梯度算法可以具有与非凸设置中的精确近端梯度算法相同的收敛速率。最后，我们展示了我们的非精确的近端梯度算法在三个代表性非凸学习问题上的应用。所有的实验结果证实了我们新的非精确近端梯度算法的优越性。

引言

许多机器学习问题涉及非光滑正则化，例如具有各种稀疏诱导惩罚的机器学习模型（Bach et al。，2012）。因此，有效地解决非光滑正则化的优化问题对于许多机器学习应用而言是重要的。在本文中，我们关注具有非光滑正则化的机器学习模型的优化问题如下：

其中对应于经验风险，是光滑的也可能是非凸的，并且对应于正则化项，是非光滑的也可能是非凸的。

近似梯度方法在解决各种非平滑正则化优化问题方面很受欢迎。近端梯度法的关键步骤是解决近端操作者如下：

其中gamma;是步长。如果函数足够简单，我们可以解析地得到近端算子的解。例如，如果，近端算子的解可以通过收缩阈值算子获得（Beck和Teboulle，2009）。如果函数很复杂以至于相应的近端算子没有解析解，则应该设计一个特定的算法来求解近端算子。例如，如果 = （Zhong和Kwok，2012）用于具有自动特征分组的稀疏回归，Zhong和Kwok（2012）提出了一种用于精确求解近端算子的迭代群合并算法。

然而，当函数很复杂时，求解近端算子将会很昂贵。再次以OSCAR为例，当数据具有高维度（经验上大于1,000）时，迭代组合并算法将变得非常低效。更糟的是，当函数过于复杂时，没有解算器可以精确求解近端算子。例如，Grave，Obozinski和Bach（2011）提出追踪Lasso范数，以考虑设计矩阵的相关性以稳定回归估计。然而，由于追踪Lasso规范的复杂性，就我们所知，仍然没有解算器来解决相应的近端算子。

为了解决上述问题，Schmidt，Le Roux和Bach（2011）首先提出了非精确的近端梯度方法（包括基本方法（IPG）和Nesterov加速方法（AIPG）），它近似地解决了近端算子（即容忍近端操作计算中的误差）。他们证明，非精确的近端梯度方法可以具有与精确近端梯度方法相同的收敛速度，前提是计算近端算子的误差以适当的速率下降。独立地，Villa et al。（2013）提出了AIPG算法并证明了相应的收敛速度。在（Villa et al。，2013）的论文中，他们将AIPG称为在信号处理领域众所周知的非精确的前向后向分裂法（AIFB）。我们在表1中总结了这些方法。

表1：代表性（精确和非精确）近端梯度算法。（C和NC分别是凸和非凸的缩写。）

从表1，我们发现现有的非精确近端梯度方法只考虑凸问题。但是，机器学习中的很多优化问题都是非凸的。非凸性来源于经验风险函数或正则化函数。首先，我们研究经验风险函数（即损失函数）。correntropy诱导的损失函数（Feng et al，2015）被广泛用于稳健的回归和分类，它是非凸性的。未标记样本的对称S形丢失用于半监督支持向量机（Chapelle，Chi和Zien，2006），它是非凸的。其次，我们研究正则化函数。Capped-l1penalty（Zhang，2010）用于无偏变量选择，低秩约束（Jain，Meka和Dhillon，2010）广泛用于矩阵完成。这两种正则化函数都是非凸的。然而，我们对非精确近端梯度方法的了解在非凸设置中非常有限。

为了解决这个挑战，本文首先提出了三种非精确的近端梯度算法，包括基本和Nesterov 加速方法，它们可以处理非凸问题。然后，我们对基本和涅斯捷罗夫的加速方法进行理论分析。理论结果表明，我们的非精确近端梯度算法可以具有与精确近端梯度算法相同的收敛速率。最后，我们提供了我们的非精确近端梯度算法在三个代表性非凸学习问题上的应用。在稳健的OSCAR和链路预测上的应用表明我们的非精确的近端梯度算法可能比精确的近端梯度算法快得多。在强大的Trace Lasso上的应用填补了没有近端梯度算法的空缺。

主要贡献：本文的主要贡献总结如下：

1.我们首先提出了具有严格收敛保证的基本和加速非精确的近端梯度算法。具体而言，我们的非精确的近端梯度算法可以具有与非凸设置中的精确近端梯度算法相同的收敛速率。

2.我们提供了我们的非精确近端梯度算法在三个代表性非凸学习问题上的应用，即鲁棒OSCAR，链路预测和强大的Trace Lasso。结果证实了我们非精确的近端梯度算法的优越性。

相关工作

近端梯度法是解决各种非平滑正则化优化问题的最重要方法之一。有多种精确的近端梯度方法。具体而言，对于凸问题，Beck和Teboulle（2009）提出了基本近端梯度（PG）方法和Nesterov加速近端梯度（APG）方法。他们证明了PG的收敛速度为 ，APG的收敛速度为，其中T是迭代次数。对于非凸问题，Ghadimi和Lan（2016）认为只有可以是非凸的，证明了APG方法的收敛速度为。Bot，Csetnek和Laszlo（2016）认为和都是非凸的，证明了PG方法的收敛性。Li和Lin（2015）认为和都可以是非凸的，并且证明了APG算法可以在有限次数的迭代中以线性速率或次线性速率收敛，）在不同的条件下。我们总结了表1中的这些确切的近端梯度方法。

除上述批次精确近端梯度方法外，还有随机和在线近端梯度方法（Duchi和Singer，2009； Xiao和Zhang，2014）。因为它们超出了本文的范围，所以我们在本文中没有对它们进行评论。

初步准备

在本节中，我们引入Lipschitz光滑，近似的次微分和近似Kurdyka-Lojasiewicz（KL）性质，它们对非凸近似梯度方法在非凸设置中的收敛性分析至关重要。

Lipschitz光滑：对于光滑函数，我们有nabla;的Lipschitz常数L（Wood和Zhang，1996）如下。

假设1.：L是nabla;的Lipschitz常数。因此，对于所有x和y，可以呈现L-Lipschitz平滑如下：

同样的，L-Lipschitz平滑也可以写成公式（4）。

近似次微分：因为本文使用了不精确的近端梯度，近似近似算子可能产生近似的次微分。在下文中，我们给出近似次微分（Bertsekas et al。，2003）的定义，它将用于近似KL特性（即定义2）。

定义1（-近似微分）： 给定一个凸函数：和一个正标量，点（表示为）的的近似次微分是：

基于定义1，如果disin;，我们说d是在点x处的的近似子梯度。

-近似KL特性：本文首先引入KL特性分析非凸近似梯度方法的收敛速度（Li和Lin，2015；Bot，Csetnek和Laszlo，2016）。由于本文关注不精确的近端梯度方法，我们相应地在定义2中提出了近似的KL性质，其中函数由 定义，S是R^N的一个子集。

定义2（-KL属性）：一个函数具有-KL性质，如果存在，则U的邻域u和函数phi;isin;Phi;eta;，使得对于所有 ，下面的不等式成立：

其中Phi;_eta;表示一类函数phi;：[0，eta;）→R 满足：

1. ϕ是在（0，eta;）上的凹函数和连续可微函数；
2. ϕ在0点处连续，ϕ(0) = 0。
3. 并且ϕrsquo;(x)gt;0, forall;xisin;(0, eta;)。

不精确的近端梯度算法

在本节中，我们首先提出了基于非精确近邻梯度的非凸优化算法，然后提出了两种不精确的近端梯度加速算法。

基本方法

如表1所示，对于凸问题（即函数和都是凸的），Schmidt，Le Roux和Bach（2011）提出了一种基本不精确的近端梯度（IPG）方法。我们遵循IPG框架（Schmidt，Le Roux和Bach，2011），并给出我们的IPG算法用于非凸优化问题（即函数或函数是非凸）。

具体来说，我们的IPG算法在Algorithm1中给出。类似于精确的近端梯度算法，我们的IPG（即算法1）的关键步骤是如下计算不精确的近端算子。

其中表示近端算子的计算中的误差。正如在（Tappenden，Richtarik和Gondzio，2016）中所讨论的，有几种方法可以计算不精确的近端算子。最流行的方法是使用原始双重算法来控制双重差距（Bach et al。，2012）。基于对偶差距，我们可以严格控制近端算子的计算误差。

加速方法

我们首先提出一个Nesterov的加速非精确近端梯度算法用于非凸优化，然后给出一个非单调加速的不精确近端梯度算法。

如表1所示，对于凸优化问题，Beck和Teboulle（2009）提出了Nesterov的加速不精确近端梯度（即APG）方法，Schmidt，Le Roux和Bach（2011）提出了Nesterov的加速不精确近端梯度（即AIPG）方法。APG和AIPG都以动力学术语加速。然而，正如（Li和Lin，2015）所提到的，传统的Nesterov加速方法可能会遇到非凸优化的动量项。为了解决不利的动量项，Li和Lin（2015）增加了另一个近端算子作为监测器，以使目标函数充分下降。为了使我们的AIPG产生的目标函数严格下降，我们遵循APG的框架（Li和Lin，2015）。因此，我们计算两个不精确的近邻算子和，其中v_{k 1}是一个监测器，目标函数严格下降。具体而言，我们的AIPG在算法2中提供。

为了解决非凸形式中的不利动量项，我们的AIPG（即算法2）使用一对不精确的近端算子来使目标函数严格下降。因此，AIPG是一种单调算法。实际上，使用两个近端操作者是一个保守的策略。正如在（Li和Lin，2015）中所提到的，如果它满足标准，我们可以直接接受z_{k 1}作为x_{k 1}，这表明y_k是一个很好的外推。只有当这个标准不被满足时才计算v_{k 1}。因此，可以减少近端操作者的平均数量。遵循这个思想，我们在算法3中提出了非单调加速不精确近端梯度算法（nmAIPG）。

收敛性分析

如前所述，对于非凸问题，不精确的近端梯度方法的收敛性分析仍然是一个开放的问题。本部分将解决这一挑战。

具体而言，如果是递减序列且，我们首先证明IPG和AIPG收敛于凸或非凸设置的临界点（定理1）。接下来，我们证明当误差以适当的速率下降时，IPG对于非凸问题（定理2）具有收敛率。然后，我们证明非凸集合中AIPG的收敛速度（定理3）。定理1，2和3的详细证明可以在附录中找到。

IPG和AIPG的收敛性

我们首先证明IPGA和AIPG收敛于临界点（定理1），如果是递减序列和。

定理1.在假设1中，如果是递减序列，并且，则IPG和AIPG的凸和非凸优化中有。

备注1.定理1保证IPG和AIPG在凸或非凸设置的无限次迭代之后收敛到临界点（或称为驻点）

IPG的收敛速度

由于函数和都可能是非凸的，我们不能直接使用或来分析IPG的收敛速度，其中x *是（1）的最优解。在本文中，我们使用来分析IPG在非凸设置下的收敛速度。详细的原因在附录中提供。定理2表明，当误差以适当的速率下降时，IPG具有非凸优化的收敛速率，这与无误差情况完全相同（参见备注2中的讨论）。

定理2.对于是非凸的，并且是凸的或者非凸的，我们对于IPG有如下结果：

如果是凸的，我们有：

其中， 。

如果是非凸的，我们有：

备注2.定理2意味着IPG对非凸优化没有错误具有收敛速度。如果是可以求和的并且是凸的，那么我们也可以让IPG对于非凸优化具有收敛率O（1T）。如果是可以求和的并且是非凸的，那么我们也可以让IPG具有非凸优化的收敛率。

AIPG的收敛速度

在本节中，基于-KL性质，我们证明了AIPG在非凸集合中的不同条件下以线性速率或次线性速率收敛于有限次数的迭代（定理3），这正好是 与无错案例相同（Li和Lin，2015）。

定理3.假设g是一个带Lipschitz连续梯度的非凸函数，h是一个适当的和较低的半连续函数。如果函数f满足-KL性质，，并且desingularising函数的形式为，对于某些，那么：

1. 如果，则存在lt;

   剩余内容已隐藏，支付完成后下载完整资料

   ---

   资料编号：[22610]，资料为PDF文档或Word文档，PDF文档可免费转换为Word