主动回归考虑了一个线性回归问题，其中学习者会收到大量数据点，但只能观察到少数标签。由于在线算法可以处理增量培训数据并利用低计算成本，因此我们考虑了主动回归问题的在线扩展：学习者一一接收数据点，并立即决定是否应该收集相应的标签。目的是有效地维护收到的数据点的回归，并具有少量的标签查询回归。我们在$ \ ell_p $损失下为此问题提出了新算法，其中$ p \ in [1,2] $。要获得$（1+ \ epsilon）$ - 近似解决方案，我们提出的算法仅需要$ \ tilde {\ Mathcal {o}}（\ epsilon^{ - 2} d \ log（n \ kappa））$查询标签，其中$ n $是数据点的数量，而$ \ kappa $是数据点的数量，称为条件号。数值结果验证了我们的理论结果，并表明我们的方法与离线活性回归算法具有可比性的性能。

我们研究了用于线性回归的主动采样算法，该算法仅旨在查询目标向量$ b \ in \ mathbb {r} ^ n $的少量条目，并将近最低限度输出到$ \ min_ {x \ In \ mathbb {r} ^ d} \ | ax-b \ | $，其中$ a \ in \ mathbb {r} ^ {n \ times d} $是一个设计矩阵和$ \ | \ cdot \ | $是一些损失函数。对于$ \ ell_p $ norm回归的任何$ 0 <p <\ idty $，我们提供了一种基于Lewis权重采样的算法，其使用只需$ \ tilde {o}输出$（1+ \ epsilon）$近似解决方案（d ^ {\ max（1，{p / 2}）} / \ mathrm {poly}（\ epsilon））$查询到$ b $。我们表明，这一依赖于$ D $是最佳的，直到对数因素。我们的结果解决了陈和Derezi的最近开放问题，陈和Derezi \'{n} Ski，他们为$ \ ell_1 $ norm提供了附近的最佳界限，以及$ p \中的$ \ ell_p $回归的次优界限（1,2） $。我们还提供了$ O的第一个总灵敏度上限（D ^ {\ max \ {1，p / 2 \} \ log ^ 2 n）$以满足最多的$ p $多项式增长。这改善了Tukan，Maalouf和Feldman的最新结果。通过将此与我们的技术组合起来的$ \ ell_p $回归结果，我们获得了一个使$ \ tilde o的活动回归算法（d ^ {1+ \ max \ {1，p / 2 \}} / \ mathrm {poly}。 （\ epsilon））$疑问，回答陈和德里兹的另一个打开问题{n}滑雪。对于Huber损失的重要特殊情况，我们进一步改善了我们对$ \ tilde o的主动样本复杂性的绑定（d ^ {（1+ \ sqrt2）/ 2} / \ epsilon ^ c）$和非活跃$ \ tilde o的样本复杂性（d ^ {4-2 \ sqrt 2} / \ epsilon ^ c）$，由于克拉克森和伍德拉夫而改善了Huber回归的以前的D ^ 4 $。我们的敏感性界限具有进一步的影响，使用灵敏度采样改善了各种先前的结果，包括orlicz规范子空间嵌入和鲁棒子空间近似。最后，我们的主动采样结果为每种$ \ ell_p $ norm提供的第一个Sublinear时间算法。

科恩（Cohen）和彭（Peng）的开创性工作向理论计算机科学界推出了刘易斯（Lewis）的重量抽样，从而产生了快速采样算法的近似值$ d $二维子空间$ \ ell_p $ to $ \ ell_p $ to $ \ ell_p $ to $（1+ \ epsilon）$错误。几项工作将这一重要原始性扩展到其他设置，包括在线核心，滑动窗口和对抗流型模型。但是，这些结果仅适用于\ {1,2 \} $中的$ p \，$ p = 1 $的结果需要一个次优$ \ tilde o（d^2/\ epsilon^2）$样本。在这项工作中，我们设计了第一个几乎最佳的$ \ ell_p $ subspace嵌入在（0，\ infty）$中的所有$ p \ in Online Coreset，滑动窗口和对抗流型模型中的第一个$ p \。在所有三个模型中，我们的算法存储$ \ tilde o（d^{1 \ lor（p/2）}/\ epsilon^2）$行。这回答了[bdmmuwz2020]的主要开放问题的实质性概括，并给出了所有$ p \ notin \ {1,2 \} $的第一个结果。为了我们的结果，我们首先分析了“一击”采样行对其刘易斯重量的采样行采样，带有样品复杂性$ \ tilde o（d^{p/2}/\ epsilon^2）$对于$ p> 2 $。以前，该方案仅具有样品复杂性$ \ tilde o（d^{p/2}/\ epsilon^5）$，而$ \ tilde o（d^{p/2） }/\ epsilon^2）$是否使用了更复杂的递归抽样。递归抽样不能在线实施，因此需要对一击刘易斯重量采样进行分析。我们的分析使用与在线数字线性代数的新颖连接。 [MSSW2018]引入的复杂性参数$ \ mu $，我们显示第一个下限表明对$ \ mu $的线性依赖性是必要的。

