机器学习中非光滑凸优化问题的拟牛顿方法
本文中我们考虑在闭凸子集上最小化一个非光滑非凸的目标函数 $f (x)$,同时满足附加的非光滑非凸约束 $c (x) = 0$。我们开发了一个统一的框架来发展基于 Lagrangian 的方法,在每次迭代中通过某些子梯度方法对原始变量进行单步更新。这些子梯度方法被 “嵌入” 到我们的框架中,以黑盒更新原始变量的方式加以合并。我们证明了在温和条件下,我们提出的框架继承了这些嵌入子梯度方法的全局收敛性保证。此外,我们证明了我们的框架可以扩展到解决具有期望约束的约束优化问题。基于我们提出的框架,我们展示了一系列现有的随机子梯度方法,包括 proximal SGD、proximal momentum SGD 和 proximal ADAM,可以嵌入到基于 Lagrangian 的方法中。对深度学习任务的初步数值实验表明,我们提出的框架可以为非凸非光滑约束优化问题提供高效的 Lagrangian-based 方法变体,并具有收敛性保证。
Apr, 2024
本文介绍了一种应对分布式计算和多批处理中不可靠计算节点带来的问题的 L-BFGS 方法实现方式,并说明了如何在多批处理中进行稳定的拟牛顿更新以及算法在机器学习的分类与神经网络训练问题中的行为表现及其收敛性质。
Jul, 2017
证明了解决大规模机器学习中随机目标优化问题的在线随机有限内存版本的 Broyden-Fletcher-Goldfarb-Shanno 拟牛顿法全局收敛性,数值实验证明其优于随机梯度下降算法。
Sep, 2014
本文提出了一种更高效的准牛顿方法,它将对称秩 - 1 更新纳入增量框架中,从而得到了不依赖条件数的局部超线性收敛速率。此外,我们通过在 Hessian 近似上应用块更新来提升方法,以实现更快的局部收敛速率。数值实验表明,所提出的方法明显优于基准方法。
Feb, 2024
提出了一种稀疏优化的通用框架,使用了二阶信息和有限的 BFGS Hessian 逼近,通过坐标下降的方法解决问题,并对其全局收敛率进行了新颖的分析。
Nov, 2013
我们提出了一种适应性步长方法,用于解决一个广泛类别的非凸多目标规划问题,且不包含线搜索技术,适用于无界约束集。我们证明了在适度假设下,该方法的收敛性,并应用该方法进行了一些实验以验证其有效性。
Feb, 2024
本文提出了一种基于限制记忆的 BFGS 更新公式和子采样 Hessian - 向量积的随机拟牛顿方法来有效地、稳健地和可伸缩地处理如何将曲率信息纳入随机逼近方法的问题,并通过机器学习问题上的数值结果展示其前景。
Jan, 2014
利用可适应性光滑函数的概念和 Bregman 基础的近端梯度方法,在解决具有复杂目标函数的非凸、非光滑最小化问题时,实现全局收敛。
Jun, 2017
提出了一种基于次梯度的算法,用于处理具有通用凸不等式约束的非光滑问题,通过使用线性最小化预言机和拉格朗日乘子更新规则,在不需要对可行域进行投影的情况下实现了 ε- 次优解。
Nov, 2023
这篇文章研究了在有界局部次梯度变化情况下的非光滑优化问题,定义了目标函数的类别,包括传统优化问题中基于目标函数的 Lipschitz 连续性或梯度的 Holder/Lipschitz 连续性的函数,并且包含了既不是 Lipschitz 连续也没有 Holder 连续梯度的函数类别。研究结果表明在传统的优化问题类别中,所定义的类别参数能够得到更为精细的复杂度界限,并恢复了最坏情况下的传统 oracle 复杂度界限,同时对于不是最坏情况的函数通常能够得到更低的 oracle 复杂度。此外,该文章还强调了在并行计算环境中非光滑优化的复杂度与次梯度集合的平均宽度有关。
Mar, 2024