{'fraction_non_alphanumeric': 0.04824274175944117, 'fraction_numerical': 0.018882340100414757, 'mean_word_length': 4.101893095768374, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A divergence formula for regularization methods with an L2 constraint

We derive a divergence formula for a group of regularization methods with an L2 constraint. The formula is useful for regularization parameter selection, because it provides an unbiased estimate for the number of degrees of freedom. We begin with deriving the formula for smoothing splines and then extend it to other settings such as penalized splines, ridge regression, and functional linear regression.


Introduction
A variety of regularization methods have been proposed in modern statistics (Hastie et al., 2009). Usually, the regularization is controlled by a tuning parameter, and it is crucial to select an appropriate value of the tuning parameter. Many criteria have been discussed for tuning parameter selection (Hastie et al., 2009). Some of these criteria, including AIC (Akaike, 1973), GCV (Graven and Wahba, 1979), and BIC (Schwarz, 1978), depend on estimating the number of degrees of freedom, which measures the model complexity.
Here we consider the problem of estimating the number of degrees of freedom for a group of regularization methods, the ones with an l 2 constraints. We derive a divergence formula, which provides an unbiased estimate for the number of degrees of freedom (Stein, 1981;Ye, 1998;Efron, 2004). To understand our goal, we take smoothing slines as an example.
Smoothing splines are a popular approach to nonparametric function estimation (Wahba, 1990). Given observations where x i ∈ [0, 1] and i ∼ N (0, σ 2 ), one is to estimate f (x). Assume that f (x) is smooth in the sense that its second derivative exists and is small. The smoothing splines approach to the estimation of f (x) is through minimizing where the penalty parameter λ controls the tradeoff between the lack of fit and the roughness of the function estimation. An alternative derivation is through minimizing where ρ is called the constraint parameter. The solution to (3) usually falls on the boundary of the constraint, and by the Lagrange method, these two formulations are equivalent up to the choice of λ and ρ. Gu (1998) pointed out that the mapping from ρ to λ is one-to-one but changes with the least squares functional, n i=1 (y i − f (x i )) 2 . In the literature, it is well-known that the divergence in terms of λ is equal to the trace of the "hat" matrix (e.g., Hastie and Tibshirani, 1990). However, the divergence formula in terms of ρ is still not available. Because of the importance of tuning parameter selection, it is worth deriving this formula.
The remaining of the manuscript is organized as follows. In Section 2, the divergence formula in terms of ρ is derived for smoothing splines. In Section 3, the result is extended to some other settings. In Section 4, the two divergence formulas for smoothing splines, in terms of λ and ρ respectively, are compared through a simulation study. Some discussion is in Section 5 and technical proof is in Appendix.

Definition
We start with reviewing the definition of degrees of freedom. In ordinary linear regression, the degrees of freedom simply count the number of parameters. There are some generalizations of the degrees of freedom, including Stein's unbiased risk estimate in Stein (1981), the generalized degrees of freedom in Ye (1998), and the covariance penalty in Efron (2004).
Because the definitions are similar for both λ and ρ, we use θ for the smoothing parameter, which could be either λ or ρ. Let f θ (·) be the solution to either (2) or (3) for a given θ, and Assume that y 0 i is a new response generated from the same mechanism that generates y i . By arguments in Efron (2004), we obtain a decomposition of the prediction error, where is called the divergence in terms of θ (either λ or ρ) in Kato (2009), and its expectation is defined as the degrees of freedom in terms of θ (either λ or ρ). Clearly the divergence is an unbiased estimate of the degrees of freedom.

The divergence in terms of λ
Since the solution to (2) is natural splines (Wahba, 1990), it can be written as where d = n in smoothing splines approach (d could be different from n in other settings), and {N j (x)} is an n-dimensional set of basis functions for representing this family of cubic natural splines. Then the regularization problem (2) becomes where y = (y 1 , · · · , y n ) . β = (β 1 , · · · , β d ) , The "hat" matrix H(λ) = N(N N + λΩ N ) −1 N y, and the divergence in terms of λ is well-known to be equal to the trace of it (Hastie and Tibshirani, 1990), that is,

The divergence in terms of ρ
To develop the divergence in terms of ρ, we rely on the Demmler-Reinsch algorithm used in Eubank (1988). The algorithm can also speed up the computation of div(λ).
where N is n × d. Let U be orthogonal and C be diagonal such that UCU = BΩ N B .
where r is the rank of C, and c 1 ≥ c 2 ≥ · · · ≥ c r are the non-zero diagonal elements of C.
Up to the choice of λ and ρ, the problem (8) is equivalent to Because β Ω N β = γ Cγ, the problem (10) becomes Let γ(ρ) = ( γ 1 , · · · , γ d ) be the solution to the problem (11) with constraint ρ and γ 0 be the solution to the problem without constraint. By some tedious arguments in Appendix, we derive the following divergence formula in terms of ρ.

Some extensions
The formula in the theorem can be extended to many other settings; for example, penalized splines, ridge regression, and functional linear regression. For these settings, div(λ) is equal to the trace of the corresponding hat matrix.

Penalized splines
Penalized splines approach was proposed by Eilers and Marx (1996) to estimate f (x) in (1).
For fixed order p and knots κ 1 < · · · < κ K , penalized splines approach finds a function of An advantage of penalized splines over smoothing splines is that K is much smaller than n.
Ruppert (2002) claimed that the choice of K is not important as long as it is large enough.
To apply the theorem to derive div(ρ) in penalized splines, let N be an n × (p + K) matrix with the ith row being (1,

For the functional linear regression, Yuan and Cai (2010) developed a reproducing kernel
Hilbert space (RKHS) approach. They showed that the solution to (15) can be written as wherex(s) = x i (s)/n and K(t, s) is a kernel function. Let Σ be an n × n matrix where , and c = (c 1 , · · · , c n ) . Then problem (15)  To apply the theorem to derive div(ρ) in functional linear regression, let the QR decom- is orthogonal and R is upper triangular, with T Q 2 = 0. Since T c = 0, c must be in the column space of Q 2 , giving c = Q 2 η for some η an n − 2 vector. Therefore, to apply the theorem, let N be replaced by n × n matrix (ΣQ 2 : T) and let Ω N be replaced by n × n matrix diag(0, Σ).
First, we compare the convergence formulae in terms of λ and ρ respectively. For each replicate, at each λ in the grid, f (x) was calculated, the corresponding ρ is calculated, and then div(λ) and div(ρ) are calculated through (9) and (12) respectively. For the first 10 replicates, the divergences are summarized in Figure 1. In the left panel, the curves of div(λ) against λ (they are identical) are drawn in red and the curves of div(ρ) against λ are drawn in blue. In the right panel, the curves of div(λ) against ρ are drawn in red and the curves of div(ρ) against ρ are drawn in blue. Further, as an application, the divergence formulas of λ and ρ can be used in construction of smoothing parameter selection criteria such as GCV and AIC. Again, because the criteria are commonly defined for both λ and ρ, we use notation θ, which could be either λ or ρ. Let Another effective smoothing parameter selection criterion is Generalized Cross-Validation (GCV; Craven and Wahba (1979)), We compare the performances of AIC and GCV in terms of λ and ρ. Following Caution 1 in Gu (1998), we consider the risk function indexed in terms of ρ, where the expectation is with respect to i . By Caution 1, the risk function indexed in terms of λ is meaningless because model index λ is data-specific. The comparison is based on the following relative error in Hastie et al. (2009, p.241), .
We should explain ρ in the above formula. If AIC(ρ) is applied, ρ = arg min ρ AIC(ρ). If AIC(λ) is applied, ρ is defined as the counterpart of λ = arg min λ AIC(λ). Similar ρ is defined for GCV. The results are summarized in Figure 2. It is found that the performances of criteria in terms of ρ are almost the same as those in terms of λ. This finding supports the correctness of the derived formula. For regularization methods with an l 1 penalty, the divergence formula (in terms of λ, if adopt our notation) was derived in Zou et al. (2007). For regularization methods with an l 1 constraint, the divergence formula (in terms of ρ, if adopt our notation) was derived in Kato (2009). This manuscript considers the divergence formula for the l 2 regularization, which appears ahead of the l 1 regularization.
Although the divergence formula (in terms of λ) for regularization methods with an l 2 penalty has been existing long ago, the divergence formula (in terms of ρ) for regularization methods with an l 2 is still not available in the literature. Now this missing formula is derived.