大规模监督学习中的共同挑战是如何利用新的增量数据到预先训练的模型，而无需从头开始重新培训模型。受到这个问题的激励，我们重新审视动态最小二乘回归（LSR）的规范问题，其中目标是通过增量训练数据学习线性模型。在此设置，数据和标签$（\ mathbf {a} ^ {（t）}，\ mathbf {b} ^ {（t）}）\ in \ mathbb {r} ^ {t \ times d} \ times \ MathBB {R} ^ T $以在线方式发展（$ t \ gg d $），目标是有效地将（近似）解决方案保持为$ \ min _ {\ mathbf {x} ^ {（t）}} \ | \ mathbf {a} ^ {（t）} \ mathbf {x} ^ {（t）} - \ mathbf {b} ^ {（t）} \ | \ | \ |在$中的所有$ t \。我们的主要结果是一种动态数据结构，它将任意小的恒定近似解，与摊销更新时间$ o（d ^ {1 + o（1）}）$，几乎匹配静态的运行时间（草图 - 基于）解决方案。相比之下，对于精确的（甚至$ 1 / \ mathrm {poly}（n）$ - 准确性）解决方案，我们在静态和动态设置之间显示了分离，即动态LSR需要$ \ω（d ^ {2- O（1）}）OMV猜想下的摊销更新时间（Henzinger等，STOC'15）。我们的数据结构在概念上简单，易于实施，并且在理论和实践中快速速度，通过对合成和现实世界数据集的实验进行了证实。

我们研究了用$ q $ modes $ a \ in \ mathbb {r}^{n \ times \ ldots \ times n} $的近似给定张量的问题。图$ g =（v，e）$，其中$ | v | = q $，以及张张量的集合$ \ {u_v \ mid v \ in v \} $，以$ g $指定的方式收缩以获取张量$ t $。对于$ u_v $的每种模式，对应于$ v $的边缘事件，尺寸为$ k $，我们希望找到$ u_v $，以便最小化$ t $和$ a $之间的frobenius norm距离。这概括了许多众所周知的张量网络分解，例如张量列，张量环，塔克和PEPS分解。我们大约是二进制树网络$ t'$带有$ o（q）$核的大约$ a $，因此该网络的每个边缘上的尺寸最多是$ \ widetilde {o}（k^{o（dt） } \ cdot q/\ varepsilon）$，其中$ d $是$ g $的最大度，$ t $是其树宽，因此$ \ | a -t'-t'\ | _f^2 \ leq（1 + \ Varepsilon）\ | a -t \ | _f^2 $。我们算法的运行时间为$ o（q \ cdot \ text {nnz}（a）） + n \ cdot \ text {poly}（k^{dt} q/\ varepsilon）$，其中$ \ text {nnz }（a）$是$ a $的非零条目的数量。我们的算法基于一种可能具有独立感兴趣的张量分解的新维度降低技术。我们还开发了固定参数可处理的$（1 + \ varepsilon）$ - 用于张量火车和塔克分解的近似算法，改善了歌曲的运行时间，Woodruff和Zhong（Soda，2019），并避免使用通用多项式系统求解器。我们表明，我们的算法对$ 1/\ varepsilon $具有几乎最佳的依赖性，假设没有$ O（1）$ - 近似算法的$ 2 \至4 $ norm，并且运行时间比蛮力更好。最后，我们通过可靠的损失函数和固定参数可拖动CP分解给出了塔克分解的其他结果。

