新算法让核梯度下降更快更省,适合大规模数据。
Truncated Kernel Stochastic Gradient Descent with General Losses and Spherical Radial Basis Functions
- 用球形径向基函数投影梯度到低维空间,自适应调节泛化能力。
- 证明了迭代结果和平均结果均达最优收敛速度。
- 计算量大幅降低,适合流式数据处理,可推广至多种损失函数。
本文提出一种新型核随机梯度下降算法,用于大规模监督学习中的广义损失优化。相比传统核SGD,通过球形径向基函数的无穷级数展开,将随机梯度投影至自适应缩放的有限维假设空间,提升泛化性能。基于对核诱导协方差算子谱结构的新估计,建立统一的优化与泛化分析框架,证明最后迭代值和后缀平均值均以极小最大率收敛,并在再生核希尔伯特空间中实现最优强收敛。该框架适用于最小二乘、Huber及逻辑损失等经典损失函数。算法结合线性SGD的坐标更新机制,避免核SGD中耗时的成对运算,显著降低计算复杂度并达到最优存储复杂度,支持高效流式数据处理。大量数值实验验证了方法的有效性。
原文摘要 · Abstract (English)
In this paper, we propose a novel kernel stochastic gradient descent (SGD) algorithm for large-scale supervised learning with general losses. Compared to traditional kernel SGD, our algorithm improves efficiency and scalability through an innovative regularization strategy. By leveraging the infinite series expansion of spherical radial basis functions, this strategy projects the stochastic gradient onto a finite-dimensional hypothesis space, which is adaptively scaled according to the bias-variance trade-off, thereby enhancing generalization performance. Based on a new estimation of the spectral structure of the kernel-induced covariance operator, we develop an analytical framework that unifies optimization and generalization analyses. We prove that both the last iterate and the suffix average converge at minimax-optimal rates, and we further establish optimal strong convergence in the reproducing kernel Hilbert space. Our framework accommodates a broad class of classical loss functions, including least-squares, Huber, and logistic losses. Moreover, the proposed algorithm significantly reduces computational complexity and achieves optimal storage complexity by incorporating coordinate-wise updates from linear SGD, thereby avoiding the costly pairwise operations typical of kernel SGD and enabling efficient processing of streaming data. Finally, extensive numerical experiments demonstrate the efficiency of our approach.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。