非凸非光滑优化的不精确近端梯度法
本文提出了一种高效的近端梯度算法,每个迭代只需要一个不精确(因此更便宜)的近端步骤,收敛于非凸问题的临界点并具有 O (1/k) 的收敛速度,比一阶方法中非凸问题的最佳速度还要快。
Dec, 2016
本文探讨了使用近端梯度法优化平滑凸函数和非平滑凸函数的和时,如果在计算平滑项的梯度或非平滑项的邻近算子时存在误差,基本的近端梯度法和加速近端梯度法可以实现与没有错误的情况下相同的收敛率,前提是错误以适当的速度减小。使用这些速度,在一组结构稀疏性问题上,我们的表现与精心选择的固定误差级别相当或更好。
Sep, 2011
我们提出了一种新的近端 - 梯度方法,用于最小化可微、可能非凸的函数加上凸、可能非可微的函数,并探讨了度量可能在每次迭代中改变,近似计算近端点并给出充分条件的可能性。我们还展示了这个方法在图像恢复问题中的竞争力。
Jun, 2015
本文研究了求解由平滑强凸函数和可得到其 Proximal 算子的非光滑凸函数组成的函数和的最优收敛速度,并利用半定规划等工具,建立了 Proximal 梯度算法的准确最坏情况收敛速度,同时提出可将强凸性等条件放宽以保证相应的收敛速度,得到了三种性能度量的同一步长最优的证明。
May, 2017
提出了非凸问题的近似解决方案;采用了三次正则化和信任域算法的不精确变体,并且可以应用于有限和问题,通过随机子采样法对梯度和 Hessian 进行适当精度逼近,实现了计算效率与最优迭代复杂度的权衡。
Feb, 2018
本文介绍了一种基于随机投影次梯度方法的弱凸(即均匀逼近正则)非光滑非凸函数的算法,并通过简单证明证明这种方法与用于光滑非凸问题的随机梯度方法具有相同的收敛速度;这似乎是第一个针对弱凸函数类的随机次(或确定性)梯度法的收敛速度分析。
Jul, 2017
本文研究随机算法优化非凸、非光滑的有限和问题。针对此问题,本文提出快速的随机算法,可获得常数迷你批量的收敛性。本文还使用这些算法的变种,证明了比批量近端梯度下降更快的收敛性,并在非凸、非光滑函数的一个子类中证明全局线性收敛率。
May, 2016
本文探讨了凸优化中的两个基本一阶算法,梯度下降法(GD)和近端梯度法(ProxGD)。我们着重于通过利用光滑函数的局部曲率信息,使这些算法完全自适应。我们提出了基于观察到的梯度差异的 GD 和 ProxGD 的自适应版本,因此没有额外的计算成本。此外,我们证明了方法的收敛性,仅需假设梯度在局部利普希茨连续。此外,所提出的版本允许使用比 [MM20] 最初建议的更大的步长。
Aug, 2023
本文介绍了一种利用步长乘以线性误差边界的方法来实现凸函数最小化的近端梯度算法;通过证明将误差边界与一种自然二次生长条件的等价性,直观地解释了观察到的线性收敛现象;我们的方法将推广到用于最小化由光滑映射组成的非光滑函数的近端方法,同时观察到算法中的短步长暗示了接近稳定状态,建议作为可靠的终止准则。
Feb, 2016
本文针对复合优化问题中一般且高效的不精确近端拟牛顿算法,在强凸目标函数下分析了其精确和不精确执行的收敛性质,并建立了一个简单的停止标准来改善其实用性。同时,对基于 FISTA 的近端拟牛顿算法进行加速,并与传统算法进行比较和分析,结果表明加速并没有带来任何好处。
Jul, 2016