我们给出了一种基于草图的迭代算法，该算法计算$ 1 +\ varepsilon $近似解决方案，用于脊回归问题$ \ min_x \ | ax-b \ | ax-b \ | _2^2 +\ lambda \ lambda \ | x \ | x \ | _2^2 $ were $ a \ in r^{n \ times d} $带有$ d \ ge n $。我们的算法对于恒定数量的迭代（需要输入量的恒定通过），通过要求素描矩阵仅具有较弱的近似矩阵乘法（AMM）保证，可以改善早期工作（Chowdhury等人）（Chowdhury等人）。在$ \ varepsilon $上，以及恒定的子空间嵌入保证。相反，较早的工作要求素描矩阵具有取决于$ \ varepsilon $的子空间嵌入保证。例如，要在$ 1 $迭代中生产$ 1+\ varepsilon $近似解决方案，需要$ 2 $通过输入，我们的算法需要OSNAP嵌入$ m = o（n \ sigma^2/\ lambda \ lambda \ varepsilon \ varepsilon ）带有稀疏参数$ s = o（\ log（n））$的$行，而Chowdhury等人的早期算法。使用相同数量的OSNAP行需要稀疏$ s = o（\ sqrt {\ sigma^2/\ lambda \ varepsilon} \ cdot \ log（n））$，其中$ \ sigma = \ opnorm = \ opnorm {a}是矩阵$ a $的光谱规范。我们还表明，该算法可用于为内核脊回归提供更快的算法。最后，我们表明，我们的算法所需的草图大小实质上对于山脊回归算法的自然框架实质上是最佳的，它通过证明AMM的遗漏素描矩阵上的下限。 AMM的草图大小的下限可能具有独立的兴趣。

我们创建经典的（非量词）动态数据结构，为推荐系统和最小二乘回归的查询提供了与量子类似物相当的查询。近年来，这种算法的去量化引起了人们的关注。我们为这些问题获得了更清晰的界限。更重要的是，我们通过争辩说，这些问题的先前量子启发算法正在做杠杆或脊杠杆得分取样，以实现这些改进。这些是随机数值线性代数中强大而标准的技术。有了这种识别，我们能够在数值线性代数中采用大量工作来获得这些问题的算法，这些算法比现有方法更简单或更快（或两者兼而有之）。我们的实验表明，所提出的数据结构在现实世界数据集上也很好地工作。

在数值线性代数社区中，建议要获得诸如等级计算等各种问题的几乎最佳边界，找到最大线性独立的列（基础），回归或低秩近似，自然方式是解决尼尔森和尼文森的主要开放问题（Focs，2013）。该问题关于现有的忽略子空间嵌入的草图维度的对数因子，实现了恒因子近似的嵌入。我们展示了如何使用精细的草图技术绕过这个问题，并获得这些问题的最佳或几乎最佳的范围。我们使用的关键技术是基于不确定原理和提取器的Indyk的明确映射，在首次应用已知的漏窃子空间嵌入后，允许我们快速展开载体的质量，以便采样现在有效。由此，我们避免了在使用矩阵Chernoff不平等的界限中是标准的草图维度的对数因子。对于排名计算的基本问题和找到基础，我们的算法改善了张，郭和刘（Jacm，2013），并且在恒因因子和多个（日志日志（n）） - 因子中是最佳的。此外，对于恒定因子回归和低秩近似，我们给出了当前矩阵乘法指数的第一个最佳算法。

kronecker回归是一个高度结构的最小二乘问题$ \ min _ {\ mathbf {x}}} \ lvert \ mathbf {k} \ mathbf {x} - \ mathbf {b} \ rvert_ \ rvert_ {2}^2 $矩阵$ \ mathbf {k} = \ mathbf {a}^{（1）} \ otimes \ cdots \ cdots \ otimes \ mathbf {a}^{（n）} $是因子矩阵的Kronecker产品。这种回归问题是在广泛使用的最小二乘（ALS）算法的每个步骤中都出现的，用于计算张量的塔克分解。我们介绍了第一个用于求解Kronecker回归的子次数算法，以避免在运行时间中避免指数项$ o（\ varepsilon^{ - n}）$的$（1+ \ varepsilon）$。我们的技术结合了利用分数抽样和迭代方法。通过扩展我们对一个块是Kronecker产品的块设计矩阵的方法，我们还实现了（1）Kronecker Ridge回归的亚次级时间算法，并且（2）更新ALS中Tucker分解的因子矩阵，这不是一个不是一个纯Kronecker回归问题，从而改善了Tucker ALS的所有步骤的运行时间。我们证明了该Kronecker回归算法在合成数据和现实世界图像张量上的速度和准确性。

