Newton-Sketch 和子采样 Newton 方法的研究
本文研究了通过子采样获得渐进和海森矩阵的近似解来解决随机优化问题,提出了利用这些近似的 Newton-like 方法,并讨论了如何协调渐进和海森矩阵的准确度,得到期望中的超线性收敛速度。该文第二部分分析了一种利用共轭梯度方法近似求解线性系统的不精确 Newton 方法,并且采样的是海森矩阵而不是梯度(梯度被认为是精确的)。我们提供了一种基于 CG 迭代和海森矩阵近似质量的复杂度分析,并将其与采用随机梯度迭代而不是 CG 方法的方法进行了比较。最后,我们报告了初步的数值结果,说明了在 logistic 回归的机器学习应用中,不精确子采样牛顿方法的表现。
Sep, 2016
本文论述了大规模优化问题中 Sub-sampling 的迭代算法,提供了 Hessian 和梯度子采样的收敛边界,使用随机数值线性代数来获得适当的采样策略,并为在大规模线性系统下近似更新的情况下的全局收敛结果提供了解决方案
Jan, 2016
该研究提出了一种随机化的二阶优化方法 ——Newton Sketch,使用随机投影或子采样 Hessian 实现近似牛顿步。对于自共轭函数,该算法证明具有超线性收敛和指数高概率,与条件数和相关问题独立的收敛和复杂度保证。对于适当的初始化,即使在没有自共轭的情况下,也可以保证类似的保证对于强凸和光滑的目标。我们还描述了将我们的方法扩展到具有自共轭屏障的凸约束程序。我们讨论和说明了其应用于线性程序,带有凸约束的二次程序,逻辑回归和其他广义线性模型以及半定规划的扩展问题。
May, 2015
本文研究了随机草图方法,以近似解决带有一般凸约束的最小二乘问题,并提出了一种名为迭代 Hessian 草图的新方法,同时提供了数值模拟实验,包括面部表情分类实验。
Nov, 2014
考虑到大型数据的拟合应用中需要解决高维参数的大量函数之和的优化问题,本文运用子采样的方式以提高计算效率,并分析了牛顿方法中的 Hessian 矩阵和梯度的子采样对收敛速度的影响。
Jan, 2016
利用随机矩阵的谱分析最新进展,我们开发了一种新的技术,提供了随机投影矩阵的期望值的确切表达式,这些表达式可以用来表征多种常见的机器学习任务中的降维性能,包括低秩估计和迭代随机优化等。我们的结果适用于多种流行的草图方法,包括高斯和 Rademacher 草图,结果表明,我们推导出的表达式反映了这些草图方法的实际性能,甚至体现了较低阶效应和恒定因子。
Jun, 2020
本文提出了一种结合子抽样技术与低秩逼近,收敛速度可与牛顿法相媲美但迭代成本较小的随机批量算法,且具有较强的鲁棒性和复合收敛速度,同时也能用于先前被提出的子抽样算法,并且应用于多个著名机器学习问题的数据集上,具有更好的效果。
Aug, 2015
本文从优化的角度研究素描技术,提出了加速 Hessian 素描和双重随机投影的方法,并通过迭代对原始和对偶公式进行素描来解决大规模问题。在合成和真实数据集上进行了广泛的实验验证。
Oct, 2016
本文提出了一种分布式加速线性回归的方法,通过使用随机化草稿技术和改善异步系统中的顽固者韧性来确保安全性,同时应用随机齐次正交矩阵和子采样块来安全获取信息和减少回归问题的维度。
Aug, 2023