通过分块设计提升低秩近似效率，加速核岭回归
Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method
- 将原方法拆解为多个小块近似，降低计算开销
- 在相同预算下，谱尾估计更优，逼近精度更高
- 适合大规模核方法与优化问题，尤其数据谱衰减快时
Nyström 方法是处理核方法与凸优化中大型矩阵的常用低秩近似技术。然而，当数据呈现重尾谱衰减时，问题的有效维度可能过高，导致即使使用 Nyström 方法也超出计算预算。为此，我们提出 Block-Nyström 算法，通过在 Nyström 框架中引入块对角结构，显著降低计算成本，同时保持强逼近保证。我们证明，Block-Nyström 可用于构建改进的二阶优化预条件器，并高效求解希尔伯特空间上的核岭回归。关键洞察在于：在相同计算预算下，组合多个较小的 Nyström 近似，比使用单一更大的近似能获得更强的输入谱尾估计。此外，我们提出了高效的 Block-Nyström 矩阵逆递归预条件方案，并为一类广义近似核岭回归求解器提供了新的统计学习界。
原文摘要 · Abstract (English)
The Nyström method is a popular low-rank approximation technique for large matrices that arise in kernel methods and convex optimization. Yet, when the data exhibits heavy-tailed spectral decay, the effective dimension of the problem often becomes so large that even the Nyström method may be outside of our computational budget. To address this, we propose Block-Nyström, an algorithm that injects a block-diagonal structure into the Nyström method, thereby significantly reducing its computational cost while recovering strong approximation guarantees. We show that Block-Nyström can be used to construct improved preconditioners for second-order optimization, as well as to efficiently solve kernel ridge regression for statistical learning over Hilbert spaces. Our key technical insight is that, within the same computational budget, combining several smaller Nyström approximations leads to stronger tail estimates of the input spectrum than using one larger approximation. Along the way, we provide a novel recursive preconditioning scheme for efficiently inverting the Block-Nyström matrix, and provide new statistical learning bounds for a broad class of approximate kernel ridge regression solvers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。