本文展示了如何适应$ k $ -MEANS问题的几种简单和经典的基于采样的算法，以使用离群值设置。最近，Bhaskara等人。 （Neurips 2019）展示了如何将古典$ K $ -MEANS ++算法适应与异常值的设置。但是，他们的算法需要输出$ o（\ log（k）\ cdot z）$ outiers，其中$ z $是true Outliers的数量，以匹配$ o（\ log k）$ - 近似值的$ k的近似保证$ -Means ++。在本文中，我们以他们的想法为基础，并展示了如何适应几个顺序和分布式的$ k $ - 均值算法，但使用离群值来设置，但具有更强的理论保证：我们的算法输出$（1+ \ VAREPSILON）z $ OUTLIERS Z $ OUTLIERS在实现$ o（1 / \ varepsilon）$ - 近似目标函数的同时。在顺序世界中，我们通过改编Lattanzi和Sohler的最新算法来实现这一目标（ICML 2019）。在分布式设置中，我们适应了Guha等人的简单算法。 （IEEE Trans。知道和数据工程2003）以及Bahmani等人的流行$ K $ -Means $ \ | $。 （PVLDB 2012）。我们技术的理论应用是一种具有运行时间$ \ tilde {o}（nk^2/z）$的算法，假设$ k \ ll z \ ll n $。这与Omacle模型中此问题的$ \ Omega（NK^2/z）$的匹配下限相互补。

求解线性系统的迭代方法的收敛速率$ \ mathbf {a} x = b $通常取决于矩阵$ \ mathbf {a} $的条件号。预处理是通过以计算廉价的方式减少该条件号来加速这些方法的常用方式。在本文中，我们通过左或右对角线重构重新审视如何最好地提高$ \ mathbf {a}条件号的数十年。我们在几个方向上取得了这个问题。首先，我们为缩放$ \ mathbf {a} $的经典启发式提供了新的界限（a.k.a.jacobi预处理）。我们证明了这种方法将$ \ MATHBF {a} $的条件号减少到最佳可能缩放的二次因素中。其次，我们为结构化混合包装和覆盖了Semidefinite程序（MPC SDP）提供了一个求解器，它计算$ \ mathbf {a} $ in $ \ widetilde {o}（\ text {nnz}（\ mathbf {a}）\ cdot \ text {poly}（\ kappa ^ \ star））$ time;这与在缩放到$ \ widetilde {o}（\ text {poly}（\ kappa ^ \ star））$ factors之后求解线性系统的成本匹配。第三，我们证明了足够一般的宽度无关的MPC SDP求解器将暗示我们考虑的缩放问题的近乎最佳的运行时间，以及与平均调理措施有关的自然变体。最后，我们突出了我们的预处理技术与半随机噪声模型的连接，以及在几种统计回归模型中降低风险的应用。

深度学习的成功以巨大的计算和能源成本，而训练大规模过度参数的神经网络的可伸缩性正成为AI进步的真正障碍。尽管传统反向传播通过梯度不错的传统反向传播的流行和低成本，但在理论和实践中，SGD在非凸面设置中具有高度的收敛速度。为了减轻这一成本，最近的工作提议采用替代性（牛顿型）培训方法，但收敛速度更快，尽管其每题成本更高。对于具有$ m = \ mathrm {poly}（n）$参数的典型神经网络，$ n $ datapoints in $ \ mathbb {r}^d $ of $ n $ datapoints的输入批次， Weinstein，ITCS'2021]需要$ \ sim mnd + n^3 $每次迭代。在本文中，我们提出了一种新颖的培训方法，它仅需要$ m^{1- \ alpha} n d + n^3 $摊销时间在同一过度叠加机制中，其中$ \ alpha \ in（0.01,1）$是某些固定常数。此方法依赖于神经网络的新替代视图，作为一组二进制搜索树，每个迭代都对应于修改树中节点的一小部分。我们认为，这种观点将在DNN的设计和分析中进一步应用。

