回归问题的运行时间保证
探讨了在普通最小二乘回归中,找到或推翻删除数据集中的小子集会反转系数符号的实用算法;通过实证研究了用于此任务的成熟算法技术在一般线性回归问题和特殊情况下的精确贪婪方法方面的性能,证明这些方法在几个维度的回归问题中优于现有技术并提供了实用的鲁棒性检查;但对于维度为 3 或更高的回归问题中推翻这种小型影响样本存在性的重要任务仍存在显著的计算瓶颈;通过使用源自算法稳健统计的最新创新思想的谱算法在这一挑战中取得了一些进展;总结了在几个挑战数据集中,已知技术的限制,以促进进一步的算法创新。
Jul, 2023
本文提出了一种基于采样技术和新的乘性更新算法的新颖子线性时间逼近算法,可用于解决一些机器学习优化问题,如训练线性分类器和查找最小包含球,此外,还用于解决一些核化版本的这些问题,如 SVM 等。此外,文章还在半流数据流设置中给出了实现,实现了第一个低通多项式空间和次线性时间算法。
Oct, 2010
提出一种基于平均加速正则梯度下降的算法,通过细化初值和 Hessian 矩阵的假设,最优地优化回归问题,并证明其在偏差与方差之间具有最优性、大数据时初始化影响可达到 O(1/n2)以及对于维度 d 的依赖程度为 O(d/n)。
Feb, 2016
本文提供了一种新的矩阵估算近似保证方法,其基于约束强凸性和平滑性的标准假设。同时,本文揭示了低秩估算和组合优化之间的新联系,并针对两个重要的现实问题提供了贪心估计与基准估计间的经验比较。
Mar, 2017
通过矩阵分解和投影梯度下降算法解决约束最优化问题,提供了一种通用理论框架,当给定适当的初始化时,可以几何级数地收敛到具有统计意义的解,适用于许多具体模型。
Sep, 2015
通过复杂性理论的标准假设(NP 不在 P/poly),我们证明了稀疏线性回归的极小化预测风险可以由多项式时间算法实现,但实际上实现优化算法时,二者之间存在差距。特别是在设计矩阵不良条件下,多项式时间算法可以实现的极小化预测损失可能会明显高于优化算法。这是首个已知的多项式和最优算法在稀疏线性回归中的差距,而且不依赖于平均时间复杂度的猜想。
Feb, 2014
本论文研究线性回归问题并提出了一种新的算法,它能够在存在离群值的情况下,对有限矩(至 $L_4$)的样本进行最佳的次高斯误差边界估计,并且通过使用谱方法研究了线性回归问题与最远超平面问题之间的关系,同时引入了第三个经验过程进行统计学属性的研究。
Jul, 2020
本文首次给出了一个多项式时间算法,用于在示例和标签中对抗性堕落下执行线性或多项式回归,并基于 SoS 方法提出了一种自然的凸松弛方法来解决非凸优化问题。
Mar, 2018
本文讨论了随机优化中的种群风险以及解决大规模问题中经验风险计算的困难,提出了一种基于随机梯度下降算法的解决方案,以 OLS 估计器为基础进行最小化种群风险的近似。
Nov, 2016