{'fraction_non_alphanumeric': 0.06597721207144323, 'fraction_numerical': 0.021427838226236912, 'mean_word_length': 3.674223341729639, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Non-asymptotic theory for nonparametric testing

We consider nonparametric testing in a non-asymptotic framework. Our statistical guarantees are exact in the sense that Type I and II errors are controlled for any finite sample size. Meanwhile, one proposed test is shown to achieve minimax optimality in the asymptotic sense. An important consequence of this non-asymptotic theory is a new and practically useful formula for selecting the optimal smoothing parameter in nonparametric testing. The leading example in this paper is smoothing spline models under Gaussian errors. The results obtained therein can be further generalized to the kernel ridge regression framework under possibly non-Gaussian errors. Simulations demonstrate that our proposed test improves over the conventional asymptotic test when sample size is small to moderate.

1. Introduction. Many classical statistical inferential procedures are built upon large sample theory that relies on a growing amount of data information or a large number of samples. However, in practice, it is often the case that only a small to moderate amount of samples are available, which limits the applicability of the classic asymptotic inferential procedures. Recently, finite sample inferential theory has provided a new perspective for statistical analysis. For instance, with the aid of various notions of concentration inequality, [2,3,17,22,23,30] have developed statistical inference procedures that are theoretically valid for any fixed sample size. As far as we are aware, the parameter of interest in these works is finite dimensional. The goal of this paper is to develop finite sample theory in another important setting -nonparametric models.
In the asymptotic regime, there is a vast amount of literature devoted to developing theories for nonparametric inferences such as testing and confidence band; see [26,28]. However, little progress has been gained towards finite sample theory for nonparametric inference procedures. Our work can be viewed as an initial attempt to establishing a non-asymptotic framework for nonparametric testing, which covers the existing asymptotic theory as a direct consequence. This effort requires new technical tools such as (uniformly valid) large deviation bounds. In particular, two Wald-type test statistic are constructed with their cut-off values being adjusted according to any finite sample. This is in sharp contrast with conventional asymptotic tests that rely on the null limit distributions, e.g., likelihood ratio test in [8,20].
We begin with smoothing spline models under Gaussian errors. As a first attempt, we consider a test statistic simply defined as a discrepancy between the null function and smoothing spline estimate, and develop a corresponding nonasymptotic deviation inequality (see Theorem 3.1). Despite its simplicity, this naive test is shown minimax sub-optimal in an asymptotic sense according to [12,15,4]. This is due to a non-vanishing bias term that reduces the power. This motivates the development of a more refined non-asymptotic deviation bound (see Theorem 3.4) for a "de-biased" smoothing spline estimate, based on which our second test statistic is proposed and shown to achieve the minimx optimality by correcting the bias explicitly. To our knowledge, this deviation bound is the first non-asymptotic expansion of the smoothing spline estimate up to a higher-order decaying remainder term. Based on these large deviation results, Type I and II errors are controlled for any finite sample size in both methods; see Corollaries 3.3 and 3.6. As an interesting by-product, a lower bound on the sample size is quantified to yield desirable Type I and II errors. The relation between the proposed tests and the asymptotically valid likelihood ratio test ( [20]) is also highlighted. As for other smoothing-spline-based tests such as LMP ( [7]), they were developed from Bayesian setup and always rely on complicated null distributions involving nuisance parameters, as reviewed in [16].
Three non-trivial generalizations are further carried out. First, we consider a general class of composite hypothesis, e.g., the null set is a subspace of polynomial functions. Second, we extend our test to more general regression settings where errors might be non-Gaussian. Third, we demonstrate that our finite sample testing framework also accommodates the more general kernel ridge regression (KRR) [21], including smoothing spline as a special case.
In practice, the choice of smoothing parameter is crucially important. However, it is known that the widely used generalized cross validation (GCV, [25]) does not lead to a minimax optimal testing procedure; see [8]. Importantly, our non-asymptotic theory yields a practically useful formula to select an optimal smoothing parameter. To be more specific, it is obtained by directly minimizing a separation function (that quantifies the minimal detectable signal strength) derived in the nonasymptotic framework. As far as we are aware, this non-asymptotic formula is new.
Our simulations demonstrate the empirical advantage of the above selection method over GCV in both the proposed test and the conventional asymptotic test such as penalized likelihood ratio test (PLRT, [20]). Additionally, the simulation study confirms that our finite-sample based testing procedure is uniformly more powerful than PLRT as the sample size grows (under the same choice of smoothing parameter). Besides the non-asymptotic design, another reason for this empirical success is that the proposed test removes a bias term from the PLRT due to penalization. Although this bias term is asymptotically of higher order, it can significantly deteriorate the power of the test when sample size is small to moderate. We count this as another highlight by applying our finite sample framework.
The rest of this paper is organized as follows. In Section 2, background and preliminaries are introduced. Sections 3 and 4 include the main results of this paper. In Section 3, test statistic based on smoothing spline estimation are constructed and their non-asymptotic properties are investigated. The methods are valid for both simple and composite hypotheses. Section 4 includes extensions to more general regression settings. Section 5 includes a simulation study. Main proofs are provided in Section 6, while the rest are deferred to a supplementary document [29].
2. Preliminary. In this section, we state the nonparametric models and hypothesis of interest, and also review some basic theory of reproducing kernel Hilbert space (RKHS).
Let D n = {(Y i , X i ) : i = 1, 2, . . . , n} be iid random samples following the nonparametric regression model where is a random error with mean zero and unit variance. For simplicity, we consider the onedimensional case where X ∈ I := [0, 1], and assume that the design X and are independent. Let the marginal density function of X be π(x) which satisfies 0 < inf x∈I π(x) ≤ sup x∈I π(x) < ∞.
We assume that f belongs to an m-th order Sobolev space S m (I) = f ∈ L 2 (I)| f (j) are abs. cont. for j = 0, 1, . . . , m − 1, and Let P f denote the probability measure under f , and E f be the corresponding expectation. Consider the following hypothesis testing problem: where F 0 is a proper subset of S m (I). For example, F 0 = {f 0 } for some known f 0 ∈ S m (I) in simple hypothesis, while F 0 = {all linear functions in S m (I)} in composite hypothesis. Our testing statistic is constructed based on the following smoothing spline estimator where n,λ (f ) is the penalized loss function defined as where λ > 0 is the penalty parameter and J(f, g) . It follows that ·, · defines a valid inner product in S m (I); see [20]. Endowed with ·, · , S m (I) is an RKHS. We use the notation · to denote the corresponding RKHS norm. Let K(x 1 , x 2 ) denote the reproducing kernel function, a function from I × I to R satisfying the reproducing property K x , f = f (x) for any x ∈ I and f ∈ S m (I), where K x (·) : = K(x, ·) is an element in S m (I) for any x ∈ I. Let P λ denote a self-adjoint operator from S m (I) to itself that satisfies f, P λ g = λJ(f, g), for all f, g ∈ S m (I); see [20] for the existence of such an operator.
We make the following assumption on the existence of eigen-pairs (ρ ν , ϕ ν ) that simultaneously diagonalize V and J. This assumption is commonly made in smoothing spline literature.
It follows from [20] that for any x ∈ I, . Under Assumption A1, it is straightforward to verify the following property of K x 3. Main Results. In this section, we construct two nonparametric test methods based on f n,λ . The first type is straightforward but sub-optimal in the minimax sense, while the second attains the minimax optimality by removing the bias from the former. Our major contribution is to develop non-asymptotic theoretical analysis for both testing methods. Specifically, Type I and II errors can be controlled for any finite sample size. This leads to a non-asymptotic formula in selecting the optimal λ in practice. These non-asymptotic results are developed based on large deviation bounds between f n,λ and f that are shown uniformly valid over an "unit ball" in S m (I).
In this section, we assume Gaussian errors and uniform design, i.e., ∼ N (0, 1) and X ∼ Unif(I), and postpone extensions to general error distributions to the next section.
3.1. A Preliminary First-Order Testing Procedure. To illustrate the idea, we first focus on the simple hypothesis H 0 : f = f 0 , where f 0 is a known function in S m (I). Under the null, f n,λ converges to f 0 under suitable norms as sample size n tends to infinity. Naturally, the deviation between f n,λ and f 0 can be used as a test statistic: Despite the simple form of T n,λ , it will be shown to be asymptotically sub-optimal. We call T n,λ as first-order testing in the rest of the paper.
The null hypothesis is rejected if T n,λ exceeds some threshold d n (M ) (to be defined later), where M is a constant controlling the significance level of the test. To calibrate a finite sample valid d n (M ), we first need to establish a large deviation bound for T n,λ uniformly over an "unit ball" in S m (I), defined as H m (1) = {f ∈ S m (I)|J(f, f ) ≤ 1}.
is an explicit function of h defined in Remark 3.1 below.
Theorem 3.1 is proven in Section 6.2.
Remark 3.1. The function A(h) in Theorem 3.1 is defined as A(h) = A(h, 2). As will be seen below, A(h, ε) is an explicit formula depending on Dudley's entropy integral, which controls the upper bound of a concentration inequality (Lemma 6.1) that plays a key role in the proof of Theorem 3.1. Specifically, where τ = √ log 1.5 ≈ 0.6368 and the function Ψ(r), resulted from Dudley's entropy integral (see [24]), is defined as Ψ(r) = r 0 log(1 + exp(x −1/m ))dx. In the above, c 0 is chosen as the constant controlling the packing number of G := {g ∈ S m (I) : g sup ≤ 1, J(g, g) ≤ c −2 K h −2m+1 }, i.e., c 0 satisfies, for any ε > 0, where N (ε, G, · sup ) is the ε-packing number. Existence of such c 0 follows from [24,20].
According to (3.2), we choose r = (nh) −1/2 . In this case, the threshold becomes δ n (M, (nh) −1/2 ), denoted as d n (M ). The following theorem, as an immediate consequence of Theorem 3.1, characterizes the upper bounds of Type I and II errors for any finite sample size.

then it holds that
Type I error : Type II error : sup Theorem 3.2 implies that the Type I error falls below α and Type II error falls below β if we set M = M 0 := log(2/α) and L = L 0 := log(2/β), respectively. Consequently, the separation rate between f and f 0 (in terms of · ), under which the testing power is at least 1 − β, is ρ n (M 0 , L 0 ).
We summarize the above discussions in the Corollary below.
Corollary 3.3. Under the assumptions of Theorem 3.1, for any α, β ∈ (0, 1), we have Type I error : where ρ n (log(2/α), log(2/β)) = 4h m + c K ( 2 log(2/α) + 2 log(2/β) + 2)(nh) −1/2 , as a function of h, achieves its minimum at The value of c K = sup x∈I hK(x, x) in (3.4) can be approximately determined by (2.4) which in turn requires the estimate of ϕ ν sup . The latter estimation can be done numerically by the spectral decomposition of the reproducing kernel matrix w.r.t. J. For instance, the R packages gss ( [9]) and assist ( [27]) both allow us to extract the kernel matrix corresponding to J, and the eigenvectors of the matrix provide a good estimate of the eigenfunctions.
The minimal separation rate (computed at h * ) is given as where D(c K , α, β) is a positive constant depending on c K and (α, β) only. Nevertheless, the above rate fails to match with the minimax lower bound, namely, n −4m/(4m+1) (see [12,15,4]). Hence, the first order testing procedure is sub-optimal from an asymptotic perspective. A finite sample valid and asymptotically optimal testing method is further proposed in Section 3.2.

3.2.
An Optimal Second-Order Testing Procedure. In this subsection, we improve the first order testing to attain minimax optimality. A closer examination of T n,λ reveals that its suboptimality is due to a large bias arising from the deviation f n,λ − f 0 , which inflates the separation gap ρ n (M, L). Fortunately, this bias can be easily removed as shown in the following second order deviation result. This observation motivates a new testing procedure, i.e., (3.6).
Theorem 3.4 is proven in Section 6.2 by employing a concentration inequality (see Lemma 6.1) for an operator-valued empirical process and a contraction mapping argument.
We remark that the threshold γ n (M, r) in Theorem 3.4 converges to zero faster than the threshold δ n (M, r) in Theorem 3.1 if we choose (r, h) to satisfy r 2 = (nh) −1 , h = o(1) and In this case, f n,λ − f and n −1 n i=1 i K X i − P λ f are of the same asymptotic order. For this reason, we call (3.2) a first-order deviation bound, and (3.5) a second-order deviation bound.
In view of (3.5), a second-order test statistic is developed as where the second term n −1 The term P λ f 0 in T n,λ is a bias correction term due to penalization. Subtracting a f -independent constant n −1 ν≥1 (1 + λρ ν ) −1 in T n,λ is merely for technical simplicity in the subsequent derivations. The corresponding testing rule is φ n,λ = I(| T n,λ | ≥ d n (M, h)), where d n (M, h) controls Type I error through the choice of (M, h). Based on Theorem 3.4, we will prove in Theorem 3.5 that (3.7) Type I error : Type II error : sup Under H 0 : f = f 0 , we can decompose the test statistic T n,λ as i j K(X i , X j ) + higher-order remainder. (3.8) By controlling the first two terms in (3.8), we can obtain large deviation bounds for T n,λ under both null and alternative hypotheses (see Lemma 6.2 and Lemma 6.3 in Section 6.3). This leads to the following theorem characterizing the finite sample property of the proposed test T n,λ .
The following corollary is obtained as an immediate consequence of Theorem 3.5.
Corollary 3.6. Under the assumptions of Theorem 3.4, for any α, β ∈ (0, 1), we have Type I error : Type II error : sup An important implication of Theorem 3.5 is that T n,λ is asymptotically minimax optimal. In fact, using the expression (3.9) of d n (M, h), we see that under the asymptotic regime n → ∞, the leading term in ρ n (M, L, h) scales as By minimizing this leading term w.r.t. h, we obtain the minimal separation rate when h is chosen as The above minimal separation rate matches with the minimax rate of testing obtained in [12,15,4].
The practical implementation of T n,λ requires us to estimate (I − P λ )f 0 . Instead of direct estimation, we approximate it by the following "noiseless" version of smoothing spline estimator By applying Theorem 3.4 with i ∼ N (0, 0), it is easy to see that f N L n,λ − (I − P λ )f 0 has the same derivation bound as As a consequence, we can replace (I − P λ )f 0 in T n,λ by f N L n,λ . In simulations, this approximated version of T n,λ (by using f N L n,λ ) is found to work very well, and have a larger power than T n,λ especially when f 0 under the null is far from zero (so that P λ f 0 incurs a relatively large bias).

Remark 3.2. (Relation with likelihood ratio test)
The non-asymptotic results obtained for T n,λ and T n,λ can be extended to another type of nonparametric testing: likelihood ratio test. We first define the penalized likelihood ratio test (PLRT) as follows In comparison, our test statistic (up to constants) can be expressed as where g = f 0 for T n,λ and g = (I − P λ )f 0 for T n,λ . Note that the first term in (3.14) is the expectation of that in (3.13) according to the definition of V (f, f ). In Appendix S.6, we prove that for any g ∈ S m (I), the deviation between 2P LRT (g) and f n,λ − g 2 is of higher order comparing to the dominating term of d n (M, h), i.e., 4ρ K √ M /(n √ h). Therefore, after some modifications, the results for T n,λ and T n,λ also hold for 2P LRT (f 0 ) and 2P LRT ((I − P λ )f 0 ), respectively. Remark 3.3. (Effective sample size for testing) An interesting consequence of Theorem 3.5 is that the minimal sample size, named as "effective" sample size, can be derived to simultaneously achieve the pre-determined size and power. We demonstrate this idea using a simple example. Directly solving inequality (3.15) for the effective sample size is nontrivial. Instead we can get an approximate solution. Specifically, ρ n (M, L,ĥ(M, L)) can be approximated by its leading term as Therefore, instead of solving (3.15), one can solve A numerical solution to (3.16) can be used as an "effective" sample size.

Extension to Composite Hypothesis.
Our results can be generalized to testing composite hypothesis. For example, one composite hypothesis of particular interest is whether f is a polynomial function, say with degree less than m. In this case, a new test statistic is proposed with similar non-asymptotic guarantee and asymptotic minimax optimality. For technical simplicity, we assume m ≥ 2 throughout this section.
For simplicity, we consider testing whether f is linear in this section: We propose a test statistic as . In general, we will establish that for any finite sample size (as in (3.7)) We still start from large deviation bounds of the test statistic under both null and alternative hypotheses. To do so, T com n,λ needs to be decomposed as (3.19) based on the following arguments. Let f 0 be the true linear function in F 0 from which dataset D n is generated, and let f = f H 0 n −f 0 . It follows by Theorem 3.4 that, under H 0 , T com n,λ can be decomposed as where = ( 1 , . . . , n ) T . The second equality follows from the fact that Since both f 0 and f are linear functions, P λ f 0 = P λ f = 0, and hence, As a consequence, the preceding display (3.18) can be further simplified as Based on (3.19), we can control the type I and type II error of the test (see Lemma 6.4 and Lemma 6.5), yielding finite sample analysis for the composite hypothesis testing procedure.
Theorem 3.7. Suppose that Assumption A1 holds. For any constants (h, M, L) satisfying Similarly, we have the following corollary for the composite test.
Similar to the simple hypothesis testing, Theorem 3.7 provides a non-asymptotic approach to select the smoothing parameter h by numerically minimizing the separation function h → ρ com n (log(24/α), log(60/β), h). Note that the leading terms of d com n (M, h) and ρ com n (M, L, h) are exactly the same as d n (M, h) and ρ n (M, L, h) in Section 3.2 for simple hypothesis. Hence, the selectedĥ in both cases are asymptotically rate-equivalent. Under such anĥ, the composite testing procedure in consideration is minimax rate-optimal.

Extensions.
In this section, we generalize our main results to non-Gaussian errors and the more general setup of kernel ridge regression.
Condition (4.1) says that (j) ( ) for j = 1, 2, 3 satisfies exponential tail condition. Note that for any a ∈ R, exp( ( + a))d = 1. Taking first-and second-order derivatives with respect to a, it can be shown that Setting a = 0 in (4.2), one gets E{η} = 0 and E{η 2 } = σ 2 . Therefore, Assumption A2 is a reasonable one. Similar to Theorems 3.1 and 3.4 for the Gaussian errors, we develop the following derivation bounds for the first-and second-order approximations of the penalized likelihood estimate f n,λ .
Theorem 4.1. Suppose that Assumptions A1 and A2 are satisfied. For any positive M, r n , h satisfying Condition H in Section S.1, the following two results hold: Here A(h) is defined in Section 3.1.
Based on Theorem 4.1, it is straightforward to extend the rest non-asymptotic theory in Section 3 to the general noise setting. However, we want to point out that the proof of Theorem 4.1 is more involved. The main reason is that now we need to bound higher-order derivatives of the log-likelihood function (which is zero given the quadratic stricture of the log-likelihood function under Gaussian error). Details are deferred to Section S.5 in the supplement for conserving space.

4.2.
Kernel Ridge Regression. The second extension is to consider the general framework of kernel ridge regression (KRR) [10,21], where f 0 is assumed to belong to a reproducing kernel Hilbert space (RKHS), denoted as H. The corresponding KRR estimator is defined as where · H is the norm associated with H. When H is chosen as S m (I), f KRR reduces to the smoothing spline estimate f n,λ . We first present a brief review on RKHS theory. Denote L 2 (I) as the space of square-integrable functions on I. A subspace of L 2 (I) is defined as RKHS if for each x ∈ I, the evaluation function f → f (x) is a bounded linear functional. Any RKHS is generated by a positive semidefinite kernel function K : I × I → R. More precisely, consider the space of all functions of the form By taking the closure of this space, it can be shown that we generate an RKHS H equipped with a norm · H , and this H is uniquely associated with the kernel K; see [1].
Our finite sample theory can be naturally extended to KRR, by replacing f n,λ with f KRR in the test statistic T n,λ . After this replacement, it can be shown that the leading term in the separation function ρ KRR n (M, L, λ) for testing the simple hypothesis , where X 1 , X 2 iid ∼ X. By direct examinations, it can be shown that where ρ ν are the eigenvalues defined in Section 2. Note that in (4.3), L 1 (λ) is increasing in λ while L 2 (λ) is decreasing in λ. To minimize the above leading term, we can select λ = λ * ,KRR by equating L 1 (λ) and L 2 (λ), i.e., solving the equation Below is a list of solutions to (4.4) in three concrete situations: • For polynomial kernel with ρ ν ν 2m , the solution of equation (4.4) is which recovers our previous result (3.12) by noting the relation that h = λ 1/(2m) .
• For finite rank kernel with ρ −1 ν I(ν ≤ k) for a rank k > 0, the solution of equation (4.4) is • For Gaussian kernel with ρ ν exp(ν 2 ), the solution of equation (4.4) becomes 5. Simulation Study. Simulation results are provided for examining our theory. Consider the following two types of hypotheses: . Set Type I and II errors as α = β = 0.05. • For simple hypothesis testing, data were generated as follows • For composite hypothesis testing, data were generated as follows ).
Note that the function f c in model (5.2) lies in the orthogonal complement of the subspace of linear functions in the sense that E{f c (X)} = E{Xf c (X)} = 0 for any scaling constant c. We first consider simple hypothesis testing. In some cases, the cutoff value d n (log(15/α), h) (see Corollary 3.6) provided in (3.9) can be quite conservative due to the use of some loose concentration inequalities. In practice, we suggest choosing an "exact" cutoff value d n (log(15/α), h) by Monte Carlo simulation. Specifically, by conditioning on X, we simulate a number of synthetic datasets . In simulations, we chose h by directly minimizing ρ n (log(15/α), log(30/β), h). Note that we did not replace d n by d n in the above minimization to save computational cost. Such a choice of h is supported by our simulations, and denoted as h F S . Then, d n (log(15/α), h F S ) is used as the cutoff value for the testing procedure. Note that all constants in ρ n (M, L, h) such as ρ K , ζ K and c K only depend on h and the eigenvalues of the reproducing kernel operator, which can be well approximately by the empirical eigenvalues of the reproducing kernel matrix.
For simple hypothesis, we compare four testing procedures: (S1) The proposed T n,λ with the smoothing parameter h F S ; (S2) PLRT statistic P LRT (f 0 ) as described in Remark 3.2 with the same h F S ; (S3) The proposed T n,λ with h selected by GCV 2 , denoted as h GCV ; (S4) PLRT statistic P LRT (f 0 ) with the same h GCV .
The cut-off value for PLRT in S2 and S4 is obtained from Monte Carlo simulation and the null limit distribution given in [20], respectively. Simulation results are reported in Table 1. The rejection proportion (RP) under c = 0 reflects the Type I error, while under c = 0, RP reflects the power. Overall, all four procedures have comparable type I errors, i.e., c = 0, for any sample size. As for power performances, we note that (i) the test using h F S is always more powerful than that using h GCV ; (ii) T n,λ is always more powerful than PLRT given the same choice of h. In other words, S1 is always the most powerful one. The observation (i) justifies the finite sample advantage of the non-asymptotic formula in selecting h, while (ii) supports the need of removing estimation bias in nonparametric testing; see Remark 3.2. The third observation is that as c increases, h GCV continues decreasing and becomes closer to h F S , but never reaches h F S . This is consistent with their different asymptotic orders (recall h F S n −1/(2m+1/2) and h GCV n −1/(2m+1) ).  Table 1 Simulation results for simple hypothesis testing. hGCV is an average value over 500 replicates (that varies as c). RPF S , RPP LRT , RPGCV and RP GCV are average rejection proportions by T n,λ with hF S , PLRT with hF S , T n,λ with hGCV and PLRT with hGCV respectively, over 500 replicates.
For composite hypothesis, we compare two testing procedures:  Simulation results are reported in Table 2. We observe similar phenomena as in the simple testing case. In particular, C1 is uniformly more powerful than C2 due to the use of h com F S .
6. Proofs. In this section, we provide proofs of the main theorems in the paper. More technical details are provided in the supplementary material.
6.1. Preliminaries for penalized likelihood estimation. Before formal proofs, let us introduce some preliminaries. Considering model (2.1) parametrized by the unknown regression function f ∈ H m (1). The Fréchet derivative of the penalized loss function n,λ at g ∈ S m (I) can be identified as when operated on arbitrary function g 1 in S m (I). Let S λ (g) = E f {S n,λ (g)} be expectation of S n,λ (g), for any g ∈ S m (I). We denote the second-and third-order Fréchet derivatives of S λ by DS λ and D 2 S λ . By the optimality of the smoothing spline estimator f n λ , we have S n,λ ( f n,λ ) = 0. Therefore, S n,λ (f ) can be expressed as The Fréchet derivatives of S n,λ and DS n,λ are denoted DS n,λ (g)g 1 g 2 and D 2 S n,λ (g)g 1 g 2 g 3 . These derivatives can be explicitly written as We have the following concentration inequality for sum of iid elements {K X i : i = 1, . . . , n}, which plays a critical role in proving our large deviation bounds for the smoothing spline estimator. A proof is deferred to Section 6.5. Recall that G := {g ∈ S m (I) : Lemma 6.1. Suppose that ψ n,f (z; g) is a measurable function defined upon z = (y, x) ∈ Y × I and g ∈ G satisfying ψ n,f (z; 0) = 0 and the following Lipschitz continuity condition: for any f ∈ H m (1), i = 1, . . . , n and any g 1 , g 2 ∈ G, Then for any constant t ≥ 0 and n ≥ 1, where recall A(h) = A(h, 2) and 6.2. Proofs of large deviation bounds for smoothing spline estimates. Given the development in the previous subsection, we are now ready to prove the two large deviation bounds in Theorem 3.1 and Theorem 3.4.
Proof of Theorem 3.1. For any g, g 1 ∈ S m (I), we have the following sequence of identities, g 1 (X i )K X i − P λ g 1 , and D 2 S n,λ (g) = 0.
For any f ∈ S m (I), define f λ = f + S λ (f ). It follows from [20, Proposition 2.3] that DS λ (f ) = −id, where id denotes the identity operator. Then By using the property S λ (f λ ) = 0, we have the following bound Now we bound the two terms on the right hand side, respectively. To bound the first term, we apply Lemma 6.1, with ψ n,f (Z; g) = g/( If we let the event leading to the following bound for the first term To bound the second term, let Σ = [K(X i , X j )] 1≤i,j≤n and = ( 1 , . . . , n ) T . By the Hanson-Wright inequality (see, for example, [11]), we have where · F is the Frobenius norm. Since

Now if we let event
then we have P (E n ) ≥ 1 − exp(−M nhr 2 ), and on E n , the second term can be bounded as Putting pieces together, we obtain that with probability at least P (E n ∩E n ) ≥ 1−2 exp(−M nhr 2 ), Now let us consider the following class of operators, indexed by functions f in S m (I), as T f (g) = g + S n,λ (f λ + g), for all g ∈ S m (I).
By adding and subtracting the same term, we can express T f as By (6.4), we obtain that with probability at least 1 − 2 exp(−M nhr 2 ), for any g ∈ S m (I), where the last inequality follows by the condition c 2 K M 1/2 rh −1/2 A(h) ≤ 1/2. Since for any g 1 , g 2 ∈ S m (I), T f is a contraction mapping on B(r ). Therefore, by the contraction mapping theorem ( [19]), there exists g ∈ B(r ) such that S n,λ (f λ + g) = 0. Since the smoothing spline estimate f n,λ also satisfies S nλ ( f n,λ ) = 0, and the solution is unique, we must have f n,λ = f λ + g. Hence, inequality (6.5) yields f n,λ − f = g ≤ h m + r . Consequently, we obtain where δ n (M, r) = 2h m +c K ( √ 2M r+(nh) −1/2 ). This expression of δ n follows from Proof of Theorem 3.4. Given the development in the proof of Theorem 3.1, the proof for this theorem is easy. Let us define g n = f n,λ − f . Note that on E n ∩ E n Moreover, we have the identity 6.3. Proof of Theorem 3.5. We will make use of the following two lemmas that control the type I and type II errors of the test. Their proofs are provided in the supplement.
where ρ 2 K = hE[K 2 (X 1 , X 2 )] with X 1 , X 2 iid ∼ X, and the explicit form of the remainder term where the explicit form of the remainder term R 2,n (L) is provided in Section S.2. Now, we will prove the theorem. By applying Lemma 6.2, if we set M = log(15 α −1 ), then By using Lemma 6.3, we obtain where ζ K = sup g∈H m (1) λ −1 P λ g 2 and ρ n (M, L, h) is the solution to the equation: 6.4. Proof of Theorem 3.7. Similar to the simple hypothesis testing case, we make use of the following two lemmas that control the type I and type II errors of the composite test. Their proofs are provided in the supplement.
where the form of R c 2,n (L) is provided in Section S.2.
Now we prove the theorem. By applying Lemma 6.4, if we set M = log(24 α −1 ), then By using Lemma 6.5, we obtain where ζ K = sup g∈H m (1) λ −1 P λ g 2 and ρ com n (M, L, h) is the solution to the equation: 6.5. Proof of Lemma 6.1. For any f ∈ H m (1) and n ≥ 1, and any functions g 1 , g 2 ∈ G, we have the following bound for each additive component in the sum, For fixed g 1 , g 2 , we apply the bounded difference inequality (see, for example, Theorem 3.5 of [18]) to obtain the following concentration inequality for the sum, , for any t > 0. (6.9) Due to the equivalence between the sub-Gaussian tail of a random variable and its Orlicz norm (Lemma 8.1 in [13]), we obtain where · ψ 2 denotes the Orlicz norm associated with ψ 2 (s) ≡ exp(s 2 ) − 1. Let τ = √ log 1.5 ≈ 0.6368 and φ(M ) = ψ 2 (τ x). Then it is easy to check that φ(1) ≤ 1/2, and for any x, y ≥ 1, φ(M ) φ(y) ≤ φ(xy). By applying Lemma 8.2 in [13], we have the following relationship between the Orlicz norm of the max of l (l ∈ N) random variables and the max of their individual Orlicz norms, for any random variables ξ 1 , . . . , ξ l . Next we apply a "chaining" argument to prove the desired concentration inequality based on (6.9). Let T 0 ⊂ T 1 ⊂ T 2 ⊂ · · · ⊂ T ∞ ≡ G be a sequence of finite nested sets satisfying the following properties: (i). for any T j and any s, t ∈ T j , s − t sup ≥ ε2 −j ; each T j is "maximal" in the sense that if one adds any point in T j , then the inequality will fail; (ii). the cardinality of T j is upper bounded by where c 0 > 0 is absolute constant; Here we used the fact that the covering entropy of an R-ball in S m (I) relative to the sup-norm is of order R −1/m . (iii). each element t j+1 ∈ T j+1 is uniquely linked to an element t j ∈ T j which satisfies t j − t j+1 sup ≤ ε2 −j .
Based on this sequence {T k : k ≥ 0}, for arbitrary s k+1 , t k+1 ∈ T k+1 with s k+1 − t k+1 sup ≤ ε we can choose two chains (both of length k + 2) {t j : 0 ≤ j ≤ k + 1} and {s j : 0 ≤ j ≤ k + 1} with t j , s j ∈ T j for 0 ≤ j ≤ k + 1, such that the end points s 0 and t 0 satisfy Now, it follows from (6.10) that On the other hand, we have Combining these two bounds together, we obtain max s,t∈T k+1 s−t sup≤ε where in the last step we used the definition of A(h, ε). Now consider any two functions g 1 , g 2 ∈ G with g 1 − g 2 sup ≤ ε/2. For any k ≥ 2, since T k is "maximal" due to our construction, there must exist (s k , t k ) ∈ T 2 k such that max{ g 1 − s k sup , g 2 − t k sup } ≤ ε2 −k , which also implies s k − t k sup ≤ ε. Therefore, we can decompose the difference between Z n,f (g 1 ) and Z n,f (g 2 ) by

Now we can obtain
Taking ε = 2 in the above inequality, we obtain sup g 1 ,g 2 ∈G g 1 −g 2 sup≤1 Consequently, by choosing g 2 = 0 and using the equivalence between sub-Gaussian tails and the Orlicz norm (Lemma 8.1 in [13]), we obtain This completes the proof.

Supplementary document to Non-asymptotic Theory for Nonparametric Testing
In this supplement file, additional technical support is provided.
• Section S.1 provides Condition H that is used in Theorem 4.1.
• Section S.2 summarizes the remainder terms in Section 3.
• Section S.3 provides technical proofs of the lemmas in Section 6.3 in the main paper.
• Section S.4 provides technical proofs of the lemmas in Section 6.4 in the main paper.
• Section S.5 provides the proof of Theorem 4.1.
• Section S.6 provides the validity of the quadratic approximation of the PLRT test.
• Section S.7 provides a set of auxiliary results such as concentration inequalities.

S.1. Condition H. Condition H consists of:
is a known function of h given in .
S.2. Remainder terms. In this subsection, we summarize the remainder terms appeared in Section 3.
The following lemma provides large deviation bound for n −1 n i=1 i f (X i ) over f ∈ S m (I).
Lemma S.8. For any M ≥ 0, it holds that S.3.2. Proof of Lemma 6.2. Direct calculations yields that under H 0 , the remainder term in equation (3.8) is Then the claimed bound follows by applying Lemma S.6 and Lemma S.7 to the first term in equation (3.8) and using the bound in (S.2) with f = f 0 for the above remainder term (see the proof of Lemma 6.3 below).

S.3.3. Proof of Lemma 6.3. Direct calculations gives
First, we provide a non-asymptotic bound for the remainder term R n . By where remainder term with δ n (M, r) = 2h m + c K ( √ 2M r + (nh) −1/2 ) the "effective" estimation convergence rate. From an asymptotic perspective, this remainder term R 3,n (M ) corresponds to the higher-order errorconverging to zero faster than the estimation convergence rate δ n (M, (nh) −1/2 ).
Combining Lemma S.6, Lemma S.7 and inequality (S.1), we obtain the following large deviation bound for the remainder term R n , Next, we consider the leading term I n . Simple calculation suggests The first and the second terms in the stochastic component W n (E W n = 0) can be bounded by Lemma S.8 and Lemma 6.2, respectively, yielding  S.4. Proof of the lemmas in Section 6.4. In this subsection, we prove the two lemmas in Section 6.4 . We use P X to denote the marginal probability measure of the covariate {X i } n i=1 .
S.4.1. Proof of Lemma 6.4. By Cauchy-Schwarz inequality, we have Since ( α, β) T = (D T X D X ) −1 D T X , we can further derive that After simple calculations, it is easy to show that the largest eigenvalue λ X of matrix (D T X D X ) −1 is By Hanson-Wright inequality, the denominator D n satisfies for all M > 0. By Cauchy-Schwarz inequality, the numerator N n satisfies Combining the last two displays, we obtain for all M ≤ n/4. Combining the above display with inequality (S.4), we obtain that it holds with probability at least 1 − exp(−M ) that Moreover, since D X (D T X D X ) −1 D T X is a projection matrix with rank 2, we have, by Hanson-Wright inequality, that for any M > 0 Combining the last two displays, we obtain that for all M ≤ n/4 Finally, the claimed result is a direct sequence by applying Lemma S.6, Lemma S.7, equation (3.19) and equation (S.5) to the first four terms, and the bound (S.8) in the proof of Lemma 6.5 to the remainder term in decomposition (3.19).
Next, we consider the leading term I c n . Simple calculation suggests Similar to the proof of Lemma 6.3, we have the following tail bound for W c 1,n , Combining (S.7), Lemma S.9 and Lemma 6.2, we obtain the following tail bound for W c 2,n ,  T 1f (g) = g + S λ (f + g), g ∈ S m (I).
For i = 1, . . . , n, let By direct calculations, it can be shown that where the second last inequality follows by Assumption A2, i.e., E{sup |a|≤1 | (3) (η + a)|} ≤ C 0 C 1 , and the last inequality follows by condition h m−1/2 < σ 2 /(4c K C 0 C 1 ). Therefore, it can be shown by f λ − f sup ≤ 1/3 that Using Cauchy-Schwartz inequality, Let δ = hr n /(4C 0 c K ). Recall that h 1/2 r n ≤ 1 which implies δ ≤ (4C 0 c K h −1/2 ) −1 . Therefore, E{exp(δ R i )} ≤ C 1 exp ( It follows by Theorem 3.2 of [18] that, for We note that the right hand side in the above inequality does not depend on f . It is easy to see It follows by Lemma 6.1 that n,f (g) ≤ M nhr 2 n A(h)}. For any g ∈ S m (I)\{0}, letḡ = g/d n , where d n = c K h −1/2 g . It is easy to see that Therefore,ḡ ∈ G. Consequently, on E n,3 , for any g ∈ S m (I)\{0}, we get Z n,f (ḡ) ≤ M nhr 2 n A(h), which leads to that Note that the above inequality also holds for g = 0.
Therefore, for any f ∈ H m (1), on E n , T 2f is a contraction mapping from B(r 2n ) to itself. By contraction mapping theorem, there exists uniquely an element g ∈ B(r 2n ) s.t. T 2f (g ) = g . Let f n,λ = f λ + g . Then on E n , f n,λ − f ≤ f λ − f + f n,λ − f λ ≤ r 1n + r 2n = 2bh m + 6L(M )r n . The desired conclusion follows by the trivial fact: sup f ∈H m (1) P n f (E c n ) ≤ (2C 1 + 4) exp(−M nhr 2 n ). Proof of (i) is completed.
Define ψ n,f (Z i ; g) = (2) (η i )g(X i )c −1 K h 1/2 C 0 (M nhr 2 n + log n) where A i is defined in (i). Then it is easy to see that for any g 1 , g 2 ∈ G, It follows by Lemma 6.1 that sup f ∈H m (1) P n f (E c n,5 ) ≤ 2 exp(−M nhr 2 n ), where E n,5 = {sup g∈G Z