我们提供了新的基于梯度的方法，以便有效解决广泛的病态化优化问题。我们考虑最小化函数$ f：\ mathbb {r} ^ d \ lightarrow \ mathbb {r} $的问题，它是隐含的可分解的，作为$ m $未知的非交互方式的总和，强烈的凸起功能并提供方法这解决了这个问题，这些问题是缩放（最快的对数因子）作为组件的条件数量的平方根的乘积。这种复杂性绑定（我们证明几乎是最佳的）可以几乎指出的是加速梯度方法的几乎是指数的，这将作为$ F $的条件数量的平方根。此外，我们提供了求解该多尺度优化问题的随机异标变体的有效方法。而不是学习$ F $的分解（这将是过度昂贵的），而是我们的方法应用一个清洁递归“大步小步”交错标准方法。由此产生的算法使用$ \ tilde {\ mathcal {o}}（d m）$空间，在数字上稳定，并打开门以更细粒度的了解凸优化超出条件号的复杂性。

算法高斯化是一种现象，当使用随机素描或采样方法生成较小的大数据集的较小表示时，可能会出现的现象：对于某些任务，已经观察到这些草图表示表现出许多可靠的性能特征，这些性能是在数据样本中出现的，这些性能来自次高斯随机设计，是一个强大的数据分布统计模型。但是，这种现象仅研究了特定的任务和指标，或依靠计算昂贵的方法。我们通过为平均值提供用于高斯数据分布的算法框架来解决这一问题，并证明可以有效构建几乎无法区分的数据草图（与亚高斯随机设计有关的总变化距离）。特别是，依靠最近引入的素描技术称为杠杆得分稀疏（少）嵌入，我们表明一个人可以构造$ n \ times d $矩阵$ a $的$ n \ times d $ sketch of $ n \ times d $ n \ ll n $，几乎与次高斯设计几乎没有区别$ a $中的非零条目的数量。结果，可以直接适用于我们的草图框架，可直接适用于我们的草图框架。我们通过对草图最小二乘正方形的新近似保证进行了说明。

我们研究了在存在$ \ epsilon $ - 对抗异常值的高维稀疏平均值估计的问题。先前的工作为此任务获得了该任务的样本和计算有效算法，用于辅助性Subgaussian分布。在这项工作中，我们开发了第一个有效的算法，用于强大的稀疏平均值估计，而没有对协方差的先验知识。对于$ \ Mathbb r^d $上的分布，带有“认证有限”的$ t $ tum-矩和足够轻的尾巴，我们的算法达到了$ o（\ epsilon^{1-1/t}）$带有样品复杂性$的错误（\ epsilon^{1-1/t}） m =（k \ log（d））^{o（t）}/\ epsilon^{2-2/t} $。对于高斯分布的特殊情况，我们的算法达到了$ \ tilde o（\ epsilon）$的接近最佳错误，带有样品复杂性$ m = o（k^4 \ mathrm {polylog}（d）（d））/\ epsilon^^ 2 $。我们的算法遵循基于方形的总和，对算法方法的证明。我们通过统计查询和低度多项式测试的下限来补充上限，提供了证据，表明我们算法实现的样本时间 - 错误权衡在质量上是最好的。

We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to robustness which can produce private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy for a wide range of fundamental high-dimensional parameter estimation problems, including mean and covariance estimation. We show that this reduction can be implemented in polynomial time in some important special cases. In particular, using nearly-optimal polynomial-time robust estimators for the mean and covariance of high-dimensional Gaussians which are based on the Sum-of-Squares method, we design the first polynomial-time private estimators for these problems with nearly-optimal samples-accuracy-privacy tradeoffs. Our algorithms are also robust to a constant fraction of adversarially-corrupted samples.

我们提出了一种输入稀疏时间抽样算法，该算法可以近似于$ q $ - 折叠的列量张量产品$ q $矩阵的量子矩阵，使用几乎最佳的样品，从（q）$因素。此外，对于数据集的$ q $倍自量量的重要特殊情况，这是学位的功能矩阵-y $ q $ polyenmial kernel，我们方法运行时的领先术语与该方法的大小成正比输入数据集，并且不依赖$ Q $。以前的技术要么在其运行时产生Poly $（Q）$的放缓，要么以$ Q $的依赖性为代价，但要以次优目标维度为代价，并在其运行时四处依赖于数据点的数量。我们的抽样技术依赖于$ q $部分相关的随机预测的集合，这些预测可以同时应用于数据集$ x $的总时间，这仅取决于$ x $的大小，同时又有其$ q $ - fold kronecker产品在$ x^{\ otimes q} $的列跨度中的任何固定向量的近乎等值线。我们还表明，我们的采样方法概括为多项式以外的其他类别的内核，例如高斯和神经切线核。

