提出SQUEAK算法，用更简单的方法实现高效核岭回归近似。
Pack only the essentials: Adaptive dictionary learning for kernel ridge regression
- 基于未归一化的岭杠杆得分，动态采样核矩阵列
- 空间复杂度仅比精确方法差常数倍，适合大规模数据
- 无需估计有效维度，适合资源受限的在线学习场景
核岭回归（KRR）在处理大规模数据时面临存储和计算瓶颈，其核矩阵需 O(n²) 空间。Nystrom 方法通过采样 m 列将空间复杂度降至 O(nm)，但均匀采样需 m 与核矩阵最大自由度成比例，可能达 O(n)。基于岭杠杆得分（RLS）的采样可实现更优性能，但精确计算 RLS 需 O(n²) 空间。现有 INK-Estimate 算法虽能在线更新，但依赖最大特征值，最坏情况下仍为 O(n)。本文提出 SQUEAK 算法，采用未归一化的 RLS，简化流程，无需估计有效维度，空间复杂度仅比精确 RLS 采样差一个常数因子。
原文摘要 · Abstract (English)
One of the major limits of kernel ridge regression (KRR) is that storing and manipulating the kernel matrix K_n for n samples requires O(n^2) space, which rapidly becomes unfeasible for large n. Nystrom approximations reduce the space complexity to O(nm) by sampling m columns from K_n. Uniform sampling preserves KRR accuracy (up to epsilon) only when m is proportional to the maximum degree of freedom of K_n, which may require O(n) columns for datasets with high coherence. Sampling columns according to their ridge leverage scores (RLS) gives accurate Nystrom approximations with m proportional to the effective dimension, but computing exact RLS also requires O(n^2) space. (Calandriello et al. 2016) propose INK-Estimate, an algorithm that processes the dataset incrementally and updates RLS, effective dimension, and Nystrom approximations on-the-fly. Its space complexity scales with the effective dimension but introduces a dependency on the largest eigenvalue of K_n, which in the worst case is O(n). In this paper we introduce SQUEAK, a new algorithm that builds on INK-Estimate but uses unnormalized RLS. As a consequence, the algorithm is simpler, does not need to estimate the effective dimension for normalization, and achieves a space complexity that is only a constant factor worse than exact RLS sampling.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。