Kernel Regression in Structured Non-IID Settings: Theory and Implications for Denoising Score Learning
Authors: Dechen Zhang
Zhenmei Shi
Yi Zhang
Yingyu Liang
Difan Zou
Venue: NeurIPS 2025 poster ()
Keywords: kernel ridge regression
generalization
sample complexity
diffusion model
Primary area: theory
TL;DR: We provide a refined analysis on the excess risk of kernel ridge regression in structured non-i.i.d. setting and apply it to denoising score learning.

Abstract: 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. Under standard spectral decay assumptions, we develop a novel blockwise decomposition method that enables precise concentration analysis for dependent data. Using this technique, 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.

Kernel Regression in Structured Non-IID Settings: Theory and Implications for Denoising Score Learning
Dechen Zhang!
Zhenmei Shi
Yi Zhang'
Yingyu Liang
Difan Zou 1.2
Institute of Data Science, The University of Hong Kong School of Computing and Data Science, The University of Hong Kong
Computer Sciences Department, University of Wisconsin-Madiss
dechenzhang@ccomeet akkuhk, dzoušhku. hk
Abstract
Kernel ridge regression (KRR) is 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..d. data with signal-noise causal structure, where observations represent different noisy views of common signals. By developing 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 results denoising
learning, establishing generalization guarantees and providing principled guidance for sam- pling noisy data points. This work advances KRR theory while providing practical tools for analyzing dependent data in modern machine learning applications.
Introduction
Kernel ridge regression (KRR) occupies central role in machine learning. Recently, driven by the insight that many deep neural networks (DNNs) can be viewed as converging to specific kernel regimes [31, 17]. the research community has paid renewed attention directed toward the general- ization behavior KRR. A central question in KRR is to derive generalization guarantees with the regularization parameter À > 0 under finite samples. In the special linear kernel case, Bartlett al. [4] and Tsigler and Bartlett [68] established nearly tight upper and lower bounds on the excess risk for general X. Their results demonstrate that non-vacuous generalization achievable under specific conditions on the data covariance and global optimum. More recently, a series of works extended this analysis nonlinear kernels, deriving the learning curve for KRR under power-law decay assumptions on the RKHS spectrum and mild assumptions on the target function[46, 37, 39, I]]. Their work shows that benign generalization occurs for a well-defined range of X.
Despite these remarkable breakthroughs in characterizing the learning ability of KRR, a fundamental limitation persists: existing results are largely restricted to the i.i.d. setting. Specifically, they rely on the critical assumption that training samples are independently and identically distributed (i.i.d.) drawn from the underlying data distribution. However, in many real-world applications, collected data points often deviate from strict i.i.d. conditions due to inherent correlations introduced during data generation or collection processes. For example, consider data collected in a noisy environment, where each observation consists of an underlying signal x corrupted by environmental noise u. When multiple samples are generated from the same signal but with different noise realizations u up....uk.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