我们在高斯分布下使用Massart噪声与Massart噪声进行PAC学习半个空间的问题。在Massart模型中，允许对手将每个点$ \ mathbf {x} $的标签与未知概率$ \ eta（\ mathbf {x}）\ leq \ eta $，用于某些参数$ \ eta \ [0,1 / 2] $。目标是找到一个假设$ \ mathrm {opt} + \ epsilon $的错误分类错误，其中$ \ mathrm {opt} $是目标半空间的错误。此前已经在两个假设下研究了这个问题：（i）目标半空间是同质的（即，分离超平面通过原点），并且（ii）参数$ \ eta $严格小于$ 1/2 $。在此工作之前，当除去这些假设中的任何一个时，不知道非增长的界限。我们研究了一般问题并建立以下内容：对于$ \ eta <1/2 $，我们为一般半个空间提供了一个学习算法，采用样本和计算复杂度$ d ^ {o_ {\ eta}（\ log（1 / \ gamma） ）））}} \ mathrm {poly}（1 / \ epsilon）$，其中$ \ gamma = \ max \ {\ epsilon，\ min \ {\ mathbf {pr} [f（\ mathbf {x}）= 1]， \ mathbf {pr} [f（\ mathbf {x}）= -1] \} \} $是目标半空间$ f $的偏差。现有的高效算法只能处理$ \ gamma = 1/2 $的特殊情况。有趣的是，我们建立了$ d ^ {\ oomega（\ log（\ log（\ log（\ log））}}的质量匹配的下限，而是任何统计查询（SQ）算法的复杂性。对于$ \ eta = 1/2 $，我们为一般半空间提供了一个学习算法，具有样本和计算复杂度$ o_ \ epsilon（1）d ^ {o（\ log（1 / epsilon））} $。即使对于均匀半空间的子类，这个结果也是新的;均匀Massart半个空间的现有算法为$ \ eta = 1/2 $提供可持续的保证。我们与D ^ {\ omega（\ log（\ log（\ log（\ log（\ epsilon））} $的近似匹配的sq下限补充了我们的上限，这甚至可以为同类半空间的特殊情况而保持。

我们考虑培训多层过参数化神经网络的问题，以最大限度地减少损失函数引起的经验风险。在过度参数化的典型设置中，网络宽度$ M $远大于数据维度$ D $和培训数量$ N $（$ m = \ mathrm {poly}（n，d）$），其中诱导禁止的大量矩阵$ w \ in \ mathbb {r} ^ {m \ times m} $每层。天真地，一个人必须支付$ O（m ^ 2）$时间读取权重矩阵并评估前向和后向计算中的神经网络功能。在这项工作中，我们展示了如何降低每个迭代的培训成本，具体而言，我们提出了一个仅在初始化阶段使用M ^ 2美元的框架，并且在$ M $的情况下实现了每次迭代的真正子种化成本。 ，$ m ^ {2- \ oomga（1）} $次迭代。为了获得此结果，我们利用各种技术，包括偏移的基于Relu的稀释器，懒惰的低级维护数据结构，快速矩阵矩阵乘法，张量的草图技术和预处理。

我们提出了一个算法框架，用于近距离矩阵上的量子启发的经典算法，概括了Tang的突破性量子启发算法开始的一系列结果，用于推荐系统[STOC'19]。由量子线性代数算法和gily \'en，su，low和wiebe [stoc'19]的量子奇异值转换（SVT）框架[SVT）的动机[STOC'19]，我们开发了SVT的经典算法合适的量子启发的采样假设。我们的结果提供了令人信服的证据，表明在相应的QRAM数据结构输入模型中，量子SVT不会产生指数量子加速。由于量子SVT框架基本上概括了量子线性代数的所有已知技术，因此我们的结果与先前工作的采样引理相结合，足以概括所有有关取消量子机器学习算法的最新结果。特别是，我们的经典SVT框架恢复并经常改善推荐系统，主成分分析，监督聚类，支持向量机器，低秩回归和半决赛程序解决方案的取消结果。我们还为汉密尔顿低级模拟和判别分析提供了其他取消化结果。我们的改进来自识别量子启发的输入模型的关键功能，该模型是所有先前量子启发的结果的核心：$ \ ell^2 $ -Norm采样可以及时近似于其尺寸近似矩阵产品。我们将所有主要结果减少到这一事实，使我们的简洁，独立和直观。