Research map / Learning theory and algorithms / Kernels and regression theory
Kernel Regression in Structured Non-IID Settings: Theory and Implications for Denoising Score Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives excess-risk bounds for kernel ridge regression on structured non-i.i.d. data (each signal paired with k noisy views) via a new Bernstein-type concentration for k-gap independent data, and applies it to denoising score learning to guide the choice of noise multiplicity k.
Problem
Generalization of kernel ridge regression when training samples are dependent: multiple noisy observations derive from shared underlying signals, as in denoising score matching, where i.i.d. theory does not apply.
Approach
Models data with a causal structure x -> g <- u (n signals each paired with k i.i.d. noises), introduces k-gap independence, and proves a Bernstein-type concentration via iterative blockwise decomposition into independent fragments. The resulting variance bound blends 1/n and 1/(nk) weighted by a data-relevance parameter, so extra noise samples help unless signal correlation dominates.
Key results
- Excess-risk bound for KRR under k-gap independent data has variance scaling n^{alpha_0 theta}(r/n + (1-r)/(nk)), so increasing k helps unless signal correlation r is large.
- In a MoG denoising score experiment with fixed nk=128, k=1 is best at low noise levels (t=0.5, 0.7) while larger k is better at high noise (t=0.9, 0.95).
- Lower bound shows that for theta >= beta the variance term is Omega(sigma_L^2/k), so generalization is not benign in that regime.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| set noise multiplicity to k=1 rather than increasing k | three-layer ReLU MLP score estimation · two-component MoG, t=0.50 | score estimation error | Helped |
| set noise multiplicity to k=1 rather than increasing k | three-layer ReLU MLP score estimation · two-component MoG, t=0.70 | score estimation error | Helped |
| increase noise multiplicity k | three-layer ReLU MLP score estimation · two-component MoG, t=0.90 | score estimation error | Helped |
| increase noise multiplicity k | three-layer ReLU MLP score estimation · two-component MoG, t=0.95 | score estimation error | Helped |
Surprising findings
- Dependence among noisy views of the same signal can help generalization rather than hurt it, since the variance shrinks with k when the relevance is below one.
Limitations
- Theory covers only the learnability of individual score functions, not the full sampling error of the denoising process.
- Assumes polynomial eigenvalue decay, identical k per signal, and a specific causal structure; general non-i.i.d. settings are left open.
- Experiments are on a small synthetic MoG with an MLP, not kernel regression or real image diffusion in the main text.
Experimental setup
Datasets: two-component mixture of Gaussians (synthetic)
Benchmarks: synthetic two-component MoG score learning
Metrics: score estimation error (mean and s.d.)
Baselines: i.i.d. KRR theory mixing-based concentration bounds
Builds on: denoising score matching DDPM concentration for mixing sequences
Closest papers by meaning
- A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression (NeurIPS 2024 · similarity 0.92)
- Towards Theoretical Understanding of Learning Large-scale Dependent Data via Random Features (ICML 2024 · similarity 0.89)
- Kernel conditional tests from learning-theoretic bounds (NeurIPS 2025 · similarity 0.89)
- Supervised Kernel Thinning (NeurIPS 2024 · similarity 0.88)
- Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality (NeurIPS 2024 · similarity 0.88)
- Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrum (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.