Kernel Regression in Structured Non-IID Settings: Theory and Implications for Denoising Score Learning
This work addresses the gap in KRR theory for structured non-i.i.d. data, which is common in real-world applications like denoising score learning, offering both theoretical advances and practical tools.
The paper tackles the problem of kernel ridge regression (KRR) generalization for non-i.i.d. data with structured dependencies, such as in denoising score learning, by developing a novel blockwise decomposition method to derive excess risk bounds that depend on kernel spectrum, causal parameters, and sampling mechanisms, and applies these results to provide generalization guarantees and sampling guidance for denoising score learning.
Kernel ridge regression (KRR) is a foundational tool in machine learning, with recent work emphasizing its connections to neural networks. However, existing theory primarily addresses the i.i.d. setting, while real-world data often exhibits structured dependencies - particularly in applications like denoising score learning where multiple noisy observations derive from shared underlying signals. We present the first systematic study of KRR generalization for non-i.i.d. data with signal-noise causal structure, where observations represent different noisy views of common signals. By developing a novel blockwise decomposition method that enables precise concentration analysis for dependent data, we derive excess risk bounds for KRR that explicitly depend on: (1) the kernel spectrum, (2) causal structure parameters, and (3) sampling mechanisms (including relative sample sizes for signals and noises). We further apply our results to denoising score learning, establishing generalization guarantees and providing principled guidance for sampling noisy data points. This work advances KRR theory while providing practical tools for analyzing dependent data in modern machine learning applications.