arXiv:2410.11188cs.LG2024-10IJCAI被引 1

提出快速在线核学习方法,实时处理大规模推荐系统数据。

Fast Second-Order Online Kernel Learning through Incremental Matrix Sketching and Decomposition

  • 采用增量矩阵压缩与分解,实现高效核近似和特征映射构建。
  • 理论证明其后悔率对数增长,时间复杂度线性于预算,显著提升效率。
  • 适合高并发、对抗环境下的实时推荐系统,尤其在大规模数据上表现优异。

在线核学习(OKL)因其在流式环境中的出色预测性能受到广泛关注。二阶方法因能提供更优的后悔率保证而尤为吸引人,但现有方法在预设预算下至少具有二次时间复杂度,难以满足大规模流式推荐系统的实时需求。此外,获取显式特征映射所需的奇异值分解计算成本高昂,且缺乏增量更新机制,导致在对抗性环境和真实流式推荐数据集上表现不佳。为此,我们提出 FORKS,一种面向二阶在线核学习的快速增量矩阵压缩与分解方法。FORKS 构建了二阶核化梯度下降的增量维护范式,包含用于核近似的增量矩阵压缩和用于显式特征映射构造的增量矩阵分解。理论分析表明,FORKS 在保持预算线性时间复杂度的同时,达到与其它二阶方法相当的对数后悔率保证,显著提升了效率。我们在真实流式推荐数据集上进行了大量实验,验证了 FORKS 在可扩展性和抗对抗攻击方面的优越性能。

原文摘要 · Abstract (English)

Online Kernel Learning (OKL) has attracted considerable research interest due to its promising predictive performance in streaming environments. Second-order approaches are particularly appealing for OKL as they often offer substantial improvements in regret guarantees. However, existing second-order OKL approaches suffer from at least quadratic time complexity with respect to the pre-set budget, rendering them unsuitable for meeting the real-time demands of large-scale streaming recommender systems. The singular value decomposition required to obtain explicit feature mapping is also computationally expensive due to the complete decomposition process. Moreover, the absence of incremental updates to manage approximate kernel space causes these algorithms to perform poorly in adversarial environments and real-world streaming recommendation datasets. To address these issues, we propose FORKS, a fast incremental matrix sketching and decomposition approach tailored for second-order OKL. FORKS constructs an incremental maintenance paradigm for second-order kernelized gradient descent, which includes incremental matrix sketching for kernel approximation and incremental matrix decomposition for explicit feature mapping construction. Theoretical analysis demonstrates that FORKS achieves a logarithmic regret guarantee on par with other second-order approaches while maintaining a linear time complexity w.r.t. the budget, significantly enhancing efficiency over existing approaches. We validate the performance of FORKS through extensive experiments conducted on real-world streaming recommendation datasets, demonstrating its superior scalability and robustness against adversarial attacks.

在线学习核方法流式推荐增量计算

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。