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

Jul 23, 2026

Regularized Optimization on Grassmann Manifold: Theory, Algorithm and Applications

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.

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

Ask PDF

Sep 3, 2026

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

The computation of the Bures-Wasserstein (BW) barycenter of an ensemble of positive definite matrices arises throughout machine learning, optimal transport, and quantum information. Riemannian gradient descent (RGD) at unit step size -- the fixed-point iteration used in practice -- converges rapidly, yet existing analyses present a dichotomy: unit-step guarantees carry worst-case exponential dependence on the dimension, while dimension-independent guarantees require small step sizes that forfeit the empirical speed. We resolve this dichotomy, not by improving the guarantees for unit-step RGD, but by proposing a Projected RGD algorithm that achieves dimension-independent linear convergence at unit step size. The achieved rate,

(1 - κ^{-3/2})

, where

κ

is the condition number of the ensemble, also polynomially improves on the best small-step guarantee (

κ^{3/2}

versus

κ^{5/2}

iteration complexity). The crux is a novel Projection Lemma: clipping the eigenvalues of a positive matrix to an interval

[α, β]

is the closed-form, non-expansive (1-Lipschitz) BW-metric projection onto the set

\{S : αI \leq S \leq βI\}

-- a statement which, unlike its known one-sided counterpart, does not follow from convexity. The projection is moreover free: it reuses an eigendecomposition the next iteration must perform in any case, so the projected and unprojected iterations cost the same per step. The same analysis covers the invariant matrix projection problem of Brahmachari et al. (2025), whose fixed-point algorithm we identify as unit-step RGD on a totally geodesic submanifold, thereby extending the dimension-independent guarantee to that setting verbatim.

A. Afham

Centre for Quantum Technologies, National University of Singapore, Singapore

Riemannian Optimization Optimization Convergence Analysis Wasserstein Barycenters Optimal Transport

Ask PDF

Apr 25, 2026

Learning Curves and Benign Overfitting of Spectral Algorithms in Large Dimensions

Existing large-dimensional theory for spectral algorithms resolves either the optimally tuned point or the interpolation limit, but leaves the under-regularized regime unexplored. We study the learning curve and benign overfitting of spectral algorithms in the large-dimensional setting where the sample size and dimension are of comparable order, i.e.,

n \asymp d^γ

for some

γ>0

. We first consider inner-product kernels on the sphere

\mathbb{S}^{d-1}

and establish a sharp asymptotic characterization of the excess risk across the full regularization path under various source conditions

s \geq 0

, where

s

measures the relative smoothness of the regression function. Our results reveal that the learning curve is not simply U-shaped but instead consists of three distinct regimes: over-regularized, under-regularized, and interpolation regimes. This characterization allows us to fully capture the benign overfitting phenomenon, demonstrating that benign overfitting arises consistently across both the under-regularized and interpolation regimes whenever

s

is positive but no larger than a critical threshold. We further show that, in the sufficiently regularized regime, the kernel learning curve is recovered by an associated sequence model. Finally, we extend the learning-curve analysis to large-dimensional KRR for a class of kernels on general domains in

\mathbb{R}^d

whose low-degree eigenspaces satisfy spectral-scaling and hyper-contractivity conditions.

Weihao Lu, Qian Lin, Yingcun Xia +1

Department of Statistics and Data Science, National University of Singapore. · Department of Statistics and Data Science, Tsinghua University.

Kernel Ridge Regression Benign Overfitting Learning Curves Spectral Methods

Ask PDF

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