BLOKS：利用草图化分块预条件扩展核求解器的规模

arXiv:2610.13382v1 公告类型：新提交 摘要：核岭回归（KRR）是一种具有坚实理论基础的非参数学习算法，也常被用于研究深度学习的性质。然而，精确的 KRR 形式所需的时间和内存开销使其无法适用于大型数据集，这推动了近似求解器的发展。这些算法依赖于：（i）迭代方法，以避免直接求解的计算负担；（ii）草图化或分批处理，以缩减问题规模；以及（iii）预条件，以加速收敛。虽然预条件对于快速收敛至关重要，但它也会带来内存开销。减少模型的自由参数数量可以控制这部分开销，却可能牺牲模型的表达能力，进而降低准确性。为应对这一挑战，我们提出了 BLOKS，这是一种基于共轭梯度法的求解器，用于经过 Nyström 草图化的 KRR，其核心是一种将分块 Jacobi 近似与草图化相结合的新型预条件器。BLOKS 预条件器的内存开销既不依赖于数据集大小，也不依赖于参数数量，因此能够扩展至大型模型。我们提供了一种内存高效、支持 GPU 加速的实现，并表明 BLOKS 在保持良好的时间和内存复杂度的同时，能够取得出色的准确性。事实上，在用于核求解器基准测试的标准大规模数据集上，BLOKS 的表现与最先进的方法相当或更优。