Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms

Caixing Wang; Yue Wang

stat.MLOct 22, 2026

Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms

Authors: Caixing Wang, Yue Wang

Organizations: School of Statistics and Data Science, Southeast University, Nanjing, 210000, Jiangsu, China · Faculty of Business for Science and Technology, School of Management, University of Science and Technology of China, Hefei, 230000, Anhui, China

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\in (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.

Figures & tables

Figure 1: Illustration of the source range for optimality in our work. Panels from left to right represent the worst case ( $\alpha=1$ ), general case ( $\alpha\in[{1}/{\beta},1]$ ), and benign case ( $\alpha_{0}={1}/{\beta}$ ), respectively.

Method	Filter Function $g_{\lambda}(t)$	Parameters	Qualification $\tau$	$(E,\,F_{\tau})$
Tikhonov Regularization (KRR)	$\dfrac{1}{t+\lambda}$	$\lambda>0$	$1$	$(1,\,1)$
Iterative Regularization	$\displaystyle\sum_{k=1}^{l}\lambda^{k-1}(\lambda+t)^{-k}$	$l\in\mathbb{N}$	$l$	$(l,\,1)$
Gradient methods (GM)	$\displaystyle\sum_{k=1}^{l}\eta(1-\eta t)^{l-k}$	$\eta\in(0,\kappa^{2}],\ \lambda=\frac{1}{\eta l}$	any $\tau>0$	$\bigl(1,\ \max\{1,(\tau/e)^{\tau}\}\bigr)$
Spectral cutoff (SC)	$\displaystyle\begin{cases}1/t,&t\geq\lambda,\\ 0,&\text{otherwise}\end{cases}$	$\lambda>0$	any $\tau>0$	$(1,\,1)$

Table 1: Several common spectral algorithms, along with their corresponding filter functions, qualifications, and the associated constants.

Parameter	Concept	Intuitive Meaning
$\beta$	Capacity condition	Measures the complexity of the RKHS (a larger $\beta$ indicates a smaller space).
$\alpha$	Embedding condition	Controls the continuous embedding of the RKHS interpolation space into $L^{\infty}$ (a larger $\alpha$ reflects a weaker embedding).
$\alpha_{0}$	Embedding index	The smallest embedding exponent in the limiting sense.
$s$	Source condition	Characterizes the smoothness of target function (a larger $s$ implies a smoother function).
$\gamma$	Norm index	Determines the error evaluation norm ( $\gamma=0$ for standard $L^{2}$ error, $\gamma=1$ for RKHS error).

Table 2: Summary of technical parameters used in the main results.

Figure 2: Log empirical learning rates of SARP with different spectral algorithms and projection methods for the mis-specified case when $s=0.5$ averaged over 50 independent trials. The dashed lines represent the theoretical slopes. The gray lines represent the full spectral algorithms.

Figure 3: Log empirical learning rates of SARP with different spectral algorithms and projection methods for the well-specified case when $s=1.5$ averaged over 50 independent trials. The dashed lines represent the theoretical slopes. The gray lines represent the full spectral algorithms.

Figure 4: Log empirical learning rates of SARP with different spectral algorithms and projection methods for the well-specified case when $s=2$ averaged over 50 independent trials. The dashed lines represent the theoretical slopes. The gray lines represent the full spectral algorithms.

Figure 5: Performance of SARP with different spectral algorithms and projection methods on the USPS and cpusmall datasets. The gray lines represent the full spectral algorithms.

Algorithm	GAU	ROS	NY	ALS	Full
KRR	$0.825\pm 0.163$	$1.339\pm 0.612$	$0.258\pm 0.076$	$0.238\pm 0.010$	$2.425\pm 0.237$
GM	$0.883\pm 0.198$	$1.332\pm 0.628$	$0.230\pm 0.027$	$0.274\pm 0.002$	$0.661\pm 0.012$
SC	$0.899\pm 0.147$	$1.391\pm 0.590$	$0.309\pm 0.030$	$0.267\pm 0.011$	$3.342\pm 0.103$

Table 3: Computational time (in seconds) of different spectral algorithms and projection methods for

m=500

Generalization Bounds

Generalization bounds quantify how training performance can differ from population or test performance as sample size and model complexity change.

See all 162 papers

Regularized Optimization on Grassmann Manifold: Theory, Algorithm and Applications
Jul 23, 2026Zhuan Liang, Zheng ZhaiSpectral Regularization Riemannian Optimization
Department of Statistics, Faculty of Arts and Sciences at Beijing Normal University, Zhuhai
Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Size
Sep 3, 2026A. AfhamRiemannian Optimization Optimization Convergence Analysis
Centre for Quantum Technologies, National University of Singapore, Singapore
Learning Curves and Benign Overfitting of Spectral Algorithms in Large Dimensions
Apr 25, 2026Weihao Lu, Qian Lin, Yingcun Xia +1Kernel Ridge Regression Benign Overfitting
Department of Statistics and Data Science, National University of Singapore. · Department of Statistics and Data Science, Tsinghua University.

Jul 23, 2026J/K move · Enter open · S save

Regularized Optimization on Grassmann Manifold: Theory, Algorithm and Applications

Zhuan Liang, Zheng Zhai

Department of Statistics, Faculty of Arts and Sciences at Beijing Normal University, Zhuhai

Spectral Regularization Riemannian Optimization Nonconvex Optimization Graph Clustering Spectral Methods

Open paper AskPDF arXiv

Spectral methods are among the most widely used techniques for community detection, clustering, and graph learning. Their performance, however, critically depends on the accurate estimation of the underlying spectral subspace and can deteriorate substantially in the presence of noise, outliers, or model perturbations. To address this limitation, we propose a Regularized Projection Matrix Approximation (RPMA) framework for robust estimation of rank-

K

projection matrices. RPMA extends classical spectral projection by incorporating a regularization term, producing projection estimates that are more robust, sparse, and interpretable. We formulate the proposed model as an optimization problem on the manifold of rank-

K

projection matrices and exploit its geometric equivalence to the Grassmann manifold. Based on this manifold characterization, we derive the first- and second-order optimality conditions, establish the local stability of the regularized leading eigenspace, and characterize the stability of the critical-point landscape under sufficiently small regularization. To efficiently solve the resulting nonconvex optimization problem, we develop a Riemannian gradient projection algorithm with backtracking line search, together with a more efficient Cayley--Sherman--Morrison--Woodbury (Cayley--SMW) gradient method that avoids repeated eigendecompositions. Extensive experiments on both synthetic and real-world datasets demonstrate that RPMA substantially improves the recovery accuracy of projection matrices and consistently outperforms conventional spectral projection methods for community detection and clustering under noisy environments.

Abstract

Generalization Bounds

Explore similar work

Regularized Optimization on Grassmann Manifold: Theory, Algorithm and Applications

Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Size

Learning Curves and Benign Overfitting of Spectral Algorithms in Large Dimensions