Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms
Random projections (RP) offer a powerful way to reduce the $O(n^3)$ cost of kernel spectral algorithms, but existing theory has largely been confined to well-specified settings or narrow mis-specified regimes under restrictive boundedness assumptions. This paper establishes high-probability minimax optimal learning rates in Sobolev norms for RP-based spectral algorithms under general source conditions and a Bernstein noise condition, without assuming uniform boundedness of the regression function $f_\rho$. By exploiting the RKHS embedding property and a refined operator similarity analysis, the authors enlarge the optimal source range from $s \geq 1 - 1/\beta$ to $s > \alpha_0 - 1/\beta$, showing that projection dimensions proportional to the effective dimension preserve statistical efficiency while yielding substantial computational savings.
The paper makes a solid theoretical contribution by broadening the conditions under which random projection-based spectral algorithms achieve minimax optimality. The key advance is a rigorous high-probability analysis in Sobolev norms under general source conditions, removing the uniform boundedness assumption on $f_\rho$ and pushing the valid source range from $s \geq 1 - 1/\beta$ to $s > \alpha_0 - 1/\beta$. The bounds are sharp and accompanied by matching lower bounds; however, the practical impact is partially limited by the abstract nature of the embedding index $\alpha_0$ and the explicit exclusion of the saturation regime $s > 2\tau$.
The mathematical analysis is careful and structurally sound. The decomposition into approximation, empirical, and projection errors is standard but executed with non-trivial refinements, particularly the new lemma bounding $\|P\phi(C_{K,n})P - \phi(PC_{K,n}P)\|$ via a block-operator decomposition rather than spectral perturbation. The minimax lower bound in Theorem 1 under general source conditions is a genuine advance, and the upper bounds in Theorems 2 and 3 align with it in the prescribed regime.
Several limitations temper the strength of the claims. First, the theory is restricted to $s \in (0, 2\tau]$, explicitly excluding the saturation regime $s > 2\tau$ where inverse-problem theory suggests rates plateau; the authors acknowledge this but leave it unresolved. Second, the noise assumption remains fairly restrictive: while the uniform boundedness of $f_\rho$ is removed, the Bernstein condition on $\varepsilon$ still excludes heavy-tailed noise, and the authors admit adapting to finite-moment settings is future work.
Third, the experimental section is weak for a theory paper: the synthetic experiments merely confirm asymptotic slopes on a single toy kernel, and the real-data applications are limited to two UCI datasets without reporting confidence intervals or rigorous non-asymptotic verification of the projection dimension scaling.
The evidence supports the theoretical claims reasonably well within the paper's scope, but comparisons are largely self-referential. The authors correctly position their results against Lin and Cevher (2020a), Yang et al. (2017), and Rudi et al. (2015), noting that earlier works treated only $s \geq 1$ or $s \geq 1-1/\beta$. The synthetic experiments corroborate the predicted rates for KRR, gradient methods, and spectral cutoff across several projection strategies, which adds confidence. However, the experiments do not independently probe the boundary case $s \leq \alpha_0 - 1/\beta$ where suboptimality is predicted, nor do they validate the specific logarithmic factors or the constants hidden in the $\lesssim$ notation.
Reproducing the theoretical results is feasible for experts in learning theory, as the proof strategy follows a clear bias-variance-projection decomposition and cites standard concentration tools. However, several practical barriers exist. The proof of the key block-operator lemma and several supporting results are deferred to a supplementary material that was not provided in the document. Hyperparameter selection is crucial: the theorems prescribe $\lambda \asymp \Phi^{-1}(n^{-1})$ and projection dimensions scaling with effective dimensions that depend on unknown quantities ($\alpha_0$, $\beta$, $s$), making the bounds non-constructive without oracle knowledge. The code for the numerical experiments is not mentioned or linked, and the real-data experiments depend on the NNI toolbox for tuning, which introduces an external uncontrolled variable.
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\"{o}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> \alpha_0-1/\beta$, where $s,\beta$, and $\alpha_0$ denote the smoothness index, capacity index, and the embedding index, respectively. In the benign case when $\alpha_0=1/\beta$, the optimality holds for all $s\in (0,2\tau]$ with $\tau$ and $\gamma$ denoting the qualification index and norm index. Experimental results demonstrate both the theoretical validity and the practical effectiveness of the proposed method.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.