随机投影谱算法性能大突破！Sobolev范数下学习率竟达极小极大最优，计算成本显著降低！
Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms
📖 AI 总结
该论文研究随机投影（RP）在谱算法中的泛化性能，针对现有分析多局限于特定核正则化算法、良好设定及严格条件的问题，提出在一般条件下不牺牲统计效率的改进分析。作者利用再生核希尔伯特空间的嵌入性质和算子相似性的精细分析，建立了Sobolev范数下达到极小极大下界（至多对数因子）的最优学习率。对于随机草图与Nyström子采样（均匀或基于杠杆分数）两种常见RP实现，证明达到最优性所需的投影维度与平均或最大有效维度成正比，从而在保持统计效率的同时显著降低计算成本。结果不依赖回归函数的一致有界性假设，适用于s>α₀−1/β的广泛源条件；在α₀=1/β的良好情形下，对所有s∈(0,2τ]均保持最优性。实验验证了理论有效性与实际效果。
🔑 关键词速览
| 随机投影 (Random Projections, RP) | 一种通过随机矩阵将高维数据映射到低维空间的技术，旨在降低计算和存储开销，同时近似保持数据的几何结构。 |
| 谱算法 (Spectral Algorithms) | 一类基于核矩阵特征分解或正则化算子谱理论的机器学习算法，常用于回归和分类任务。 |
| 再生核希尔伯特空间 (RKHS) | 由核函数定义的具有再生性质的希尔伯特空间，是核方法中函数表示和泛化分析的核心框架。 |
| Sobolev范数 (Sobolev Norms) | 一种衡量函数光滑性的范数，同时考虑函数本身及其导数的L^p范数，常用于非参数回归的误差分析。 |
| Nyström子采样 (Nyström Sub-sampling) | 一种通过选取部分列来近似核矩阵的低秩方法，常用于大规模核方法的加速。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