Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms

Caixing Wang, Yue Wang

Random projections (RP) offer an effective method for reducing computational and storage overhead while preserving the geometric structure of data. However, existing studies have primarily focused on the optimal generalization performance of specific kernel-regularized algorithms with RP in the well-specified setting and under restrictive conditions. In this paper, we provide a comprehensive and improved analysis of the generalization performance of RP-based spectral algorithms under general conditions \change{without sacrificing statistical efficiency}. By leveraging the embedding property of the reproducing kernel Hilbert space (RKHS) and a refined analysis of the operator similarity, we establish optimal learning rates in Sobolev norms that match the minimax lower bounds up to logarithmic factors. For two common implementations of RP, randomized sketches and Nyström sub-sampling (uniform or leverage-based), we show that the projection dimension required for optimality is proportional to the average or maximal effective dimension, yielding a significant reduction in computational cost while maintaining the statistical efficiency. Our results do not rely on the uniform…