these samples become statistically dependent and thus the i..d. assumption will no longer hold. This dependency also occurs in denoising score matching [30, 69, 26], where multiple noisy versions of each clean data point are used to learn score functions, creating an inherently non-i.i.d. training set.
To the best of knowledge, prior work has systematically studied KRR with such causal- structured non-i.i.d training samples (each i.i.d. signal is paired with k i.id. noise). In particular, it remains an open question whether data dependencies benefit hinder the generalization performance of KRR. The key technical barriers are two-fold: (1) the inapplicability of standard i.i.d. theory, and (2) the prevailing tendeney in non-i.i.d. analysis view data dependence unfavorably. This fundamental limitation poses significant challenges in establishing sharp theoretical guarantees for the -tusal-structured non-i.i.d. setting.
Notations. We use asymptotic notations o()), (-) and ((). and use Ô(-) suppress logarithm terms. We also use the probability versions of the asymptotic notations such as Oz(-). Moreover, following the notations in existing work [37, 39], we denote an = Opoly (bn) ) an = O(nbb,) for any p 0, an = Qooly (b,,) if on S2(n (b,,) for any p > 0, an @pnly (6n) if an Opoly((b))
and On Quolyy (b,,): and add subseript P for their probability versions.
1.1 Our Main Results
In this paper, we initiate the generalization study of the KRR estimator fx for non-i.id. data. In particular, we consider the data model with a causal structure: x x- g < u, where 9 denotes the observed data point, and x and u denote the factors from the signal source X' and noise source respectively. Then, when generating the training samples, we first generate i.i.d. signals 21..... from X, then pair each 2; with k i..d. noise realizations Ua...... uik from U, leading nk dependent observations {9.) through the causal mechanism (see Section 3.1 for more details).
Signal
g
Observation
Noise
Figure I: Causal structure of our data model.
Furthermore, as conventional concentration methods are ill-suited for the causal-structuu data model, we introduce a novel methodology that systematically partitions correlated random sequences into independent blocks through iterative decomposition. Building on this approach, we establish Bernstein-type concentration inequality for k-gap independent data (see definition in Section 3.1) 1),, which uncovers the benefit of dependency and nearly matches the rates of classical i.i.d. concentration bounds- up to logarithmic factors. Equipped with this technique, we characterize the excess risk of KRR in the structured non-i.i.d. setting, summarized as follows:
Theorem 1. (Informal statement of Theorem 4.1) Under general assumptions, if the regularization parameter À = Ω (n "), then the asymptotic rate (with respect to sample size n.) of the generalization error (excess risk) R(A) is roughly
R(A) & Öp (A*) +1))+520p0 20Opooy A
i
F nk
Bias
Variance
where denotes the decay rate of the kernel eigenvalues, represents the smoothness of target function, o² is the population noise level and i quantifies the relevance of observations sampled from the same underlying signal but corrupted by different noise.
Note that when l- = 1, the setting reduces to the standard i.i.d. setting, recovering the prior results [37]. The theoretical result reveals the interplay between the data relevance i and noise sample size k. which further implies the benefit of data relevance. In particular, while increasing noise samples enhances generalization, the improvement critically depends on the underlying signal relevance.
To further illustrate the theoretical result, we apply Theorem to single timestep of Denoising Diffusion Probabilistic Models (DDPM) [26], where the input data is generated by the weighted sum of the real-world observation and noise with weight /az and vI- ag, i.c., 9ij = vanzz +
VI - Uij. Under certain condition, our theoretical results show that the optimal value of the optimal
noise multiplicity depends critically on the ratio (1 11--- o /a where p E (0, 1] characterizes the Hölder-continus property for kernel (see Assumption and Theorem 4.4 for details). This

---

theoretical finding aligns well with the intuitive understanding that a larger & is more beneficial when a smaller-that is, when the noise component dominates.
Concretely, our contributions can be summarized as follows:
We establish the first excess risk bound for KRR in structured non-i.i.d. setting (see Section 3.1 for details), characterizing the fundamental relationship between the data causal model and the sample sizes from different sources (signal and noise sources), which provides useful guidance for developing efficient data sampling strategies.
We apply our framework to denoising diffusion probabilistic models (DDPMs) and derive the optimal noise sample size k" for each data point that minimizes the excess risk bound. Specifically, we show that the noise sampling schedule depends precisely on the time-varying noise-to-signal ratio (1 - ot p/3 /at )/a p/2
at a each timestep t. This provides new insights for improving the training efficiency of diffusion models.
We develop a novel Bernstein-type concentration inequality for k-gap independent data (see definition in Section 3.1), which explicitly quantifies the benefit of data dependency. This general- purpose technique advances the theoretical toolkit for dependent data analysis and may find applications beyond our current setting, which is of independent interest to the community.
2 Related Works
Theoretical Analysis of Kernel Regression. Theoretical guarantees for the generalization property have attracted significant attention in machine learning. Seminal work by Bartlett et al. [4), Tsigler and Bartlett [68] derived nearly tight upper and lower excess risk bounds in linear (ridge) regression for general regularization schemes. Zou et al. [77, 76], Wu et al. [71] later extended this analysis to SGD and established sharp excess risk bound under substantially weaker assumptions on the spectrum of the data covariance. Their results demonstrate that benign overfitting is achievable under certain conditions on the data covariance and global optimum. For non-linear kernel, large number of works [5, 56, 40, 38] studied the classical underparameterized (finite dimension) regime under specific polynomial decay kernel spectrum and smoothness of the ground-truth function. Specifically, Li et al. [40] proved the saturation effect that KRR fails to achieve the information theoretical lower bound when the smoothness of the underground truth function exceeds certain level. With regards to high- dimensional data, a line of work [42, 44, 48, 10] derived risk bounds by high-dimensional random matrix concentration for general kernel, while another line of research [22, 72, 50, 51, 46, 49, 11, 45] characterized the precise risk under specific conditions where the spectrum of kernel can be explicitly accessed. In particular, Mallinar et al. [46] and Medvedev et al. [49] demonstrated that the slow kernel eigenvalue decay and increasing dimensionality enable benign overfitting under Gaussian design assumption.
Learning under Non-ii.d Data. Standard provide generalization guarantees for support vector machines (SVM) [62] kernel methods under non-i.i.d. setting. To address this challenge, line of work established the consistency under processes satisfying law of large numbers [65], or satisfying empirical weak convergence [47]. However, the corresponding convergence rates typically remain unclear under such strong forms of non-i.i.d.-nness. Another line of research focused on the regression over trajectories generated by dynamic system, including both linear cases [75] and non-linear [58] cases. However, the reliance surrogate trajectory assumptions limits the applicability these results to broader scenarios. A further body of literature examines learning under mixing conditions which characterize dependence via measures of correlation across time or sequence distance. Steinwart and Christmann [63], Hang and Steinwart [25] derived high- probbbbibbbbittt concentration bounds under geometric mixing, while Yu [73], Mohri and Rostamizadeh [53], Kuznetsov and Mohri [33] analyzed settings with algebraic mixing. Our k-gap independent case cannot be covered by these works, the correlation between data points will remain high as long as they are from the same group with size k. Notably, although concentration results under general mixing framework (assuming the asymptotic mixing property) [53] could in principle accommodate our setting, our new results yield tighter bounds as we demonstrate the benefit of data relevance stands in contrast long line of work learning from dependent data.
concentration inequalities [1, 12, 13] fail to
Theoretical Analysis for Diffusion Model. Recent theoretical advances diffusion models have primarily addressed two fundamental aspects: (1) distribution estimation and (2) sampling guarantees.
3

---

For distribution estimation, seminal work by Song et al. [60] established the first statistical estimation bounds for diffusion models. Subsequent research by Chen et al. [7] demonstrated that when the target density lies on low-dimensional manifold, the sample complexity scales only with the intrinsic dimension, thus avoiding the curse of dimensionalityy Further studies have characterized the learning dynamics for specific data distributions, including Gaussian mixtures [61, 15, 57, 9, 21] and other structured distributions [36, 23, 24, 70J. On the sampling theory front, early convergence results required strong Z -accurate score estimates [16]. A significant advance by Lee et al. [34] established polynomial-time convergence under more practical & Eg-accuracy assumptions, albeit requiring log-So Sobolev inequalities. Later work relaxed these requirements to either bounded moment conditions [35, 8] or Lipschitz continuity of scores [8]. Recent developments have further improved computational efficiency through high-order discretization schemes [28, 27, 66] and exploitation of low-dimensional structures [29, 55, 41].
3 Theoretical Setup
3.1 Structured Non-i.i.d Data
We consider the scenario that the same signal can differ owing to the existence of the random environment noise, leading to different but dependent observations. As shown in Figure 1, we formally define the data model as follows:
Data model. We consider the data model with two independent sources: signal source X' = Rd and noise source U/ x y c IR x R... Let μx,, p be a probability distribution on X,4 x y respectively. The marginal distribution on UI is denoted by Puu- The data observation is formulated of the signal, denoted as g( u). where g Rd x RR - Rd is the realization function, x E X and E 2/ are independent signal and noise from their corresponding sources. Denote G == (
noisy realization
Training data generation. Following the causal structure in Figure 1, n signals are first generated. then for each signal, generate its k noisy realizations via & i.idd noise, yielding the training sample set S = (Maj Vay f.j=1 We call a sequence of random variables (X;) is k-gap independent if any random variable X, is independent with (Xjjiikk Xjjiivik). Obviously, G = {9.,) 1n. k-gap independent. On the technical level, we develop concentration techniques under the general k-gap independence and apply our results on training samples G (see Section 1 for details).
=,j=1 is
We assume an identical number of noisy realizations for all signals to simplify our analysis. However, our framework can be readily extended accommodate varying numbers of realizations, though this would require somewhat more involved calculations. To further elucidate the data model and sampling methodology, we present two examples from real-world applications.
Example 3.1. Signal processing in communication system. The fundamental setting in signal processing is the communication system leveraging multiple transmissions [6]. Each source signal is transmitted & times through noisy channel where environmental disturbances u1....,, Uy uniquely corrupt each transmission. This results in & distinct received signals g(x, un g1),9(x u2)..... 9(x, un) originating from the same source. More generally, for multiple source signals T1, Z2. Ens the received signals are {g(z,, My)))
Example 3.2. Denoising score learning. denoising score learning frameworks [30, 69, 26]. a common strategy involves learning score functions using multiple noisy versions of clean data points. Specifically, for single model certain timestep I, each clean data points Hi, i E (1...., is perturbed with k independent noises Wa,, U:2..... uak This perturbation follows a predefined function: g(x, u) vaur v1 a,u, yielding noisy dataset (g(2,, (1z))
3.2 Kernel Ridge Regression in Structural Non-i.id Setting
Let i be continuous positive definite kernel over & and 'H be the separable reproducing kemee Hilbert space (RKHS) associated with k.. Denote the regularization parameter > 0, then the
'We consider the agnostic setting in this paper, i.e., we do not make any explicit assumption on the relationship between the data gij =(zi, May) and its label yij-

---

kernel ridge regressor of each dimension can be represented as
f arg min foR
-
\ == 1,.....
Vig i=1j=1
nk
Denote fo (r) , 1,... d as the population optimal solution, then the excess risk of is:
R(A) Σ
f fp (po)
Σ S (7 -1)
dur(
where Hig the probability measure on G. By the optimality of fo (g), it holds
f*(r) 0. i 1,2,
1100 -
E {[(1>)
es (x()) (1)
1,....d. d.
(3.1)
To bound the excess risk. further introduce the widely used integral operator and the embedding index of RKHS [37, 39, 5, 43, 20J. Let g c Id be compact and k(..-) is continuous, we assume 1,2 is Hilbert-Schmidt operator. Let St L H. be the adjoint operator of Sμ. and T ;= SySt L - L?, Then, it is easy show that T' is integral operator given by T()) Ig k(g, ))(g)))((() By the spectral theorem of compact self-adjoint operators and the Mercer's theorem [64]:
k(+,)) -) is bounded [37]. Then the natural embedding Sp.
T() = >f es, k(x, = (B..)>>>eassa))) (es())))
where (2, is the of positive eigenvalues of the kernel in descending order and (cs)i3 is the corresponding eigenfunction, which forms orthonormal basis of Ran Sn L??
Besides, for & > 0, we define T T - with (e( E. (f, er. Correspondingly,
define the interpolation space [37]
[H] = Ran 7
Σ a22 es Σ <0 L2
with the norm Σ, a 64
(E, a?
It is easy to verify that [7]] is Hilbert space with
[1]]
orthonormal basis {A es 11 Further, we define the embedding index og of H. which characterizes the embedding property whether [H]] can be continuously embedded into (9,
ag = inf a: ||[]] - (G. = ess sup gGG.PG PG
Σ xg = Ma < v0
iEN
where ess sup is the essential supremum. For theoretical simplicity, we denote Vy E G:
Tyf Σ (e(l)))( To E'T Tay =
Tex Ta X.
3.3 Assumptions and Definitions
Assumption 1.
We make the following assumptions on the data distribution and kernel function: Polynomial eigenvalue decay. There is some 3 and constants cg. C3 such that
czi cgi & X & Coi =,2,....... 1,2..... Relative smoothness of the regression function. For any 1,2,.. d, there are some > 1 and a sequence a;
such that
f=1
(+(r)
Σ
Xi 0<es
10 for some constants c, C.
"This setting handles real-world vector-output tasks like denoising score learning where noise is assumed independent per dimension.
5

---

nab-Gaussian noise. For each r ......d, noise == -t is o nub-Gaussian conditionally 9. the second moment of ( conditionally on g are bounded by o²:
| 6
Ce. Bicl") o o², 9.9 E G almost everywhere.
For each 1, 1, d and observation Dij.
(1) Eg 1ig. 91y'
[ 9 ...., Ish oR.
E
(r) Ozj. Piy
< oØ.
0/2
ftölder-continuone kernel. The kernel k(.--) -) is Hölder-continuous with index that is, there exist some e (0, 1] and such that
(k(1,,)) k( w2)] < L (11, (2r2, y2) 12) Saxa, Vx,, 21, E g.
These assumptions largely consistent with existing work [37, 391, making our bound clearer and facilitating direct comparison with established results in the i.i.d. setting. The polynomial eigenvalue decay is satisfied by well-known kernels such as the Sobolev kernel [20], Laplace kernel, and neural tangent kernels for fully-connected multilayer neural networks. Notably, our framework is readily extensible to general spectra from technical standpoint and the polynomial decay assumed for theoretical simplicity (see Section F. for details).
The relative smoothness f*(r) are also widely used [37, 39, 14, 32], showing that fp for any t < s. In fact, our general theoretical bound still holds true under the relaxation from s > 1 to 0. The assumption > 1 is used estimate the relevance parameter for providing concise bound and clear insights (see Section F.2 for details). Under this assumption,
(+(r) [7A
The assumption on noise are widely used in Li et al. [37, 39]. Bartlett et al. [4], Tsigler and Bartlett [68], Cheng et al. [11], all with respect to a single data point. For technical reasons to handle multiple signal realizations, extend this assumption to hold conditionally dependent data points.
Following Li et al. [37, 39], we assume the Hölder continuity with index p to establish uniform concentration bounds via covering number estimates (see Section F.3 for details). This implies that
fo f*((r) H Hölder-continuous with index & for r I,...,d d [19, 18]. Hence, there exists L, >> such that
+ (g)) - -fth < L. 10 933 r- 1.r=1..... d,
where we construct Dey = g(24, uig), 8g = Viy (r)) ( with xf independent of x;, We further assume that og J. which is made in prior works [37, 39] and holds for numerous RKHSs. Examples include Sobolev RKHSs, those associated with periodic vransation-invaaiann kernels, and those corresponding to dot-product kernels on spheres [37, 39, 74].
For detailed analysis in structured non-i.i.d. setting, summarize some key definitions charac- terizing the data dependency structure and the population noise level. To be specific, we extend the concept of population noise level o² to structured non-i.i.d. settings by introducing the variance bound o conditioned on dependent data pairs. For technical reasons, we also take the smoothness of noise into account.
Definition 3.1. Define the population noise level ō² = L3 0² oz.
The population noise level captures the strength of both noise and its smoothness.
Definition 3.2. (Data relevance) Denote gr; = g(24, uzj), E independent of xt. We respectively define the relevance of data, the relevance over the eigenfunction and the relevance under the integral operation
(r)
Vij fo (ges)) with x is
Σd. Cov
(r) -985
1
9ij
1 sup Eler (g
To :=
Pe
nd
Var
2
ET
k( g) (r) k( 9
FT sup yeg
k >) 82
where the expectation is over 9ij. g Iis Pito Eijs Eijo.

---

All these parameters To. To. E [0, 1] characterize how the signal source a contribute to the observation gzz, u). To be precise, To describes the correlation between g(z, u1) and g(z, u2) (with independent and u2), while r. and rT capture this correlation in the context of the eigenfunction 6 and the integral operator T respectively.
Definition 3.3. (Conditional orthogonality) The conditional orthognnaliyy holds for r + 8 if
ôrs := Eu [g)ee(()
We call an orthogonal basis ec(+) that satisfies the conditional orthogonality örs = O, Vr o 8.
There are many cases where the conditional orthogonality holds, which discussed in Section Generally, Definition 3.2 and 3.3 capture the data dependency in structured non-i.i.d. setting, which determines the impact of the noise sample size (see Section for details).
4
Main Results
In this section, we will deliver the excess risk bound of the KRR estimator in our structured non-i.i.d. setting. In order better explain the result, we first present the following bias- decomposition for the excess risk, which is commonly adopted in many recent works [4, 68, 59, 46, 49, 11, 37, 39] (see details in Section A.I). Denote
d Σ TaxTas pe(n)
d Σ
k T kgig, )
Bias?())
Var(A)
(r)
12
nk
12
then
R(A) & 2Bias (A) (A).
We present our main theorem as follow. Theorem 4.1. Under Assumption I, x 0 (),
R(A) & 6p (n mi)
+ ô O2Opy
n00
TT
+
TT
(4.1)
n
nk
Blas? (X)
Var(A)
Further, if the conditional orthogonality holds,
R(A) & Op min(s.2)0
+ 8² OPooly n00
re +
(1- ro) (1 re)
(4.2)
nk
(A)
Var(A)
Remark 4.2. Two novel concepts are introduced in our excess risk upper bound, the conditional orthogonality condition (Definition 3.3), which captures the dependency in structured non-i.i.d. setting and holds in many cases (Section E), and the parameters ro, Te, Pr, which characterize the data correlation between g(x , (1) and g(x, u2) under different conditions (Definition 3.2).
Overall, the non-vacuous generalization attainable when E (0, in agreement with the asymp- totic results of Li et al. [37]. Denote the correlation level f = Te emerges: our bound explicitly blends and nk weighted by and reveals a critical trade-off between relevance and noise sample size: when the correlation level F is large, i.e., the signal dominates in observed noisy data, increasing & offers little benefits while increasing k helps generalization when the noise component prevails.
A key theoretical insight Consequently, this result
In the regime 0 E o)), theoretical lower bound in the i.i.d. setting is provided by some monotonicity properties with respect to À [37, 39]. implying the generalization is vacuous in this case that À small. For the reason that the correlation of data might be positive, we can merely derive a lower bound for the variance term by taking conditional expectations over Gijlii for Var(A).
Theorem 4.3. Under Assumption I, if X = n 0 [8,00),
L9.. Bias (A) Opoly (n-min((+2))) Ea, El ... Ee,, 19., [Var(A)] > Opoly
7 k
where of is the lower bound of ( (g] for g e G almost everywhere.
This lower bound for the variance term in case 0 [B, co) demonstrates that the generalization will never be benign, aligning well with the prior results [37.39]

---

Ev0.50
t-0.70
t-0 00
tw0.95
0.36
0.14
0.34
Score ISEE
Scare MSE
0.10
0.4
0.58
0.04
Figure 2: Score estimation error (mean + s.d.) versus the number of noise per data, i.e., k for four noise levels, where lower eπror implies better score learning.
4.1 Implication to Denoising Score Learning
At a single timestep in denoising score learning, the goal is to minimize the loss given the training set S = {(ge( Exy) (t)) where ge( {) = vana T + -I-ast applies data on noise.
nk Ei So (.)())
Since our structured non-i.i.d. framework does not make any assumptions on the relationship between the noisy data and its label, denoising score learning naturally fits our agnostic setting. Under the same notations in Assumption I, we apply Theorem 4.1 to denoising score learning as follow.
Theorem 4.4. Consider the denoising score learning at timestep t. Assuming that H[z²] < o B[Ca] & a x n (0,3) and the conditional orthogonaliiy holds, under Assumption /
ar VT (1- a a1 re) re)) )
R(A) Öp nn min(s,210) + o2Opoly m00
n
nik
Theorem 4.4 can be easily derived by computing To given g(z, u) Varz + VT- aru. In practical denoising score learning, the main challenges arise from the underlying data distribution, the properties of the score function für and the spectral decay of the chosen kernel. Our theory provides general framework to characterize the learnability of different data distributions. Practitioners can leverage this framework as follows: first, select kernel appropriate to the problem domain; second, check the decay rate of the kernel's spectrum; and finally, apply Theorem 4.4 to rigorously determine (i) whether the distribution can be learned efficiently and (ii) the sample complexity required for convergence.
Furthermore, building on the theoretical trade-off that increasing helps generalization when the noise component prevails while incrasingg &o is useless when the signal dominates. a key inspiration for empirical study emerges: for a fixed batch size, if signal dominates, then setting k = 1 enough; while when noise dominates, one is encouraged to increase k to roughly (1 - a,) a,)/a,, more
precisely, (1 (1-a7 a ) / This adaptive design for noise multiplicity may advance the empirical study for denoising score learning.
Numerical Experiments. We train a three-layer ReLU MLP (100 neurons each) to learn the score of two-component MoG (μ [-5,5]] via denoising score matching loss, where the networks are trained separately. Each network is optimized with SGD (Ir 10 momentum 0.9) and 0.9 EMA. In each iteration, we consider a fixed batch size nk = 128, with a varying number noises paired with each data, i.e., k, from to 64. The results displayed in Figure 2 over 100 independent runs. More experiments real image diffusion training and experiments using kernel ridge regressor rather than neural network are detailed in Section G.1 and Section G.2.
0.2) at four noise levels t {0.50, 0. 0.70, 0.90, 0.95)
From the experimental results, we demonstrate an important relationship between the noise level t and the optimal noise- sample ratio k. For lower noise levels (t = 0.5, 0.7), we find that pairing each data point with a single noise sample (k = 1) yields optimal score learning performance.
We present general theoretical framework on denoising score learning under mild Assumption here. while deferring derivations for specific data distribution and kernel future work.

---

Conversely, at higher noise levels (t = 0.9, 0.95), better results are achieved by increasing k. These empirical findings directly support our theoretical analysis in Theorem 4.4, which shows that the optimal & should scale with the noise level / (or equivalently, inversely with az). The results provide practical insights for optimizing the training efficiency diffusion models, suggesting that adaptive noise-sample pairing strategies may offer significant computational benefits.
5
Proof Details
In this section, we outline the proof and present our key techniques, focusing particularly on the novel blockwise decomposition method developed to establish Bernstein-type high-probabilityy bound.
Proof roadmap for Theorem 4.1. For Bias(A), (A), standard concentration techniques- which rely heav- significant challenges when applied to dependent data. Motivated by Banna et al. [3], we develop a novel blockwise decomposition method for k-gap independent random sequence and derive the Bernstein-tyy -ype high probability bound tailed to structured non-i.i.d. bounded data. Overall, we adopt two-step concentration analysis using our developed technique to characterize Bias( A). For Var(A), instead of conditioning
ily on the i.i.d. assumption-
to take expectations over the noise e [4, 68, 46, 37, 39, 11], we perform direct concentration analysis on 6, a necessity due inherent data dependencies that invalidate standard conditional expectation techniques. Overall, we charac- terize Var(>) by adopting three-step concentration analysis, where the concentration arguments in structured non-i.i.d. setting is similar as the analysis for Bias(
5.1 Key Proof Techniques
As outlined in the proof roadmap, classical concentration inequalities crucially depend on the i.i.d. assumption, limiting their applicability to dependent data regimes. This dependence invalidates foun- dational steps in traditional concentration proofs, such as the decomposition of wooment-generateee funetions (MGFs), where the equality E e X. IT E fails to hold under non-i.i.d. condi- tions. We present our novel techniques in the following Lemma 5.1, which stated under mild k-gap independent condition" With this novel result Lemma 5.1, we can perform refined concentration inequalities in structured non-i.idd setting.
Lemma 5.1. Consider a kagap sequence of random variables (X,) taking values of self-adjoint Silbert-Schmidl operators. Suppose that there exists positive constant M such that for any i > 1,
E(X,) 0 and Amax((x)) & M almost surely.
27 "):
Denote 22
sup (k
Cardk
Amax
E
Σ
X
intd = intdim [EX?) where
iiE
intdim (A)
u((A) is the intrinsic dimension of A. For any positive such that tM < logn' [AT
nkk
nk intd
169
log EEr
exp
X;
I
< log n log 3 + log
+ + nkn
2
1 t. & log
Key proof insight of Lemma 5.1. Lemma 5.1 is proved by iteratively partitioning the random sequence into mutually independent blocks and incorporating the separated bounds. On high level, we develop a different block scheme compared with current mixing techniques, enabling us to capture the underlying data independence and fully utilize the intra-block randomness. This refined study helps discover some benefits of data dependency.
Step 1: Partition and derive the separated bound. We firstly partition Ao == (1, (I,...,yuk nk) into three fragments, delete the middle fragment to guarantee the remaining two fragments are independent; secondly partition each of the two remaining terms into three fragments, delete the middle fragment to guarantee the remaining two fragments are independent. After repeating this procedure & times, we denote the remaining terms as K A. From the partition, ΣxeKA, X, can be represented as the sum
*Our novel concentration bound can extend the case where the number of noisy realizations A; varies per signal x,, by replacing & with kmas = max, k. Our result can also generalize to the case where block gaps are only approximately independent. e.g., some weakly dependent process assuming specific mixing property, by quantifying block dependence [52, 3J.

---

of 2 mutually independent random fragments. Consequently, we derive the separated bound (see details in Proposition D.1).
Step 2: Incorporate the separated bounds. After obtaining KAg we can also undertake the same partition for the remaining elements (f1,--., , (1, (1,..., Aj (a. Repeating & O(log n) times, the sum En X; can be represented as the sum of L + fragments which can be bounded by the analysis in Step 1. Finally, incorporate the separated bound by simple incorporating lemma and prove the Lemma 5.1 (see details in Proposition D.2).
Consider the case d = 1, Lemma 5.1 can be simplified as: There exists a constant C such that for any positive such that tM Flogn
Tik X
C
log E exp
(5.1)
tM logn
For simplicity, discuss technique via the case d 1. In particular, the novel concentration inequality can be obtained by (5.1):
nk
-" (-
2/2
X
& 2exp
(5.2)
+ M logn
Comparison concentration bound under general mixing assumption. For simplicity, we consider M is on constant level. Under general mixing assumption lim, o(i) = 0 where 6(-) is the mixing coefficient for zero-mean random variables Wi, W..... Wnk,-- .... previous concentration techniques treat the data dependency as bad effect, yielding the following concentration inequality
(Theorem 8 in [53]) mik
W
< Ög
(1+2/
Öp (Vz) ( In contrast, our result (5.2)
Vik
implies
1
m
X
Op
22 = ÓP
(V
Ar+1-r nk
which decreases as k increases. The
nk
intuition is that we do not treat the data dependency a bad effect but aim to discover some benefits for reducing the error, otherwise would be intractable to prove the vanishing generalization error in our setting for general k:
Conclusion and Limitations
In this work, provide refined analysis on the excess risk of kernel ridge regression in structured non-i.i.d. setting, by deriving a novel Bernstein-type concentration inequality for k-block independent data. Our theoretical upper bound of excess risk demonstrates that when the noise dominates in the observed noisy data, increasing & helps generalization. In practical denoising score learning, empirical findings directly support our theoretical insight and further inspire adaptive noise-sample pairing strategies for optimizing the training efficiency of diffusion models.
Our limitations twofold: (i) only establish the learnability of individual score function but no fully characterization of the sampling error throughout the entire denoising process, and (ii) our analysis is confined to structured non-i..dd settings, leaving rigorous theoretical characterization of general non-i.i.d. scenarios as an open problem.
Acknowledgements
We would like thank the anonymous reviewers and area chairs for their helpful comments. This work is supported by NSFC 62306252, Hong Kong ECS award 27309624, Guangdong NSF 202441515012444, and the central fund from HKU IDS.
'Here we invoke k-gap condition, which implies that ((1) for > k, and we note that [o(1) bounded by constant for i [2].
'Hrr e [0, 1] denotes the relevance between data points with sequence distance smaller than k.
10

---

References
[1] Yasin Abbasi-Yadkori. Online learning for linearly parametrized control problems. 2013,
[2] M Eren Ahsen and Vidyasagar. On the computation of mixing coefficients between discrete- valued random variables. In 2013 9th Asian Control Conference (ASCC), pages 1-5. IEEE, 2013.
[3] Marwa Banna, Florence Merlevède, and Pierre Youssef. Bernstein-type inequality for class of dependent random matrices. Random Matrices: Theory and Applications, 5(02):1650006, 2016.
[4] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30033-3000 2020.
[5] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7:331-368 2007.
[6] A Bruce Carlson. communication systems: introduction to signal noise in electrical commu- nication. 2002.
[7] Minshuo Chen, Kaixuan Huang, Tuo Zhao, and Mengdi Wang. Score approximation, estimation and distribution recovery of diffusion models on low-dimensional data. In International Conference on Machine Learning, pages 4672-4712. PMLR, 2023.
[8] Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is as easy learning the theory for diffusion models with minimal data assumptions, arXiv preprint 12Xiv:2209.11255. 2022.
[9] Sitan Chen, Vasilis Kontonis, and Kulin Shah. Learning general gaussian mixtures with efficient score matching. arXiv preprint MXXi:2444.18893 2024.
[10] Yihang Chen, Fanghui Liu, Taiji Suzuki, and Volkan Cevher. High-dimensional kernel methods under covariate shift: data-dependent implicit regularization. arXiv preprint arXiv:2406.03/7/, 2024.
[11] Tin Sum Cheng, Aurelien Lucchi, Anastasis Kratsios, and David Belius. Characterizing overfit- ting in kernel ridgeless regression through the eigenspectrum. arXiv preprint arXiv:2402.01299, 2024.
[12] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference on Machine Learning, pages 844 853. PMLR, 2017.
[13] Sayak Ray Chowdhury and Aditya Gopalan. No-regret algorithms for multi-task bayesian optimization. In International Conference on Artificial Intelligence and Statistics, pages 1873- 1881. PMLR, 2021.
[14] Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates kernel regression: The crossover from the noiseless to noisy regime. Advances in Neural Information Processing Systems, 14110111-1114: 2021.
[15] Hugo Cui, Florent Krzakala, Eric Vanden- Eijineen, and Lenka Zdeborová. Analysis of learning flow-based generative model from limited sample complexity. arXiv preprint arXiv:2310.03575. 2023.
[16] Valentin De Bortoli, James Thornton, Jeremy Heng, and Arnaud Doucet. Diffusion schrödinger bridge with applications to scoee-based generative modeling. Advances in Neural Information Processing Systems, 14:17695-17709, 2021.
[17] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterizeed neural networks. arXiv preprint arXiv:1810.0265: 2018
[18] JC Ferreira and Valdir Antônio Menegatto. Positive definiteness, reproducing kernel hilbert spaces and beyond. Annals of Functional Analysis, 4(1), 2013.

---

[19] Christian Fiedler. Lipschitz and h\ older continuity in reproducing kernel hilbert spaces. arXiv preprint arXiv:2310.18078, 2023.
[20] Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least- -quares algorithms. Journal of Machine Learning Research, 21 21(25))11333 2020.
[21] Khashayar Gatmiry, Jonathan Kelner, and Holden Lee. Learning mixtures of gaussians using diffusion models. arXiv preprint arXiv:2404. 18869, 2024.
[22] Nikhil Ghosh, Song Mei, and Bin Yu. The three stages of learning dynamics in high-dimensional kernel methods. arXiv preprint arXiv:2111.07160 2021.
[23] Andi Han, Wei Huang, Yuan Cao, and Difan Zou. On the feature learning in diffusion models. In The Thirteenth International Conference on Learning Representations, 2025. URL https:
/ //openreview. net wost/ffoummidd JjdU6ysnCr.
[24] Yujin Han, Andi Han, Wei Huang, Chaochao Lu, and Difan Zou. Can diffusion models learn hidden inter-feature rules behind images?, 2025. URL htttthttt///reee www.v..rggaas//52222 04725.
[25] Hanyuan Hang and Ingo Steinwart. Fast learning from a-mixing observations. Journal of Multivariate Analysis, 127:184-199 199, 2014.
[26] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-68511 2020.
[27] Daniel Zhengyu Huang, Jiaoyang Huang, and Zhengjiang Lin. Convergence analysis of probability flow ode for score-based generative models. IEEE Transactions on Information Theory, 2025.
[28] Xunpeng Huang, Difan Zou, Hanze Dong, Zhang Zhang, Yian Ma, and Tong Zhang. Reverse transition kernel: flexible framework accelerate diffusion inference. Advances Neural Information Processing Systems, 777795115-95578 2024.
[29] Zhihan Huang, Yuting Wei, and Yuxin Chen. Denoising diffusion probabilistic models are optimally adaptive to unknown low dimensionality. arXiv preprint arXiv:2410. 18784, 2024.
[30] Aapo Hyvärinen. Estimation of normalzze statistical models by score matching. Journal of Machine Learning Reseurch, 6(24):695-709 2005. URL http: /tt////www/// jmlr wrg/paperst vo volume6/ haa.m/////yyaaaeeeeee/////rrreee
[31] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[32] Hui Jin, Pradeep Kr Banerjee, and Guido Montúfar. Learning curves for gaussian process regression with power-law priors and targets. arXiv preprint arXiv:21 12231, 2021.
[33] Vitaly Kuznetsov and Mehryar Mohri. Generalization bounds for non-stationary mixing pro- cesses. Machine Learning, 106(1) (16(1)999 1197 2017.
[34] Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. Advances in Neural Information Processing Systems, 35:22870-22882, 2022.
[35] Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In International Conference Algorithmic Learning Theory, pages 946-985. PMLR, 2023.
[36] Xiang Li, Yixiang Dai, and Qing Qu. Understanding generalizability of diffusion models requires rethinking the hidden gaussian structure. Advances in neural information processing systems, 37:57499-57538, 2024.
[37] Yicheng Li, Qian Lin, et al. On the asymptotic learning curves of kernel ridge regression under pawer-law decay, Advances in Neural Information Processing Systems, 16:49341-4994 2023,
12

---

[38] Yicheng Li, Weiye Gan, Zuoqiang Shi, and Qian Lin. Generalization enror curves for analytic spectral algorithms under power-law decay. arXiv preprint arXiv:2401.01599 2024.
[39] Yicheng Li, Haobo Zhang, and Qian Lin. Kernel interpolation generalizes poorly. Biometrika, 111(2):75--722, 2024.
[40] Yicheng Li, Haobo Zhang, and Qian Lin. On the saturation effect of kernel ridge regression. arXiv preprint urXiv:2405.09362, 2024.
[41] Jiadong Liang, Zhihan Huang, and Yuxin Chen. Low-dimensional adaptation of diffusion models: Convergence in total variation. arXiv preprint arXiv:2501.12982. 2025.
[42] Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. The Annals of Statistics, 48(3), June 2020. ISSN 0090-5364. doi: 10.1214/ 19-aos 1849. URL http: / doi 0rg/10. 1214/19-A0S1849.
[43] Junhong Lin, Alessandro Rudi, Lorenzo Rosasco, and Volkan Cevher. Optimal rates for spectral algorithms with least-squares regression over hilbert spaces. Applied and Computational Harmonic Analysis, 48(3):868-88) -800, 2020.
[44] Fanghui Liu, Zhenyu Liao, and Johan Suykens. Kernel regression in high dimensions: Refined analysis beyond double descent. In International Conference on Artificial Intelligence and Statistics, pages 649-657. PMLR, 2021.
[45] Weihao Lu, Yicheng Li, Qian Lin, et al. On the saturation effects of spectral algorithms in large dimensions. Advances in Neural Information Processing Systems, 37:701 1-7059, 2024.
[46] Neil Mallinar, James B Simon, Amirhesam Abedsoltan, Parthe Pandit, Mikhail Belkin, and Preetum Nakkiran. Benign, tempered, or catastrophic: taxonomy of overfitting. arXiv preprint wwxi::2207.06569 2022.
[47] Pierre-Fras Fiarre-François Massiani, Sebastian Trimpe, and Friedrich Solowjow. On the consistency of kernel methods with dependent observations. arXiv preprint arXiv:2406.06101 2024.
[48] Andrew McRae, Santhosh Karnik, Mark Davenport, and Vidya Muthukumar. Harmless in- terpolation in regression and classification with structured features. In International Conference on Artificial Intelligence and Statistics, pages 5853-5875, PMLR, 2022.
[49] Marko Medvedev, Gal Vardi, and Nati Srebro. Overfitting behaviour of gaussian kernel ridgeless regression: Varying bandwidth or dimensionality. Advances in Neural Information Processing 3ystemss,7:522644 5766,,2--2669, 2024.
[50] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. In Conference on Learning Theory, pages 3351-3418 PMLR, 2021.
[51] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Generalization error of random feature and kernel methods: hypercontractivity and kernel matrix concentration. Applied and Computational Harmonic Analysis, 59:3-84, 2022.
[52] Florence Merlevède, Magda Peligrad, and Emmanuel Rio. Bernstein inequality and moderate deviations under strong mixing conditions. In High dimensional probability V: the Luminy volume, volume 5, pages 273-293. Institute of Mathematical Statistics, 2009.
[53] Mchryar Mohri and Afshin Rostamizadeh. Stability bounds for stationary ---mixing and 8-mixing processes. Journal of Machine Learning Research, 1 12)), 2010.
[54] losif Pinelis and Aleksandr Ivanovich Sakhanenko. Remarks on inequalities for large deviation probabilities. Theory of Probability & Its Applications, 30(1)):1431144 1986.
[55] Peter Potaptchik, Iskander Azangulov, and George Deligiannidis. Linear convergence of diffusion models under the manifold hypothesis. arXiv preprint 41X1v:2410.09046,, 2024.
13

---

[56] Abhishake Rastogi and Sivananthan Sampath. Optimal rates for the regularized learning algorithms under general source condition. Frontiers in Applied Mathematics and Statistics, 3, 2017.
[57] Kulin Shah, Sitan Chen, and Adam Klivans. Learning mixtures of gaussians using the ddpm objective. Advances in Neural Information Processing Systems, 36:19636-19649 2023.
[58] Max Simchowitz, Horia Mania, Stephen Tu, Michael I Jordan, and Benjamin Recht. Learning without mixing: Towards a sharp analysis of línear system identification. In Conference On Learning Theory, pages 439-473. PMLR, 2018.
[59] James Simon, Madeline Dickens, Dhruva Karkada, and Michael R WeWeese. The eigen- learning framework: A conservation law perspective on kemel ridge regression and wide neural networks. Transactions on Machine Learning Research, 2023.
[60] Yang Song, Sahaj Garg, Jiaxin Shi, and Stefano Ermon. Sliced score matching: A scalable approach to density and score estimation. Uncertainty artificial intelligence, pages 574-584. PMLR, 2020.
[61] Yang Song. Liyue Shen, Lei Xing, and Stefano Ermon. Solving inverse problems in medical imaging with score-based generative models. arXiv preprint arXiv:2111.0000) 2021.
[62] Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008.
[63] Ingo Steinwart and Andreas Christmann. Fast learning from non-iid observations. Advances in neural information processing systems, 22, 2009.
[64] Ingo Steinwart and Clint Scovel. Mercer's theorem on general domains: On the interaction between measures, kernels, and rkhss. Constructive Approximation, 35:363 417, 2012.
[65] Ingo Steinwart, Don Hush, and Clint Scovel. Learning from dependent observations. Journal of Multivariate Analysis, 100(1):155-194, 2009.
[66] Mahsa Taheri and Johannes Lederer. Regularization can make diffusion models more efficient. arXiv preprint arXiv:2502.09/55/ 2025.
[67] Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends@ in Machine Learning. 8(1-2):1-230, 2015.
[68] Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. Journal of Machine Learning Research, 24(123):1-76, 2023.
[69] Pascal Vincent. connection between score matching and denoising autoencoders. Neural Computation, 23(7):1661-1644 2011. doi: 10.1162/NECO. a 00142.
[70] Peng Wang. Huijie Zhang. Zekai Zhang, Siyi Chen, Yi Ma, and Qing Qu. Diffusion models learn low-dimensional distributions via subspace clustering. arXiv preprint 200.v22409002220 2024.
[71] Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Last it- erate risk bounds of sgd with decaying stepsize for overparameterized linear regression. In International conference on machine learning, pages 24280-24314, PMLR, 2022.
[72] Lechao Xiao, Hong Hu, Theodor Misiakiewicz, Yue Lu, and Jeffrey Pennington. Precise learning curves and oideer-order scalings for dot-product kernel regression. Advances in Neural Information Processing Systems, 35:4558-4570, 2022.
[73] Bin Yu. Rates of convergence for empirical processes of stationary mixing sequences. The Annals of Probability, pages 94-116 1994.
[74] Haobo Zhang, Yicheng Li, and Qian Lin. On the optimality of misspecified spectral algorithms. Journal of Machine Learning Research, 25(188):1-50, 2024.
14

---

[75] Ingvar Ziemann and Stephen Tu. Learning with little mixing. Advances in Neural Information Processing Systems, 35:4626-4637, 2022.
[76] Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, Dean Foster, and Sham Kakade. The benefits of implicit regularization from sgd in least squares problems. Advances in neural information processing systems, 34:5456-5460 2021.
[77] Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Benign overfitting of constant-stepsize sgd for linear regression. In Conference Learning Theory, pages 4633-4635. PMLR, 2021.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the claims made, including the contributions made in the paper and important assumptions and limitations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We include the limitation discussion in Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

Justification:
This paper made the following assumptions: Assumption is in Section 3.3.
For each theoretical result:
The proof of Theorem 4.1 is in Section A. The answer NA means that the paper does not include theoretical results.
The proof of Theorem 4.3 is in Section A.
The proof of Theorem 4.4 is in Section A.
Guidelines:
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
See Section G.3.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
17

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
See Section G.3.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
public/guide httg///dd///odeuuuniiin
/wwoe//umiiisioonnaaao Plllcy for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurlPS code and data submission guidelines (https: //ni http:ppulllpldpdeeeepppp wtt.gddeeeeeeeudmiiiiiaa SrooddSubmissionnl..
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See Section G.3.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: See Section G.3.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
18

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Section G.3.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: tttttps://euuree /nwrrps.....p// cc/ cc/public/ Ceabllcc//thtt /tthi crcuicisseeeeenneen lins?
Answer: [Yes]
Justification: All authors have reviewed and confirmed that the research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We include the broader impacts discussion in Section H.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
19

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The paper cites the original paper that produced the code package or dataset.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
20

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
21

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy btttp:://eeurps... for what should or should not be described.
22

---

Appendix
We provide detailed proofs for Theorem 4.1, Theorem 4.3 and Theorem 4.4 in Section In particular, we develop novel Bernstein-type concentration techniques in Section D and apply this to establish concentration lemmas in Section These concentration lemmas are essential for the derivation of our theory. In Section E, we provide two specific examples to illustrate when the conditional orthogonality holds. further provide comprehensive discussion on our assumptions in Section To supplement our numerical experiments, we perform experiments on image diffusion and kernel ridge regressor Section G.
The following proof dependency graph visually encapsulates the logical structure and organi- zational architecture of the theoretical results in our paper. This graph serves as map for navigating the paper's 's proofs, allowing readers to quickly grasp the global structure, identify core technical components, and understand the interrelationships that underpin our main find- ings. In particular, the arrow from element X to element Y means the proof of Y relies on X.
Theorem 4.1
Theorem 4.3
Theorem 4.4
Theorem A.1
Theorem A.2
Theorem A.3
Theorem A.4
Theorem A.5
Theoram A.6
Lemma B.1
Lemma B.2
Lēmma B.3
Lemma B:4
Corollary B.5
Lemma B.6
Lemma 1.10
Lemma B.7
Lemma B.8
Lemma B.9
Proposition D.2
Proposition D.3
Lemma B.11
Proposition D.1
Corollary C.2
Lemma C.6
Lemma C.12
Lemma C.16
Lemma C.3
Lemma C.4
Lemma C.9
Lemma C.10
Lemma C.17
Lemma
Lemma
Lemma
Lemma
Lemma C.15
Lemma C8
Lemma
Lemma C.11
23

---

Appendix Contents
Detailed Proofs
25
A.1
Bias-Varianee Variance Decomposition
25
A.2
Large Regularization Induces Non-vacuous Generalization
25
A.2.1
Bounds for the Bias Term
25
A.2.2
Bounds for the Variance Term
26
A.2.3
Excess Risk Bounds under Conditional Orthogonality Condition
30
A.3
Small Regularization Induces Vacuous Generalization
30
A.3.1
Bounds for the Bias term
30
A.3.2
Bounds for the Variance term
31
A.4
Excess Risk Bounds in Denoising Score Learning
32
Concentration Lemmas
33
Auxiliary Lemmas
52
C.1 Key Lemmas
52
C.2 Technical Lemmas for Concentration of k-gap Independent Data
54
Bernstein-type Concentration for k-gap Independent Data
55
Conditional Orthogonality Condition
59
F Discussion Assumptions
60
F.I
Polynomial-decay Kernel Spectrum
60
F2 Relative Smoothness
61
F33 Hölder continuity
61
Experiment
G.1 Real Image Diffusion Training
61
G.2 Kernel Ridge Regressor
62
G.3 Experiment Details
62
H. Broader Impacts
62
24

---

A Detailed Proofs
In this section, we present detailed proofs for our main results. To be specific, we prove Theorem 4.1 in Section A.2, Theorem 4.3 in Section A.3 and Theorem 4.4 in Section A.4. For simplicity, we denote min(s,2). Before presenting the detailed proofs, we firstly perform bias-variance decomposition.
A.1 Varsaner Decomposition
We first undertake bias-variance decomposition, which is commonly used in analyzing excess risk [4, 68, 59, 46, 49, 11, 39]. By the definition of the integral operator, we express the kernel ridge regressor as
K (Ta + X)
k(ag Du .......d.
nk
We denote the conditional kernel ridge regressor
A = E [ (To + Tof r= l....,d,
where we use (3.1) Hence, the excess risk
d
R(A)
Σ
((r)
d
Σ
f( -5z(1)
+
(To + A) "k(gu, )e
nk
(1 [,-00 (
2 Σ
(To k(gi)) )
(r)
L2
nk
1m13m1
12
For each 1, .....,... d, we define
1
B²(A) = ( - p 52
V.(A) = nk
TT A) 1) -k(00js )c(p (r)
(A.1)
The key part of our proof is to provide bounds for (A) and (A).).
A.2
Large Regularization Induces Non-vacuous Generalization
In this section, we prove Theorem 4.1. In particular, we derive upper bounds for bias and variance respectively in Section A.2.1 and Section A.2.2.
A.2.1 Bounds for the Bias Term
Theorem A.1. Under Assumption 1, = n=000 (0, then
BA(A) Ôp (1: (m=mu((+2))0//)
d.
Proof. We analyze bounds in each dimension. For simplicity, we ignore script r. We decompose the bias term by introducing the expectation of fs = (To + A) Tals:
fa = (T)) Tf.
then
ffx fl1l -1
<B()) JA f 17
1FA
11
12
25

---

We first compute the term fx - f 1.2 Apply Lemma C.4 and take 0 we have
llf f = 6 (5m min(s,
f fa fall the key is to perform concentration analysis. To this end,
Secondly, with regards to
into two components related to G and analyze each component by f fx L2
decompose
concentration.
F - f2
T fs - -f)) n 1.2
ने (TaS² Toxt2))
|T5 (Tafe -TotsN)
< Nेता ||
| (Tof, -Taxfa) 1
गेत || T (Ta5ž - -IT A - f2)
Nेक ||
| [[Tof=- TafA) -TT - TT1)]]
1 1- -T-
T [TTf$ - -afA) - -T Tfxl
where the last inequality utilizes the fact that:
T Tax 47
- (T To) T {]
TT (o))
By Lemma B.1, for on being sufficiently close, with high probability,
(T $1 < (v
A>-a A--0 = (1).
By Lemma B.2, with high probability,
T [Tal - -To()) - (T - T[W]]
$ E (Λτ)
Hence,
| Ak-Ballz salla= & oΦ (x²)
Therefore,
B(A) = 6p (n (n-miu(+.))0/2)
A.2.2 Bounds for the Variance Term
Theorem A.2. Under Assumption 1, xx==== E (0, then
V₂(A) & gg
000
PT +
1 1- Pr
)) r= I..,.d, d.
nk
26

---

Proof. By definition,
(A)
(Te + 2) 1) ((gg:
nk
12
(T + 2) kc k( s) dpg(و).
gg 1-
For simplicity, we first ignore script in ej The proof for upper bounding V(A) undertakes several steps of concentration. We first separate Ta by interpolating its expectation T,, and then analyze the discrepancy between To and T and the remaining term respectively.
k
T ((glg
n2a k2
Tax (95g))9))))
Tx
k(gbj,))
n
n2
(A.2)
AG
7x k9gg,9)
n 2
Intuitively, V is consist of the covariance between sampled observations, which can be categorized by the expectation value into the covariance of an individual observation itself, the covariance across noises per signal and the covariance across signals. We further perform decomposition according to these intuition:
T (Olns k(ghsiz lein Fizial
n 2 2
1
k: 9);; 2
k2
k
T k(
1.22
1J2 Ah
Tx ( k(gizin Deitn Cindas
1212
where Vi characterizes the covariance of observation, V/2 captures the covariance across noises per signal and V/3 reflects the covariance across signals. We first bound V1, By Lemma B.3, for 0g being sufficiently close, for g E 9 almost everywhere.
k(gg 9)2² - 117, M| & Ör x
A-a (x-an/
nk
n
By Lemma B.7, for ag being sufficiently close, for g e & almost everywhere,
[T k(g 1e )55l 12
[T k(g 9) 19
Öp
-21
a-a
nu
7
27

---

Jointly, for a > an being sufficiently close, with high probability, for 9 E G almost everywhere,
k
Vi
T
9)
n2
1
((gss.))) 2) E E[eyllss + Ög
a
nk
ni
i=1j=1
0²
|T k(g >ll +0p / /2
1
Öp
o²--a
nk
n
nkk
71
a²
[1Tx k(g 11:0 ör (A-9)
nk
a² (1Tx M11.)
Ör
nk
where the last equality results from Corollary C.2 that &
We then bound V22 By Lemma B.8, for > og being sufficiently close, with high probability, for g E 9 almost everywhere,
1 nk(k- 1) 1-1 J2
Σ
Ty Moh. " g)ag2 ET (Mgg)g9) ((gt2
& (0 + +z) (A
Therefore, togeter with Corollary C.2, we have, with high probability, for g e 9 almost everywhere,
@2 1) Ör (ITx' k(.
V2 rr
nk
We at last bound V3. By Lemma B.9, with high probability, for g E 9 almost everywhere,
n
V/3
Σ Σ
Σ
Tx
k(ghnn
TT k(gian eiii 6izi2
22
12=1
T k(g.
lizz
1-rT
< T20
PT +
k
Here complete the analysis for V. For AG,
1
&
2
n
2
AG
T
k(gss
n
n2
11 n22k2
1j=1
T
T
14 k( 9)6
nk
nk 1=1--
1 1
T k (ggg)
Σ
T
k(gi))9)Es
nk: 1-1-
E+ T Takk
We first
apply
Corollary
B.5 deal with
nk Σズ Ej= Tx ((gg, For a og being sufficiently close, with high probabil-
28

---

ity, for E G almost everywhere,
Ta (9155,)) ) -
Tx
k( g)61s)
nk
nk
i=1j=1
==1==1
1
(T
Tx 9)
nk
oh
& [ - -T M
nh. nk
Note that
k
o
M(g))))
-
k(g.)
n nk 1=1=-1
n
H
we then separate it to several components related to G' as in the proof of Theorem A. to perform concentration.
T (T - Tx -x)) K(g 11m)
n
(To - Tx k(g :) km)
To To G2
n
11
ा 3 (TG 2) 315 k(g (r 1m))
=0p
n
T (Te (To- * (m)
n
By Lemma B. for a > og being sufficiently close, with high probability,
T $ O0((1,
| } (To - -T) Or (V A-a
By Corollary C.2,
T kk(..)) 7
& -
Note that
rē #
t ++ 1
< sup
we have for a > au being sufficiently close, with high probability, for g E 9 almost everywhere,
n2
) )
1 T ((0b))
n
k(0)))))3)) 9)cs) ) konōr (v 7-200) n2
T To Morj-))es)
(A.3)
nk
nk:
Secondly, regarding tend to handle this term by Equation (A.3). For an being sufficiently close, with high probability,
1
T ((gggg)(;))))) we in- nk Σ E5= (og +
29

---

for G almost everywhere,
n
k T k(g))
Σ
Σ
T
k(g Das
nk
12k
-11x 1ik
2
k(gis, DEG
+
T
((95)
< Tx
k( g)
nk
nk
i=1j=1
==1j=1
a-aa ??
/1-20 n²
(V=²
(A.4)
where the last inequality results from Lemma B.4 and Equation (A.3).
Therefore, for a > ag being sufficiently close, with high probability, for g E almost everywhere,
(v
A- A
a
(
A A-2a 2a
AG < Op
O
o?
+ +z
n²
n2²
A-30
= (o? o
3/3
Combining the bounds for V and AG, with high probability, for G almost everywhere,
T (Gtg
Öp (ITx k(g ([T'kK(g,)) ((1.)))(2))
82
PT
+
1 -
n2
n
nk
Hence,
k
V(A)
T k(gii g)cs)
dpp(9)
og n²h2
i-1j-!
$ O'Opply
100
rT
1 - rT
nk
A.2.3 Excess Risk Bounds under Conditional Orthogonality Condition
Theorem A.3. Under Assumption and the conditional orthogonality, if = n (0,
R(A)= < θz (n min(),2)0 + O2o
ro v Te +
(1 ro) (1 (1-re) re))
n
nk
Bias?
Var(A)
Proof.
This can be directly proved by applying Lemma B.11 to Theorem A.I and Theorem A.2.
A.3
Small Regularization Induces Vacuous Generalization
In this section, we prove Theorem 4.3. To be specific, we derive upper bounds for bias and variance under small regularization respectively in Section A.3.1 and Section A.3.2.
A.3.1
Bounds for the Bias term
Theorem A.4. Under Assumption 1, x====== n0, 0 [B, o0), then
(A( Opoly (n-min(x.2)8/2) r I,...,d d.
30

---

Proof.
Similar to [37], the bias term can also be written as
(A) = |A(To + 1 2
For simplicity, we first ignore script r. Similar to [37], assume that f T for some g e I with llgllz & C, and restrict further that f. & 2. Let = n- for E (0, .). Using the notations of Lemma C.12, denote 1/x X(To A)-1, by the definition of B(2), we have
B(A) = 1 T T2/2 g) 7L
Utilizing Lemma C.12,
1x/
T/// 9 /
< < ( 1//2 | g)
CIT/// // 1/21 1 -2/2((/
$
C/T1/22
// 1 | 2"
1/2 /
//
10
(2-1)/2
|1 T
CX
10 2- (2-1)/2 / 1
1/2
t-1
G²
where the third inequality uses Lemma C.12, the last equality uses the definition of and the last inequality uses Lemma C.6. Finally, by Lemma B. with high probability,
T } GA
= , + < |
|
| 0(1).
Since / < min(s,2 2) and I < B can be arbitrarily close,
(A) OF (X002) -Opoly (n -min(s. 2)8/2 (n-min(s2)8//)
A.3.2 Bounds for the Variance term
Theorem A.S. Under Assumption 1. if = n 0 (8 (3)
of
Ee Eeg,aln Aln [Vr(A)] > Spoly
r L,...,d,
where of is the lower bound of E[ gg g G almost everywhere.
Proof. The proof is similar to the proof of lower bound in [37]. Note that V,(A) is monotonically
decreasing with respect to X, it holds
V,(A) (n
d.
Following the notations in Section A.2.2 and ignoring the script r, we have
V(A) [ n²
aa k(gg 9)c
dpg(l).
By the optimality (3.1), we further assume as Li et al. [9],
E[elg] 0, g G almost everywhere,
31

---

then, for a > an being sufficiently close, with high probability,
2
als, 2e1. Ben, 1gn.k
n2
1
= =ee,, Belllor Ben,elon lan.
(Tex ((tss
n2212
1
-le 2l ... Ben klank
(Txk
n2
==
of 3 nk
(T)))(o))))))
nk
where we use Lemma B.7. By Lemma B. 10, for a > og being sufficiently close, with high probability,
Te 11 - | 1n1 & Ōp A
n = R1.
By Lemma B.3, for an being sufficiently close, with high probability, for almost everywhere,
(A-On) a-a
9)9 - k(g & 2Or
A (A-a
nk 1=1ø=1
Hence, with high probability, for g almost everywhere,
1 n nk
T k(g)))))
| :)
H
| 1)
T k(g, ||= T k(g :) 12
7
T ((g.)
T :k(.)) .) | (
) H
+ | (2) + >
7
T 1 ) 1mm))
| 1k[g :) {
Rí
Ri +
1 n
k
Rı
R1 +
T k(og).0)) nk
T k(ggt 9)
nk
Rπp (|T>> ((gg.))1..
Therefore, with high probability, by Corollary C.2.
on Spoly 1
La,, Ee, alor, Een, vln, Besploy V(n 00)
Opoly
nk
k
A.4 Excess Risk Bounds in Denoising Score Learning
We prove Theorem 4.4 in this section. rewrite it as the theorem as follow. Theorem A.6. Consider the denoising score learning at timestep Assuming that
E 2 & o2
BIE31 $ oz
32

---

, then if X >=== 0 8) and the conditional orthogonality holds, under Assumption the excess risk satisfies
R(A) & Öp n min(s.2)0
+ 0 Op
no
ai
v re +
(1 - a (1 re)
nk
Bias" (A)
Var(A)
Proof. We prove by simply computing To. In the setting of denoising score learning at timestep t,
gij Varss v1 Outa..
Therefore,
1 nd Cov Dij ( .
4
0 2(1 ao + 20,0
0(1).
To 2
Var
(ij
Hence, the proof is completed by applying Theorem 4.1.
B Concentration Lemmas
For simplicity, we sometimes use Jrh, to represent {ggh--iu=-- where the first & components
01....:4 9h represent 91.1----, 91.k- the second l components 9k+1.-...1 92* represent 92,1 :2.1:-.-- ...... and iteratively, Umm-1)k+1..... section.
92.
represent 9n.1:.... -n.kk We always ignore the script in this
Lemma B.1. Under Assumption 1, if = n- (0, B), such that for being sufficiently close, with high probability,
x-
T + (T TG)T $1 & (1
Further,
T イ -- - < Op(1).
Proof. The proof is standard in concentration inequalities, while utilize our novel Bernstein- type bound, i.e., Proposition D.2, to handle the k-gap independent random sequence. Denote A(g) Tx (T T E[A(g) O, then à To)T d Erh. A(gi). For simplicity, we denote A; = A(g:). As the first step, for any positive r,
nk
nk
Amax
Σ
A
Eir
exp
Σ
A -
-1)
tr
where I is the identity. Then prove by Proposition D.2. We first bound ||((g) by Corollary C.2,
T
T
M2x-a
which implies that
|A(g)) 2M2
Therefore, by Proposition D.2, for any positive t such that t. 2M3x <
E Tog
log Eir
exp
Σ
nk
A
-
log n log + log
nkk T
intd))
Pnkoo
169
1 t. 2222 log
where
2 ))
2
sup (c(...nnk)
Amax
Σ A(ga)
intd intdim (E [B())))]])
Cardk
K=
iek
33

---

Hence, for any positive
nk
P
Amax
Σ
A
2 x
log n log + log (22 intd) + +nkvv
169 1-2-2.12 - log
exp
inf
1=0:12M² A
= Toam
e
exp
log log log
nk ( (inidd)
inf t=u:2
1
exp (-tx + 1- L. 1.2M2 -0 log
169t2nku²
x212
log
where the last inequality holds by the basic inequality:
3
1
e
x 0.
x22
As the second step, we select L. Denote 0 169nkv2
Φ
2M2 log and let / 20+
then
nik intd) ))
(20 + dor))
x²²/2
P
Amax
A
exp
logg + log
1 [
exp
x
28 + or
If x 3 20 + dx then
P
Amax
Σ
Aj
x
<
4exp
(ognnogg + log
nk intd)
exp
x²/2
20 dx
Therefore,
P
1 nu
Σ 1-1
A
nk
1
4exp
[lognlog log + log
nk intd
exp
20 dx
x²/2
By setting 8 = 4 exp (log n log 3 log (aki intd)) exp (-
x²/2
and solving
20
4exp (log n log 3 log (nk intd))
4exp (log n log 3 + log nk intd))
x & 2Φ log
+
40 log
5
we have, with high probability,
1/2
4 log log 3 1fth intd))
[eexp(log log 3 log( intd))
2Φ log
40 log
nk
5
A
nk
nk
4expl lox
lox 31 lone at intd))
40 log
We next consider the bound for
Note that
n²
27
sup
CardK Amax
E
Σ A(oc)
K (l......))
sup
CardK Amax
E [A()))
k E [[.
further note that
Lr (E [1)
E [A(g) log [E (A)g)))
34

---

increases monotonically with respect to E [A(g))]. and by Corollary C.2,
E |Agg) = E (T> "T, }}}
x Max -E
T $ Ty $
Ma "TTx
have
"M E1f [11)= [
4 4exp
log n log 3+ 1o
2/ ||1||1<>>]]
4eexpllg log 3+logg( 2 intd))
676b log
40 log
n n2?
nk
nktz 5ry 1)
exp
log log log
676M22 looo
TTX
By Lemma C.3,
tr (TT)))
A
(ITT + A)A
$ 0
=0
$ 00(A-a00))
TT
[TT 1|
T
Therefore,
1exp(log log 3og u intd))
40 log
A
k22k2
n
We finally obtain that for oxp
x-a
A
& Ör
(
nk i=1
Further, we have
{ T 1/2 (To 1(T + A)T 1)23 -1
I
12 (Ta + 1/- =
(1 - T 1/2 To)
(1- 1|- : (T -Ta)Ts $ $1)
$ 0+(1).
Lemma B.2. Under Assumption 1, if = n 9,00 e0 (0,3).
T [(Taft [[Taff
Tafx) -Tfx)
Tafx)- (T - Tfxl] 2e (2E).
Proof. The proof is standard in concentration incqualities, while we utilize our novel Bernstein- type bound, i.c.. Proposition D.3, handle the k-gap independent random sequence. Denote
E(g) T (Taf# TyfA). E(g:). then
nk Σ
|r [[Tatt Tefx) -
IEg
H
nk
74
Further let X = - Es, X; = E - EGG, then
| t
[[Taft Tafa) - -
1
n
X;
nk
7
35

---

For any positive z, 0 we have
c - X;
P
X
nk Σ
2c
Fcosh
x;
(B.1)
(+)
nk
2c
||elll
X
i-1
nk
$ 2c
where (*) is the result of Lemma C.8. Then we are going to apply Proposition D.3. Similar to [37], separate to two cases: ag and ag. where use truncation technique to handle the more difficult 8 & og case.
Firstly, we consider the case > By Lemma C.7, for > og being sufficiently close,
| Ô (X (A-at .x..
Hence, by Proposition D.3, there exists a constant C" such that for any positive such that t.Mx x <
Flogn
nk X₂
On
log E exp
MMxklogn
where
2
2 = sup
E
Σ
Cardk
K k= ()......)))
jEK
Apply into (B.1) and take 0
20"nkv²2 + x Mx log have
nk
Oz E nk
P
Σ
X
<2c
X
H
i=1
C"ffnku?
$2
exp
0Mxxloog
x²/2
=2cxp
nO" + x Mxklogn
x²/2
=xp
U U++VV
where U nkunk Mxglogn. n. Let 5 2exp
x2// (-Utel
we have
< 2V
+ 2U log = Or (Mxklogn + Vnko²)
log
Then with high probability,
nk
Mx log
22
A log 11
v2
X,
$ Op
& Öz
(B.2)
nk
n
nk
n
nk
H
Secondly, we consider the case & ag.
For any > 0, denote Ωr = (g E G [f) < f and
E(g) [(g) X = & EE, X, & EEC Then similar to Lemma C.7, for 0g being
36

---

sufficiently close,
| & Ma $ $ (oE (57 f2
< MaX $ (1 10 +
< Ma & (Mo / |M]0 + +()
< OA + 11 $
Mx;
where the last inequality uses Lemma C.5. Further we decompose
1
n
nk E
nk
E
EE
E
+
E
(
+ Eg + (oen,)l
(B.3)
nkk
nk
nkk
H
1
H
Regarding the first term in (B.3), set = n', 1 < high probability,
a+00 << a=* 0, then, similar to (B.2), with
Mx log
< Ōe A a log n
62
BE
< Op
no
nk
nk
H
where
2
1²
sup KS k)
Cardk
E
Σ
1x,l
jER
To bound the second term in (B.3), only need consider the case Ii $ Q4 Since the Markov's inequality yields
P ParPg (g $ Ω4) & 1 2a (referring to Lemma C.11), we have
where q
PP (gt,1 Pc. 96,2 Pu..... 9s,k ,9.
Ω2) & (9 le) & t 9
Then we get
(gg E Vi) > 1 11-t-911910
So the second vanishes with high probability as long as l 1
For the third term in (B.3),
[g) (ge
$ BlE(g) (o
= 1 (o (f%(e) - fx(9)) |. 1/2 k(g :) 1|1m
< Mad a//E [1 (1ye),)) 18% (g) fx(2))]
< Max a/2 (f (g) - fx())) [P $ 2nj
< Ma a (A8/2) t //2 9/2
where the second inequality holds by Corollary C.2, and the last inequality uses Lemma C.4. If I all then
A [E(g)) & ō
Vn At)
Finally, the three requirements of are
Oa
<<
2 0
1>
and
where q == 2a. It easy to verify these three requirements hold.
37

---

Combine the two cases, with high probability,
1
nk
22
X;
E Öp
+
+
T
nkki
H
where
2
2
Σ
|x5111
sup () Cardk
jEK
The last thing is to handle v² It is easy to verify that
v & CardK E| & xE| #
Note that
E X BlIl sup, |T k(g,
H :)
|| (1000) MaA (1,(6)) -
then by Lemma C.4, have
E
(f)(g)) fa())) =((2).
Hence,
Therefore,
T [TTa Tafx) (TSØ - -Thw]]
& oe (1t)
Lemma B.3, Under Assumption 1, if x= n0 e f)r og being sufficiently close, with high probability. for g G almost everywhere.
k TT k(gg. 9)]
-| k(g $ 2 (1-
a-a n
nk
Proof. The proof standard in concentration inequalities, while we use the net theory to obtain union high probability bound as Li et al. [37, 39] and utilize our novel Bernstein-lype bound, i.e. Proposition D.3, handle the k-gap independent random sequence. Denote X. [T> klggg g)]
with its expectation over each data 9zj
[ k(1g,,
1 * = μ.
For any positive s,
n &
1 (Xij p))
PP
17,
g) De < 2e
exp
71
We next prove by applying Proposition D.3. Note that by Corollary C.2,
Xxal & T k(g, ((gg)))le & MM 2a B,
then by Proposition D.3, for any
<
nk 2 logn
n
b
C" 22k22
Eexp
(Xi 11)
$ exp
nk
n²k2 (1
uk 2Bk logn)
where 2
sup
Card E
Σ (Xij - (1)
Then by setting
3C""442.0 log ne
enk
k= (1)
jEk
1 R
C" nkk?
P
Σ X1g
17 9(11))
=e
$ 0t exp
nk
n2122 (1
A 2B log
@nk
< 2 exp
40"0² + 4Bk log ne
38

---

Let 0 = eexp
2n 40.044 4BB log ne
and solve we obtain
4 log B log n
16 nk log
2
n
For the reason that considering the union bound for any g, denote Kx {Tx k(g, geg and utilize the net theory. By Lemma C.9, we can find an e-net F c Kx c H such that
{ $ Cre(eee 2d
where
e(n) Then, with probability at least V.
4 log 3 B log
16C nk
2| log
X,y - | 9)
nk
8
Note that by Corollary C.2, we have
2 (I m))
2 sup E
kB
T *TtK(-99lli
kc Card
jEK
which implies that
A a
v2
1-220
0
nk
11
Hence with high probability, Vf
Xij
|Tx k(. 9(:1)))
< < (A-O//
a-a
nk
n
At last, by the definition of for any g there exists some f F, such that | - fl E,,
which implies that
k
kg. -15112 < =0(A-9)
X
p ((g)
=00
nk
Therefore, for a > on being sufficiently close, with high probability, Vg e 9 almost everywhere,
1 (A-0//
x-a n
Xuj - kl. 9)1f3 < &
n
Lemma B.4. Under Assumption 1, if = n- (0, for a og being sufficiently close, with high probability, for g G almost everywhere.
T Mg. & (v>
(~-0 of
nk
Proof.
The proof is mainly based on the fact that cig 1ig is nab-Gaussian with norm
P
x k: M15 015))1
>
2exp
nk
==1==
1 E Σ T
b 9:9 (1519s
Here Vf e means & such that 17 ((g,
39

---

Hence, consider the net F constructed in Lemma B.3, with high probability, Vf E F,
k
Tx
x(g.919))c)
EOp
Tx
k(g: guy)cyl9ns
nk
nk
$ Or
1
Σ
T
((gg9:5) ses)essloss
nk
V2
O
1
Σ
n
| x lg (1gg.995)c3 (ayloll
nk
i=1
2
1
<
TTx k(g k(gg [eyllvls
nk
o²
< Öp
[T k(g, [e)]
nk
Further, Vg G, there exists fe F such that
T k(g, g2s) - / 10 =5= -
Hence,
1
k(g - [(9s)] 6ij
Eij
nk
nkki ==1
==1==1
Note that englgs is a² sub-Gaussian, then
12
Eigl 3 & exp
2nk
Hence, with high probability,
1 n k nk
02 $ Op
legl
n1
j=1
which implies that
1 1 k
1
T
k(g.9.) f(gh))
G1
loyl
Op
nk
n nk
n
Therefore, for > og being sufficiently close, with high probability for E 9 almost everywhere,
1 n ru
ΣΣ
k(g.gt)e
where we Lemma B.3 and Corollary C.2.
Corollary B.5. Under Assumption 1, if = n00 0 (0, 3), then for > orp being sufficiently close, with high probability, for g e G almost everywhere,
& ( - 1x7) K(os
nk - TT k(g.9))e & &Op
(1
Ti nk
Proof.
Corollary B.5 can be casily proved by Lemma B.4 and Lemma C.10.
40

---

Lemma B.6. (Concentration on <²) Under Assumption 1, if = n 0. (0, R), with high probabil- ity,
1 n nk ==1j=1
2 0² + Ör (o::-72)
+
Proof. The proof is mainly based on the sub-Gaussianity of elg. Define Xij = cigy 9.5 - -Eleflou.l Hence EX2; = 0. For any 8, > 0,
0
Xij
21 t
< 2exp(-6t) exp log exx
_
Xz3
nk
nk
The key part is to bound
log E exp
Xij
log
exp
Σ
k
Xig
n
log E exp
0
Σ
k
Xis
nk
nk
n2
j-1
5=1
Note that X,y is sub-exponential, then for
nk
Oxo7'
o² Cko
0
log Eexp
X1j
nakz
nkk
Cko?
0
nk
By Lemma C.17,
h Σ
C ok 12
log E exp
Xij
$
nk:
Cxo2
j-1
Hence,
0 n
k
C 40
ko
log E exp
Xzj
nk
Ckoza
i-1
Set 0 +
then
k
(
12 2 + Cxo2t
I
Xij
=
$
2exp
nk:
Let 6 = exx
( +xxo2
ckt
12
then we can solve that
& Ör (o2n 2)-
Therefore, with high probability,
n2
k
Öp (o= t).
Xij i=1j=1
nk
Note that the conditional expectation
k
nk
1-
then with high probability,
1
$ 0² + +0 (0,n $)
c
nk 1-1 1-
41

---

Lemma B.7. Under Assumption 1, if = n E ()r > og being sufficiently close, with high probability, for g almost everywhere.
10 [2 Öp (x-x)/ A-a / n
1 nb
[ k(g.. DEN
[T k(gg.
oe
Proof. The proof can be easily extended from the proof of Lemma B.6. We first focus the finite net constructed in Lemma B.3. Similarly, we denote XCx = {Tx *k(g)) geg By Lemma C.9, we can find an e-net J C X H such that
|F
CxT r,
where e(n) 1 Then
Denote Xi,
TTx kgoj.. 9) [[ -Eeyylos) lois with Bes Xzj O.
X k(ijj 9].] 2
T K(ai [ B 1
Xij.
nk
nk -=1j=1
nk
1=15=1
By the fact that e lig is o² sub-exponential, there exists a constant Ck. such that for 0 nk
Uxo?
log exp ( nk
0
[6llo - Beigooss) < Cho n2
9)) =0
Hence, for
1
nk
Oxo?
02 [Tx 1 k(gg 9)
log E exp
[ Gkyloss [Ee]]ou]]
& o
rik:
22222
In this sense, we get an equivalent (kki Cko² [TT k((gg 9)]² with sub-exponential norm C,iii Hence,
That is, Xis is sub-exponential
E
(1)) 2ij11
g² n²
log Eexp
Xij
&
n2
(1))
1=1
max; 1- K nk
Denote A
m मं
2i-1
ck
B
nk
((0) max; Σ/- K and for any positive I, take
0
2
we have
Bt
f2/2
Xig
>t
<
2exp
nk
2A + Bt
//2 then with probability at least
Set 8 = 2exp
8,
2
2 ;
t Op
B log
+
A log
Hence, with probability at least 8.
2[FF]
2 8
X
B log
A Aog
nk
8
We next derive bounds for and B. By Corollary C.2,
X 2a
B < 8,0
n
42

---

To bound A, by definition, we have
Clif)
A
n² 1=1
C n
[Tx
k(g [tt)] of
< T
k(g
CR 1
Σ Σ
[Tx k(g.95))'
n nk 1-1
By Lemma B.3, with high probability, EfeF.
(ggg. 9)] - 1 k(g. )12 < A V x-
nk
By Lemma C.2,
TT (kggg,)) & Ma1-2a |TT & MaX-a
then
(
a 11-30 ot
A Ör
Jointly, with high probability for all fE
k
[T> k( (
nk ==1==1
nk
Ö
oe
Further, by the net theory, Vg G. there exists E F such that
[T> "(ar P(aw)) ==0(1-))= =
n
Hence,
1
[Tx K ((w)))
E & 0
A
nk
71
nk 1-1
a n
O²0Op
where the last inequality is the result of Lemma B.6. Jointly, with high probability, for all g G,
[T> (kgggggg))
12
1
[T k(gg. [)] 1
Öp (-a1
a
nk
n
The following Lemma B.8 can be viewed as an extension from the combination of Lemma B.3 and Lemma B.7
Lemma B.S. Under Assumption 1, if n , (0, for a ag being sufficiently close, with high probability, for g G almost everywhere,
1
n
k Σ
Tx K(gihn TT
ET, k(gg)) g). Tx M(ggpo9)ess
nkik
jj
7-a 1
02
Öp
1 00
+ 02.0
= =o02 + o)-ōr(1-0)
01
n2
n
43

---

Proof. We first concentrate elg and then concentrate Denote
Xijia = Migis Cy. T k(gis S) Gija Pij. T k(on 9)Tx k(gi Bei Cija (yy Fijs
Note that 1új,9:hh : 9iiz 6ig Mhis Mijz is the product two sub-Gaussian random variables, then ctj, 9ht Pizz Et 1inl 9ide is sub-exponential. Similar to the proof for Lemma B.7, for mk(R-1) S
og
Olthiba)) 2
E 21==
E 21z- Jotkj
0² (k- Ck
0
log Eexp
Xiniaa
$
nkkik:: 1)
1= =1 1,
max; 2jj=1 2 222 1o
Cx
0 nk(k-1]
where
Ofiriia) CK.x k(gis, k k(git) g)0
Denote
(hhrsa)) )
A = 12 - 1)2 i=1 J1 j== j=
ck
B
1 nk(k - 1)
maxx
k
51 j2 I.
and take 0 BA have
12/2
Xijia 31 1
& 2exp
nk(k - 1)
2A + Bt
1=11f
2/2 (2A+BB
Set 8 = 2exp
then can solve that
2 + B Blog
2 Alog
& Op
Hence, using the net F constructed in Lemma B.7, with probability at least 1 8,V5 E F,
1 nk(k 1)
F
22
Σ
X <0
B log
Alog
1-1
1.
By Corollary C.2,
A 2a
B < o
To bound A, note that
C
k
2
Σ
A
n2 2
1)2
i=1
J1=1
C
n
Σ
[T k(g Disi (kgg,iis))
[T, 1 o.
n n2k(k- 1)
1=1 1
T k(g >|
T k(g (ll..9)] o..0"
nk
By Lemma B.3, with high probability, Vf
k -17, 11EE2 2 1 (~-0 a-a
nk 1=1-=1
n
By Lemma C.2,
T k(g.,))12 < Ma
44

---

then
A Op (1-30
0012 (2m0
Jointly, with high probability for all FEF,
k
Σ
k(anh TT k(gig 9) (Gij Gizz - E [ean Caja Iin Pisz 1)
nk(k - 1) da 1.22i
a
Oz A
Further, by the net theory, Vg G, there exists f E F such that
[Tx Kaihh T k(gg)a)) 9) - (995) & =0(A-9) = 0 (A aa
Hence,
Σ
[T
( ((9isa f(gg)) Gi Cia
nk(k 1)
1= 11
J2 1,22/1
Ama
1
n1
<0
Extal
71
nk:kk - 1)
A n
&
<0
n
nk: i-1 j-1
0 A
where the last inequality uses Lemma B.6. Jointly, with high probability for all E G.
k
T 7 kk(gigs g) (eij C E [eig Eija With Rijz))
nkikk - 1)
1,22h
a-a
& Oz
1
As the second step, we concentrate g. This step is similar the proof of Lemma B.3. For simplicity, we directly deduce
1 nk(k- - 1)
T k(ghs. g)Tx k(gi), [eg, E loulo.. 91t.] E [T, (19s)h9)7y k(g gea 2
Est2
j2
Jji
A 1 1-a
< 0000=
n
Therefore, for a > og being sufficiently close, with high probability, for g E almost everywhere,
Σ
kK T * 9) Tx K(ghhs 9) ETx M(ghi T 9
nk(k 1) i=1
12=1,
T k(gsn, k(ghtz 9) (Ei, Eigz - E [eEh Esgz 19sh s11zl)
nkkkk 1) i-1
j1
j2
a1
k
Σ
k(gifi 1900s)19911 TT k( 9)B [ess (assina 63fa Moth M9pa) ETx" k(ysn D)su, Tx k(g (
nkik - 1)
i-1
1=-1
A-o
A 2 2>-V
E02 61.2
Ör
1 1-0
+ 00
n
45

---

Lemma B99. Under Assumption 1, if = n 0 (0, 3), with high probability, for E G almost everywhere,
T k(ghssi k(graf "kigaat D) Go2i2
n²
f1=1 12=1
Tx k(g.
1- rT PT
1-re) )
< E
k
Proof. We prove by the truncation technique. Denote X; Eij Tx "(gg Dis..ii)e.... We truncate by 7 which will be determined later.
X, =X . + X [3je
-xLLllulerrshh.... E X (lyglssss- (e(l E X (30
x
= + x!!)
Therefore,
Tx ((B Moiniii Graja
n2
J1 12
12
Σ
X X
2
x x()) + x x(!) + xx x + xxx1xxx
n2
We first bound the main term
n
2 2ig
17
m
x x!
Note that by Corollary C.2,
x(11 00
EX!" 0,
by Proposition D.3, we have
n
62/2
PP
Σ
x
(1)
>
2exp
(B.4)
< log ni) 1. + Ei_ Ex(11)
which implies that
f/2
p
x
(1)
D 2
< 2exp
kA- 1) + Σn_ EX(11²
(-
1/2
Set 8 = 2exp
then solve that
log 1ogn)++ Ex!Lyy
2 t 3 0 1- log 5 ))²
Σ
EX EX
(1) 2
+0
log
and
? & 0 (0x100000
x22-002 22? 2 n nlog²
2
+ 0
Σ !X! log 2
8
8
46

---

Therefore, considering the net F constructed in Lemma B.3, it holds with probability at least 1 5, for any f E
2
1
X
11)
72
R-2
2|
Σ Ex! (1)
n
2|
0
2ax - 22, log* log"
+ +0
log
k2
2nk
2nk no² T k(g,)) 'i' (kºrT + k(1 rT)) log ô
)
0 A
1 k2,2 2 log" n log"
+ O
k2
where the last inequality uses the definition of net F and Definition 3.2. By setting т = n'ā with L-ad we have with high probability, for any f F,
i <
Tx k(g
rT+ 1 1-r7 rT ))
0²
12
2
(xx")² 2
We then consider
Applying Proposition D.3,
((x(t))
X (x n/
3 2exp
E (xxa²) 27
Hence, with high probability, for any f F.
(x;1)) 2
> nE (x("))² 27
+
2a 2 log
x
Óp
n2 2
nk2
n2hb2
T klgg -112
Pr 1 1- 1-rr )) +0z
x-TToV nd + + 2
0
k
n2
T k(g ) 11 1 - PT
=Ōp
02
FT
n
Combining these bounds, with high probability, for any f F, the main term
Σ
x
$ Ō₂ g2 T *
PT + 1- Pr
))
n
k
1,g
We second bound the residual terms
Σ
Σ
x x!1x (2)) xx!2!
xxx2) x!2]
n212
By Markov inequality,
|
P
E3j [k], > r} &
Σ
p
fl > r] & Σ
74
Here the net is the e-net with 1
47

---

then
11-
19
P
cisl & KT, Vie n|, vf F
Σ
Lo
5
That said, if we set l > 1 then [((] vanishes for the reason that e is (conditional) uub-Gaussian. Hence, with high probability, for any f F
q
Σ
+ (2)
x
11) + x 2 (2)
x E [tL(sje(()))cusr ] + E [xl[pjetthlepmmm x + E3 [[
n2k
n nk
E²
E
Firstly, by Cauchy-Schwarz inequality
122
X
[E)
(6y1
1.2
EXPP
Σ |etll Kr
Σ Egj
(1 - rT)
(B.5)
+
3²0(1
12
k979
(1 rT)
0²0 a
Pr +
Secondly, by Equation (B.4),
12/2
P
Σ
3 t
& 2exp
0 (A- (2- nk) + ΣT= Ex.")
we have with high probability, YFEF,
(rT (1-rT)
G2 T k(g x
Ör
\
nk
n
Further, by Equation (B.5),
E
X,I
Jey [x
/ (
(1 - -rr)
50
Therefore
2 E
X
(eglskk)
|l
nkh
x(") $ rr +
(1 - rr)
k
11/277
Note that under the condition l > 1. it holds
x-
and -
X
79
1/277
Then with high probability for all f E F, the residual terms
T T k ||
x (1) x
(2)
x (2) 0
+ x
x x
(2)
ōp
(
1 rT
n
48

---

Jointly, if we select 1 < l <
1-ad
then with high probability, for all f E F,
Tx
9TTx
k(giiiz D) Gizi2
n212
1==1
k(g,
TT (TT+ 1-rr rT k
E Op
m
At last, for any g G, there exists f E F, such that
(125
k(g, -)l nk
Tx (( f(ghn)))
(kg. =0
Hence,
[ l ( K(gnszz) g) - f(ghi)) Einj Eruja
k2
=1 12
1,62
J1 =1 f2=1
|T kigg 1
122
<0
Eiy Eigtal
nk
122
|Tx ki 11zz2
<0
Öp (p)
nk
|T k(g -
=0²Ōp
nkke
| | ((g,))())))))) -1
E
nk
where the second inequality utilizes Lemma B.6. Jointly, with high prohability, for E 9 almost everywhere,
11
Σ
k
Σ Tx
"( k(gizin enn Giai <0²0;
IT \T> ) 1|22 (IT +
1 1- rT
n2
n
phis
Lemma B.10. Under Assumption if n000 e (), for >> ong being sufficiently close, with high probability. for g G almost everywhere.
A-a 1
r Tat - T H
& Ō
n
Proof.
(rāratkle
| k(g,
T -
1
(T To)T k(g. 111
ाेाaž , I (T -T)T = |r>
For the first term,
r &
a. < 1 satisfies this condition.
49

---

For the second and the third term, by Lemma B.1.
IT N & Oz(1),
A,==0))
A- n
IT
For the last term, by Corollary C.2,
|TT k(g. & Mad
Therefore
( Crataikla M2 / k(g. )N & <Op 1
n
Lemma B.11. If the conditional orthogonality holds, then
ETx ETTik(0s ((0,,.9))a.,, Tx '(gija gia & (re v ro)o (1TT (kg,))))))))))))
Proof. By the optimality (3.1), we decompose:
E [T k gen T k( g)
= =E [[Tx (T g)g Tx - (ee))))))))))))) (Tx g) - T "Kgr (. s)
where 9 and Oiji share the same uin but with independent x, and 2t. Jr and gijz share the same Wijz but with independent z; and x²,, ev == yii - f (9r5)); ei == Vidz f ;2) Further,
(Tx klgin g) T klggn g) (Tx 1 9) - (1r"(((r))))))<<)) (Tx kKgusn (Cis (rj)) + Gij (Tx k(iij g) - T (((r))))))
T kl ()( (rr))) + Eijs (Tx k(g 9) - - k(9r))a)))))
kigus (occisi:)(es) g)( -E k(gr 9) (Etg2 (11j2- C4
A
T ( - Dej, ( 9) ((9
A
+ Eiji (((())))) T k(gr)) 9)) Tx k(g 944zz E(
+ Gij ((9s))))))))) ( 9)) cija " T "N(g g))
Then we bound each term under expectation respectively. For Ar,
E [[Ai] = E [Tx k(gr), g)T g(gr))))) =E(i) - -x4)))]
< E (T k(gvnn 9)) (Tx k(gess 9) ?| E [(eih - evn ) - )
- k(g 11 E [(Eg Ezg, -2, (ee) 21
Note that the kernel Hölder-continuous assumption implies that fo e H. Hölder-continuoss with index [19, 18]. Hence, there exists L. > 0, such that
1Gtp crnl & Le 196n
9 11
then
1esh Evrs 12 E L3 |1ash
gey IP.
50

---

Therefore,
[[A]] & E |lo. - giss |2
820 (IT5 klg. 1112))
< [8 [199)] - grsh 111))
-²0 (17x \r 11 11(2))
< ro000 (115 k(g -) 112))
For A2,
E = E [Tx k () ceji 1afa (Tx k( 9) TT ())
$ E (Tx k(grs 9))² k(gttr 9) 52 9))² 1
[(e,, - Epg, )e}$
E (Ix k(gh 9)) E (I k( 9) Tx k(g 9)) 2 2 E [(Eg =
= - kke 11r. E
(Tx ((lis.)))) 9) -xx ((g 9)
2 23/ E B[ - )3,,)
< <aa |Ty k(y, ( >11>>> y ((0ss)0))))))) Tx "k 9))
(ea - +35))
Similarly,
E [(e,, - =rr,,) < v1))
We then focus on
E
(Tx k(gij.)) 9) -Tx ((aw)s))))))
Σ dad Mis
= E
Xp) (1 Aa) (g)es) (x (er(()))) (g(r))) (ea(gii)) - (((rs2))
X2
Σ X,, )2
e (g) Z -
Aadr
(2+++ (c00 +
Σ
(e
X.)
If the conditional orthogonality holds, then
-
X
E k(g 9) - T k( =
(A + Ar er (g) 2 (er(o)))) - crr(ss)))
By the definition of re.
E (((((r)))e((gr)))))) cr( $ rre)(.).
Hence,
E| 8²0 (| Viaro.
For Ag which is the same as Ag. if the conditional orthogonality holds, then
E[Aa] < 8²0 ((o,))(( Vrato-
For A4.
E[A+] E Eij (( -
:k(grnn 9) Eijz
< 2y (T= - " 9)) 2
E
4/ (Tx (h-Misis g) - T (x((()9))))))) 27
2
< BB (Tx ( TT 1 k 9)) |
$ 00²1.0
"k(g (1T5'b(g.))1 11ze).
51

---

where the last inequality repeats the same procedure in bounding A2- Jointly, if the conditional orthogonality drs 0, Vr, 8,
ETy (koosi. Tx "kgija Giys (r v ro)0 (1Tx-M(9,))
C Auxiliary Lemmas
C.1 Key Lemmas
Lemma C.1. (Lemma A.5 in (391) Suppose H has embedding index onp Let p.y 3 0, a > au such that 0 < r 2p then
kkg > [ap & M2 9 G almost everywhere.
Corollary C.2. (Corollary A.6. (39]) Suppose H has embedding index ag and ag. Then the following holds for E G almost everywhere
T k(g
100 < Ma
| M(g :)
?
12 & M²
T 1/2 k(g, :)
< Max0a
Lemma C.3. (Proposition B.2 in [39]) Under Assumption 1, if = n and A E B), then for any p > we have
tr (T
Lemma C.4. (Lemma A.3 in (37]) Under Assumption for any 0 < & s, 1, have
x
9-922 2:
(*(r)
X2 log
8- 7 2; 8 7 > 2.
Lemma C.5. (Lemma A.7 in (37)) Under Assumption for any 0 & 7 < 8 2,r 1,...,d, have
d, we
A*
s s< 9i
|
= 7 ? Lemma C.6. (Lemma B.6 in (37]) Let A, be two positive semi-definite bounded linear operators on separable Hilbert space H. Then
log
[+]]
1,
A B BB( < |ABBl E [0,
Lemma C.7. Denote E(g) = T 1/2 (Tol -TgAa 10 Under Assumption if agg a > 0gg then
1k & Ô (A-at)).
where & min(s, 2).
Proof.
[l = IT [T (gg fx(o))
< |T, k(g: 11 - SALL
< MaA 8 115/ fxlle
where the last inequality is obtained by Corollary C.2. Then the proof is completed by
1/5 fAll & Mo SAllpa Ö (((66-a)72)
where we use Lemma C.4.
Here state the lemma for any I,..., d. For simplicity, ignore the script
52

---

Lemma C.8. (Theorem 3 in [54]) If X' is Hilbert space, X E X, and EX, = 0 for all j. then
11
12
Ecosh A
Σ X
E
MAx - ||x31]
Lemma C.9. (Lemma B.8 in (39]) Assuming that 9 = TR.d is bounded and k(;;)) CD 9) for
some p (0, 1]. Denote KCx {Tx " :)g geg Then the E-covering number of Kxx
(Kx, la, & (AE) ",
where CM is a positive constant not depending on c. Lemma C.10. Assuming that 9 S I& is bounded and k(-,-) E CG x for some E (0, 1]. Denote KG.A = { (TT)) - 1) k(g. " geg. Then with high probabiliry, the e-covering number of KG.x
N (KG.2 (bo,,) & C (*T( 26 P, where C!"H is positive constant not depending À or
Proof. For any a, b.b e 9.
1 - 15)) k(a,,) - (1a) k(b, )1
supgeg (Ta) - 1) k(. - (TG) ' 9)
suPgeg (T 1) kgg,0) - (Tat - k(g b)
Note that by the properties of RKHS,
(T Tx 1) k(g,a) (Tat- 1) k(g b]l
(To) TT') k(g,)) 111 [1(((,,) - k(b,
(T - 1 k(g, 1) V Vk(a, a) 2k((u, b) + k(b,b)
(T - 1 k(g.) )) /k(a, a) - -k(a, b) + k(b,b) k(a, b)
- - k(g, :) 22 ||aa - b/
&V < 11 + |T> k(g :) lxx) ||a - bl
<VI <VI T
k(g -) )11x) la bll
<VIxA- 61
where the third inequality use the Hölder-continuity assumption on kernel function, the last inequality uses Lemma B.1
| = T 1/2 1 Oz(),,
and the kernel function is bounded by K
sup yEg [k(g [k(g -11 & K.
Therefore, to find an s-net of Ka.A with respect to I| we only need to find an ě-net of 9 with respect to the Euclidean norm, where غ
2
cd (Tx.
Hence, the covering number
N (Ka. (bo::)) & N (1. C!" (XE) 24
Lemma C.11. (Proposition A.9 in [37]) Under Assumption 1, for any 0 E og and a > ao, we
have embedding
2a
[H]* - (g dp),
9s a - s X(T + x)-1 Suppose X1 & X2 then for any
Lemma C.12. (Proposition A.11 in [37]) Let 1/>
8, p.P 20 0
T & = | T
<
T S
1 T
53

---

C.2 Technical Lemmas for Concentration of k-gap Independent Data
Lemma C.13. (Lemmaa 4 in [3]) Let K be a finite subset of positive integers. Consider family (Ua)kek of d x d self-adjoint random matrices that are mutually independent. Assume that for any e K
E(U+)) O and Amax(UR) & B 0..8,
where a positive constant. Then for any >
Etr (e Enew Uk) & dexp
(g
Σ E(aa) KEK
where g(x) = 2 xx 1 1).
Lemma C.14. (The Intrinsic Dimension Lemma, [67]) Let & be a convex function on the interval [0, 00) with (00) 0. For any positive semi-definite matrix A:
trØ(A) & intdim intdim((A)) (A))
Lemma C.15. (Lieb inequality) For a fixed symmetric n x n matrix and a n x n. random matrix Z, it holds
Estr exp (H + 2)1 & tr cxp H + logEe²)
We extend Lemma C.13 follow.
Lemma C.16. Under the setting of Lemma C.I3,
EE )
Etr Us I) & intdim
E
Σ
U3 exp (oo(t)))max
AEK
REK
Proof. Take ((A) EA
Etr (e' Enex Uc - 1) =Etr (e Liee Ut) - tr(I)
Σ log Uk ) ) ) -tx(())
< exp
tI())
KEK
<trexp
Σ
log (1 + t g(BB)) (u?])
tI((I)
kEk
<trexp
Σ log exp (t>g(t)E [u]]] tr(()
ME
=trexp
(3)(IB)
Σ E [ tr(I)
ke
=tr exp
e Pg(lB)
Σ E [už] -1 -1)
keK
tro
(g((
Σ
E
[
KEK
<intdim
U
cxp
(g Amax
Σ E
[ [Uj]]
kek
where the first inequality holds by iteratively using Lieb inequality (refer to Lemma C.15), the second inequality holds by Taylor expansion, and the last inequality uses Lemma C.14.
Lemma C.17. (Lemma 5 in [3]) Let Uo, Up,... be a sequence of d d self-adjoint random matrices. Assume that there exists positive constants To. Ti.... .... Jn and Ki, Ki, ... Kn such that for = 1, .... n and any [0. kg
1]
log Etr (e Ca (a.t))/((1 knt).
54

---

Then any t E [0, #1
log Eir (e' (e Ub) & Ca + (o1)2/(1 -l).
where a = du + 01 + + on and K Ky + 161 + Fi..
We extend Lemma C.17 follow.
Lemma C.18. Under the setting of Lemma C.17, if
log Etr (c I) Cintd (a,t)²/(1- nitt,
Then
log Etr (e (e' Uk -1 I) & (n - 1)log3 + Cinia + (ot)2/(1 ks).
Proof.
[t (e - I)] & (
tr
E tr ((et0 10 - 1) (c!U,- - (e -1) + (c - 1))]
(ot)²
(oot)
(o1t)²
exp
Cinta
exp
Cinid
exp
Cinad
1- xil
1 no0
1 15
(ot)²
(ont)
(a11)
exp (Cinta)
exp
+ exp
+ exp
1- xi.
1 Knott
1 Kit
(ot)²
< exp
Cintd
3,
1 kt
where (+) is the result of Lemma C.17. Hence,
logE(tr(e"oo-1,, I)] < log3 + Cintd + (ot)²
1- ket'
By iteration, we complete the proof:
log Etr (c (o- Us - 1) & (n 1)log3 Cintd (at))/(1 1st).
D Bernstein-type Concentration for k-gap Independent Data
In this section, mainly present some useful propositions for undertaking Bernstein-type concen- tration for k-gap independent data, which are quite crucial for the concentration results Section B. This novel technique also be used for other weakly dependent processes assuming specific mixing property, i.e. structure of the a-mixing or r-mixing coefficient decay [52, 3].
Proposition D.1. Consider k-gap independent sequence of random variables (X,)z%, taking values of self-adjoint Hilbert-Schmidt operators. Suppose that there exists positive constant M such that for any i 1,
B [ and Amax(%)) < M
almost surely.
Denote
3 sup [C()....kk)
CardK Amax
E
Σ % KEE
and
intd intdim IX
Let A be a positive integer larger than 2. Then there exists a subset K of (1. with Card(K A/2, such that for any positive t such that tM < 2.
( Ts. - 1] $ log inid
A.
x 3.1f2 Au
log Eir
+
Mkt 2
55

---

Proof. The key step is to construct KA. As developed in [3], the set KA will be finite union of 2 disjoint sets of consecutive integers with same cardinality spaced according a recursive "Cantor" construction. Let
log 2
i :== LA sup Supijens jeN= A8(1 -5)--1
8 == 2 log A'
2k
2
Let no and for j 11. ..... f]. define
A(1 5)5
n =
and dj-1 = - 2my.
2
To construct KA A we proceed as follows. At the first step, we divide the set {1...A} into three disjoint subsets of consecutive integers: I1,1 f0 and I1.2. These subsets are such that 11.1( = (ard(]1.2) = and Card(TT,1)
dg. At the second step, each of the sets of integers I,,;, i 1.2 divided into three disjoint subsets of consecutive integers as follows: for any
1,2, J
12.21-1 11, 22,2 where Card (ard(T2,2:: (1) = Card = n2 and Card(T = d₁. Iterating this
procedure we have constructed after j & la steps, 2 sets of consecutive integers L5,6. i The of consecutive integers KA is then defined by
1. 1,2.... .......2. 2
KA
TeN-
W
Therefore
1-1 2
8-1
Card (J\K..,,AAAK))
Σ
Σ
Card (17))
Σ 2'd, A 2'n
j-0i-1
1-0
Note that
A 2 & A (1
= Ad Σ (1 - 8)² & Adl < A
1-1
2'
j-0
then
A Card(KA) > A/2.
For simplicity, for any 1 (1,...,(} 2) and any j {1, {I....,27 (1,...,2''') 211,,, we define
52 x
Kw = KAKS=
U
Ie. s/h
Σ X
i= W+1
KEK
16(1 A6(1-8)'-1
Then for the reason that do ... 3 de-1 for any &
2 E 2k: we obtain for k = 0...., f--1 1,
21
Eir ( (122) 844))
= Eir (e) sq(it())
Hence, by iteration,
22 t
Etr exp
t
Σ
X = Etr exp
8(9)
Ye
KA
The rest of the proof consists of giving a suitable upper bound for Etr expp (1_911 83). With this aim, let p be positive integer to be chosen later such that
2
9 2
tM
where q Tie. Let Mg. [2/() for any e (1...., 29), we divide Ke,; into 2m consecutive intervals Zj., 1 1 2mg each containing p consecutive integers plus remainder interval
z 2. containing r consecutive integers with r = q 2pm & 2p - 1. With this notation,
my. +1
myp
5 =
Σ
1,21 1
+
3.25
1=1
56

---

Since tr exp is convex, we get
2
2
mg,0+1
+1
2'
Etr exp
t
2
Etr
2f
j:20-1
+ Etr exp
2
1
2F
Σ
2(1)
3.25
1=1
j=1
1=1
(D.1)
Note that the gap between
(2(0)
3,28-11
and (z
if
2
7/4 2
> k and
k
(D.2)
IM
then (2 } and { | are mutually independent, respectively. For the first condition in (D.2),
2. we set LM & E. while for the second condition in (D.2), note that
A
A8(1
5)
q = n
2
2k,
2
2
hence,
!
A
A6
A5(1
8)8-1
k.
4
2
2.2 2
2.
After undertaking the decomposition (D.1), are going to bound Etr exp (tE 83) by bounding each term in (D.1) using Lemma C.16. To be specific, given that
4
2 (2)21-1) & 2Mp & almost surcly,
by Lemma C.16, we obtain
Etr
exp
2t
2
m
(()
j,2i
& intdim
E
Σ
(2/0 2//20.)
)²))
exp(4 x.14 At?v?)
i-1
and
2 my +1
(())
Σ
22/2
(]) exp(4 3.1 At
Etr
exp
2t
3,26
- I
<
intdim
E
9.2x
Note that intdim A + B) & intdim( (A) + intdim(B)) and intd (itdim(EX3).. we have
2
my.p
A intd exp(4 3.1 Att
Etr
exp
2t
2
1/2/-1
I
2
and
my +1
Err
exp
2t
2 (2)
j.26
A
intd exp(4 3.1 AP
Therefore,
Etr
exp
Σ I
H
YEAA
(0)
Etr
exp
I
Etr
exp
21.
(
-j,21-1
-I
I
2
1
Btr
exp
21
Σ
mz.p
Σ
7
(
j-1
i-1
intd exp(4 ( x 3.1 x At2
2
57

---

Propasition D.2. Consider gap independent sequence of random variables (X;) taking values of self-adjoint filbeett-chhmid operators. Suppose that there exists a positive constant M such that for any i 2 1,
[ and max (Ka) & M
almost surely.
Denote
2
sup
CardK max
Σ VEE
X
k= (
and
intd = intdim (EX*).
Then for any positive & such that tM
E logn'
nk %i
nk ? intd) Pnkk?
169
log Etr
exp
<
log n log3 log
t.M log
Proof. Let Ao A = ruk, and (i) = X,, i= L, I,..,, Ag. Let A be the discrete Cantor type as defined from Proposition D.I. Let A Ao Card(K A.) and define for any j = L,..., A1,
()) = Xr where (il...., i = KAAKA
Now for > 1, let KA, be defined from (I...., A,} exactly as KA is defined from (1..... AA. Set
A1+1 A; - Card K A;) and ........A4 KA, For 1,..., A define
(() (ja).
Set I. = Ln = =iffjj No, A₁ < 2k). Then the following decomposition clearly holds,
Σ X
Σ
w
())
t=
JEKAr
Let
A y(1()).
U, = Σ
(f) for si L- Uz
JEKA,
By proposition D.1, for any positive / such that I. <
k.
2
nkk2-
x
log Etr (exp(1U,) - I) & log
intd
+
0.1,...,I 1-1 (D.3)
2
Mkk
Note that
Amax( & MA2 2kM,
By Lemma C.16, for any positive t such that tM 1
2kt2p²
log Etr (exp(fUz) - I) & log(intdim(BU3)) 2kt² 2² & log(2kintd) 1 Mkt'
(D.4)
At last, we aggregate Equation (D.3) and (D.4) by Lemma C.18. Let
Mk
R; 2 O,
1; Kg Mk,
2k σi 2 V 3.1nk, O,... L σL vv 2k.
Note that
zk -
AL-1 2k, have I. logn. n. Then
Mk(++1)
Ki
& MM
2
58

---

Σ
2v3.Inku O,
+ uv 13vnkv.
v2 h log
Therefore, for any positive t such that tM
ride
nk logn log + log
169
log Etr
exp
X
-
intd ) nnkk?
1- --Mk log
(D.5)
Proposition D.3. Consider the setting in Proposition D.2. Consider the case d = 1. There exists constans C" such that for any positive such that tMM
k klog n²
nk 1
Cnk2
log E Eexp
X
$
t.Mllog''
1=1
where
2²
sup (kk.....kkk)
CardK
max
E
Σ
Proof. This result can be obtained by (D.5) Proposition D.2, where we replace Lemma C.16 and Lemma C.18 with Lemma C.17 and Lemma C.13, and take 1.
E Conditional Orthogonality Condition
In this section, we exemplify the conditional orthogonality condition. For simplicity, we merely prove the scalar case, that is, = 1, where the vector case can be generalized trivially. We present some examples as follows.
Example E.1. (Additive Gaussian distribution and Hermite polynomial)
H4
x o2), N(O, 1), g Vaez vT- aru, eg(g)
Vi!
where o3 010 04 and H₂(-) is the Hermite polynomial.
Proof. Denote Z = T-vT-oeu then Vaida
Z N(O.1). 1).
Hence,
vI
aee
y ya.os Z
[[e(g))
E H,
1m
0g
0g
We then focus on computing
E
H
aiu
v
Z
1u1
E [,H, (a + bZ)
0g
0g
where
Vaioz Z ~ (0.1)).
a
0g
0g
By the definition of Hermite polynomial,
Σ t
(a bZ) = ((ath2)
Taking expectation over Z, we have
RHS at 62-1.2
59

---

By Taylor expansion,
8
1
n!! ml(n - 2mm
a"
Σ
(b²
1)maa
n!
Hence, by matching with
20
t
Σ
Hn(a (a + bZ),
we obtain
1
i!
E [H + 6Z)] -
Σ
(b² 1) n 7-2m 2m
ml(i 2m 12
m=0
Setting
0,0
1 04
a²
c² = 12
0 a
+ 1 -0
0007 a1
u?2
then
E[e:(g)lu]= = E (a + b2)]
Vi!
i! ml(i - 2m) 12mh
Σ
(b² 1) f-2m
Vi!
i! m!(i 2m)) 12
2m
Note that by the definition of Hermite polynomial,
+ H₂(x)
i! m!(i 2mm)2m
Σ
2m
m2-
Hence,
Ble(g))lu Hi(u).
Vi!
At last,
c+ E. H,, 0.
E, [[(e())))l
Vilj!
Example E.2. (Additive Uniform distribution on a cyclic group and discrete Fourier basis)
satisfy the Uniform distribution on cyclic group En {0, 1, 2, n 1}, g x + u modn, eg(g) v w/ w 2wi/n .j 0, 1, 1....,n
Proof. For j # 0
W 1 n
Eg [g)e(g))] =E,
u (m+u))
w 0.
V ni n
F Discussion on Assumptions
F.1
Polynomial-decay Kernel Spectrum
The polynomial spectrum assumption makes our bound clearer and facilitates direct comparison with established results in the i.i.d. setting (consistent with prior works [37, 39]). This makes the core theoretical insights more accessible. While the assumption simplifies presentation, our framework
60

---

is readily extensible to general spectra on the technical level. In particular, the key terms (e.g. (r(TTy yr, { mmp? and - fo (r) [ in Lemma C.3-C.5) can be expressed directly in terms of individual eigenvalues A2, .2, ...) rather than the decay rate 3. For instance, the norm [lfall(agy is fundamentally given by a series (shown below) that depends on the full eigenvalue
p p= + + 2 Therefore, the polynomial decay is primarily tool for deriving clearer, interpretable bounds without fundamentally limiting the scope of our technical approach. We believe best serves the goal of presenting our core theoretical contributions transparently.
sequence: [[Aa|pma> = =
F.2
Relative Smoothness
In deriving our general theoretical bound (4.1), relax to s > O and obtain exactly the same result, as we have technically leveraged assumptions and properties of interpolation spaces for refinements. While for the specified bounds under conditional orthogonality ((4.2) and Theorem 4.4), 8 > is required to estimate the relevance parameter r'r (Lemma B.1 for providing a concise bound and clear insights, where the relevance parameter is explicitly related to ax- Technically, the smoothness on f enables continuity to convert the relevance in the function space into the relevance ro in the data space. We consider this specific case to make our conclusion more clear and understandable. Indeed, without the strong smoothness > 1, we can also provide estimation (less
concise expression) for rr. We merely need to replace with Tp == 2/ (I5") ( (gi5) ( 110**(())
1 (gr))²
[0, 1J. maintaining all convergence guarantees.
F.3 Hölder continuity
The primary purpose of the Hölder continuity assumption is eliminate the need for the often unrealistic sub-Gaussian design assumption in deriving our general bounds [37, 39j. Technically, is essential for establishing a uniform concentration bound via covering number estimates (Lemma C.9 and C.))). Furthermore, this assumption allows us to derive concise estimates for relevance parameter in specific scenarios, such as when conditional orthogonality holds. We note that Hölder continuity is naturally satisfied by important kernel classes like the Laplace kernel, Sobolev kernels, and Neural Tangent Kernels [37, 39].
G Experiment
G.1 Real Image Diffusion Training
To demonstrate the applicability of our method beyond toy examples, conducted ablation study on the CIFAR-10 dataset. We trained a diffusion model using a dataset of 1024 samples for 100 epochs with batch size of 1024, optimized using Adam with learning rate of 2e-3. The model architecture was a two-layer U-Net, and time conditioning was implemented by expanding the time variable t and concatenating
an additional input channel the image.
We report the diffiusion loss on the test set with a size of 1024 at = 1.0 and t = 0.1 across different values of A (number of noisy realizations per data). Each configuration was evaluated over 100 parallel runs to ensure robustness.
As shown in Figure 3a, increasing & consistently improves performance at t 1, indicating better fitting of the complex score function. However, it also leads to degradation at = 0. consistent with our empirical findings on the MoG settings in the paper. Both our empirical findings on the MoG settings and CIFAR-10 align well with our theory that when is large (i.e., noise dominates), increasing k is beneficial to generalization.
61

---

CIFAR10
0.18
2.5
DSM Loss (t=1 1.0)
Score MSE (t-0.1)
Score MSC (t=18 1..0)
0.16
(t=1)
0.80
0.0020
8.2
0.0020
2.0
0.0015
8.1
0.75
0.0015
1.5
0.12
0.0010
8.0
0.0010
0.10
0.70
100
50
100
50
100
Noise
Noise
(a) CIFAR-10
(b) NTK
(c) RBF
Figure 3: Score estimation versus the number of noise per data, i.e., k. for noise levels.
G.2 Kernel Ridge Regressor
To supplement, we conducted the same experiments as the Numerical Experiments in Section using both NTK and RBF kernel regressor. As shown in Figure 3b and Figure 3c, the results show consistent trends with our MLP findings.
G.3 Experiment Details
The paper fully discloses all the information, including training and testing details, needed to reproduce the main experimental results the paper to the extent that it affects the main conclusions of the paper, as described in Section G.I. Section G.2 and Numerical Experiments in Section All data are either synthetically generated with detailed description or publicly open dataset. The experimental results report statistical information including mean and standard deviation in Fig.2. All experiments are conducted using a single 4090 GPU.
H Broader Impacts
Our theory provides general framework to characterize learnability of different data distribu- tions. Practitioners can leverage this framework follows: first, select kernel appropriate to the problem domain; second, check the decay rate of the kernel's spectrum; and finally, apply Theorem 4.4 to rigorously determine (i) whether the distribution can be learned efficiently and (ii) the sample complexity required for convergence.
Our results provide practical insights for optimizing the training efficiency of diffusion mod- els, suggesting that adaptive noise-sample pairing strategies may offer significant computational benefits.
Our general- purposse concentration technique advances the theoretical toolkit for dependent data analysis and may find applications beyond our current setting, which is of independent interest to the community.
62


Reviews:
[{"review_id": "BVEeAd0Ovr", "reviewer": "Reviewer_Vqf9", "summary": "The paper develops excess‐risk bounds for kernel ridge regression when the training data consist of multiple noisy observations of shared latent signals, a setting that breaches the usual i.i.d. assumption. A new blockwise decomposition technique yields a Bernstein‐type concentration inequality for k-gap independent sequences, leading to bounds that expose how the number of noises per signal k and a relevance parameter r jointly govern variance. The theory is specialized to denoising score learning in diffusion models, where it predicts an optimal k that grows as noise dominates, and small simulations corroborate the trend.", "questions": "Please clarify whether the blockwise concentration still holds if k varies per signal or if gaps are only approximately independent. \n\nCould the relevance parameters be estimated from data to guide k adaptively in practice? \n\nHow sensitive are the bounds to the Hölder index p; can slower continuity be handled? \n\nAn ablation on real image diffusion training would strengthen claims; what computational overhead would varying k incur?", "limitations": "The authors include a brief limitations section but should discuss the restrictiveness of the equal‑k assumption and the challenge of estimating r and spectral decay in high dimensions.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Quality: proofs appear rigorous, with explicit assumptions and detailed appendices, and the novel concentration inequality is broadly useful. Clarity: notation is heavy but consistent; proofs are sketched in the main text with full details deferred, and key intuitions are conveyed. Significance: the work fills a gap by treating structured dependence that arises in modern generative modeling, giving actionable guidance for noise‑pairing schedules. \nOriginality: the blockwise Bernstein bound and its application to kernel regression under causal noise structure are new. \n\nMain weaknesses are strong spectral and Hölder continuity assumptions, reliance on equal k across signals, no comparison with alternative dependent‑data analyses, and only toy simulations on a 1‑D mixture that limit empirical support. Practical impact on diffusion training remains speculative without large‑scale experiments.", "was_revised": true, "final_justification": "I thank the authors for their thorough rebuttal. My primary concern in my initial review was the limited empirical support, which made the practical impact of the theory speculative. The authors have now addressed this by providing new experiments on CIFAR-10, not only with an MLP but also with KRR.\n\nWhile it is not possible to fully vet the code in the rebuttal phase, the specificity of the experimental setup and the coherence of the results give me confidence in their claims. The authors have strengthened the paper and demonstrated the relevance of their work. Based on these improvements, and with the expectation that the full details of these new experiments will be incorporated into the final paper, I will raise my score.", "rebuttal": "Thanks for your time and efforts reviewing our paper. We now address raised questions as follows.\n\n* Q1: Reliance on strong spectral assumption.\n    \n    Thanks for your comment. We consider the **polynomial spectrum** to make our bound clearer and facilitates direct comparison with established results in the i.i.d. setting (consistent with prior works [1,2]), which can make the core theoretical insights more accessible. While the assumption simplifies presentation, our framework is readily extensible to general spectra on the technical level. The key terms (e.g. $tr(TT_\\lambda^{-1})^p$, $\\Vert f_\\lambda^{(r)}\\Vert_{[\\mathcal{H}]^\\gamma}^2$ and $\\Vert f_\\lambda^{(r)}-f_\\rho^{*(r)}\\Vert_{[\\mathcal{H}]^\\gamma}^2$ in Lemma C.3-C.5) can be expressed directly in terms of individual eigenvalues ($\\lambda_1, \\lambda_2, \\dots$) rather than the decay rate $\\beta$. For instance, the norm $\\Vert f_\\lambda\\Vert_{[\\mathcal{H}]^\\gamma}^2$ is fundamentally given by a series (shown below) that depends on the full eigenvalue sequence: $\\Vert f_\\lambda\\Vert_{[\\mathcal{H}]^\\gamma}^2\\asymp\\sum_{i=1}^\\infty\\left(\\frac{\\lambda_i^p}{\\lambda_i+\\lambda}\\right)^2i^{-1}.$ Therefore, the polynomial decay is primarily a tool for deriving clearer, more interpretable bounds without fundamentally limiting the scope of our technical approach.\n    \n* Q2: Reliance on the Hölder continuity assumption.\n\n    Thanks for your comment. The primary purpose of **the Hölder continuity assumption** is to eliminate the need for the often unrealistic sub-Gaussian design assumption in deriving our general bounds [1,2]. Technically, it is essential for establishing a uniform concentration bound via covering number estimates (Lemmas C.10 and C.11). Furthermore, this assumption allows us to derive concise estimates for the relevance parameter $r_T$ in specific scenarios, such as when conditional orthogonality holds. We note that Hölder continuity is naturally satisfied by important kernel classes like the Laplace kernel, Sobolev kernels, and Neural Tangent Kernels [1,2].\n\n* Q3: Please clarify whether the blockwise concentration still holds if k varies per signal or if gaps are only approximately independent.\n\n    Thanks for your question. The blockwise concentration remains valid **when the number of noisy realizations $k_i$ varies per signal $x_i$**. A simple method to handle is replacing $k$ with $k_\\mathrm{max}:=\\max_i k_i$. The key insight is that the entire training observations $G$ satisfies $k_{\\mathrm max}$-gap independent (see definitions in line 146-148), preserving the concentration properties. **If gaps are only approximately independent**, e.g., some weakly dependent process assuming specific mixing property, our framework can also be readily extended to accomodate the dependency. The core technique is to incorporate the specific dependence structure (e.g., mixing coefficients) to modify the concentration bounds by adding terms quantifying block dependence. Established methods for handling such dependencies can be adapted from [3,4].\n\n* Q4: No comparison with alternative dependent‑data analyses.\n\n    Thanks for your comment. Current literature on dependent-data analyses rely heavily on mixing conditions, which characterize the correlation between random variables from certain distance in the sequence. Differently, we consider the $k$-gap independent data, where the random variables are categorized multiple groups with size $k$, the data point will be highly correlated/dependent with the data in the same group, but is independent of the data from other groups. Then we would like to explain the difference between our work and these related works in the following aspects:\n    \n    * **Setting and Assumption**\n        \n        While many works have derived tight concentration high-probability bounds for non-i.i.d. data under the geometrically regular mixing assumption [5,6] or the algebraically mixing assumption [7], which characterize the decay of correlation between random varaiables as the distance increases, our $k$-gap independent case **cannot be covered by these works**, as the correlation between data points will remain high as long as they are from the same group with size $k$. Therefore, our $k$-gap independent case requires a fundamantally different non-i.i.d. data analysis.\n    \n    * **Analysis Intuition**\n    \n        Most of the existing results [5-7] perform analysis under the intuition to control the approximation error between independent blocks and dependent blocks by mixing coefficients. That being said, the data dependency is treated as an bad effect in their analysis and will finally appear as an error term. However, in our setting, we do not treat the data dependency a bad effect but aim to discover some benefits for reducing the error, otherwise it would be intractable to prove the vanishing generalization error in our setting for general $k$. To this end, we perform refined study in decomposing blocks to eliminate direct error approximation.\n\n    * **Insight**\n    \n        Our analysis demonstrating the benefit of data relevance stands in contrast to a long line of work on learning from dependent data, providing insights for understanding data dependence. We believe some of our techniques and methodologies can be potentially extended to a broader settings (e.g., the size of each group could vary).\n    \n    On the technical level, prior work [5-7] use **single-layer decomposition** that requires constructing independent surrogate blocks and carefully controlling approximation errors. On the contrary, we introduce **a more refined decomposition**, yielding multiple partitions with several independent blocks respectively, which enables us to apply standard symmetrization techniques for each partition individually and resolve cross-partition dependencies through our **novel incorporating lemma** (Lemma C.20). \n\n* Q5: Could the relevance parameters be estimated from data to guide k adaptively in practice?\n\n    Thanks for your question. In the case when $\\alpha_t \\to 0$, i.e., the data $x_t$ becomes more noisy, the optimal $k$ can be selected as $k^*=\\Theta\\left(\\frac{1-\\alpha_t^{p/2}}{\\alpha_t^{p/2}}\\right)$. For general $t$, the suggestion from our theory is to use larger $k$ when $t$ increases. Nevertheless, it still requries a bit hyper-parameter tuning for different practical tasks.\n\n\n* Q6: How sensitive are the bounds to the Hölder index p; can slower continuity be handled?\n \n    Thanks for your question. Under the specific conditional orthogonality, our **general upper bound** is $R(\\lambda) \\leq \\tilde{\\Theta} _ {\\mathbb{P}}\\left({n}^{-\\operatorname*{min}(s,2)\\theta}\\right) + \\tilde{\\sigma}^2 O _ \\mathbb{P}^{\\rm poly}\\left(n^{\\alpha_0\\theta}\\left(\\frac{\\tilde{r} _ 0^{p/2}\\vee r_e }{n}+\\frac{(1-\\tilde{r} _ 0^{p/2}) \\wedge (1-r_e)}{nk}\\right)\\right)$. Overall, $p$ affects both the tightness of our bounds and the benefit of multiple observations ($k$). To be specific, larger $p$ implies the domination of $\\frac{1}{nk}$, showing the underlying benefit to generalization by increasing $k$. In contrast, smaller $p$ (**slow continuity**) implies the generalization error is up to $O_\\mathbb{P}^{\\mathrm{poly}}(n^{\\alpha_0\\theta}/n)$.\n    \n* Q7: Only toy simulations on a 1‑D mixture that limit empirical support. Practical impact on diffusion training remains speculative without large‑scale experiments. An ablation on real image diffusion training would strengthen claims.\n \n    Thanks for your comment. To demonstrate the applicability of our method beyond toy examples, we conducted an ablation study on the CIFAR-10 dataset. We trained a diffusion model using a dataset of 1024 samples for 100 epochs with a batch size of 1024, optimized using Adam with a learning rate of 2e-3. The model architecture was a two-layer U-Net, and time conditioning was implemented by expanding the time variable `t` and concatenating it as an additional input channel to the image.\n\n    We report the diffusion loss on the test set with a size of 1024 at \\( t = 1.0 \\) and \\( t = 0.1 \\) across different values of \\( k: number of noisy realizations per data\\). Each configuration was evaluated over **100 parallel runs** to ensure robustness:\n\n    | **k**  | **Loss at t = 1.0** | **Loss at t = 0.1** |\n    |-------:|--------------------:|---------------------:|\n    | 1      | 0.00268199          | 0.09571435           |\n    | 16     | 0.00175084          | 0.09752702           |\n    | 32     | 0.00123094          | 0.10304873           |\n    | 64     | 0.00102835          | 0.12863263           |\n    | 128    | 0.00069417          | 0.18158743           |\n\n    As shown, increasing $k$ consistently improves performance at $t=1$, indicating better fitting of the complex score function. However, it also leads to degradation at $t=0.1$, consistent with our empirical findings on the MoG settings in the paper. Both our empirical findings on the MoG settings and CIFAR-10 align well with our theory that when $t$ is large (i.e., noise dominates), increasing $k$ is beneficial to generalization.\n\n* Q8: What computational overhead would varying k incur?\n\n    Thanks for your question. Varying $k$ will not incur any computational overhead, as we always conside a fixed batchsize in experiments. No matter how $k$ varies, the computation is the same as the case $k=1$.\n\nWe hope above response can address your concern and we are open to discuss more if any question still hold.\n\n[1] On the asymptotic learning curves of kernel ridge regression under power-law decay.\n\n[2] Kernel interpolation generalizes poorly.\n\n[3] Bernstein-type inequality for a class of dependent random matrices.\n\n[4] Bernstein inequality and moderate deviations under strong mixing conditions.\n\n[5] Fast learning from non-iid observations.\n\n[6] Fast learning from $\\alpha$-mixing observations.\n\n[7] Rates of convergence for empirical processes of stationary mixing sequences."}, {"review_id": "FIBzWsZ8Pg", "reviewer": "Reviewer_imqV", "summary": "This paper analyzes kernel ridge regression under a structured non-i.i.d. setting where each latent signal generates multiple noisy observations.  A k-block model captures blockwise intra-dependencies with inter-block independence.  The authors derive excess risk bounds using a blockwise concentration approach.  The results describe how sampling and dependency affect generalization in denoising score learning.", "questions": "1. The theoretical contribution mainly extends known bias-variance analysis to a blockwise non-i.i.d. setting. Could the authors clarify what key steps or insights make this extension substantially novel compared to existing kernel generalization theory?\n\n2. The paper’s findings on the optimal noise sampling schedule provide some guidance for diffusion models. Could the authors comment on how these results might inspire practical training or data usage strategies more broadly?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The paper provides an explicit excess risk bound for kernel ridge regression under a structured non-i.i.d. block setting, which clarifies how the causal data model and sampling scheme affect generalization.\n2. The analysis connects directly to denoising diffusion probabilistic models, showing how the optimal noise sampling ratio should depend on the time-varying noise-to-signal ratio, which is practically relevant.\n3. The paper develops a Bernstein-type concentration inequality tailored for block-dependent samples, offering a reusable tool for analyzing learning with dependent data.\n\n**Weaknesses：**\n\n1. The paper does not propose a new algorithm but focuses mainly on theoretical bounds, which is not a novel direction by itself given that excess bias-variance bounds for kernel methods have been widely studied.\n2. The new Bernstein-type concentration inequality mainly builds on existing techniques, including the Intrinsic Dimension Lemma and standard $\\phi(a) = e^a - 1$ tricks from related literature, which limits its originality.\n3. In Assumption 1, the notation for sub-Gaussian variance proxies is not used consistently: $\\sigma^2_\\epsilon$, $\\sigma^2_{\\epsilon_{1,2}}$, $\\sigma^2$, and $\\sigma^2_G$ appear without clear distinction. Since this assumption underpins the main risk bound, clearer notation or explicit definitions for each variance term would improve clarity and rigor.\n4. The paper states “Yes” for open access to data and code, but only synthetic data generation details are described; no actual code link or repository is provided, which limits full reproducibility.", "was_revised": true, "final_justification": "I appreciate the overall completeness and clarity of the analysis. The derivation is solid and well-aligned with existing literature. I maintain my overall score of 4.", "rebuttal": "Thanks for your time and efforts reviewing our paper. We now address raised questions as follows.\n\n* Q1: The paper does not propose a new algorithm but focuses mainly on theoretical bounds, which is not a novel direction by itself given that excess bias-variance bounds for kernel methods have been widely studied.\n\n    Thanks for your comment. While excess risk bounds for kernel methods are well-studied in i.i.d. settings, no prior works have studied the excess risk and even learnability in the structured non-i.i.d. setting which is ubiquitous and important in applications like diffusion models. This paper contributes the analysis to the novel structured non-i.i.d. setting. Our theoretical bound explicitly characterizes the learnability in the structured non-i.i.d. setting and demonstrates how multiple noisy observations ($k$) affect generalization. \n    \n    Beyond theoretical bounds, our theory also guides noise-sample pairing strategies when training diffusion models: for general $t$, using large $k$ when $t$ increases.\n\n* Q2: The new Bernstein-type concentration inequality mainly builds on existing techniques, including the Intrinsic Dimension Lemma and standard $\\phi(a) = e^a - 1$ tricks from related literature, which limits its originality.\n\n    Thanks for your comments. The Intrinsic Dimension Lemma and standard $\\phi(a) = e^a - 1$ tricks are used in the standard i.i.d. Bernstein inequality. However, for $k$-gap independent data which is non-i.i.d. in our setting, exisiting techniques cannot handle data dependence. Therefore, we introduce **a refined block decomposition**, yielding multiple partitions with several independent blocks respectively. The novel technique enables us to apply standard symmetrization techniques for each partition individually and resolve cross-partition dependencies through our **novel incorporating lemma** (Lemma C.20). Our technique can also extend to more general cases (e.g. varying $k$ per signal, approximately independent block gaps), serving as a new tool in dependent data analysis for machine learning community.\n    \n\n* Q3: Could the authors clarify what key steps / insights make this extension substantially novel compared to existing kernel generalization theory?\n\n    Thanks for your question. Our extension advances kernel generalization theory through two key innovations. One key step lies in the development of **the new Bernstein inequality** tailored for KRR analysis in the structured non-i.i.d. setting. The other key step is providing **additional concentration analysis** for $V_3$ (line 547), where we utilize the truncation technique and the novel Bernstein inequality (Lemma B.9). Both the two steps are essential for excess risk analysis in dependent cases. / To existing kernel generalization theory, we provide novel insights for **whether data dependencies benefit or hinder the generalization performance of KRR**. Our theoretical bounds explicitly blends $\\frac{1}{n}$ and $\\frac{1}{nk}$, revealing a critical trade-off between relevance and noise sample size: when the correlation level $\\tilde{r}$ is large, i.e., the signal dominates in the observed noisy data, increasing $k$ offers little benefits while increasing $k$ helps generalization when the noise component prevails.\n  \n* Q4: Clearer notation or explicit definitions for each variance term.\n  \n\n    Thanks for your good points. $\\sigma_\\epsilon$ and $\\sigma^2$ control the decay of the population noise conditionally on data, with the former controlling the exponential decay (sub-Gaussian norm) and the latter controlling the quadratic decay (second moment). In parallel, for technical reasons to analyze dependent data, we extend $\\sigma_\\epsilon$ and $\\sigma$ which are single-data conditioning to $\\sigma_{\\epsilon_{1,2}}$ and $\\sigma_G^2$ which are dependent-data conditioning. \n    We provide explicit definitions as follows. For $(g,y)\\in \\mathcal{G}\\times \\mathcal{Y}$, for any dimension $r=1,\\dots, d$, denote $\\epsilon^{(r)}:=y^{(r)}-f_\\rho^{(r)* }(g)$. Then $\\sigma_\\epsilon$ is the upper bound of the sub-Gaussian norm of $\\epsilon^{(r)}$ conditionally on $g$ and $\\sigma_{\\epsilon_{1,2}}$ is the upper bound of the sub-Gaussian norm of $\\epsilon^{(r)}$ conditionally on $g,g'$ where $g\\neq g'\\in \\mathcal{G}$. To be specific, $$\\Vert\\epsilon^{(r)}|g\\Vert _ {\\psi_2}=\\inf\\left\\\\{t>0{:}\\ \\mathbb{E}\\left[\\exp\\left(\\left(\\epsilon^{(r)}\\right)^2/t^2\\right)|g\\right]\\leq2\\right\\\\}\\leq\\sigma_\\epsilon,\\ g,g'\\in \\mathcal{G} \\ \\text{almost everywhere}.$$ $$\\left\\Vert\\epsilon^{(r)}|g,g'\\right\\Vert_{\\psi_2}=\\inf\\left\\\\{t>0{:}\\ \\mathbb{E}\\left[\\exp\\left(\\left(\\epsilon^{(r)}\\right)^2/t^2\\right)\\big|g,g'\\right]\\leq2\\right\\\\}\\leq\\sigma_{\\epsilon_{1,2}}, \\ g,g'\\in \\mathcal{G} \\ \\text{almost everywhere}.$$ Similarly, $\\sigma^2$ and $\\sigma_G^2$ are the upper bounds of the second moment of $\\epsilon^{(r)}$ conditionally on $g$ and $g,g'$ respectively. $$\\mathbb{E}\\left[{\\epsilon^{(r)}}^2|g\\right]\\leq\\sigma^2,\\ \\mathbb{E}\\left[{\\epsilon^{(r)}}^2|g,g'\\right]\\leq \\sigma_G^2, \\ g,g' \\in \\mathcal{G} \\ \\text{almost everywhere}.$$\n\n\n* Q5: The paper states “Yes” for open access to data and code, but only synthetic data generation details are described; no actual code link or repository is provided, which limits full reproducibility.\n\n    Thanks for your comment. As we can not provide any code link in the rebuttal stage, we will provide the actual code link or repository in the revised manuscript.\n\n* Q6: The paper’s findings on the optimal noise sampling schedule provide some guidance for diffusion models. Could the authors comment on how these results might inspire practical training or data usage strategies more broadly?\n \n    Thanks for your question. The optimal noise sampling schedule provides inspirations for practical training of denoising score learning. Consider training with a **fixed batch size** $nk$, for varying $t$ (or equivalently, $\\alpha_t$), practitioners can adaptively choose $k$ for optimizing the training efficiency: if signal dominates, then setting $k=1$ is enough; while when noise dominates, practitioners are encouraged to increase $k$ to $\\Theta\\left((1-\\alpha_t^{p/2})/\\alpha_t^{p/2}\\right)$. This adaptive design for noise multiplicity $k$ may advance the empirical study for denoising score learning. \n    \n    Additionally, our insights can also extend beyond denoising score learning to **flow-based diffusion model** (e.g. flow matching, rectified flow) and other noise schedules (e.g. Variance-Exploding (VE), Variance-Preserving (VP), sub-VP, Linear, EDM), unifying noise sampling principles across diffusion paradigms. Overall, our $k$-adaptation principle provides the first theoretical grounding for noise scheduling decisions - enabling systematic design rather than empirical guesswork.\n\n\nWe hope above response can address your concern and we are open to discuss more if any question still hold."}, {"review_id": "qEuf7Bq7dS", "reviewer": "Reviewer_aGuy", "summary": "This paper proposes upper bounds on the risk of scalar kernel ridge regression in the misspecified setting (meaning that the optimal regressor is in a specific power space of the RKHS) with block-independent data. The first theorem (4.1) provides the upper bound, showing polynomial decrease rates of the population risk if the regularization parameters decreases slowly enough. In contrast, the second theorem establishes that the risk is lower bounded by a positive constant if the regularization parameter decreases too sharply, establishing the absence of generalization (which I understand as consistency of the estimator).\nThe paper then applies the obtained rates to conclude on the successful learning of the denoising score algorithm under theoretical assumptions. This use case is the motivational application for the theory, and is illustrated in experiments on a toy problem.\nOn a technical level, the main novelty seems to reside in a block argument to recover the case of iid variables (cf. Section 5.1).", "questions": "My questions are detailed in the section \"Strengths and weaknesses\". In particular:\n1. How do your results relate to the works mentioned?\n2. Is there a reason to considering the \"mild\" non-iid-ness of block-independent data compared to mixing data, and how do your proof techniques relate to those for mixing data?\n3. Can you clarify Assumption 1 and the assumptions of $f_\\rho$? In particular, is it assumed to lie in $\\mathcal H$ and, if not, how is this consistent with Assumption 1?\n4. Can you provide guidelines or related works on how to design neural networks to abide by the assumptions of Theorem 4.4?", "limitations": "The paper does not satisfyingly identify the limitations of its Assumption 1, leading to an overblown claim of lack of assumptions on the ground truth, and the limitations of Theorem 4.4 of the difficulty/impossibility for neural networks to abide by the assumptions of the theorem, leading to an overblown claim of practicality.\nOther than that, the authors adequately address the potential negative societal impact of their work.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper is well-motivated and generally well-written (modulo the issues raised below). It proposes interesting ideas, including in the extensive appendix. However, I have significant concerns regarding several aspects: the completeness of the related work discussion, the meaningfulness of the theoretical setup, the adequacy of the assumptions relative to the claimed contributions, and the validity of the application to denoising score learning. I also raise concerns about some aspects of the writing.\n\nGiven the scope and depth of these issues, I believe that fully addressing them within the rebuttal period may be challenging. That said, I remain open to discussion and would welcome a constructive exchange.\n\n1. **Related work** The paper does not sufficiently discuss its relation to the following bodies of work: \n\t1. Classical literature on statistical learning of support vector machines (SVM) [R1]: a central goal in statistical learning is to derive generalization guarantees in the form of high confidence bounds on the excess risk. While the paper does acknowledge that it is a central question in KRR (which is a special case of SVMs), it does not acknowledge the classical theory like that of [R1]\n\t2. Learning with SVMs from non-iid data [R2,R3,R4]: there is a rich literature on learning from non-iid data, either asymptotically for general losses [R2,R3] or in the finite-sample case with mixing assumptions [R4,R5] or without (under assumptions on the loss and kernel) [R6,R7]. I believe the results on mixing are of particular interest to the authors, because block-independent processes _are_ mixing. This connects to one of my concern below about the fact that the non-iid-ness considered in this work is mild.\n\t3. Time-uniform concentration inequalities in bandits and Bayesian optimization: there is a class of concentration results bounding the error between the target function and the KRR estimate pointwise in the input [R8, Corollary 3.17], [R9, R10]. While these results originate from a different community and are not immediately applicable to the present use case (well-specified case, no asymptotic analysis), they should be mentioned in the related work and may be of interest to the authors.\n2. **Setup** The non-iid-ness considered in the general paper is mild, in the sense that simple subsampling recovers iid data, or more generally that it implies any form of mixing, which is a very standard assumption to handle dependent data in learning theory. \nIn particular, what seems to be the main novelty in the proof (decomposing the data in independent blocks) reminds me of standard arguments in $\\beta$-mixing tracing back to [R11] (see [R12] for a more recent reference on this applied to learning theory, and [R13] for an application to kernel methods). The more restricted setup considered in the paper may be sufficient for denoising score matching, but I would encourage the authors to justify why they consider this particular form of non-iid-ness compared to a form of mixing.\n3. **Assumptions** \n\t1. The paper provides insufficient details on the assumptions imposed on the kernel function. In particular, the assumptions for RKHS elements to be square-integrable and for the Mercer decomposition to exist, be well-behaved, and yield an ONB of $\\mathcal H$ instead of an ONS [48] are not stated. Furthermore, the domain and range of the operator $T$ (and related operators) need to be specified. Are they operators on $L_2$? On $\\mathcal H$? Similarly, the paper should make explicit at the beginning of 3.2 already what set $f_\\rho$ is assumed to lie in, as this may impose further restrictions on the kernel (e.g., if $f_\\rho$ is assumed square integrable at this point). Additionally, the space $[\\mathcal H]^t$ (which the paper calls \"interpolation spaces\" but is actually the power RKHS, cf. [48, Section 4]) is not always well-defined; only the actual interpolation space is [48, Eq. (36)] (and it is not a space of functions, but one of equivalence classes). I do not think these imprecisions impact the results, but they need to be addressed.\n\t2. I would like to emphasize that the classical convention [48] in the Mercer decomposition is that the family $(\\lambda^{1/2}e_i)_i$ is an ONS in $\\mathcal H$, and **not** the family $(e_i)$ (which is an ONS when embedded in $L_2$, but is not normalized in $\\mathcal H$). A different convention is used in the main text (l. 178). This is not critical as it is ultimately a convention, and I also believe this is a typo and that the authors meant to use the classical convention (given comments such as l.183). I will assume this from now on, as it is important for my next point.\n\t3. More importantly, I have significant concerns regarding the first two points of Assumption 1. Indeed, I claim that the combination of the first and second points imply that $f_\\rho\\in\\mathcal H$ if $s>1$ (see below). As a result, Assumption 1 imposes a **very strong** smoothness condition on $f_\\rho$ (RKHS membership), which directly contradicts the storyline and claims of the paper and makes unnecessary all the refinements leveraging interpolation spaces. Technically, the membership results from the additional term $i^{-1/2}$ assumed in the expansion of $f_\\rho$, which deviates from standard source conditions in the misspecified setting for KRR (interpolation space membership, which is usually expressed via the expansion in Assumption 1 without the $i^{-1/2}$ factor and assuming that $a_i$ is square summable instead of bounded above and below, cf. [48, Eq. (36)]). Finally, the assumption that $a_i\\geq c>0$ is also nonstandard, and further restricts possible values for $f_\\rho$ (in particular, $f_\\rho$ cannot be $0$, as no coefficient may be $0$ in the expansion). I encourage the authors to revise this assumption or the claims of the paper.\n\t4. I am also surprised by the form of the polynomial eigenvalue decay in Assumption 1.\n\tIn particular, I have only encountered the condition $c_\\beta i^{-\\beta}\\leq \\lambda_i$ to show _lower bounds_ on the excess risk [R14, Section 5]. A discussion of why this lower bound is needed for the present results would be welcome.\n4. **Application** The application to denoising score learning in Theorem 4.4 reduces to applying Theorem 4.1 with a particular form of measurement model ($g$). Yet, the classical method (and the present numerical experiment) relies on a neural network for the regressor, and _not_ on KRR. In other words, Theorem 4.1 is only valid if the chosen neural network can represent all functions of the RKHS $\\mathcal H$ (and only those); i.e., if it behaves as KRR. This is highly unrealistic, and yet the paper does not discuss this aspect, and instead claims that the result can be applied for practitioners to perform rigorous kernel engineering. I believe this is an overclaim, as it would require an analysis of how to design the neural network should be chosen to approximate the RKHS and of the incurred error due to the approximation. I am not convinced such an analysis would be interesting, however, as one would certainly be better off using KRR rather than approximating it with a neural network. Summarizing, I believe that the claims on the relevance of Theorem 4.4 in practice and the discussion of its limitations should be adapted in light of this discussion.\n\n**Proof of $f_\\rho\\in\\mathcal H$** Define $a_i := a_i^{(r)}$, and assume that $(\\lambda_{i}^{1/2}e_{i})$ is an ONB of $\\mathcal H$ and that $s>1$. Then, the series used to define $f_\\rho$ converges in $\\mathcal H$. Indeed: $$\n\\begin{split}\\sum_{i}\\lVert a_i \\lambda_i^{s/2} e_i\\rVert^2_k\n&= \\sum_i a_i^2\\lambda_i^si^{-1}\\lambda_i^{-1}\\\\\n&\\leq \\max(c^2,C^2)\\sum_i \\lambda_i^{s-1}i^{-1}\\\\\n&\\leq \\max(c^2,C^2)\\cdot C_\\beta^{s-1}\\cdot \\sum_i i^{-\\beta(s-1)-1}.\\end{split}\n$$\nThe RHS is finite as long as $\\beta(s-1)+1>1$, which holds since $s>1$.\nAs a result, the general term of the series is square summable, implying that the series converges in norm in $\\mathcal H$ and that $f_\\rho\\in\\mathcal H$.\n\n\n**Minor comments**\n* The terminology \"the signal\" to designate the input is nonstandard; I recommend using \"the input\"\n* I recommend avoiding self-congratulatory expressions like \"advanced technique\" (l. 67)\n* I am not fond of notations like $R \\leq \\Theta(\\dots)$, $R \\geq \\Omega(\\dots)$, or $R\\leq \\mathcal O(\\dots)$. Indeed, the symbols $\\Theta$, $\\Omega$, and $\\mathcal O$ are _already_ inducing orderings, as $f\\geq g$ and $g = \\mathcal O(h)$ implies that $f = \\mathcal O(h)$. While this is merely style for $\\mathcal O$ and $\\Omega$, it becomes misleading for $\\Theta$, as the notation $f \\leq \\Theta(g)$ may have a different meaning than $f=\\Theta(g)$. I recommend using the equality symbol everywhere.\n* You should avoid informal statements like \"roughly\" (l.71) in formal statements if they are not rigorously defined/made precise later.\n* The notation $\\mu_\\mathcal G$ (l. 141) is undefined (I suspect it should be $\\rho$). I recommend redefining $\\mu_\\mathcal G:= \\rho$, however.\n* The change of notations in Example 3.2 seems unnecessary\n* It would be helpful to clarify why KRR is applied independently per dimension rather than using a multi-output variant (possibly with a diagonal kernel if the proofs don't generalize).\n* l.203: I believe that \"$f_\\rho^{(r)}\\in\\mathcal H$\" is a typo, as the paper tries to address the misspecified case (up to the points raised in my comment 3.2). This is also present l.813\n* Other undefined symbols: $\\lambda$ in Theorem 1 (undefined at this point) and $\\sigma_\\epsilon^2$,  $\\sigma_{\\epsilon_{1,2}}$, $\\sigma$, and $\\sigma_G$ ll.191--193\n* The notation $g$ is overloaded and ambiguous. It is sometimes used as a random variable on which expectations are taken (cf. (1)), sometimes as a function (l.145), sometimes as an element of $\\mathcal X\\times\\mathcal U$, and sometimes as multiple of these options (cf. the equation ll.192--193). I encourage the authors to clarify this.\n* l.141: I don't understand what is meant by $\\mu_\\mathcal G(g(x,u)) = \\mu_\\mathcal X(x)\\mu_\\mathcal U(u)$, as measures should take sets as inputs.\n\n[R1] Steinwart and Christmann, Support vector machines, 2008\n\n[R2] Steinwart et al., Learning from dependent observations, 2009\n\n[R3] Massiani et al., On the consistency of kernel methods with dependent observations, 2024\n\n[R4] Steinwart and Christmann, Fast learning from non-iid observations, 2009\n\n[R5] Hang and Steinwart, Fast learning from $\\alpha$-mixing observations, 2014\n\n[R6] Ziemann and Tu, Learning with little mixing, 2022\n\n[R7] Simchowitz et al., Learning without mixing (...), 2018\n\n[R8] Abbasi-Yadkori, Online Learning for Linearly Parametrized Control Problems, 2013\n\n[R9] Chowdhury and Gopalan, On kernelized multi-armed bandits, 2017\n\n[R10] Chowdhury and Gopalan, No-regret algorithms for multi-task bayesian optimization, 2021\n\n[R11] Yu, Rates of convergence for empirical processes of stationary mixing sequences, 1997\n\n[R12] Mohri and Rostamizadeh, Stability Bounds for Stationary ϕ-mixing and β-mixing Processe, 2010\n\n[R13] Kuznetsov and Mohri, Generalization bounds for non-stationary mixing processes, 2017\n\n[R14] Li et al., Optimal learning rates for regularized conditional mean embedding, 2022", "was_revised": true, "final_justification": "The authors have addressed my technical concerns, and I trust that they will implement the promised changes (mainly, regarding Assumption 1).\nNonetheless, I believe the exposition of this paper can be thoroughly improved and recommend rewriting it to emphasize different parts of the contribution to improve readability; the current emphasis to denoising score learning could be kept but relegated to an appendix. I also find the proofs very hard to follow and was not able to check them in details given my limited familiarity with the tools they leverage. This is the reason for a **borderline** accept.", "rebuttal": "Thanks for your time and efforts reviewing our paper. We now address raised questions as follows.\n\n* Q1: Related works.\n\n    Thanks for your question. We will add statistical learning of SVM [R1] and time-uniform concentration inequalities [R8-R10] in our revised manuscript and focus on discussing the non-i.i.d. analysis [R2,R3,R6,R7] here (deferring the discussion of learning under mixing assumptions [R4,R5,R11-R13] to Q2).\n\n    * **Setting**\n\n        A line of work established the consistency of SVMs or kernel methods under some specific assumptions e.g. processes satisfying a law of large numbers [R2], or empirical weak convergence [R3]. While the consistency can be characterized under such strong non-i.i.d.-ness, it remains unclear of the convergence speed. Another line of work focuses on the regression over trajectories generated by a dynamic system, both linear [R6] and non-linear [R7]. Though these approaches are without mixing, the surrogate trajectory assumptions limit its applicability to other settings. Our work aim to capture the asymptotic convergence rate for $k$-gap independent data.\n\n    * **Technique**\n\n        [R6,R7] utilize single-layer block decomposition and handle each blocks by Mendelson’s small-ball method, eschewing the use of standard mixing-time arguments. Regarding the specific $k$-gap independence, our technique relies on a new-designed block scheme which is free of neither Mendelson’s small-ball method nor standard mixing-time arguments. Our novel technique enables us to eliminate the approximation error between dependent blocks and their independent surrogates, revealing the benefit of data relevance (detailed in Q2).\n\n* Q2: Setup.\n\n    * Q2.1: Reason to consider the block-independence.\n\n        Thanks for your question. We clarify the difference from those related works [R4,R5,R11-R13] as follows, whose techniques cannot resolve our setting.\n\n        * **Setting**\n \n            While many works have derived concentration high-probability bounds for non-i.i.d. data under the geometrically mixing assumption [R4,R5] or the algebraically mixing assumption [R11-R13], our $k$-gap independent case **cannot be covered by these works**, as the correlation between data points will remain high as long as they are from the same group with size $k$. Therefore, our $k$-gap independent case requires a fundamantally different non-i.i.d. data analysis.\n\n        * **Intuition**\n\n            Most of the existing results [R11-R13] perform analysis under the intuition to control the approximation error between independent blocks and dependent blocks by mixing coefficients. That being said, the data dependency is treated as an bad effect in their analysis and will finally appear as an error term. However, in our setting, we do not treat the data dependency a bad effect but aim to discover some benefits for reducing the error, otherwise it would be intractable to prove the vanishing generalization error in our setting for general $k$. To this end, we perform refined study in decomposing blocks to eliminate direct error approximation.\n\n        * **Insight**\n\n            Our analysis demonstrates the benefit of data relevance, which is in totally contrast to current non-i.i.d. data analysis. We believe some of our techniques and methodologies can be potentially extended to a broader settings (e.g., the size of each group could vary).\n\n    * Q2.2: Proof techniques.\n\n        Thanks for your question. Our proof technique differs fundamentally from mixing data approaches [R11-R13] in both decomposition strategy and error handling. While all methods employ block decomposition, the **block scheme** is different. Prior work does not perform refined study on the **intra-block randomness**, as they use single-layer decomposition that requires constructing independent surrogate blocks and controlling approximation errors. The crude study of the intra-block randomness **fails to characterize the role of data dependence** in our $k$-gap independent case. Besides, **the size of block** in existing methods **fails to capture the underlying independence** in our specific $k$-gap independent setting, limiting its applicability.\n\n        In contrast, to overcome the above weakness, we introduce a more refined decomposition, yielding multiple partitions with several independent blocks respectively. This enables us to apply standard symmetrization techniques for each partition individually and resolve cross-partition dependencies through our novel incorporating lemma (Lemma C.20). Only by this technique, can we fully utilize the underlying data independence and intra-block dependence, and derive a preciser Bernstein-type high probability bound consistent with the i.i.d. case (up to some logarithm terms).\n    \n* Q3: Assumptions.\n    * Q3.1: Kernel function / Convention(l. 178).\n\n        Thanks for your good points. Operators related to $T$ are mappings: $L^2\\to L^2$. We will provide clear characterizations of other concepts according to [48] in the revised manuscript.\n\n    * Q3.2: The smoothness condition on $f_\\rho^*$.\n\n        Thanks for your comment. The smoothness condition on $f_\\rho^*$ appears in some existing work (Lemma A.12 in [31]). In fact, In deriving our general theoretical bound Eq.(2), **we can relax $s\\geq 1$ to $s>0$** and obtain exactly the same result, as we  have technically leveraged assumptions and properties of interpolation spaces for refinements. \n\n        While for the specified bounds under conditional orthogonality (Eq.(3) and Theorem 4.4), $s\\geq 1$ is required to estimate the relevance parameter $r_T$ (Lemma B.11) for providing a concise bound and clear insights, where the relevance parameter is explicitly related to $\\alpha_t$. Technically, the smoothness on $f_\\rho^* $ enables continuity to convert the relevance in the function space into the relevance $r_0$ in the data space (line 813-815). We consider this specific case to make our conclusion more clear and understandable. Indeed, without the strong smoothness $s\\geq 1$, we can also provide estimation (less concise expression) for $r_T$. We merely need to replace $r_0$ with $r_\\rho:=\\frac{\\mathbb{E}\\left[\\left(f_\\rho^{(r)* }(g_{ij})-f_\\rho^{(r)* }(g_{i'j})\\right)^2\\right]}{4\\mathbb{E}\\left[f_\\rho^{(r)* }(g_{ij})^2\\right]}\\in [0,1]$, maintaining all convergence guarantees.\n\n        Regarding the terms $i^{-\\frac{1}{2}}$ and $a_i\\geq c>0$ in this assumption, we follow the expression in the existing result [4] to provide a direct and clear comparison with the i.i.d. setting. \n\n    * Q3.3: The polynomial eigenvalue decay assumption.\n\n        Thanks for your comment. The polynomial spectrum makes our bound clearer and facilitates direct comparison with established results in the i.i.d. setting [31]. This makes the core theoretical insights more accessible. While the assumption simplifies presentation, our framework is readily extensible to general spectra on the technical level. The key terms (e.g. Lemma C.3-C.5) can be expressed directly in terms of individual eigenvalues ($\\lambda_1, \\dots$) rather than the decay rate $\\beta$. For instance, the norm $\\Vert f_\\lambda\\Vert_{[\\mathcal{H}]^\\gamma}^2$ is fundamentally given by a series (shown below) that depends on the full eigenvalue sequence: $\\Vert f_\\lambda\\Vert_{[\\mathcal{H}]^\\gamma}^2\\asymp\\sum_{i=1}^\\infty\\left(\\frac{\\lambda_i^p}{\\lambda_i+\\lambda}\\right)^2i^{-1}.$ Therefore, the polynomial decay is primarily a tool for deriving clearer, more interpretable bounds without fundamentally limiting the scope of our technical approach. \n\n* Q4: Application to denoising score learning / Design neural networks.\n\n    Thanks for your question. Our theoretical bounds are derived on KRR to provide insights and inspirations for practical data usage and training. In particular, our theoretical findings that noise multiplicity $k$ should scale with the noise level align well with the intuition that when the noise dominates in the observation, practitioners should add more noise rather than the raw data. Therefore, we believe this finding holds whatever learner is and apply our theory on practical neural network training. / The main contributions and insights of our theoretical results are to provide guidance for data sampling instead of designing neural network to approximate KRR. With our theoretical insights on KRR and empirical validations on neural network training, we believe our work can inspire practical training broadly.\n\n* Q5：Minor Comments\n\n    Thanks for your comments. We apologize for some typos and misunderstandings. For some inappropriate expressions such as \"signal\", \"advanced technique\", \"roughly\", typos \"$f_\\rho^* \\in \\mathcal{H}$\" and some confused notations such as the asymptotic notations, $\\lambda$ in Theorem 1, $\\mu_G$, Example 3.2, $g$, we will modify those in the revised manuscript. We clarify other misunderstandings as follows.\n\n    * Q5.1: KRR is applied independently per dimension.\n\n        Thanks for your comment. On the one hand, applying KRR independently per dimension yields cleaner proofs and more interpretable bounds (with standard i.i.d. results [31]) and insights. On the other hand, in practical denoising score learning example, noise is standardly assumed independent per dimension, where multi-output variant case can be reduced to ours.\n\n    * Q5.2: Second moment terms.\n\n        Thanks for your good points. $\\sigma_\\epsilon$ and $\\sigma^2$ control the decay of the population noise conditionally on data, with the former controlling the exponential decay (sub-Gaussian norm) and the latter controlling the quadratic decay (second moment). In parallel, for technical reasons to analyze dependent data, we extend $\\sigma_\\epsilon$ and $\\sigma$ which are single-data conditioning to $\\sigma_{\\epsilon_{1,2}}$ and $\\sigma_G^2$ which are dependent-data conditioning. \n\nWe hope above response can address your concern and we are open to discuss more if any question still hold."}, {"review_id": "TcoHW52ayJ", "reviewer": "Reviewer_APPF", "summary": "This paper considered the model $y_{i}^{j} = f^*(g_{i}^{j}) + \\epsilon_{i}^{j}$, $i \\leq n$, $j \\leq k$. The authors further assumed that there exists a function $g$, such that for each group $j$, the inputs are generated as $g_{i}^{j} = g( x_{i}, u_{i}^{j})$, where i.i.d. signals $\\{x_i\\}$ are independent of i.i.d. noises $\\{u_{i}^{j}\\}$.\n\nThis paper then obtained an upper bound on the convergence rate of learning curve (i.e., the excess risk w.r.t. different choices of regularization parameter $\\lambda$) of KRR under common assumptions.", "questions": "- 1) What is the motivation of setting $r \\leq d$ in line 172? I notice that $r$ systems are trained independently, and both the theoretical analysis and the example in Section 4.1 consider the special case $r = 1$.\n\n- 2) There might be typos in (2) and possibly other equations: The bias convergence rate should be $n^{-\\min (s, 2)\\theta}$; and the $\\Theta$ notation should be $O$ unless both upper and lower bounds are established.\n\n- 3) The paper would benefit from a more comprehensive discussion of relevant prior work in several areas: \n    - (i) Optimal rate of KRR and kernel gradient flow (deep neural networks, that the authors mentioned, are more closely related to kernel gradient flow). E.g., Optimal rates for the regularized least-squares algorithm; On the optimality of misspecified kernel ridge regression; Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decay.\n    - (ii) saturation effect of KRR (the appearance of $\\min$\\{$s$, 2\\} in Theorem 4.1 is related to it). E.g., Optimal rates for the regularized least-squares algorithm; ON THE SATURATION EFFECT OF KERNEL RIDGE REGRESSION.\n    - (iii) high-dimensional KRR and KGF. E.g., Just interpolate: Kernel “Ridgeless” regression can generalize; linearized two-layers neural networks in high dimension; on the Saturation Effects of Spectral Algorithms in Large Dimensions; On the Pinsker bound of inner product kernel regression in large dimensions", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- i) The authors considered the non-i.i.d. data settings, which is new within the KRR literature. They also provide two real-world examples (Examples 3.1 and 3.2) to illustrate the relevance of this setting.\n- ii) The paper is carefully written and overall enjoyable to read.\n- iii) The proof is novel compared with existing works. For example, the authors used a blockwise decomposition method for $k$-gap independent random sequence as an alternative to Bernstein-type concentration inequalities typically used for i.i.d. data (e.g., Lemma B.4 in [31]).\n- iv) The results in this paper recovered known results in the i.i.d. case when $k = 1$.\n\nWeaknesses:\n- i) The authors assume that the target function $f^* \\in L^2$ lies in the interpolation space $[\\mathcal{H}]^s$ with $s \\geq 1$. In particular, when $s = 1$, this reduces to $f^* \\in \\mathcal{H}$, i.e., the RKHS itself. This assumption may be restrictive when dimension $d$ is large. For example, \n    - Consider the Sobolev RKHS $W^{m,2}(\\mathcal{X})$ with $\\mathcal{X} \\subset \\mathbb{R}^{d}$ and $m > d/2$. Its interpolation space with $s>0$ is given by $ [W^{m,2}(\\mathcal{X})]^s \\cong W^{m s , 2}(\\mathcal{X})$, and functions in $W^{ms,2}(\\mathcal{X})$ are weak differentiable of order $m s$.\n    - On one hand, if we assume that $f_{\\star} \\in \\mathcal{H}$, then it requires that $f_{\\star}$ is weak differentiable of order $m>d/2$, which becomes increasingly unrealistic as $d$ grows. \n    - On the other hand, if we consider the interpolation space with $s>0$, then we can adopt a weaker assumption $f_{\\star} \\in W^{m s , 2}(\\mathcal{X})$, allowing the results to cover less smooth functions.\n\n    It would be helpful if the authors could discuss the challenges associated with analyzing the case $s < 1$, and whether these challenges are analogous to those in the i.i.d. setting.\n\n- ii) The experiments involve a three-layer ReLU MLP. Since there is currently no theoretical approximation framework between MLPs and kernel gradient flow (KGF) / KRR in the non-i.i.d. setting, it is better to use KRR instead.", "was_revised": true, "final_justification": "I believe the authors have addressed my main concerns.", "rebuttal": "Thanks for your time and efforts reviewing our paper. We now address raised questions as follows.\n\n* Q1: The target function $f^*$ lies in the interpolation space $[\\mathcal{H}]^s$ with $s\\geq 1$ may be restrictive. / Discuss the challenges associated with analyzing the case $s < 1$, and whether these challenges are analogous to those in the i.i.d. setting.\n\n    Thanks for your comment. The smoothness condition on $f_\\rho^*$ appears in some existing work (Assumption (B) in [1], Lemma A.12 in [4]). In fact, for the derivation of our general theoretical bound (the first statement in Theorem 4.1, Eq.(2)), **we can relax our assumption to $s>0$** and obtain exactly the same result, as we leverage assumptions and properties of interpolation spaces for refinements on the technical level. \n        \n    While for the specified bounds under conditional orthogonality (the second statement in Theorem 4.1, Eq.(3) and Theorem 4.4), $s\\geq 1$ is required to estimate the relevance parameter $r_T$ (Lemma B.11) for providing a concise bound and clear insights, where the relevance parameter is explicitly related to $\\alpha_t$. Technically, the smoothness on $f_\\rho^* $ enables continuity to convert the relevance in the function space into the relevance $r_0$ in the data space (line 813-815). We consider this specific case to make our conclusion more clear and understandable. Indeed, without the strong smoothness $s\\geq 1$, we can also provide estimation (less concise expression) for $r_T$. We merely need to replace $r_0$ with $r_\\rho:=\\frac{\\mathbb{E}\\left[\\left(f _ \\rho^{(r) * }(g_{ij})-f_\\rho^{(r)* }(g_{i'j})\\right)^2\\right]}{4\\mathbb{E}\\left[f_\\rho^{(r)* }(g_{ij})^2\\right]}\\in [0,1]$, maintaining all convergence guarantees.\n\n* Q2: The experiments involve a three-layer ReLU MLP. Since there is currently no theoretical approximation framework between MLPs and kernel gradient flow (KGF) / KRR in the non-i.i.d. setting, it is better to use KRR instead.\n\n    We thank the reviewer for the insightful comment regarding the use of MLPs. To supplement，we conducted the same experiments using both **NTK** and **RBF** kernels. The results show consistent trends with our MLP findings:\n\n    | **k**   | **NTK Loss at t = 1.0** | **NTK Loss at t = 0.1** | **RBF Loss at t = 1.0** | **RBF Loss at t = 0.1** |\n    |--------:|------------------------:|-------------------------:|------------------------:|-------------------------:|\n    | 1       | 8.3379e-05              | 0.7020                   | 0.00268199              | 0.6412                   |\n    | 16      | 8.3086e-05              | 0.6971                   | 0.00175084              | 0.6532                   |\n    | 32      | 8.0374e-05              | 0.7268                   | 0.00123094              | 0.8061                   |\n    | 64      | 8.0684e-05              | 0.7307                   | 0.00102835              | 1.3014                   |\n    | 128     | 7.9432e-05              | 0.8351                   | 0.00069417              | 2.6334                   |\n\n    These results reinforce both our theoretical insights and the empirical findings from the MLP experiments presented in the paper: **increasing \\( k \\)** consistently improves performance at \\( t = 1.0 \\), where the target function is simpler, but leads to degraded accuracy at \\( t = 0.1 \\), where the function exhibits greater complexity. These empirical findings align well with our theory that when $t$ is large (i.e., noise dominates), increasing $k$ is beneficial to generalization.\n    \n* Q3: What is the motivation of setting $r \\leq d$ in line 172? I notice that $r$ systems are trained independently, and both the theoretical analysis and the example in Section 4.1 consider the special case $r = 1$.\n\n    Thanks for your comment. Considering $r = 1, \\dots, d$ allows our framework to handle real-world vector-output tasks like denoising score learning (where outputs correspond to spatial/gradient dimensions). This generalizes prior scalar-output analyses to broader applications. While on the technical level, the vector output analysis can be reduced to $r=1$ for the reason that noise is independent per dimension. This enables provably equivalent analysis via parallel single-dimensional KRR. Focusing on $r=1$ in analysis maintains clarity in proofs and notation, and preserves all key insights.\n    \n* Q4: There might be typos in (2) and possibly other equations: The bias convergence rate should be $n^{-\\min (s, 2)\\theta}$; and the $\\Theta$ notation should be $O$ unless both upper and lower bounds are established.\n\n    Thanks for your comment. The bias convergence rate is indeed $n^{-\\min (s, 2)\\theta}$, we will modify these typos and the usage of asymptotic notations in the revised manuscript.\n\n* Q5: A more comprehensive discussion of relevant prior work.\n\n    Thanks for your suggestion. We will include the following discussion of related prior work in the revised manuscript.\n\n    * (i) Optimal rate of KRR and kernel gradient flow.\n        \n        There are rich literature showing the optimal rate of KRR and kernel gradient flow. [3] demonstrates the minimax optimality of KRR when the regression lies in the RKHS and proves the best upper bound of the generalization error is $n^{-\\frac{2\\beta}{2\\beta+1}}$. [4] further extends the result to the misspecified cases when the regression function does not lie in the RKHS. More recently, [5] studies the generalization error curves of a large class of analytic spectral algorithms, including the kernel gradient method, where the regressor $\\hat{f}_\\lambda$ is obtained by a filter function. Our paper initials the study of the generalization behavior of KRR in the structured non-i.i.d. setting and defers the study of analytic spectral algorithms to future.\n  \n    * (ii) Saturation effect of KRR.\n    \n        The saturation effect refers to the phenomenon that the kernel ridge regression (KRR) fails to achieve the information theoretical lower bound when the smoothness of the underground truth function exceeds certain level. To be specific, [2] shows that the information theoretical lower bound of the generalization error is $n^{-\\frac{s\\beta}{s\\beta+1}}$ while [3] shows that the best upper bound of the generalization error is $n^{-\\frac{2\\beta}{2\\beta+1}}$. This gap has been widely observed in practices: no matter how carefully one tunes the KRR, the rate of the generalization error can not be faster than $n^{-\\frac{2\\beta}{2\\beta+1}}$. More recently, [1] rigoriously prove the saturation effect by providing a lower bound matching the existing upper bound $n^{-\\frac{2\\beta}{2\\beta+1}}$. In our paper, let $\\tilde{r}+\\frac{1-\\tilde{r}}{k} \\asymp n^{-l}$, then the optimal $\\theta$ for generalization error is $\\theta_{opt}=\\frac{(1+l)\\beta}{\\beta \\mathrm{min}(s,2)+1}$ and the optimal generalization error rate is $n^{-\\frac{(1+l)\\beta \\mathrm{min}(s,2)}{\\beta \\mathrm{min}(s,2)+1}}$. On the one hand, when $l>0$ (implying that $\\tilde{r}$ is extremely small and $k$ is extremely large), the saturation effect still holds but with a faster rate. On the other hand, when $l=0$ (e.g. k=1), our result matches the previous result in the i.i.d. setting.\n  \n    * (iii) high-dimensional KRR and KGF.\n    \n        While kernel regression with a fixed data dimension $d$ has been extensively studied, there are rising attentions to the case when dealing with large-dimensional data. In the large-dimensional setting where $n \\asymp d^\\gamma$ with $\\gamma>0$, [6] finds that for the square-integrable regression function, KRR and kernel gradient flow are consistent if and only if the regression function is a polynomial with a low degree. Another line of work e.g. [7], considers the overfitting behavior of kernel interpolation. On the technical level, [7] utilizes the argument that high-dimensional random kernel matrices can be approximated in spectral norm by linear kernel matrices plus a scaled identity. Regarding the saturation effect, [8] explores this effects for a large class of spectral algorithms (including the KRR, gradient descent, etc.) in large dimensional settings, by providing minimax lower bound and the exact convergence rates. Besides, [9] explores the Pinsker bound problem for kernel regression models that incorporate large-dimensional inner product kernels defined on the sphere $\\mathbb{S}^d$, by addressing the scenario where the sample size $n$ is given by $\\alpha d^\\gamma (1+o_d(1))$ for some $\\alpha,\\gamma >0$. Our paper defers the analysis in high-dimensional data scnario to future.\n        \nWe hope above response can address your concern and we are open to discuss more if any question still hold.\n\n[1] ON THE SATURATION EFFECT OF KERNEL RIDGE REGRESSION.\n\n[2] Optimal rates for the regularized learning algorithms under general source condition.\n\n[3] Optimal rates for the regularized least-squares algorithm.\n\n[4] On the optimality of misspecified kernel ridge regression.\n\n[5] GENERALIZATION ERROR CURVES FOR ANALYTIC SPECTRAL ALGORITHMS UNDER POWER-LAW DECAY.\n\n[6] Linearized Two-Layers Neural Networks in High Dimension.\n\n[7] Just Interpolate: Kernel “Ridgeless” Regression Can Generalize.\n\n[8] On the Saturation Effects of Spectral Algorithms in Large Dimensions.\n\n[9] ON THE PINSKER BOUND OF INNER PRODUCT KERNEL REGRESSION IN LARGE DIMENSIONS."}]

Author rebuttal:

Meta-review: This paper investigates the excess risk of kernel ridge regression under a structured non-i.i.d. setting, where each latent signal generates multiple noisy observations. This setting goes beyond the classical i.i.d. assumption and is modeled via blockwise independence, which differs from mixing processes. The work has a natural application to diffusion models. The authors derive excess risk bounds using a blockwise concentration approach under standard assumptions (source and capacity conditions). However, it remains unclear why the additional Hölder-continuous kernel assumption is required.

After the rebuttal, all reviewers were satisfied and recommended acceptance. The authors are expected to address the reviewers’ comments in the final version. From my own high-level reading, the intuition is that the $k$ noisy observations per latent signal do not affect the bias term, while they can help reduce variance. This formulation shares similarities with pairwise learning, and there are relevant works in the kernel literature that should be discussed for completeness. Furthermore, the introduction to be rewritten would benefit from a clearer motivation, for instance emphasizing the connection to diffusion models, as highlighted by multiple reviewers.
Decision: Accept (poster)