Alignment-Sensitive Minimax Rates for Spectral Algorithms with Learned Kernels

摘要

We study spectral algorithms in settings where kernels may arise from a learning procedure, and ask how the resulting spectral order affects risk. We introduce the effective span dimension (ESD), an alignment-sensitive complexity measure that depends jointly on the target signal, the spectral order induced by the kernel, and the noise level $\sigma^2$. The ESD is defined without requiring eigen-decay conditions or source conditions, and it captures how much of the target signal lies in the leading spectral span. We prove that, for sequence models whose ESD is at most $K$, the minimax excess risk scales as $\sigma^2 K$, and we extend the framework to linear models and RKHS regression. Furthermore, we analyze over-parameterized gradient flow in a fixed-eigenbasis spectral learning model and prove that it can reduce the ESD under certain conditions. Together with numerical experiments, these results connect adaptive feature learning with reductions in ESD and offer a novel perspective on generalization beyond traditional fixed-kernel theories.