半定规划的子抽样算法
本文论述了大规模优化问题中 Sub-sampling 的迭代算法,提供了 Hessian 和梯度子采样的收敛边界,使用随机数值线性代数来获得适当的采样策略,并为在大规模线性系统下近似更新的情况下的全局收敛结果提供了解决方案
Jan, 2016
本论文提出了一种随机优化方法,该方法通过自适应地控制梯度近似计算中使用的样本量来减少方差,使用内积测试来决定增加样本量,并通过逻辑回归问题的数值实验验证了该算法的有效性。
Oct, 2017
本文提出了一种可扩展的随机主化最小化方案,能够应对大规模或可能无限的数据集,解决凸优化问题,并开发了几种基于此框架的有效算法,包括一个新的随机近端梯度方法,用于大规模 l1 逻辑回归的非凸稀疏估计的在线 DC 编程算法和解决大规模结构矩阵分解问题的有效性。
Jun, 2013
提出了一种新的高维随机优化方法,将坐标下降法推广到随机子空间,证明了使用自适应采样策略的随机子空间可以显著优于最近文献中常见的盲目采样方法,可以通过相关随机矩阵集合有效生成自适应子空间;在具有不同谱衰减的数据矩阵上验证了该方法在机器学习问题中的速度优势,包括逻辑回归、带随机卷积层的核分类和具有修正线性单元的浅神经网络。
Jun, 2019
考虑到大型数据的拟合应用中需要解决高维参数的大量函数之和的优化问题,本文运用子采样的方式以提高计算效率,并分析了牛顿方法中的 Hessian 矩阵和梯度的子采样对收敛速度的影响。
Jan, 2016
本研究提出了一种基于梯度下降的简单、可扩展、快速的算法来优化处理秩最小化问题及其相关的半定规划问题。通过对一个秩为 r 和条件数为 κ 的正半定 n x n 矩阵进行 O (r³κ²n log n) 次随机测量,我们证明了该方法可线性收敛于全局最优解。
Jun, 2015
本文提出了一种结合子抽样技术与低秩逼近,收敛速度可与牛顿法相媲美但迭代成本较小的随机批量算法,且具有较强的鲁棒性和复合收敛速度,同时也能用于先前被提出的子抽样算法,并且应用于多个著名机器学习问题的数据集上,具有更好的效果。
Aug, 2015
本文介绍了一种结构化数据拟合应用的优化问题的混合方法,同时具有增量梯度算法的高效迭代和完全梯度算法的稳定收敛性,基于这种方法提出了一个实用的拟牛顿算法实现,并通过数值实验证明了其潜在优势。
Apr, 2011
本文提出了一种基于采样技术和新的乘性更新算法的新颖子线性时间逼近算法,可用于解决一些机器学习优化问题,如训练线性分类器和查找最小包含球,此外,还用于解决一些核化版本的这些问题,如 SVM 等。此外,文章还在半流数据流设置中给出了实现,实现了第一个低通多项式空间和次线性时间算法。
Oct, 2010