Kernel-Based Regularized Learning with Random Projections: Beyond Least Squares

We consider kernel-based regularized learning with the help of the random projection technique to ease its computational burden. The random projection approaches we study here include the randomized sketching method and the Nystro"\m approximation method. Current works under the least squares loss demonstrated an optimal learning rate under an appropriate source condition and capacity condition. However, beyond this simplest loss, it seems challenging to appropriately incorporate both conditions due to the unavailability of a closed-form solution. In this work, we consider a sufficiently general class of convex losses which include logistic loss, quantile loss, and hinge loss, for example, and establish the same optimal learning rate as in the least squares case under mild regularity assumptions. Our result also covers the unattainable case where the true function is not in the reproducing kernel Hilbert space. To incorporate the source condition, Young's inequality for operators is used, while to characterize the capacity, Rademacher complexity is adopted. We illustrate the performances of random projection with some numerical examples. © 2025 Society for Industrial and Applied Mathematics.