适应性样本大小方法:全局利用拟牛顿方法的局部收敛
考虑到大型数据的拟合应用中需要解决高维参数的大量函数之和的优化问题,本文运用子采样的方式以提高计算效率,并分析了牛顿方法中的 Hessian 矩阵和梯度的子采样对收敛速度的影响。
Jan, 2016
本文提出了两种采样拟牛顿法(采样 LBFGS 和采样 LSR1),并为其提供了收敛保证。这些方法能有效地解决在机器学习中出现的经验风险最小化问题,通过对当前迭代中的随机采样点来产生黑塞或黑塞逆近似,避免了过时信息的影响,并具备在分布式计算中运行的并发能力。在二分类问题和神经网络训练任务上的数值实验结果表明,这些方法优于其经典版本。
Jan, 2019
提出了一种使用二阶信息进行通信和计算效率高的分布式优化算法来解决具有非平滑正则化项的 ERM 问题。该算法使用逐步二次逼近法,并描述了如何在分布式方式下有效地维护 Hessian 的逼近并解决子问题。该方法适用于广泛的非强凸问题,具有全局线性收敛性,需要更低的通信复杂度。同时,该方法可以收敛于非凸问题,因此具有在深度学习等应用中使用的潜力。初步的计算结果表明,该方法在凸问题上显著提高了通信成本和运行时间,超越了现有技术的方法。
Mar, 2018
本文论述了大规模优化问题中 Sub-sampling 的迭代算法,提供了 Hessian 和梯度子采样的收敛边界,使用随机数值线性代数来获得适当的采样策略,并为在大规模线性系统下近似更新的情况下的全局收敛结果提供了解决方案
Jan, 2016
本文提出了一种更高效的准牛顿方法,它将对称秩 - 1 更新纳入增量框架中,从而得到了不依赖条件数的局部超线性收敛速率。此外,我们通过在 Hessian 近似上应用块更新来提升方法,以实现更快的局部收敛速率。数值实验表明,所提出的方法明显优于基准方法。
Feb, 2024
本文提出了一种结合子抽样技术与低秩逼近,收敛速度可与牛顿法相媲美但迭代成本较小的随机批量算法,且具有较强的鲁棒性和复合收敛速度,同时也能用于先前被提出的子抽样算法,并且应用于多个著名机器学习问题的数据集上,具有更好的效果。
Aug, 2015
本文提出了增量 Newton 方法和梯度增长条件,通过实例研究,发现增量 Newton 方法需要满足梯度增长条件才能达到线性收敛率,进而得到了分布式优化方法的线性收敛率结果。
Oct, 2014
本文提出了一种基于限制记忆的 BFGS 更新公式和子采样 Hessian - 向量积的随机拟牛顿方法来有效地、稳健地和可伸缩地处理如何将曲率信息纳入随机逼近方法的问题,并通过机器学习问题上的数值结果展示其前景。
Jan, 2014
本文介绍了一种结构化数据拟合应用的优化问题的混合方法,同时具有增量梯度算法的高效迭代和完全梯度算法的稳定收敛性,基于这种方法提出了一个实用的拟牛顿算法实现,并通过数值实验证明了其潜在优势。
Apr, 2011
我们提出了两种非常简单的随机二阶方法,用于最小化大量充分光滑和强凸函数的平均值。第一种是牛顿方法的随机变体(SN),第二种是具有立方正则化的牛顿方法的随机变体(SCN)。与现有的随机二阶方法不同,我们的方法没有这种缺点,例如,我们的方法的最简单的变体每次迭代只需要计算一个随机选择函数的梯度和海森矩阵。与大多数现有的随机牛顿和拟牛顿方法相比,人们的方法保证了比一阶 oracle 更快的本地收敛,同时适应了问题的曲率。有趣的是,我们的方法不是无偏的,因此我们的理论为设计新的随机方法提供了新的直觉。
Dec, 2019