RSN:随机子空间牛顿法
本文研究了在解决变量数量和数据点数量都很大的有限和最优化问题的 Newton 法的背景下,两种数据空间维数缩减方法:Hessian 子采样和随机 Hadamard 变换。通过一系列数字实验和 Hessian 子采样方法的复杂性分析,揭示了使用共轭梯度方法相对于随机梯度迭代方法的优势。
May, 2017
提出了一种新的高维随机优化方法,将坐标下降法推广到随机子空间,证明了使用自适应采样策略的随机子空间可以显著优于最近文献中常见的盲目采样方法,可以通过相关随机矩阵集合有效生成自适应子空间;在具有不同谱衰减的数据矩阵上验证了该方法在机器学习问题中的速度优势,包括逻辑回归、带随机卷积层的核分类和具有修正线性单元的浅神经网络。
Jun, 2019
该研究提出了一种随机化的二阶优化方法 ——Newton Sketch,使用随机投影或子采样 Hessian 实现近似牛顿步。对于自共轭函数,该算法证明具有超线性收敛和指数高概率,与条件数和相关问题独立的收敛和复杂度保证。对于适当的初始化,即使在没有自共轭的情况下,也可以保证类似的保证对于强凸和光滑的目标。我们还描述了将我们的方法扩展到具有自共轭屏障的凸约束程序。我们讨论和说明了其应用于线性程序,带有凸约束的二次程序,逻辑回归和其他广义线性模型以及半定规划的扩展问题。
May, 2015
该论文研究了优化非凸连续函数的问题,提出了一种名为 SSCN 的随机坐标二阶方法,通过在随机子空间应用立方正则化来降低使用二阶信息的计算复杂性,在高维场景中表现出了良好的适用性,并且通过提出自适应采样方案,实现了比传统一阶方法更快的速度。
Jun, 2024
该研究介绍了一种新的子空间三阶正则牛顿方法,其在解决凸优化问题时具有与维度无关的全局收敛速度,并且在特定谱条件下能恢复到完全维度的三阶正则牛顿方法的收敛速度,数值实验表明该方法比现有的随机子空间方法收敛更快,尤其在高维问题上。
Jan, 2024
该研究发展了一种基于随机迭代的方法来解决线性系统问题,并通过变化两个参数来恢复广泛的已知算法,并且在单个定理中证明了误差的指数收敛,并给出了预期迭代的精确公式。
Jun, 2015
利用随机矩阵的谱分析最新进展,我们开发了一种新的技术,提供了随机投影矩阵的期望值的确切表达式,这些表达式可以用来表征多种常见的机器学习任务中的降维性能,包括低秩估计和迭代随机优化等。我们的结果适用于多种流行的草图方法,包括高斯和 Rademacher 草图,结果表明,我们推导出的表达式反映了这些草图方法的实际性能,甚至体现了较低阶效应和恒定因子。
Jun, 2020
本文论述了大规模优化问题中 Sub-sampling 的迭代算法,提供了 Hessian 和梯度子采样的收敛边界,使用随机数值线性代数来获得适当的采样策略,并为在大规模线性系统下近似更新的情况下的全局收敛结果提供了解决方案
Jan, 2016
使用 Levenberg-Marquardt 的 Gauss-Newton 和自然梯度方法,解决深度神经网络大量变量和海量数据集所产生的非凸优化问题,证明方法能够有效实现并提出数值结果。
Jun, 2019