Abstract: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.
| Comments: | 54 pages, 20 figures |
| Subjects: | Machine Learning (cs.LG) |
| MSC classes: | 68T05, 68Q32, 62L20 |
| Cite as: | arXiv:2510.04237 [cs.LG] |
| (or arXiv:2510.04237v5 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2510.04237 arXiv-issued DOI via DataCite |
From: JinHui Bai [view email]
[v1]
Sun, 5 Oct 2025 15:04:03 UTC (3,921 KB)
[v2]
Fri, 10 Oct 2025 13:00:59 UTC (3,921 KB)
[v3]
Thu, 30 Oct 2025 09:14:25 UTC (3,921 KB)
[v4]
Sat, 10 Jan 2026 13:43:49 UTC (3,915 KB)
[v5]
Fri, 17 Apr 2026 06:06:52 UTC (5,256 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。