Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms
Abstract
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 boundedness assumption on the regression function and are valid across a wide range of source conditions, i.e., s> α0−1/β, where s,β, and α0 denote the smoothness index, capacity index, and the embedding index, respectively. In the benign case when α0=1/β, the optimality holds for all s∈ (0,2τ] with τ and γ denoting the qualification index and norm index. Experimental results demonstrate both the theoretical validity and the practical effectiveness of the proposed method.
Related
- Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
- Sobolev inequalities for sections and projections of log-concave functions
- Sharp Sobolev inequalities on minimal immersions via optimal transport
- Intermediate coverings, random images, and projections
- Optimal interpolation formulas in the Sobolev space of periodic functions
BibTeX
@misc{wang2026random,
title = {{Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms}},
author = {Caixing Wang and Yue Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30948},
eprint = {2610.30948},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30948},
}
RIS
TY - UNPB
TI - Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms
AU - Caixing Wang
AU - Yue Wang
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.30948
UR - https://arxiv.org/abs/2610.30948
AB - 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 boundedness assumption on the regression function and are valid across a wide range of source conditions, i.e., s> α_0−1/β, where s,β, and α_0 denote the smoothness index, capacity index, and the embedding index, respectively. In the benign case when α_0=1/β, the optimality holds for all s∈ (0,2τ] with τ and γ denoting the qualification index and norm index. Experimental results demonstrate both the theoretical validity and the practical effectiveness of the proposed method.
ER -