A multilevel sketch-and-solve method for overdetermined least squares problems

技术摘要：用于超定最小二乘问题的多级草图 - 求解方法

问题陈述
本文解决了求解大规模、高度超定线性最小二乘问题 $\min_x \|Ax - b\|_2$ 的计算挑战，其中 $A \in \mathbb{R}^{m \times n}$ 且 $m \gg n$。通过 QR 分解的经典解法会产生 $O(mn^2)$ 的成本，这对于巨大的 $m$ 而言是难以承受的。降低成本的标准方法是草图 - 求解（Sketch-and-Solve, SAS）范式，该范式利用随机草图矩阵 $S$ 将问题投影到更小的 $s \times n$ 规模。虽然 SAS 能以高概率提供良好的估计，但其残差误差取决于草图大小 $s$ 和子空间嵌入常数 $\eta$。为了提高精度，现有文献建议对多个独立的 SAS 估计量进行平均（简单蒙特卡洛）。作者研究了多级蒙特卡洛（Multilevel Monte Carlo, MLMC）框架（该框架结合了不同分辨率级别的估计量）是否能进一步改善此类特定问题的效率或精度。

方法：多级草图 - 求解（MLSAS）
作者提出了多级草图 - 求解（MLSAS）估计量，将随机微分方程（SDEs）中的 MLMC 范式适配到最小二乘问题中。

• 级别：该方法定义了 $L+1$ 个级别 $\ell \in \{0, \dots, L\}$，对应的草图大小为 $s_\ell = 2^{(\ell+1)}n$。
• 估计量构建：解 $x^*$ 通过跨级别求和修正项来近似：
  $$x_{MLMC} = \sum_{\ell=0}^L \frac{1}{N_\ell} \sum_{i=1}^{N_\ell} \Delta x^{(\ell)}_i$$
  其中 $\Delta x^{(\ell)} = x^{(\ell)} - x^{(\ell-1)}$ 表示精细级别解与粗糙级别解之间的差异。
• 对偶变量：一个关键的方法论特征是使用“对偶变量”（antithetic variables）来减少方差。对于级别 $\ell$，草图矩阵 $S_\ell$ 通过拼接两个独立的子草图 $S_a$ 和 $S_b$ 构建。粗糙解 $x^{(\ell-1)}$ 定义为分别使用 $S_a$ 和 $S_b$ 获得的解的平均值。精细解 $x^{(\ell)}$ 则使用组合矩阵 $S_\ell = \frac{1}{\sqrt{2}}[S_a; S_b]$ 获得。这种耦合确保了差异项 $\Delta x^{(\ell)}$ 的范数小于标准独立采样情况下的范数。
• 成本优化：作者探讨了重用较低级别的样本来计算更高级别的修正，以降低每样本成本 $C_\ell$，并指出在此特定实现中，放宽了级别间独立性的标准 MLMC 假设。

主要贡献与分析

1. 方差分析：本文提供了级别方差 $V_\ell = \text{Var}[A\Delta x^{(\ell)}]$ 的理论和数值分析。
   • 不使用对偶变量时，方差按 $O(1/s_\ell)$ 缩放。
   • 使用对偶变量时，作者通过解析证明和数值演示表明，方差按 $O(1/s_\ell^2)$ 缩放。这归因于在使用源自 $S_a$ 和 $S_b$ 的 $S_\ell$ 特定结构时，差异表达式 $A\Delta x^{(\ell)}$ 中的项相互抵消。
2. 偏差分析：估计量的偏差受最精细级别 $L$ 的偏差限制，随着草图大小 $s_L$ 的增加而减小。
3. 复杂度与成本比较：核心贡献是对 MLSAS 与简单蒙特卡洛（平均 $N$ 个独立 SAS 解）进行的严格成本分析。
   • 在标准 SDE 应用中，MLMC 将复杂度从 $O(\epsilon^{-3})$ 降低到 $O(\epsilon^{-2})$，因为最精细级别的方差保持恒定而成本增加。
   • 在最小二乘背景下，作者表明简单蒙特卡洛估计量的方差已经随草图大小减小（$O(1/s)$），而成本随 $s$ 线性增加。因此，实现目标方差 $\epsilon^2$ 的简单蒙特卡洛总成本为 $O(\epsilon^{-2})$，且独立于最大级别 $L$。
   • 作者推导出，即使经过优化的样本重用和对偶方差减少，MLSAS 估计量的总成本仍严格高于简单蒙特卡洛估计量。

结果

• 方差减少：数值实验证实，使用对偶变量显著降低了方差衰减的斜率，实现了 $V_\ell \propto 4^{-\ell}$（或 $O(1/s^2)$），而标准采样为 $O(1/s)$。
• 成本低效：尽管每个级别的方差减少更优，但生成样本的计算成本（主要由 QR 分解主导）在较低级别并未下降得足够快，以抵消多级结构带来的开销。研究发现，MLSAS 的总成本略高于简单平均独立 SAS 样本的成本。
• 相关性：作者调查了跨级别重用样本引入的相关性，发现其可忽略不计（$\rho < 10^{-2}$），这在实践目的上为在方差估计中忽略协方差项提供了理由，但这并未改变关于成本的结论。

意义与主张
本文得出结论：虽然多级蒙特卡洛框架是随机路径模拟中强大的方差减少技术，但从计算成本的角度来看，通过草图将其直接应用于超定最小二乘问题是缺乏吸引力的。

• 主要原因是，在最小二乘草图化中，“粗糙”级别相对于其方差贡献而言不够便宜，不足以证明多级开销的合理性，这与 SDE 中粗糙步骤极其便宜的情况不同。
• 作者指出，“多级方法的朴素应用似乎对最小二乘问题缺乏吸引力。”
• 本文声称是首个专门针对最小二乘问题研究多级蒙特卡洛方法的工作。
• 作者谦逊地建议，多级方法在并行化潜力方面可能仍有价值，尽管这被指出不在当前分析范围内。

总之，这项工作提供了一个严谨的否定性结果：对于在最小二乘问题中实现给定精度以最小化计算成本这一特定目标，简单平均草图 - 求解解的表现优于所提出的多级策略，尽管后者在方差减少方面具有理论优势。