随机区块立方牛顿法
本文主要研究随机块 - 坐标下降方法在最小化一般光滑凸函数和块可分凸函数的和时的应用,提出一种更加针对性的收敛速度和更好的迭代复杂度,同时针对无约束光滑凸函数极小化问题提出了新的随机评估序列技术并改进了现有算法的收敛速度。
May, 2013
我们提出了两种非常简单的随机二阶方法,用于最小化大量充分光滑和强凸函数的平均值。第一种是牛顿方法的随机变体(SN),第二种是具有立方正则化的牛顿方法的随机变体(SCN)。与现有的随机二阶方法不同,我们的方法没有这种缺点,例如,我们的方法的最简单的变体每次迭代只需要计算一个随机选择函数的梯度和海森矩阵。与大多数现有的随机牛顿和拟牛顿方法相比,人们的方法保证了比一阶 oracle 更快的本地收敛,同时适应了问题的曲率。有趣的是,我们的方法不是无偏的,因此我们的理论为设计新的随机方法提供了新的直觉。
Dec, 2019
本文提出了一个随机变体的经典算法 -- 立方正则化牛顿方法。该算法可以有效地避免鞍点问题,并在仅需要 $\mathcal {\tilde {O}}(\epsilon^{-3.5})$ 个随机梯度和随机海森向量乘积评估的情况下,为一般光滑的非凸函数找到近似的局部极小值。
Nov, 2017
该论文研究了优化非凸连续函数的问题,提出了一种名为 SSCN 的随机坐标二阶方法,通过在随机子空间应用立方正则化来降低使用二阶信息的计算复杂性,在高维场景中表现出了良好的适用性,并且通过提出自适应采样方案,实现了比传统一阶方法更快的速度。
Jun, 2024
提出了随机方差约减的立方正则牛顿法,应用于非凸优化问题。该方法在半随机梯度和半随机海森矩阵的基础上工作,具有较低的复杂度,并在各种非凸优化问题上得到了验证。
Feb, 2018
本研究提出了一种基于 Bregman 距离的随机 Bregman(块)坐标下降法,解决了无法全局 Lipschitz 连续(部分)梯度假设的复合问题优化及收敛分析方面的瓶颈,给出了迭代收敛复杂度,并提出了加速 RBCD 方法。
Jan, 2020
本文研究了立方正则化牛顿法在解决具有一致凸性目标的复合最小化问题时的迭代复杂度。在引入某种程度的二阶条件数的概念后,我们证明了在非退化情况下具有自适应正则化参数估计的方法具有线性收敛率。我们的算法自动实现了具有 H"older 连续的目标平滑部分的不同问题类别中均匀凸目标函数的全局最佳复杂度界限。作为我们发展的副产品,我们证明了牛顿法在具有一致有界二阶导数的强凸函数类上的全局迭代复杂度始终优于梯度法。
May, 2019
本文介绍了一种基于随机块参数下降方法的分块近似牛顿法,用于解决复合自共轭(CSC)极小化问题的问题,该方法的计算成本通常比传统的 PDN 方法低,已在处理大规模 CSC minimization 问题方面取得了显着效果。
Jul, 2016
介绍了三次正则化方法及其改进的全局收敛性和局部二次收敛性。同时,介绍了一种弱化的错误界条件来证明方法的局部二次收敛性,使得该方法能处理出现退化情况的问题,并将其应用于相位恢复和低秩矩阵恢复的非凸优化问题。
Jan, 2018