应用于深度学习的非凸随机 Bregman 近端梯度方法

Jun, 2023

应用于深度学习的非凸随机 Bregman 近端梯度方法

Nonconvex Stochastic Bregman Proximal Gradient Method with Application to Deep Learning

Kuangyu Ding, Jingyang Li, Kim-Chuan Toh

TL;DR研究一系列随机Bregman近端梯度法（SBPG）方法，用于训练具有非Lipschitz梯度的非凸目标函数，及应用于神经网络训练中具有多项式内核函数的深度神经网络的优化算法。证明了SBPG及其动量版本（MSBPG）在非凸优化问题中有很好的收敛性，提出了MSBPG解决大规模优化中随机梯度下降法的一些不足。

Abstract

The widely used stochastic gradient methods for minimizing nonconvex composite objective functions require the Lipschitz smoothness of the differentiable part. But the requirement does not hold true for problem classes including quadratic inverse problems and training neural networks. To address this issue, we investigate a family of stochastic Bregman proxi

发现论文，激发创造

非光滑非凸优化的快速随机方法

本文研究随机算法优化非凸、非光滑的有限和问题。针对此问题，本文提出快速的随机算法，可获得常数迷你批量的收敛性。本文还使用这些算法的变种，证明了比批量近端梯度下降更快的收敛性，并在非凸、非光滑函数的一个子类中证明全局线性收敛率。

May, 2016

非凸优化问题的带动量近端梯度下降收敛分析

在非凸优化问题中，本文研究了加速近端梯度法(APGnc)以及基于其的随机方差减少(APGnc)算法，证明了其所生成的序列的极限点是目标函数的临界点，并通过KL函数的性质获得了线性和次线性的收敛速率。

May, 2017

非光滑、非凸问题的近距离引导随机次梯度方法

本文介绍了一种基于随机投影次梯度方法的弱凸（即均匀逼近正则）非光滑非凸函数的算法，并通过简单证明证明这种方法与用于光滑非凸问题的随机梯度方法具有相同的收敛速度；这似乎是第一个针对弱凸函数类的随机次（或确定性）梯度法的收敛速度分析。

Jul, 2017

一种简单的近端随机梯度下降法用于非光滑非凸优化

本文提出一种基于变量规约的Proximal 随机梯度下降算法(ProxSVRG+), 该算法在非凸性和非光滑性优化问题上具有更好的性能, 并在收敛性分析方面比之前的算法更加全面和普适性更强。

Feb, 2018

非凸优化中动量 SGD 的扩散近似理论

本文通过对非凸优化问题的扩散逼近，分析了Momentum随机梯度下降算法的算法行为，发现该算法对于强鞍点的逃逸具有帮助，但在优化器的周围区域内妨碍了收敛（未进行步长退火或动量退火），本文的理论发现部分验证了MSGD在训练深度神经网络中的实证成功。

Feb, 2018

非凸学习的随机梯度下降算法(无需假设梯度有上限)

本文研究证明了随机梯度下降在非凸学习中，无需统一梯度有界性假设也能达到最优收敛率的情况，并在一定程度上对于一般非凸目标函数和梯度主导的目标函数实现了几乎必然收敛。特别地，在方差为零的情况下可以得到线性收敛。

Feb, 2019

ProxSARAH：随机复合非凸优化的高效算法框架

提出了一种新的随机一阶算法框架来解决随机复合非凸优化问题，该算法覆盖了有限和期望设置，其中算法仅需要非凸目标项的平均光滑性假设和附加的有界方差假设，并证明了算法可以实现最佳复杂度界限。

Feb, 2019

非光滑非凸优化中随机次梯度方法的收敛性保证

本研究论文探讨了随机梯度下降（SGD）方法及其变种在训练非光滑激活函数构建的神经网络中的收敛性质，提出了一种新的框架，分别为更新动量项和变量分配不同的时间尺度。在一些温和条件下，我们证明了我们提出的框架在单一时间尺度和双时间尺度情况下的全局收敛性。我们展示了我们提出的框架包含了许多著名的SGD类型方法，包括heavy-ball SGD、SignSGD、Lion、normalized SGD和clipped SGD。此外，当目标函数采用有限和形式时，我们证明了基于我们提出的框架的这些SGD类型方法的收敛性质。特别地，在温和的假设条件下，我们证明了这些SGD类型方法以随机选择的步长和初始点找到了目标函数的Clarke稳定点。初步的数值实验表明了我们分析的SGD类型方法的高效性。

Jul, 2023

用广义的布雷格曼散度驯服非凸随机镜像下降

该论文重新审视了当今非凸优化设置中随机镜像下降（Stochastic Mirror Descent，SMD）的收敛性。通过支持一般距离生成函数（distance generating function，DGF）的新的非凸SMD收敛分析，该论文克服了先前结果对于具有光滑连续的梯度的可微性DGF的限制，并仅依赖于标准假设。此外，该论文通过Bregman前向-后向包络建立了收敛性，该包络是比常用的梯度映射的平方范数更强的度量。进一步，该论文将结果扩展到在次高斯噪声下的高概率收敛和在广义Bregman Proximal Polyak-Lojasiewicz条件下的全局收敛。此外，通过利用非光滑DGFs，我们展示了改进的SMD理论在各种非凸机器学习任务中的优势。值得注意的是，在非凸差分隐私（differentially private，DP）学习的背景下，我们的理论提供了一个（几乎）维度无关的效用界算法。对于训练线性神经网络的问题，我们开发了可证明收敛的随机算法。

Feb, 2024

基于拉格朗日法的非平滑非凸优化方法的开发

本文中我们考虑在闭凸子集上最小化一个非光滑非凸的目标函数$f(x)$，同时满足附加的非光滑非凸约束$c(x) = 0$。我们开发了一个统一的框架来发展基于Lagrangian的方法，在每次迭代中通过某些子梯度方法对原始变量进行单步更新。这些子梯度方法被“嵌入”到我们的框架中，以黑盒更新原始变量的方式加以合并。我们证明了在温和条件下，我们提出的框架继承了这些嵌入子梯度方法的全局收敛性保证。此外，我们证明了我们的框架可以扩展到解决具有期望约束的约束优化问题。基于我们提出的框架，我们展示了一系列现有的随机子梯度方法，包括proximal SGD、proximal momentum SGD和proximal ADAM，可以嵌入到基于Lagrangian的方法中。对深度学习任务的初步数值实验表明，我们提出的框架可以为非凸非光滑约束优化问题提供高效的Lagrangian-based方法变体，并具有收敛性保证。

Apr, 2024