On the Saturation Effects of Spectral Algorithms in Large Dimensions

Weihao Lu, Haobo Zhang, Yicheng Li, Qian Lin · 2025

Read On the Saturation Effects of Spectral Algorithms in Large Dimensions by Weihao Lu, Haobo Zhang, Yicheng Li, Qian Lin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-00504.txt.

Introduction

Weihao Lu and three co-authors study a flaw in a class of learning methods in a 2025 paper. These spectral methods fit curves to data, and a known flaw caps their gains when the true curve is too smooth. The flaw was seen for near twenty years and proved of late for fixed-size inputs.

The team asks how the flaw acts when inputs are huge, with size tied to sample count by a power rule. They prove a sharper floor for the best sound error, then show a flow method with early stops can hit that floor. The work maps when smooth truths beat the tools that chase them.

Catalog record

CREATORWeihao Lu, Haobo Zhang, Yicheng Li, Qian Lin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE155 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-00504

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Saturation Effects of Spectral Algorithms in Large Dimensions Weihao Lu, Haobo Zhang, Yicheng Li, Qian Lin Abstract The saturation effects, which originally refer to the fact that kernel ridge regression (KRR) fails to achieve the information-theoretical lower bound when the regression function is over-smooth, have been observed for almost 20 years and were rigorously proved recently for kernel ridge regression and some other spectral algorithms over a fixed dimensional domain. The main focus of this paper is to explore the saturation effects for a large class of spectral algorithms (including the KRR, gradient descent, etc.) in large dimensional settings where n ≍ d γ n\asymp d^{\gamma} . More precisely, we first propose an improved minimax lower bound for the kernel regression problem in large dimensional settings and show that the gradient flow with early stopping strategy will result in an estimator achieving this lower bound (up to a logarithmic factor). Similar to the results in KRR, we can further determine the exact convergence rates (both upper and lower bounds) of a large class of (optimal tuned) spectral algorithms with different qualification τ \tau ’s. In particular, we find that these exact rate curves (varying along γ \gamma ) exhibit the periodic plateau behavior and the polynomial approximation barrier. Consequently, we can fully depict the saturation effects of the spectral algorithms and reveal a new phenomenon in large dimensional settings (i.e., the saturation effect occurs in large dimensional setting as long as the source condition s > τ s>\tau while it occurs in fixed dimensional setting as long as s > 2 ​ τ s>2\tau ). 1 Introduction Let’s assume we have n i.i.d. samples (x_{i},y_{i}) from a joint distribution supported on \mathbb{R}^{d}\times\mathbb{R} . The regression problem, one of the most fundamental problems in statistics, aims to find a function \hat{f} based on these samples such that the excess risk , \|\hat{f}-f_{\star}\|_{L^{2}}^{2}=\mathbb{E}_{x}[(f_{\star}(x)-\hat{f}(x))^{2}] , is small, where f_{\star}(x)=\mathbb{E}[Y|x] is the regression function . Many non-parametric regression methods are proposed to solve the regression problem by assuming that f_{\star} falls into certain function classes, including polynomial splines Stone (1994) , local polynomials Cleveland (1979) ; Stone (1977) , the spectral algorithms Caponnetto (2006) ; Caponnetto and De Vito (2007) ; Caponnetto and Yao (2010) , etc. Spectral algorithms, as a classical topic, have been studied since the 1990s. Early works treated certain types of spectral algorithms in their theoretical analysis ( Caponnetto (2006) ; Caponnetto and De Vito (2007) ; Raskutti et al. (2014) ; Lin et al. (2020) ). These works often consider d as a fixed constant and impose the polynomial eigenvalue decay assumption under a kernel (i.e., there exist constants 0<\mathfrak{c}\leq\mathfrak{C}<\infty , such that the eigenvalues of the kernel satisfy \mathfrak{c}j^{-\beta}\leq\lambda_{j}\leq\mathfrak{C}j^{-\beta} , j\geq 1 for certain \beta>1 depending on the fixed d ). They further assume that f_{\star} belongs to the reproducing kernel Hilbert space (RKHS) \mathcal{H} associated with the kernel. Under the above assumptions, they then showed that the minimax rate of the excess risk of regression over the corresponding RKHS is lower bounded by n^{-{\beta}/({\beta+1})} and that some (regularized) spectral algorithms, e.g., the kernel ridge regression (KRR) and the kernel gradient flow, can produce estimators achieving this minimax optimal rate. However, subsequent studies have revealed that when higher regularity (or smoothness) of f_{\star} is assumed, KRR fails to achieve the information-theoretical lower bound on the excess risk, while kernel gradient flow can do so. Specifically, let’s assume that f_{\star} belongs to the interpolation space [\mathcal{H}]^{s} of the RKHS \mathcal{H} with s>0 (see, e.g., Steinwart et al. (2009) ; Dieuleveut et al. (2017) ; Dicker et al. (2017) ; Pillaud-Vivien et al. (2018) ; Lin et al. (2020) ; Fischer and Steinwart (2020) ; Celisse and Wahl (2021) ). It is then shown that the information-theoretical lower bound on the excess risk is n^{-{s\beta}/({s\beta+1})} . When 0<s\leq 2 , Caponnetto and De Vito (2007) ; Yao et al. (2007) ; Lin et al. (2020) ; Zhang et al. (2023) have already shown that the upper bound of the excess risks of both KRR and the kernel gradient flow is n^{-{s\beta}/({s\beta+1})} , and hence they are minimax optimal. On the contrary, when s>2 , Yao et al. (2007) ; Lin et al. (2020) showed that the upper bound of the excess risks of kernel gradient flow is n^{-{s\beta}/({s\beta+1})} while the best upper bound of the excess risks of KRR is n^{-{2\beta}/({2\beta+1})} ( Caponnetto and De Vito (2007) ). Bauer et al. (2007) ; Gerfo et al. (2008) ; Dicker et al. (2017) conjectured that the convergence rate of KRR is bounded below by n^{-{2\beta}/({2\beta+1})} and Li et al. (2022) rigorously proved it. The above phenomenon is often referred to as the saturation effect of KRR: KRR is inferior to certain spectral algorithms, such as kernel gradient flow, when s>2 . In recent years, neural network methods have gained tremendous success in many large-dimensional problems, such as computer vision He et al. (2016) ; Krizhevsky et al. (2017) and natural language processing Devlin (2018) . Several groups of researchers tried to explain the superior performance of neural networks on large-dimensional data from the aspects of "lazy regime" ( Arora et al. (2019) ; Du et al. (2019) ; Du et al. (2018) ; Li and Liang (2018) ). They noticed that, when the width of a neural network is sufficiently large, its parameters/weights stay in a small neighborhood of their initial position during the training process. Later, Jacot et al. (2018) ; Arora et al. (2019) ; Hu et al. (2021) ; Suh et al. (2021) ; Lai et al. (2023) ; Li et al. (2024) proved that the time-varying neural network kernel (NNK) converges (uniformly) to a time-invariant neural tangent kernel (NTK) as the width of the neural network goes to infinity, and thus the excess risk of kernel gradient flow with NTK converges (uniformly) to the excess risk of neural networks in the ‘lazy regime’. Inspired by the concepts of the "lazy regime" and the uniform convergence of excess risk, the machine learning community has experienced a renewed surge of interest in large-dimensional spectral algorithms. The earliest works focused on the consistency of two specific types of spectral algorithms: KRR and kernel interpolation ( Liang and Rakhlin (2020) ; Liang et al. (2020) ; Ghorbani et al. (2020) ; Ghorbani et al. (2021) ; Mei et al. (2021) ; Mei et al. (2022) ; Misiakiewicz and Mei (2022) ; Aerni et al. (2023) ; Barzilai and Shamir (2023) ). In comparison, results on large-dimensional kernel gradient flow were somewhat scarce, and these results largely mirrored those associated with KRR (e.g., Ghosh et al. (2021) ). Recently, Lu et al. (2023) proved that large-dimensional kernel gradient flow is minimax optimal when s=1 . Then, Zhang et al. (2024) provided upper and lower bounds on the convergence rate on the excess risk of KRR for any s>0 . Surprisingly, they discovered that for s>1 , the convergence rate of KRR did not match the lower bound on the minimax rate. Unfortunately, they didn’t prove that certain spectral algorithms can reach the lower bound on the minimax rate they provided, and hence they didn’t rigorously prove that the saturation effect

Read the complete text