Dec, 2023

路径稀疏 Lasso 的量子算法

PDF
TL;DR我们提出了一种新颖的量子高维线性回归算法，基于经典的 LARS（最小角度回归）路径算法，通过引入量子求解子程序和近似量子最小寻找子程序，实现在目标参数变化时得到完整的正则化路径，以相对比较快的速度实现了二次加速。我们的研究还证明了 LARS 算法和我们的量子算法对误差具有鲁棒性，并给出了关于未知系数向量和近似 Lasso 解的界限。
quantum high-dimensional linear regression algorithmlarsquantum algorithmapproximate quantum minimum-finding subroutinelasso cost function
发现论文，激发创造
  • 重访线性回归的量子算法：无数据依赖参数的二次加速

    线性回归是最基本的线性代数问题之一，本研究提出了一个运行时间为 O (ε^(-1) * sqrt (n) * d^(1.5)) + poly (d/ε) 的量子算法，可以在不依赖数据相关参数的情况下，提供 n 的二次量子加速效果，同时还将结果推广到多次回归和岭线性回归。

    Nov, 2023

  • 量子梯度下降用于线性系统和最小二乘法

    本文提出了一种基于量子机器学习和优化方法的梯度下降算法，通过解决线性方程组问题，构建了一种基于 QRAM 数据结构模型的量子线性系统求解器，并应用于求解正定线性系统和权重最小二乘问题，具有较小的计算成本和内存需求。

    Apr, 2017

  • 广义 Lasso 的解路径

    本文提出了一种计算广义套索问题路径的基于对偶问题的算法，能够解决广泛的应用场景，并通过对 $I$ 的情况，与 LARS 算法建立联系，并导出了广义套索拟合的自由度的无偏估计，该估计在很多应用中都非常直观。

    May, 2010

  • 量子数据拟合

    提供一种新的量子算法，通过基于解决线性方程组的有效算法（Harrow et al. Phys. Rev. Lett. 103, 150502（2009））来高效确定指数级数据集上最小二乘拟合的质量。在许多情况下，我们的算法还可以高效地找到简洁的函数来逼近要拟合的数据并限制逼近误差。对于输入数据为纯量子态的情况，该算法可以用于提供量子态的有效参数估计，因此可以作为给定容错量子计算机的完整量子态测量的替代方案。

    Apr, 2012

  • 一种可靠且高效的 Lasso 调参方案与优化保障算法

    介绍了一种新颖的方案，用于在具有 Lasso 的高维线性回归中选择正则化参数，该方案受非参数回归中带宽选择的 Lepski 方法的启发，具有最佳的有限样本保证和快速算法。

    Oct, 2014

  • 基于最短绝热演化和量子近似优化算法的量子线性系统求解器

    通过经过最佳调度函数的纵向绝热量子计算法 (AQC)，可以解决一个量子线性系统问题 (with O (kappa poly (log (kappa/epsilon)) 的运行时间 (其中 kappa 为条件数，epsilon 为目标精度），我们的方法适用于一般非厄米矩阵，当限制在厄米矩阵上时，该方法可以减少成本和量子比特的数量，最近提出的随机化方法，数值结果表明，在最短时间内，QAOA 可以相较于最优时间 AQC、香草 AQC 和最近推出的随机化方法取得最低的运行时间。

    Sep, 2019

  • 基于近端点算法的量子线性系统问题的催化剂框架

    通过选择合适的步长 η，本文提出了一种新的量子算法，对量子线性系统问题（QLSP）进行求解，解决了之前方法中依赖条件数的问题。

    Jun, 2024

  • Lasso 惩罚回归的坐标下降算法

    本文研究了基于 lasso 惩罚的回归问题，并提出了两个非常快的算法来估计回归系数，其中一个算法基于循环坐标下降，而另一个基于贪心坐标下降和 Edgeworth 的算法。此外，如果对参数进行分组并对每个组进行惩罚，则可以将现有算法扩展到新领域。

    Mar, 2008

  • 路径坐标优化

    本文介绍了 “逐一” 坐标下降算法及其在 $ L_1 $- 惩罚回归（套索）、garotte 和弹性网络等相关方法中的应用，证明了该算法可以与广泛应用的 LARS（或同伦）过程竞争，在大规模 lasso 问题中引起了不少关注。但注意到它并不适用于 “融合 Lasso”，所以论文提出了一个广义算法，在比标准的凸优化器运行时间更短的时间内得出了解决方案。最后，将该过程推广到二维融合 Lasso，并展示了其在一些图像平滑问题上的性能。

    Aug, 2007

  • 基于混合量子计算的非线性回归

    该研究论文提出了一种将非线性引入量子机器学习中的方法，使用特征映射将经典数据导入到量子状态中，并基于混合量子计算机进行实现，提出了可实现著名的多项式回归和高斯核岭回归的编码方案，其处理信息效率具有指数级加速并且适用于大规模数据集。

    Aug, 2018