基于随机投影的素描重建:一种可证明的用于大规模高维数据的恢复算法
本文研究了随机草图方法,以近似解决带有一般凸约束的最小二乘问题,并提出了一种名为迭代 Hessian 草图的新方法,同时提供了数值模拟实验,包括面部表情分类实验。
Nov, 2014
本文提出了一种名为 Dual Random Projection 的简单算法,通过将高维数据映射到低维子空间来减少计算成本,使用低维优化问题的对偶解来恢复原始优化问题的最优解,并分析了算法的理论依据。
Nov, 2012
利用随机矩阵的谱分析最新进展,我们开发了一种新的技术,提供了随机投影矩阵的期望值的确切表达式,这些表达式可以用来表征多种常见的机器学习任务中的降维性能,包括低秩估计和迭代随机优化等。我们的结果适用于多种流行的草图方法,包括高斯和 Rademacher 草图,结果表明,我们推导出的表达式反映了这些草图方法的实际性能,甚至体现了较低阶效应和恒定因子。
Jun, 2020
本文研究了在解决变量数量和数据点数量都很大的有限和最优化问题的 Newton 法的背景下,两种数据空间维数缩减方法:Hessian 子采样和随机 Hadamard 变换。通过一系列数字实验和 Hessian 子采样方法的复杂性分析,揭示了使用共轭梯度方法相对于随机梯度迭代方法的优势。
May, 2017
提出一种随机扩展的原始 - 对偶混合梯度算法用于解决在对偶变量中可分离的鞍点问题,该算法适用于一般的凸凹鞍点问题和部分平滑 / 强凸或完全平滑 / 强凸问题,并且在任意抽样的对偶变量中,有多个变体的随机方法在各种图像任务中显着优于确定性变体。
Jun, 2017
基于神经网络内在维度的研究,我们提出并研究了一种可扩展的草图算法设计空间,并在训练数据归因、Hessian 谱分析和精调预训练语言模型的内在维度计算三个应用中验证了我们方法的有效性。
Feb, 2024
该研究提出了一种随机化的二阶优化方法 ——Newton Sketch,使用随机投影或子采样 Hessian 实现近似牛顿步。对于自共轭函数,该算法证明具有超线性收敛和指数高概率,与条件数和相关问题独立的收敛和复杂度保证。对于适当的初始化,即使在没有自共轭的情况下,也可以保证类似的保证对于强凸和光滑的目标。我们还描述了将我们的方法扩展到具有自共轭屏障的凸约束程序。我们讨论和说明了其应用于线性程序,带有凸约束的二次程序,逻辑回归和其他广义线性模型以及半定规划的扩展问题。
May, 2015
本文提出了一种分布式加速线性回归的方法,通过使用随机化草稿技术和改善异步系统中的顽固者韧性来确保安全性,同时应用随机齐次正交矩阵和子采样块来安全获取信息和减少回归问题的维度。
Aug, 2023
提出了一种新的随机迭代算法 —— 随机对偶上升 (SDA),用于在线性系统的解空间中找到给定向量的投影。该算法通过随机矩阵的列子空间上的精心选择点来更新对偶变量,并证明了与对偶过程相关的原始迭代会期望指数级别收敛至投影。SDA 收敛于一致性之外的无其他假设的线性系统,特殊情况下,该方法可用于分布式平均共识问题,产生各种新算法。
Dec, 2015
该论文介绍了一种称为 “sketching” 的数据压缩技术,该技术通过随机投影将大型数据集压缩成较小的替代数据集,然后进行统计分析,该方法特别适用于大规模的线性回归问题。
Jun, 2017