Alignment-Sensitive Minimax Rates for Spectral Algorithms with Learned Kernels
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911671344168960 |
|---|---|
| author | Huang, Dongming Li, Zhifan Li, Yicheng Lin, Qian |
| author_facet | Huang, Dongming Li, Zhifan Li, Yicheng Lin, Qian |
| contents | We study spectral algorithms in the setting where kernels are learned from data. We introduce the effective span dimension (ESD), an alignment-sensitive complexity measure that depends jointly on the signal, spectrum, and noise level $σ^2$. The ESD is well-defined for arbitrary kernels and signals without requiring eigen-decay conditions or source conditions. We prove that for sequence models whose ESD is at most $K$, the minimax excess risk scales as $σ^2 K$. Furthermore, we analyze over-parameterized gradient flow and prove that it can reduce the ESD. This finding establishes a connection between adaptive feature learning and provable improvements in generalization of spectral algorithms. We demonstrate the generality of the ESD framework by extending it to linear models and RKHS regression, and we support the theory with numerical experiments. This framework provides a novel perspective on generalization beyond traditional fixed-kernel theories. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_20294 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Alignment-Sensitive Minimax Rates for Spectral Algorithms with Learned Kernels Huang, Dongming Li, Zhifan Li, Yicheng Lin, Qian Machine Learning Statistics Theory 62G05, 62G08 We study spectral algorithms in the setting where kernels are learned from data. We introduce the effective span dimension (ESD), an alignment-sensitive complexity measure that depends jointly on the signal, spectrum, and noise level $σ^2$. The ESD is well-defined for arbitrary kernels and signals without requiring eigen-decay conditions or source conditions. We prove that for sequence models whose ESD is at most $K$, the minimax excess risk scales as $σ^2 K$. Furthermore, we analyze over-parameterized gradient flow and prove that it can reduce the ESD. This finding establishes a connection between adaptive feature learning and provable improvements in generalization of spectral algorithms. We demonstrate the generality of the ESD framework by extending it to linear models and RKHS regression, and we support the theory with numerical experiments. This framework provides a novel perspective on generalization beyond traditional fixed-kernel theories. |
| title | Alignment-Sensitive Minimax Rates for Spectral Algorithms with Learned Kernels |
| topic | Machine Learning Statistics Theory 62G05, 62G08 |
| url | https://arxiv.org/abs/2509.20294 |