Sylvain Arlot
email: sylvain.arlot@ens.fr

Francis Bach
email: francis.bach@ens.fr

Data-driven calibration of linear estimators with minimal penalties

This paper tackles the problem of selecting among several linear estimators in nonparametric regression; this includes model selection for linear regression, the choice of a regularization parameter in kernel ridge regression, spline smoothing or locally weighted regression, and the choice of a kernel in multiple kernel learning. We propose a new algorithm which first estimates consistently the variance of the noise, based upon the concept of minimal penalty, which was previously introduced in the context of model selection. Then, plugging our variance estimate in Mallows' C L penalty is proved to lead to an algorithm satisfying an oracle inequality. Simulation experiments with kernel ridge regression and multiple kernel learning show that the proposed algorithm often improves significantly existing calibration procedures such as generalized cross-validation.

Introduction

Smoothing splines or kernel-based methods are now well-established tools for supervised learning, allowing to perform various tasks, such as regression or binary classification, with linear and nonlinear predictors [START_REF] Shawe-Taylor | Kernel Methods for Pattern Analysis[END_REF][START_REF] Schölkopf | Learning with Kernels[END_REF]. A central issue common to all regularization frameworks is the choice of the regularization parameter: while most practitioners use cross-validation procedures to select such a parameter, data-driven procedures not based on cross-validation are rarely used. The choice of the kernel, a seemingly unrelated issue, is also important for good predictive performance: several techniques exist, either based on cross-validation, Gaussian processes or multiple kernel learning [START_REF] Chapelle | Model selection for support vector machines[END_REF][START_REF] Rasmussen | Gaussian Processes for Machine Learning[END_REF][START_REF] Bach | Consistency of the group Lasso and multiple kernel learning[END_REF].

In this paper, we consider least-squares regression and cast these two problems as the problem of selecting among several linear estimators, where the goal is to choose an estimator with a quadratic risk which is as small as possible. As shown in Section 2, this problem includes for instance model selection for linear regression, the choice of a regularization parameter in kernel ridge regression, spline smoothing, or locally weighted regression, the choice of a kernel in multiple kernel learning, the choice of k in k-nearest-neighbors regression, and the choice of a bandwidth of Nadaraya-Watson estimators.

Another motivation for studying linear estimators is their good theoretical properties. For instance, when the signal belongs to a Sobolev ball, it is known the Pinsker estimator (which is linear) is asymptotically minimax up to the optimal constant, while the best projection estimator is only rate-minimax [START_REF] Efromovich | Sharp-optimal and adaptive estimation for heteroscedastic nonparametric regression[END_REF][START_REF] Alexandre | Introduction to nonparametric estimation[END_REF]. Furthermore, the set of signals that are well estimated by linear estimators is very rich: it contains, for instance, sampled smooth functions, sampled modulated smooth functions and sampled harmonic functions [START_REF] Juditsky | Nonparametric denoising of signals with unknown local structure. I. Oracle inequalities[END_REF]. Finally, convergence rates of some linear spectral estimators have recently been proved optimal [START_REF] Caponnetto | Optimal rates for the regularized least-squares algorithm[END_REF][START_REF] Bauer | On regularization algorithms in learning theory[END_REF].

The main contribution of the paper is to extend the notion of minimal penalty [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF][START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF] presented in Section 2 to all discrete classes of linear operators, and to use it for defining a fully data-driven selection algorithm satisfying a non-asymptotic oracle inequality. Our new theoretical results presented in Section 4 extend similar results which were limited to unregularized least-squares regression (i.e., projection operators). We also tackle continuously parameterized families of linear estimators which are typical in ridge regression and spline smoothing (where the onedimensional parameter to be estimated is the regularization parameter). In order to do, we derive novel concentration inequalities which may be useful in other contexts (Section B). Our results also enlighten the classical elbow heuristics based algorithms-e.g., "L-curve maximum curvature criterion" for Tikhonov [START_REF] Rezghi | A new variant of L-curve for Tikhonov regularization[END_REF] and several others regularization problems [START_REF] Per | The use of the L-curve in the regularization of discrete ill-posed problems[END_REF][START_REF] Grodzevich | Regularization using a parameterized trust region subproblem[END_REF])-by providing theoretical grounds to another L-curve based calibration algorithm. Finally, in Section 5, we show that our algorithm improves the performances of classical selection procedures, such as GCV [START_REF] Craven | Smoothing noisy data with spline functions. Estimating the correct degree of smoothing by the method of generalized cross-validation[END_REF], for kernel ridge regression, nearest-neighbor regression or locally weighted regression.

Linear estimators

In this section, we define the problem we aim to solve and give several examples of linear estimators.

Framework and notation

Let us assume that one observes

Y i = f (x i ) + ε i ∈ R for i = 1, . . . , n ,
where ε 1 , . . . , ε n are i.i.d. centered random variables with E[ε 2 i ] = σ 2 unknown, f is an unknown measurable function X → R and x 1 , . . . , x n ∈ X are deterministic design points. No assumption is made on the set X . The goal is to reconstruct the signal F = (f (x i )) 1≤i≤n ∈ R n , with some estimator F ∈ R n , depending only on (x 1 , Y 1 ), . . . , (x n , Y n ) , and having a small quadratic risk n -1 F -F 2 2 , where ∀t ∈ R n , we denote by t 2 the ℓ 2 -norm of t , defined as t 2 2 := n i=1 t 2 i . In this paper, we focus on linear estimators F that can be written as a linear function of Y = (Y 1 , . . . , Y n ) ∈ R n , that is, F = AY , for some (deterministic) n × n matrix A . Here and in the rest of the paper, vectors such as Y or F are assumed to be column-vectors. We present in Section 2.2 several important families of estimators of this form. The matrix A may depend on x 1 , . . . , x n (which are known and deterministic), but not on Y , and may be parameterized by certain quantities-usually regularization parameter or kernel combination weights.

Let us also define, for any matrix A ∈ M n (R) , the largest singular value of A:

|||A||| := sup t∈R n , t =0 At 2 t 2 .

Examples of linear estimators

In this paper, our theoretical results apply to matrices A such that

A ∈ M n (R) |||A||| ≤ M tr(A ⊤ A) ≤ (2 -K df ) tr(A) with K df ∈ (0, 2) , (1)
for some constants M and K df .

The main examples we have in mind are the following.

Ordinary least-squares regression / model selection. If we consider linear predictors (here, linear in the inputs x 1 , . . . , x n ) from a design matrix X ∈ R n×p , then F = AY with A = X(X ⊤ X) -1 X ⊤ , which is a projection matrix (i.e., A ⊤ A = A); F = AY is often called a projection estimator. In the variable selection setting, one wants to select a subset J ⊂ {1, . . . , p} , and matrices A are parameterized by J . If we denote X J the matrix of size n × |J| composed of the columns of X indexed by J, then the matrix A J is equal to X J (X ⊤ J X J ) -1 X ⊤ J . For this matrix, we have tr A ⊤ J A J = tr A 2 J = tr A J .

Kernel ridge regression / spline smoothing. We assume that a positive definite kernel k : X × X → R is given, and we are looking for a function f : X → R in the associated reproducing kernel Hilbert space (RKHS) F , with norm • F . If K denotes the n × n kernel matrix, defined by K ab = k(x a , x b ) , then the ridge regression estimator-a.k.a. spline smoothing estimator for spline kernels [START_REF] Wahba | Spline Models for Observational Data[END_REF], or Tikhonov regularization [START_REF] Tikhonov | Methods for the regularization of ill-posed problems[END_REF]-is obtained by minimizing with respect to f ∈ F [START_REF] Schölkopf | Learning with Kernels[END_REF]:

1 n n i=1 (Y i -f (x i )) 2 + λ f 2 F .
The unique solution is equal to f = n i=1 α i k(•, x i ) , where α = (K + nλI) -1 Y . This leads to the smoothing matrix A λ = K(K + nλI n ) -1 , parameterized by the regularization parameter λ ∈ R + . In this case, A is symmetric positive semi-definite, and we have tr A 2 tr A.

Multiple kernel learning / Group Lasso / Lasso. We now assume that we have p different kernels k j , feature spaces F j and feature maps Φ j : X → F j , j = 1, . . . , p . The group Lasso [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF] and multiple kernel learning [START_REF] Lanckriet | Learning the kernel matrix with semidefinite programming[END_REF][START_REF] Bach | Consistency of the group Lasso and multiple kernel learning[END_REF] frameworks consider the following objective function

J(f 1 , . . . , f p ) = 1 n n i=1 y i -p j=1 f j , Φ j (x i ) 2 + 2λ p j=1 f j F j = L(f 1 , . . . , f p ) + 2λ p j=1 f j F j .
Note that when Φ j (x) is simply the j-th coordinate of x ∈ R p , we get back the penalization by the ℓ 1 -norm and thus the regular Lasso [START_REF] Tibshirani | Regression shrinkage and selection via the Lasso[END_REF]. Following [START_REF] Pontil | Multi-task feature learning[END_REF][START_REF] Rakotomamonjy | SimpleMKL[END_REF], by using a 1/2 = min b 0 1 2 { a b + b} , we obtain a variational formulation of the sum of norms 2 p j=1 f j = min η∈R p + p j=1 f j 2 η j + η j . Thus, minimizing J(f 1 , . . . , f p ) with respect to (f 1 , . . . , f p ) is equivalent to minimizing with respect to η ∈ R p + (see [START_REF] Bach | Consistency of the group Lasso and multiple kernel learning[END_REF] for more details):

min f 1 ,...,fp L(f 1 , . . . , f p ) + λ p j=1 f j 2 η j + λ p j=1 η j = 1 n y ⊤ p j=1 η j K j + nλI n -1 y + λ p j=1 η j ,
where I n is the n × n identity matrix. Moreover, given η , this leads to a smoothing matrix of the form

A η,λ = ( p j=1 η j K j )( p j=1 η j K j + nλI n ) -1 , (2)
Method

A parameter Ridge regression K(K + λI) -1 λ Kernel learning K(K + I) -1 K Nadaraya-Watson W Diag(W 1) -1 α where W ij = exp(-α x i -x j 2 ) Nearest-neighbor A ∈ {0, 1/k} N ×N k Table 1: Examples of linear estimators.
parameterized by the regularization parameter λ ∈ R + and the kernel combinations in R p + -note that it depends only on λ -1 η , which can be grouped in a single parameter in R p + . Note that it corresponds to a specific parameterization of the kernel matrix K using η, and that it can be extended to other types of parameterization.

Thus, the Lasso/group lasso can be seen as particular (convex) ways of optimizing over η . In this paper, we propose a non-convex alternative with better statistical properties (oracle inequality in Theorem 3). Note that in our setting, finding the solution of the problem is hard in general since the optimization is not convex. However, while the model selection problem is by nature combinatorial, our optimization problems for multiple kernels are all differentiable and are thus amenable to gradient descent procedures-which only find local optima.

Nearest-neighbor regression. If we assume that we are given any similarity measure d : X ×X → R and k a strictly positive integer, then, from n observations x 1 , . . . , x n , we may for each i = 1, . . . , n, find k-nearest neighbors of x i , i.e., find any set J i of k points x j , j ∈ {1, . . . , n}\{k}, which are among the k closest to x i according to d (this definition takes into account possible ties). We can then build an n × n matrix A of nearest neighbors which is equal to 1/k for all pairs (i, j) such that j ∈ J i for all i ∈ {1, . . . , n}, and equal to zero otherwise.

Nadaraya-Watson estimators [START_REF] Nadaraya | On estimating regression[END_REF][START_REF] Watson | Smooth regression analysis[END_REF]. We know assume that we are given a "window function" (not to be confused with a positive definite kernel) k : X × X → R + , from which we build the n × n matrix W of pairwise evaluations. The estimator correspond to the matrix A obtained by normalizing W to have unit row-sums, i.e., A = W D -1 , where D = Diag(W 1) is the diagonal matrix of row sums. In this situation we have M ≤ max i D ii / min i D ii . A typical example is the matrix W defined as W ij = exp(-α x ix j

2 ) where x i , i = 1, . . . , n, are the observed input data points, and α is the smoothing parameter to be learned.

Except for the bound on |||A||| in the k-nearest neighbor and Nadaraya-Watson examples, Eq. (1) holds true with M = 1 and K df = 1 for all the examples mentioned, as shown by the following result.

Proposition 1. For any n ≥ 1 , tr(A ⊤ A) ≤ tr(A) ≤ n for any matrix A ∈ M n (R) among the following examples: (i) if A is symmetric with Sp(A) ⊂ [0, 1] , for instance:
(ia) Ordinary least-squares regression: A is an orthogonal projection matrix.

(ib) Kernel ridge regression, Multiple kernel learning: ∃x ∈ (0, +∞) and

K ∈ M n (R) symmetric positive semi-definite such that A = K(K + xI) -1 . (ii) if ∀i, j , A i,i ≥ A i,j ≥ 0 and n k=1 A i,k = 1 , for instance: (iia) Nadaraya-Watson regression (iib) k-nearest-neighbor regression, for some integer k ∈ [1, n] :            ∀1 ≤ i, j ≤ n , A i,j ∈ 0, 1 k with k ∈ { 1, . . . , n } ∀1 ≤ i ≤ n , A i,i = 1 k and n j=1
A i,j = 1 .

(kNN)

In example (i), |||A||| ≤ 1. In examples (ia) and (iib), tr(A) = tr(A ⊤ A) .

Proposition 1 is proved in Section C.

Other examples. Alternative linear estimators are classical in the statistical or learning literature:

• Pinsker filters [START_REF] Pinsker | Optimal filtration of square-integrable signals in Gaussian noise[END_REF][START_REF] Efromovich | Sharp-optimal and adaptive estimation for heteroscedastic nonparametric regression[END_REF], that is,

A w,α = diag ( (1 -(k α /w)) + , k = 1 . . . n
) for some parameters w, α > 0. This example matches case (i) in Proposition 1.

• Linear spectral methods for statistical inverse problems [START_REF] Bissantz | Convergence rates of general regularization methods for statistical inverse problems and applications[END_REF][START_REF] Lo Gerfo | Spectral algorithms for supervised learning[END_REF], such as spectral cut-off (or principal components regression) and ℓ 2 -boosting.

• Symmetrized k-nearest neighbors [START_REF] Yang | Linear functions of concomitants of order statistics with application to nonparametric estimation of a regression function[END_REF].

More examples and references can be found in [START_REF] Wasserman | All of nonparametric statistics[END_REF]Chapter 5] and [START_REF] Alexandre | Introduction to nonparametric estimation[END_REF]Chapter 3], for instance.

Linear estimator selection

In this section, we first describe the statistical framework of linear estimator selection, then introduce the notion of minimal penalty. Finally, we briefly review the related work on linear estimator selection.

Unbiased risk estimation heuristics

Usually, several estimators of the form F = AY can be used. The problem that we consider in this paper is then to select one of them, that is, to choose a matrix A . Let us assume that a family of matrices (A λ ) λ∈Λ is given (examples are shown in Section 2.2), hence a family of estimators ( F λ ) λ∈Λ can be used, with F λ := A λ Y . The goal is to choose from data some λ ∈ Λ , so that the quadratic risk of F λ is as small as possible.

The best choice would be the oracle:

λ ⋆ ∈ arg min λ∈Λ n -1 F λ -F 2 2 ,
which cannot be used since it depends on the unknown signal F . Therefore, the goal is to define a data-driven λ satisfying an oracle inequality of the form

n -1 F λ -F 2 2 ≤ C n inf λ∈Λ n -1 F λ -F 2 2 + R n , (3)
with large probability, where the leading constant C n should be close to 1 (at least for large n) and the remainder term R n should be negligible compared to the risk of the oracle. Many classical selection methods are built upon the "unbiased risk estimation" heuristics: If λ minimizes a criterion crit(λ) such that

∀λ ∈ Λ , E [ crit(λ) ] ≈ E n -1 F λ -F 2 2
, then λ satisfies an oracle inequality such as in Eq. ( 3) with large probability. For instance, crossvalidation [START_REF] Allen | The relationship between variable selection and data augmentation and a method for prediction[END_REF][START_REF] Stone | Cross-validatory choice and assessment of statistical predictions[END_REF] and generalized cross-validation (GCV) [START_REF] Craven | Smoothing noisy data with spline functions. Estimating the correct degree of smoothing by the method of generalized cross-validation[END_REF] are built upon this heuristics. One way of implementing this heuristics is penalization, which consists in minimizing the sum of the empirical risk and a penalty term, i.e., using a criterion of the form:

crit(λ) = n -1 F λ -Y 2 2 + pen(λ) .
The unbiased risk estimation heuristics, also called Mallows' heuristics, then leads to the optimal (deterministic) penalty

pen id (λ) := E n -1 F λ -F 2 2 -E n -1 F λ -Y 2 2 .
When F λ = A λ Y , we have:

F λ -F 2 2 = (A λ -I n )F 2 2 + A λ ε 2 2 + 2 A λ ε, (A λ -I n )F , (4)
F λ -Y 2 2 = F λ -F 2 2 + ε 2 2 -2 ε, A λ ε + 2 ε, (I n -A λ )F , (5)
where ε = Y -F ∈ R n and ∀t, u ∈ R n , t, u = n i=1 t i u i . Since ε is centered with covariance matrix σ 2 I n , Eq. ( 4) and Eq. ( 5) imply that

pen id (λ) = 2σ 2 tr(A λ ) n , (6)
up to the term -E[n -1 ε 2 2 ] = -σ 2 , which can be dropped off since it does not vary with λ . Note that df(λ) = tr(A λ ) is called the effective dimensionality or degrees of freedom [START_REF] Zhang | Learning bounds for kernel regression using effective data dimensionality[END_REF], so that the optimal penalty in Eq. ( 6) is proportional to the dimensionality associated with the matrix A λ -for projection matrices, we get back the dimension of the subspace, which is classical in model selection.

The expression of the optimal penalty in Eq. ( 6) led to several selection procedures, in particular Mallows' C L (called C p in the case of projection estimators) [START_REF] Mallows | Some comments on C p[END_REF], where σ 2 is replaced by some estimator σ 2 . The estimator of σ 2 usually used with C L is based upon the value of the empirical risk at some λ 0 with df(λ 0 ) large; it has the drawback of overestimating the risk, in a way which depends on λ 0 and F [START_REF] Efron | How biased is the apparent error rate of a prediction rule?[END_REF]. GCV, which implicitly estimates σ 2 , has the drawback of overfitting if the family (A λ ) λ∈Λ contains a matrix too close to I n [START_REF] Cao | On oracle inequalities related to smoothing splines[END_REF], so that examples have been given where GCV is not asymptotically optimal [START_REF] Li | Asymptotic optimality of C L and generalized cross-validation in ridge regression with application to spline smoothing[END_REF]; GCV also overestimates the risk even more than C L for most A λ (see (7.9) and Table 4 in [START_REF] Efron | How biased is the apparent error rate of a prediction rule?[END_REF]).

In this paper, we define an estimator of σ 2 directly related to the selection task which does not have similar drawbacks. Our estimator relies on the concept of minimal penalty, introduced by Birgé and Massart [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF] and further studied in [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF].

Minimal and optimal penalties

We deduce from Eq. (4) the bias-variance decomposition of the risk: and from Eq. ( 5) the expectation of the empirical risk:

E n -1 F λ -F 2 2 = n -1 (A λ -I n )F 2 2 + tr(A ⊤ λ A λ )σ 2 n = bias + variance , (7)
E n -1 F λ -Y 2 2 -ε 2 2 = n -1 (A λ -I n )F 2 2 - 2 tr(A λ ) -tr(A ⊤ λ A λ ) σ 2 n . (8)
Note that the variance term in Eq. ( 7) is not proportional to the effective dimensionality df(λ) = tr(A λ ) but to tr(A ⊤ λ A λ ) . Although several papers argue these terms are of the same order (for instance, they are equal when A λ is a projection matrix), this may not hold in general. If Eq. ( 1) holds for all matrices A ∈ { A λ } λ∈Λ , we only have

0 ≤ tr(A ⊤ λ A λ ) 2 -K df ≤ tr(A λ ) ≤ 2 tr(A λ ) -tr(A ⊤ λ A λ ) K df ≤ 2 tr(A λ ) K df . (9)
In order to give a first intuitive interpretation of Eq. ( 7) and Eq. ( 8), let us consider the kernel ridge regression example, where A = K(K + λI) -1 , and assume that the risk and the empirical risk behave as their expectations in Eq. [START_REF] Baraud | Estimator selection in the gaussian setting[END_REF] and Eq. [START_REF] Bauer | On regularization algorithms in learning theory[END_REF]; see also Fig. 1. Completely rigorous arguments based upon concentration inequalities are developed in the Appendix and summarized in Section 4, leading to the same conclusions as the present informal reasoning.

First, as proved by Lemma 2 in Section B.2, the bias n -1 (A λ -I n )F 2 2 is a non-increasing function of the dimensionality df(λ) = tr(A λ ) , and the variance tr(A ⊤ λ A λ )σ 2 n -1 is an increasing function of df(λ) , as well as 2 tr(A λ )-tr(A ⊤ λ A λ ) . Therefore, Eq. [START_REF] Baraud | Estimator selection in the gaussian setting[END_REF] shows that the optimal λ realizes the best trade-off between bias (which decreases with df(λ)) and variance (which increases with df(λ)), which is a classical fact in model selection (see Figure 1).

Second, the expectation of the empirical risk in Eq. ( 8) can be decomposed into the bias and a negative variance term which is the opposite of

pen min (λ) := n -1 2 tr(A λ ) -tr(A ⊤ λ A λ ) σ 2 . ( 10
)
As suggested by the notation pen min , we will show it is a minimal penalty in the following sense.

If ∀D ≥ 0, λ min (D) ∈ arg min λ∈Λ n -1 F λ -Y 2 2 + D pen min (λ) ,
then, up to concentration inequalities that are detailed in Section 4.4, λ min (D) behaves like a minimizer of

g D (λ) = E n -1 F λ -Y 2 2 + D pen min (λ) -σ 2 = n -1 (A λ -I n )F 2 2 + (D -1) pen min (λ) .
Therefore, two main cases can be distinguished:

• if D < 1 , then g D (λ)
decreases with df(λ) so that df( λ min (D)) is huge: λ min (D) overfits.

• if D > 1 , then g D (λ) increases with df(λ) when df(λ) is large enough, so that df( λ min (D)) is much smaller than when D < 1 .

As a conclusion, pen min (λ) is the minimal amount of penalization needed so that a minimizer λ of a penalized criterion is not clearly overfitting. Following an idea first proposed in [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF] and further analyzed or used in several other papers such as [START_REF] Lebarbier | Detecting multiple change-points in the mean of a gaussian process by model selection[END_REF][START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF][START_REF] Maugis | Slope heuristics for variable selection and clustering via gaussian mixtures[END_REF], we now propose to use that pen min (λ) is a minimal penalty for estimating σ 2 and plug this estimator into Eq. ( 6). Indeed, if we penalize the empirical risk n

-1 F λ -Y 2 2 by C pen min (λ) σ 2
(which does not depend on σ 2 ), then the argument above suggests that around the value D = Cσ -2 = 1 (i.e., around C = σ 2 ), we have a jump in the selected degrees of freedom. This leads to the algorithm described in Section 4.1.

Note that the minimal penalty given by Eq. ( 10) is new; it generalizes previous results [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF][START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF] where pen min (A λ ) = n -1 tr(A λ )σ 2 because all A λ were assumed to be projection matrices, i.e., A ⊤ λ A λ = A λ . Furthermore, our results generalize the slope heuristics pen id ≈ 2 pen min (only valid for projection estimators [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF][START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF]) to general linear estimators for which pen id / pen min ∈ (1, 2] .

Related work

Several procedures have been proposed in the literature for selecting among linear estimators. The most classical ones are Mallows' C L [START_REF] Mallows | Some comments on C p[END_REF] and GCV [START_REF] Craven | Smoothing noisy data with spline functions. Estimating the correct degree of smoothing by the method of generalized cross-validation[END_REF] (which have already been introduced) and cross-validation (see [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF] for references).

Recently, Baraud, Giraud and Huet [START_REF] Baraud | Estimator selection in the gaussian setting[END_REF] proposed an estimator selection procedure via penalization, that applies in particular to linear estimator selection; a possible drawback of their procedure is that it strongly assumes the noise is Gaussian, since the Gaussian distribution explicitly appears in the definition of their penalty. Two penalized maximum likelihood criteria have also been proposed for selecting the ridge regression parameter [START_REF] Ngoc | Penalized maximum likelihood principle for choosing ridge parameter[END_REF], but they are only supported by simulation experiments.

Finally, let us mention here an aggregation procedure recently proposed by Dalalyan and Salmon [START_REF] Dalalyan | Sharp oracle inequalities for aggregation of affine estimators[END_REF] for affine estimators. Their goal is different from ours (aggregating instead of selecting), but still related since they prove some oracle inequalities for their final estimator.

Main results

In this section, we first describe our algorithm and then present our theoretical results.

Algorithm

The following algorithm first computes an estimator of C of σ 2 using the minimal penalty in Eq. ( 10), then considers the optimal penalty in Eq. ( 6) for selecting λ .

Input: Y ∈ R n and { A λ } λ∈Λ a collection of matrices 1. ∀C > 0 , compute λ 0 (C) ∈ arg min λ∈Λ { F λ -Y 2 2 + C 2 tr(A λ ) -tr(A ⊤ λ A λ ) } . 2. Find C such that df( λ 0 ( C)) ∈ [ n/10, n/3 ] . 3. Select λ ∈ arg min λ∈Λ { F λ -Y 2 2 + 2 C tr(A λ )} .
In the steps 1 and 2 of the above algorithm, in practice, a grid in log-scale is used, and our theoretical results from the next section suggest to use a step-size of order n -1/2 . Step 1 can be solved efficiently (at least when Λ is finite or Λ is embedded with a total order) thanks to Algorithm 2 in [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF]. Note that it may not be possible in all cases to find a C such that df( λ 0 (C)) ∈ [n/10, n/3] ; therefore, our condition in step 2, could be relaxed to finding a C such that for all C > C(1 + δ) , df( λ 0 (C)) < n/10 and for all C < C/(1 + δ) , df( λ 0 (C)) > n/10 , with δ ∝ ln(n)/n .

Alternatively, using the same grid in log-scale, we can select C with maximal jump between successive values of df( λ 0 (C))-note that our theoretical result then does not entirely hold, as we show the presence of a jump around σ 2 , but do not show the absence of similar jumps elsewhere. See examples in Section 5.

Assumptions

Before stating our main results, let us state the main assumptions we make on (A λ ) λ∈Λ and on the distribution of the noise. We essentially consider a set of linear estimators which corresponds to a union of a discrete set and a union of matrices obtained from ridge regression (which are themselves parameterized by a single continuous parameter).

• Assumption on the matrices A λ : some constants K df ∈ (0, 2) and M ≥ 1 exists such that

∀λ ∈ Λ , A λ ∈ M n (R) is deterministic, |||A λ ||| ≤ M tr ( A λ ) ≤ n and tr(A ⊤ λ A λ ) ≤ (2 -K df ) tr(A λ ) .
(HA λ )

• Assumption on Λ:

I ∈ { A λ } λ∈Λ and Λ ⊂ Λ 0 ∪ N r Λ j=1 ( { j } × [0, +∞] ) with Card(Λ 0 ) ≤ C d Λ n α d Λ N r Λ ≤ C r Λ n α r Λ and ∀j ∈ { 1, . . . , N r Λ } , ∀x ∈ (0, +∞) , A (j,x) = K j (K j + nxI n ) -1 with K j ∈ M n (R)\ 0 Mn(R) symmetric positive semi-definite and A (j,0) = I A (j,+∞) = 0 Mn(R)                    (HΛ)
• Assumption on the noise:

ε 1 , . . . , ε n are i.i.d. ∼ N (0, σ 2 ) (HN σ 2 )
• Assumption on the bias:

∃λ 1 ∈ Λ, df(λ 1 ) ≤ √ n and b(λ 1 ) ≤ σ 2 n ln(n) . (Abias)
The above assumption set is discussed in details in Section 4.6.

Remark 1. By Proposition 1, under assumption (HΛ), assumption (HA λ ) holds with K df = 1 and M = 1 for all λ ∈ j { j } × [0, +∞] . Furthermore, if all matrices (A λ ) λ∈Λ 0 are among the examples of Proposition 1, assumption (HA λ ) holds with K df = 1 and M = sup λ∈Λ 0 A λ , which happens to be close to 1 with large probability in all the examples we considered in our simulation experiments.

Minimal penalty

Theorem 1. Let λ 0 be defined by

∀C ≥ 0, λ 0 (C) ∈ arg min λ∈Λ F λ -Y 2 2 + C 2 tr(A λ ) -tr(A ⊤ λ A λ ) . (11)
Assume (HΛ), (HA λ ), (HN σ 2 ) and (Abias) hold true. Let

β 1 = 27M β 2 = 150M K df α Λ = max α d Λ , α r Λ + 2 C Λ = 6C d Λ + C r Λ .
Then, for every δ ≥ 2 , a constant n 0 (K df , α Λ + δ, M) exists such that for every n ≥ n 0 ,

∀0 ≤ C < 1 -β 1 ( α Λ + δ) ln(n) n σ 2 , df( λ 0 (C)) ≥ n 3 ( 12
)
and

∀C > 1 + β 2 ( α Λ + δ) ln(n) n σ 2 , df( λ 0 (C)) ≤ n 10 ( 13
)
hold with probability at least 1 -

C Λ n -δ .
Theorem 1 is proved in Section D.

The first important consequence of Theorem 1 is that under mild assumptions (see Section 4.6), with a large probability, the constant C obtained by the algorithm of Section 4.1 satisfies

1 -β 1 ( α Λ + δ) ln(n) n σ 2 ≤ C ≤ 1 + β 2 ( α Λ + δ) ln(n) n σ 2 .
In particular, C is a consistent estimator of σ 2 , but Theorem 1 actually provides precise nonasymptotic multiplicative bounds for C (with a convergence rate of order ln(n)/n), that are crucial for deriving a non-asymptotic oracle inequality for the algorithm of Section 4.1, as emphasized in Remark 8 below.

Compared to classical estimators of σ 2 , such as the one usually used with Mallows' C L , C does not depend on the choice of some model assumed to have almost no bias, which can lead to overestimating σ 2 by an unknown amount [START_REF] Efron | How biased is the apparent error rate of a prediction rule?[END_REF].

Remark 2. On the same event and under the same assumptions as Theorem 1,

∀C > 1 + β 2 10 ( α Λ + δ) ln(n) n 1/4 σ 2 , df( λ 0 (C)) ≤ n 3/4 ,
by taking b n = n 3/4 in Proposition 10. Therefore, a clearer jump can be observed by looking at df( λ 0 (C)) at a slightly less precise scale, which results in a possible loss in the estimation of σ 2 .

Remark 3. The precise values n/3 and n/10 in Eq. ( 12)-( 13) have no particular meaning:

(n/3, n/10) could be replaced by (n/κ, n/κ ′ ) for any κ ′ > κ > 2 . If all matrices A λ correspond to k-NN or OLS estimators, we can even take any κ ′ > κ > 1 , for instance, (9n/10, n/10) .

Oracle inequality

Define

∀C ≥ 0 , λ opt (C) ∈ arg min λ∈Λ F λ -Y 2 2 + 2C tr(A λ ) . ( 14
)
We have the following general theorem.

Theorem 2. Let λ opt (C) be defined by Eq. ( 14) and assume that (HΛ), (HA λ ) and (HN σ 2 ) hold true. Let

β 3 = max 32M 2 , 24M 2 + 1225 and β 4 = 9928 .
Then, for every δ ≥ 2 , if n ≥ n 1 some absolute constant, with probability at least 1 -C Λ n -δ , for every C > 0 and every η ∈ (0, 2) ,

n -1 F λopt(C) -F 2 2 ≤ ( 1 + η ) inf λ∈Λ n -1 F λ -F 2 2 + 2(C -σ 2 ) + tr(A λ ) n + 32 η Cσ -2 -1 2 σ 2 1 C≤σ 2 + β 3 + β 4 η ln(n)(δ + α Λ )σ 2 n ( 15
)
and

n -1 F λopt(C) -F 2 2 ≤ ( 1 + η ) inf λ∈Λ n -1 F λ -F 2 2 + 32 η Cσ -2 -1 2 σ 2 + β 3 + β 4 η ln(n)(δ + α Λ )σ 2 n . ( 16
)
Theorem 2 is proved in Section E. Before applying it to the proposed algorithm, let us make a few remarks.

Remark 4. Note that the two inequalities in Eq. ( 15) and Eq. ( 16) differ from their treatment of underestimation and overestimation of C (compared to σ 2 ). As shown explicitly in Eq. ( 15), overestimation of C leads to a increase of generalization cost which grows as 2 tr(A λ ) n , which is small, while underestimation leads to a constant factor, which is more problematic, and requires greater care when estimating C from data, which we do in this paper.

Remark 5. When C is deterministic, we can deduce from Eq. ( 15)-( 16) an oracle inequality in expectation; we refer to the proof of Theorem 3 for details.

Remark 6. If η = (ln(n)) -1 and Cσ -2 -1 = O( ln(n)/n) ,
the remainder term in Eq. ( 15)-( 16) is of order (ln(n)) 3 σ 2 n -1 , which is negligible in front of the risk of the oracle provided that v 2 (λ ⋆ ) grows with n faster than (ln(n)) 3 , since the risk of F λ ⋆ is at least of order v 2 (λ ⋆ )n -1 . This usually holds when the bias is not exactly zero for some λ ∈ Λ with tr(A ⊤ λ A λ ) too small, as often assumed in the model selection literature for proving asymptotic optimality results.

Remark 7. The term Cσ -2 -1 2 /θ could be lowered with some assumption on sup λ∈Λ

tr(A λ ) tr(A ⊤ λ A λ ) .
Eq. ( 15)-( 16) actually correspond to the worst-case situation, where no assumption is made. For instance, if all estimators are least-squares or k-nearest neighbours estimators, this term can be replaced by Cσ -2 -1 .

Remark 8. When the noise-level σ 2 is known, taking C = σ 2 in Theorem 2 (that is, considering Mallows' C L penalty) yields the following oracle inequality instead of Eq. ( 16):

n -1 F λopt(C) -F 2 2 ≤ ( 1 + η ) inf λ∈Λ n -1 F λ -F 2 2 + β 3 + β 4 η ln(n)(δ + α Λ )σ 2 n .
As underlined in previous works [START_REF] Baraud | Gaussian model selection with an unknown variance[END_REF][START_REF] Baraud | Estimator selection in the gaussian setting[END_REF], dealing with the case of unknown variance is more challenging, even in the model selection case. In Theorem 2 above, the remainder term

Cσ -2 -1 2 σ 2
underlines how important it is to have C close to σ 2 . We conjecture this term is essentially unimprovable in the case where tr(A ⊤ λ A λ ) is close to its lower bound n -1 tr(A λ ) 2 for λ "close" to the oracle, since the penalty 2σ 2 n -1 tr(A λ ) can then be an order of magnitude higher than the risk, which is the sum of the bias and of σ 2 n -1 tr(A ⊤ λ A λ ). Therefore, estimating σ 2 with a precision as high as the one guaranteed in Theorem 1 is crucial to derive an oracle inequality valid for all linear estimators.

Combined result

As a corollary of Theorems 1 and 2, we get the following non-asymptotic oracle inequality (with leading constant arbitrarily close to 1) for the algorithm proposed in Section 4.1.

Theorem 3. Let C and λ be defined as in the algorithm of Section 4.1. Assume that (Abias), (HΛ), (HA λ ) and (HN σ 2 ) hold true. Then, for every δ ≥ 2 , a numerical constant β 5 and a constant n

2 (K df , δ + α Λ , M) exist such that if n ≥ n 2 , with probability at least 1 -C Λ n -δ , for every η ∈ (0, 2) , 1 n F λ -F 2 2 ≤ ( 1 + η ) inf λ∈Λ 1 n F λ -F 2 2 + β 5 M 2 ( α Λ + δ ) 2 ln(n)σ 2 ηn . (17)
As a consequence, if n ≥ n 2 (K df , α Λ + 2, M) , for every η ∈ (0, 2) ,

E 1 n F λ -F 2 2 ≤ ( 1 + η ) E inf λ∈Λ 1 n F λ -F 2 2 + β 5 M 2 ( α Λ + 2 ) 2 ln(n)σ 2 ηn + 2 C Λ 2σ 2 M 2 + ( 1 + M ) 2 n -1 F 2 n . ( 18
)
Theorem 3 is proved in Section F. Its main consequences are detailed in Section 4.7.

Note that taking η

= β 5 M 2 ( α Λ +2 ) 2 ln(n)σ 2 E inf λ∈Λ F λ -F 2 2
in Eq. ( 18) yields a non-asymptotic oracle inequality with leading constant one, that directly implies an asymptotic optimality result when

ln(n)σ 2 n
is negligible in front of the risk of the oracle. Gaussian noise and (HΛ). For proving Theorems 1, 2 and 3, a key ingredient is a uniform concentration inequality for four functions of λ and ε , that is, a lower bound on the probability of the event Ω ( α Λ +δ) ln(n) (Λ) defined in Section A.2. In particular, assumptions (HΛ) and (HN σ 2 ) are only used for proving this event has a probability at least 1 -C Λ n -δ . So, any alternative assumption set under which a similar uniform concentration inequality could be proved could be used instead of (HΛ) and (HN σ 2 ), leading to the same results (except for the precise values of the constants). We refer to the proofs for details.

Discussion of the assumptions

For instance, kernel ridge regression could be replaced in assumption (HΛ) by Pinsker filters (see Section 2.2) with the one-dimensional parameter set w ∈ (0, +∞).

When ε is sub-Gaussian, the key concentration results (Lemma 8) can certainly be proved for ξ = σ -1 ε (possibly with additional small deviation terms that do not change the core of the proof) at the price of additional technicalities (at least when N r Λ = 0, i.e., Λ is finite), which implies that Theorems 1, 2 and 3 would still be valid. Note that assuming the noise is Gaussian is classical when proving non-asymptotic oracle inequalities [START_REF] Cao | On oracle inequalities related to smoothing splines[END_REF][START_REF] Baraud | Estimator selection in the gaussian setting[END_REF]; only asymptotic results exist about linear estimators selection with moment conditions on the noise [START_REF] Li | Asymptotic optimality of C L and generalized cross-validation in ridge regression with application to spline smoothing[END_REF][START_REF] Li | Asymptotic optimality for C p , C L , cross-validation and generalized crossvalidation: discrete index set[END_REF]. Considering heavy-tailed noise is of clear interest but beyond the scope of this paper.

Main consequences of Theorem 3 and comparison with previous results

Oracle inequality. The algorithm of Section 4.1 satisfies a non-asymptotic oracle inequality with high probability, as shown by Eq. ( 17): The risk of the selected estimator F λ is close to the risk of the oracle, up to a remainder term which is negligible when the dimensionality df(λ ⋆ ) of the oracle grows with n faster than ln(n) , a typical situation when the bias is never equal to zero, for instance in kernel ridge regression.

Eq. ( 17) is non-asymptotic, meaning that it holds for every fixed n as soon as the assumptions explicitly made in Theorem 3 are satisfied. Most results (all but the more recent ones for linear estimator selection [START_REF] Cao | On oracle inequalities related to smoothing splines[END_REF][START_REF] Baraud | Estimator selection in the gaussian setting[END_REF]) are asymptotic, meaning that n is implicitly assumed to be larged compared to each parameter of the problem. This assumption can be problematic for several learning problems, for instance in multiple kernel learning when the number p of kernels may grow with n .

Another important feature of Eq. ( 17) is that it holds with high probability, which is stronger than most results only true in expectation, that is, similar to Eq. ( 18), or even weaker. As emphasized by [START_REF] Li | Asymptotic optimality of C L and generalized cross-validation in ridge regression with application to spline smoothing[END_REF], the difference is significant, since some examples exist where a procedure (GCV) is asymptotically optimal in expectation (like Eq. ( 18)) but not a.s. (like Eq. ( 17)).

Several oracle inequalities have been proved in the statistical literature for Mallows' C L with σ 2 known, either asymptotic [START_REF] Li | Asymptotic optimality of C L and generalized cross-validation in ridge regression with application to spline smoothing[END_REF][START_REF] Li | Asymptotic optimality for C p , C L , cross-validation and generalized crossvalidation: discrete index set[END_REF] or non-asymptotic [START_REF] Cao | On oracle inequalities related to smoothing splines[END_REF]. When σ 2 is unknown (and replaced by a consistent estimator), up to the best of our knowledge, guarantees for C L are only available for the model selection problem (see [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF][START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF] and references therein).

Comparison with other procedures. Oracle inequalities or asymptotic optimality results have been proved for several other linear estimator selection procedures.

Generalized Cross Validation (GCV) [START_REF] Craven | Smoothing noisy data with spline functions. Estimating the correct degree of smoothing by the method of generalized cross-validation[END_REF] was mostly studied for model selection and (kernel) ridge regression. GCV is asymptotically optimal in expectation under mild assumptions [START_REF] Craven | Smoothing noisy data with spline functions. Estimating the correct degree of smoothing by the method of generalized cross-validation[END_REF], but additional restrictions are needed for its almost sure asymptotic optimality [START_REF] Li | Asymptotic optimality of C L and generalized cross-validation in ridge regression with application to spline smoothing[END_REF]: some ridge regression example exists where GCV is not asymptotically optimal whereas C L is [START_REF] Li | Asymptotic optimality of C L and generalized cross-validation in ridge regression with application to spline smoothing[END_REF]. Up to the best of our knowkedge, except for model selection, non-asymptotic oracle inequalities for GCV only exist for (kernel) ridge regression [START_REF] Cao | On oracle inequalities related to smoothing splines[END_REF]; their result requires a prior upper bound tr(A λ ) ≤ n/5 for all λ ∈ Λ, and it is only valid in expectation, so it is weaker than Eq. [START_REF] Efron | How biased is the apparent error rate of a prediction rule?[END_REF]. Moreover, compared to [START_REF] Craven | Smoothing noisy data with spline functions. Estimating the correct degree of smoothing by the method of generalized cross-validation[END_REF], our results are applicable to all linear estimators and identify key assumptions regarding the bias and variance of our collection of linear estimators (i.e., Assumption (Abias)).

Asymptotic optimality results also exist for GCV for k-nearest neighbors regression [START_REF] Li | Asymptotic optimality for C p , C L , cross-validation and generalized crossvalidation: discrete index set[END_REF], that require the same assumption A λ ≤ M than we have. [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF] also satisfy some asymptotic optimality results in the nearest-neighbor regression case [START_REF] Li | Asymptotic optimality for C p , C L , cross-validation and generalized crossvalidation: discrete index set[END_REF]. Compared to GCV or to the algorithm of Section 4.1, cross-validation methods also suffer from a large computational cost, that can only be lowered by considering V -fold cross-validation with V rather small, at the price of an increased risk. See also the simulation study of Section 5 for a numerical comparison.

Cross-validation methods

Baraud, Giraud and Huet's penalization procedure [START_REF] Baraud | Estimator selection in the gaussian setting[END_REF] also satisfies a non-asymptotic oracle inequality under mild assumptions (with a leading constant C > 1 and a remainder term that can be large) assuming the noise is Gaussian. Compared to our minimal penalty algorithm, their procedure is more general and can deal with arbitrarily large collections Λ (putting aside computational complexity). Nevertheless, their algorithm is slightly more complex, and probably more dependent on the Gaussian assumption on the noise, since the Gaussian distribution explicitly appears in the definition of their penalty.

No overfitting. Finally, let us mention a special feature of the minimal penalty algorithm that may not appear in the comparison of theoretical results, in particular because it plays an important role only at second order and when n is small. By construction, the algorithm of Section 4.1 selects λ with an effective dimensionality larger than λ 0 ( C) at which the jump occurs. Therefore, our algorithm never overfits too much, in addition to the theoretical risk bounds we have proved. This is a quite interesting property compared for instance to GCV, which is likely to overfit if it is not corrected, because GCV minimizes a criterion proportional to the empirical risk.

Simulations

In this section, we report simulations experiments with examples of fixed design regression to illustrate our theoretical results. For simulations on random design regression, see [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF]. We consider the following example: we take n = 200 and use n points uniformly spaced in [0, 1], i.e., x i = (i -1)/(n -1) ∈ [0, 1]. We then consider Y i = sin(25πX i ) + ε i or Y i = sin(25πX 3 i ) + ε i , where ε i are independent standard Gaussian random variables. We performed experiments with kernel ridge regression with kernel k(x, y) = d i=1 e -|x i -y i | (where the goal is to learn the regularization parameter), with nearest-neighbor regression (where the goal is to learn the number of neighbors), and with locally-weighted regression (where the goal is to learn the bandwidth of the kernel).

Jump. In Figure 2 we study the size of the jump for kernel ridge regression. With half the optimal penalty (which is used in traditional variable selection for linear regression), we do not get any jump, while with the minimal penalty we always do. Note that on the left plots, we may get sharp (but of lower amplitude) jumps away from C = σ 2 . In this particular situation, this is due to the periodicity of the sine function.

Comparison of estimator selection methods. In Figure 3, we plot model selection results for 20 replications of data, comparing GCV [START_REF] Craven | Smoothing noisy data with spline functions. Estimating the correct degree of smoothing by the method of generalized cross-validation[END_REF] and Mallows C L penalty (which assumes the knowledge of σ 2 ). For the minimal penalty, we consider two strategies for finding the largest jump. We select the set of parameters so that the degrees of freedom are integers in [0, n]. In the first strategy, we select the value C with the largest jump, while in the second strategy we select the first C so that the selected degrees of freedom goes below n/2.

We compare to the oracle (which can be computed because we can enumerate Λ). We see in Figure 3 that (a) the largest jump is not a good heuristic as spurrious jumps may occur, (b) the minimal penalty technique outperforms GCV, and (c) that in some cases, Mallows (which assumes more knowledge) is outperformed by our minimal penalty strategy. Indeed, when the signal-to-noise ratio is small, overpenalizing a bit (i.e., multiplying Mallows' penalty by a factor κ > 1) is often useful, which turns out to be done automatically with the minimal penalty.

Conclusion

A new light on the slope heuristics. Theorems 1, 2 and 3 generalize some results first proved in [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF] where all A λ are assumed to be projection matrices. To this extent, Birgé and Massart's slope heuristics has been modified in a way that sheds a new light on the "magical" factor 2 between the minimal and the optimal penalty, as proved in [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF][START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF]. Indeed, Theorems 1-2 show that for general linear estimators,

pen id (λ) pen min (λ) = 2 tr(A λ ) 2 tr(A λ ) -tr(A ⊤ λ A λ ) , (19)
which can take any value in [START_REF] Allen | The relationship between variable selection and data augmentation and a method for prediction[END_REF][START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF] in general (assuming K df = 1 as in all the major examples we have in mind); this ratio is only equal to 2 when tr(A λ ) ≈ tr(A ⊤ λ A λ ) , hence mostly when A λ is a projection matrix or a k-NN matrix.

Covariance matrix estimation.

A natural extension of the present work appears in the multitask regression example, when p regression problems (the tasks) are solved simultaneously. Then, a key quantity is the p × p covariance matrix of the tasks, which has to be estimated for an optimal selection of regularization parameters (for instance). As shown in [START_REF] Solnon | Multi-task regression using minimal penalties[END_REF], the minimal penalty strategy can be used successfully for estimating a covariance matrix under mild assumptions, by applying the algorithm of Section 4.1 to p(p + 1)/2 well-chosen one-dimensional regression problems.

Future directions. The good empirical performances of elbow heuristics based algorithms (i.e., based on the sharp variation of a certain quantity around good hyperparameter values [START_REF] Per | The use of the L-curve in the regularization of discrete ill-posed problems[END_REF][START_REF] Grodzevich | Regularization using a parameterized trust region subproblem[END_REF][START_REF] Rezghi | A new variant of L-curve for Tikhonov regularization[END_REF]) suggest that Theorem 3 can be generalized to many learning frameworks (and potentially to non-linear estimators), probably with small modifications in the algorithm, but always relying on the concept of minimal penalty. ) , for a a fixed design problem and kernel ridge regression (top), Nadaraya-Watson estimator (middle) and K-nearest neighbor regression: note that when penalizing by the minimal penalty, there is a strong jump at C = σ 2 , while when using half the optimal penalty, this is not the case. Left:

Y i = sin(25πX i ) + ε i , Right: Y i = sin(25πX 3 i ) + ε i .
Y i = sin(25πX i ) + ε i , Right: Y i = sin(25πX 3 i ) + ε i .
In the case of projection estimators, the slope heuristics still holds when the design is random and data are heteroscedastic [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF]; we conjecture a generalization of Eq. ( 19) is still valid for heteroscedastic data with some (but not all) linear estimators.

Another interesting open problem would be to extend the results of Section 4 to more general continuous sets Λ, such as the ones appearing naturally in multiple kernel learning. We conjecture that Theorem 3 is valid without modification for a "small" continuous Λ , that is, of "small" dimension. On the contrary, in applications such as the Lasso with p ≫ n variables, the natural set Λ cannot be well covered by a grid of cardinality n α with α small, and our minimal penalty algorithm and Theorem 3 certainly have to be modified.

Appendix A Notation and first computations

Recall that

Y = F + ε where F = (f (x i )) 1≤i≤n ∈ R n is deterministic, ε = (ε i ) 1≤i≤n ∈ R n
is centered with covariance matrix σ 2 I n and I n is the n × n identity matrix.

For every x ∈ R , x + = max { x , 0 } denotes the positive part of x .

In the proofs, we use repeatedly that

∀a, b ≥ 0 , ∀θ > 0 , 2 √ ab ≤ θa + θ -1 b , (20)
with equality for θ = b/a.

A.1 General framework

For every λ ∈ Λ, F λ = A λ Y for some n × n real-valued matrix A λ , so that

F λ -F 2 2 = (A λ -I n )F 2 2 + A λ ε 2 2 + 2 A λ ε, (A λ -I n )F , (21)
F λ -Y 2 2 = F λ -F 2 2 + ε 2 2 -2 ε, A λ ε + 2 ε, (I n -A λ )F , (22)
where ∀t, u ∈ R n , t, u = n i=1 t i u i and t 2 2 = t, t . Now, define, for every λ ∈ Λ ,

b(λ) = (A λ -I n )F 2 2 v 1 (λ) = tr(A λ )σ 2 v 2 (λ) = tr(A ⊤ λ A λ )σ 2 δ 1 (λ) = ε, A λ ε -tr(A λ )σ 2 δ 2 (λ) = A λ ε 2 2 -tr(A ⊤ λ A λ )σ 2 δ 3 (λ) = 2 A λ ε, (A λ -I n )F δ 4 (λ) = 2 ε, (I n -A λ )F ,
so that Eq. ( 21) and ( 22) can be rewritten

F λ -F 2 2 = b(λ) + v 2 (λ) + δ 2 (λ) + δ 3 (λ) ( 23
)
F λ -Y 2 2 = F λ -F 2 2 -2v 1 (λ) -2δ 1 (λ) + δ 4 (λ) + ε 2 2 . ( 24
)
Note that b(λ), v 1 (λ) and v 2 (λ) are deterministic, and for all λ ∈ Λ and i = 1 . . . 4 , δ i (λ) is random with zero mean. In particular, we deduce the following expressions of the risk and the empirical risk of F λ :

E n -1 F λ -F 2 2 = n -1 (A λ -I n )F 2 2 + tr(A ⊤ λ A λ )σ 2 n , (25)
E n -1 F λ -Y 2 2 -σ 2 = n -1 (A λ -I n )F 2 2 - 2 tr(A λ ) -tr(A ⊤ λ A λ ) σ 2 n . (26)
A.2 The event Ω x

In this section, we define the large probability event on which all our main results hold. Let C Ω ∈ [0, +∞) 6 be fixed. Then, for any x ≥ 0 , we define the event

Ω x = Ω x (Λ) = Ω x Λ, C Ω
on which, for every λ ∈ Λ and every θ 1 , θ 2 , θ 3 , θ 4 ∈ (0, 1] ,

|δ 1 (λ)| ≤ θ 1 σ 2 tr(A ⊤ λ A λ ) + C Ω 1 + C Ω 2 θ -1 1 xσ 2 (27) |δ 2 (λ)| ≤ θ 2 σ 2 tr(A ⊤ λ A λ ) + C Ω 3 + C Ω 4 θ -1 2 xσ 2 ( 28
)
|δ 3 (λ)| ≤ θ 3 (I n -A λ )F 2 2 + C Ω 5 θ -1 3 xσ 2 (29) |δ 4 (λ)| ≤ θ 4 (I n -A λ )F 2 2 + C Ω 6 θ -1 4 xσ 2 . ( 30
)
A. [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF] Splitting assumption (HΛ)

We actually deal with assumption (HΛ) by considering separately the case of discrete Λ (assumption (HΛdis)) and the case of ridge regression with a continuous one-dimensional parameter (assumption (Hridge)):

• The set Λ is finite (with a polynomial size w.r.t. n):

Card(Λ) ≤ C d Λ n α d Λ (HΛdis)
• In the kernel ridge regression example:

Λ = [0, +∞] A 0 = I n A ∞ = 0 Mn(R) ∃K ∈ M n (R)\ 0 Mn(R) symmetric positive semi-definite such that ∀λ ∈ (0, +∞) , A λ = K(K + nλI n ) -1      (Hridge)
Once the concentration results will be proved under each assumption, an union bound will yield the desired results under the composite assumption (HΛ).

A.4 Kernel ridge regression

Let us now prove a few useful elementary results that are specific to kernel ridge regression, that is, when assumption (Hridge) holds true.

Under assumption (Hridge), a key remark is the following. Since K is symmetric positive, non-negative numbers µ 1 , . . . , µ n and some orthogonal matrix P ∈ M n (R) exists such that

K = P ⊤ diag(µ 1 , . . . , µ n )P . Then, ∀λ ∈ Λ , A λ = P ⊤ D λ P where D λ = diag µ j µ j + nλ 1≤j≤n , (31)
with the convention D 0 = I n and D ∞ = 0 Mn(R) . We also define (f j ) 1≤j≤n = P F . Proof of Lemma 2. According to Eq. ( 31), for every λ ∈ [0, +∞),

tr(A λ ) = df(λ) = n j=1 µ j µ j + nλ tr(A ⊤ λ A λ ) = n j=1 µ j µ j + nλ 2 2 tr(A λ ) -tr(A ⊤ λ A λ ) = n j=1 2µ j µ j + nλ - µ j µ j + nλ 2 = n j=1 µ j (µ j + 2nλ) ( µ j + nλ) 2 b(λ) = (A λ -I n )F 2 2 = n j=1 1 - µ j µ j + nλ 2 f 2 j ,
The result follows since µ j ≥ 0 for every j .

A.5 A useful lemma

Lemma 3. Let n ≥ 1 an integer. Then, for any matrix

A ∈ M n (R), tr(A) ≤ n tr(A ⊤ A) , (32)
from which we get

∀A ∈ M n (R) , x ≥ 0 , θ > 0 , x tr(A) ≤ θ tr(A ⊤ A) + x 2 n 4θ . (33)
Proof of Lemma 3. First, since (A, B) → tr(A ⊤ B) is a scalar product on M n (R) , by Cauchy-Schwarz inequality, for every

A ∈ M n (R), ( tr(A) ) 2 = tr(I ⊤ A) 2 ≤ tr A ⊤ A tr I ⊤ I = n tr A ⊤ A .
Therefore, for every x ≥ 0, θ > 0,

x tr(A) ≤ 2 tr(A ⊤ A) x 2 n 4 ≤ θ tr(A ⊤ A) + x 2 n 4θ
by Eq. ( 20).

B Key concentration inequalities

In this section, we state the concentration inequalities showing the event Ω x has a large probability. Our main contributions are the following. Proposition 6 slightly extends a result by Laurent and Massart [START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF] for the concentration of quadratic forms of a Gaussian vector. In the kernel ridge regression example, we prove uniform concentration inequalities (over a continuous set) for some linear forms of a Gaussian vector (Proposition 5 and Lemma 13), and for some quadratic forms of a random vector (Proposition 7). All results are proved in Section G.

B.1 Linear functions of ε

In the Gaussian case, concentration inequalities for δ 3 (λ) and δ 4 (λ) come from the following standard result.

Proposition 4. Let ξ be a standard Gaussian vector in R n , α ∈ R n and Z = ξ, α = n j=1 α j ξ j . Then, for every x ≥ 0 ,

P |Z| ≤ √ 2x α 2 ≥ 1 -e -x .
Proof of Proposition 4. The result is clear when α = 0. Otherwise, ξ, α ∼ N 0, α 2 which gives the result.

In the kernel ridge regression case, we get a similar result (with larger constants) uniformly over Λ = [0, +∞]. Up to the best of our knowledge, Proposition 5 is a new result that could be useful for studying kernel ridge regression in a more general framework.

Proposition 5. Assume that (Hridge) and (HN σ 2 ) hold true. Then, for every x ≥ 0, an event Ω R

x of probability at least 1exp(-x + 1026 + ln(n)) exists on which for every λ ∈ Λ ,

|δ 3 (λ)| ≤ 35σ (I n -A λ )F √ x, (34)
|δ 4 (λ)| ≤ 35σ (I n -A λ )F √ x . ( 35
)
Proposition 5 is proved in Section G.1.

B.2 Quadratic functions of ε

In the Gaussian case, concentration inequalities for δ 1 (λ) and δ 2 (λ) come from the following result.

Proposition 6. Let ξ be a standard Gaussian vector in R n , M a real-valued n × n matrix and

Z := ξ, M ξ -tr(M ) = ξ ⊤ M ξ -tr(M ) .
Then, E [ Z ] = 0 and for every x ≥ 0 ,

P Z ≤ 2x ( tr(M 2 ) + tr(M ⊤ M ) ) + 2 |||M ||| x ≥ 1 -exp ( -x) . (36)
Since tr(M 2 ) ≤ tr(M ⊤ M ) (by Lemma 15), we get that for every x ≥ 0 ,

P ξ, M ξ ≤ tr(M ) + 2 x tr(M ⊤ M ) + 2 |||M ||| x ≥ 1 -exp ( -x ) . (37)
Proposition 6 extends [22, Lemma 1]; it is proved in Section G.2. The main deviation term in Eq. ( 36) is optimal since var(Z) = tr(M 2 ) + tr(M ⊤ M ) as shown in Section H.2.

C.2 Case (ii)

tr(A ⊤ A) = 1≤i,j≤n A 2 i,j ≤ n i=1 n j=1 A i,j A i,i = n i=1 A i,i = tr(A) ≤ n i=1 n k=1 A i,k = n .
In particular, if (kNN) holds true, then tr(A) = n/k and

tr(A ⊤ A) = 1≤i,j≤n A 2 i,j = 1 k 1≤i,j≤n A i,j = n k .

D Minimal penalty (proof of Theorem 1)

Let us recall the definition (11) of λ 0 (C):

∀C ≥ 0, λ 0 (C) ∈ arg min λ∈Λ F λ -Y 2 2 + C 2 tr(A λ ) -tr(A ⊤ λ A λ ) .
We prove in this section Theorem 1, which is actually a corollary of the following proposition:

Proposition 10. Let λ 0 be defined by Eq. [START_REF] Cao | On oracle inequalities related to smoothing splines[END_REF]. Assume that I ∈ { A λ } λ∈Λ , (HA λ ) holds true, and let c n ∈ [0, n] and β n ≥ n ln(n) be such that 6 and define

∃λ 1 ∈ Λ, df(λ 1 ) ≤ c n and b(λ 1 ) ≤ σ 2 β n . (Abiais ′ ) Let C Ω ∈ [0, +∞)
K Ω A := 2C Ω 1 + C Ω 3 + 3C Ω 5 + 3C Ω 6 and K Ω B := 6C Ω 2 + 3C Ω 4 .
Then, for every γ ≥ 2, L 1 > 0, a constant n 3 > 0 only depending on

K Ω A , K Ω B , γ, L 1 exists such that if n ≥ n 3 , for every a n ∈ [0, n 2 ) and b n ∈ [ 10 K df max{K Ω B γ ln(n), 2c n }, n] ∀0 ≤ C < 1 -2 2K Ω B + 1 L 1 γ n ln(n) n -2a n σ 2 , df( λ 0 (C)) ≥ a n (40)
∀C > 1 + 25 27 + 1 L 1 + 40 9 K Ω B γβ n K df b n σ 2 , df( λ 0 (C)) ≤ b n . (41)
hold on the event Ω γ ln(n) (Λ, C Ω ) .

In particular, under assumptions (HΛ) and

(HN σ 2 ), if n ≥ n 4 (γ, M), with probability at least 1 -( 6 Card(Λ 0 ) + N r Λ exp ( 1027 + ln(n) ) ) n -γ , ∀a n ∈ 0, n 2 , ∀0 ≤ C < 1 - 9Mγ n ln(n) n -2a n σ 2 , df( λ 0 (C)) ≥ a n ( 42
)
∀b n ∈ 10 K df max K Ω B γ ln(n), 2c n , n , ∀C > 1 + 15γβ n M K df b n σ 2 , df( λ 0 (C)) ≤ b n . ( 43
)
Proof of Theorem 1. Taking c n = √ n and β n = n ln(n) , assumption (Abiais ′ ) becomes (Abias). Let a n = n/3, b n = n/10 (which is possible in Proposition 10 as soon as n/ ln(n) ≥ 100K Ω B γ and n ≥ (200/K df ) 2 ). Then, choosing γ = α Λ + δ , Eq. ( 40) becomes Eq. ( 12), Eq. (41) becomes Eq. ( 13), and they hold with probability at least

1 -( 6 Card(Λ 0 ) + N r Λ exp ( 1027 + ln(n) ) ) n -α Λ -δ ≥ 1 -6C d Λ n α d Λ + C r Λ exp ( 1027 + (α r Λ + 1) ln(n) ) n -α Λ -δ = 1 -6C d Λ n α d Λ -α Λ + C r Λ exp ( 1027 + (α r Λ + 1 -α Λ ) ln(n) ) n -δ ≥ 1 -6C d Λ + C r Λ exp ( 1027 -ln(n) ) n -δ ≥ 1 -6C d Λ + C r Λ n -δ
as soon as ln(n) ≥ 1027 , since α Λ ≥ 2 + α r Λ and α Λ ≥ α d Λ .

Remark 10. On the event Ω γ ln(n) (Λ) where Eq. ( 40) and (41) hold and under the same assumptions, we can derive from Eq. ( 23), ( 28)

with θ 2 = 1/2, ( 29
) with θ 3 = 1, that ∀λ ∈ Λ , n -1 F λ -F 2 2 ≥ tr(A ⊤ λ A λ )σ 2 2n - (C Ω 3 + 2C Ω 4 + C Ω 5 )γ ln(n)σ 2 n .
Since tr(A ⊤ λ A λ ) ≥ n -1 ( df(λ) ) 2 we deduce that for all λ ∈ Λ:

df(λ) ≥ n ln(n) ⇒ n -1 F λ -F 2 2 ≥ σ 2 1 2 ( ln(n) ) 2 - (C Ω 3 + 2C Ω 4 + C Ω 5 )γ ln(n) n .
Hence, the blow up of df( λ 0 (C)) holding when the penalty is below the minimal penalty also implies a blow up of the risk n

-1 F λ 0 (C) -F 2 2
.

Remark 11. Using assumption (HA λ ) and Lemma 3, we deduce that for every λ ∈ Λ ,

( df(λ) ) 2 n ≤ tr(A ⊤ λ A λ ) ≤ 2 tr(A λ ) = 2 df(λ) .
Therefore, on the event defined by Proposition 10, a jump in tr A ⊤ λ 0 (C)

A λ 0 (C) also occurs when C goes through σ 2 . Indeed,

df( λ 0 (C)) ≥ a n implies that tr A ⊤ λ 0 (C) A λ 0 (C) ≥ a 2 n
and this lower bound becomes n/9 if a n = n/3 . Furthermore,

df( λ 0 (C)) ≤ b n implies that tr A ⊤ λ 0 (C) A λ 0 (C) ≤ 2b n
which is equal to 2n 3/4 when b n = n 3/4 , for instance.

Let us now prove Proposition 10. The proof is organized is as follows:

1. Section D.1 makes use of the definition of the event Ω γ ln(n) (Λ, C Ω ) for controlling uniformly over C and λ ∈ Λ the criterion crit C minimized by λ 0 (C). Combining the two conditions. Finally, we have proved that whatever the value of df(λ 1 ) , df( λ 0 (C)) < b n holds if conditions (59) and ( 62) are both satisfied and if n/ ln(n) ≥ L 2 , b n ≥ 10 K df max{K Ω B γ ln(n), 2c n } . Eq. ( 41) follows by choosing

L 2 = 3(K Ω A + K Ω B )L 1 .
Merging all assumptions on n made in the proof, the constant n 3 is defined by inf

n≥n 3 n ln(n) ≥ max K Ω B γ, 16 K Ω A + K Ω B 2 L 2 1 .

D.4 Second part of Proposition 10

We apply Lemmas 8 and 9 and the union bound, taking L 1 = 3 and noticing that

K Ω A = 4M + 2M 2 + 3 max{2M

E Oracle inequality (proof of Theorem 2)

Recall the definition ( 14) of λ opt (C) :

∀C ≥ 0 , λ opt (C) ∈ arg min λ∈Λ F λ -Y 2 2 + 2C tr(A λ ) .
We prove in this section Theorem 2, as a corollary of the following proposition.

Proposition 11. Let λ opt (C) be defined by Eq. [START_REF] Craven | Smoothing noisy data with spline functions. Estimating the correct degree of smoothing by the method of generalized cross-validation[END_REF]. Assume that (HA λ ) holds true. Let C Ω ∈ [0, +∞) 6 and define

K Ω C := 4C Ω 1 K Ω D := 8 C Ω 3 + 2C Ω 4 + 2C Ω 5 and K Ω E := 2 4C Ω 2 + C Ω 6 .
Then, for every γ ≥ 2 , on the event Ω γ ln(n) (Λ, C Ω ) , for every θ ∈ (0, 1/4) ,

n -1 F λopt(C) -F 2 2 ≤ 1 + 2θ 1 -4θ inf λ∈Λ n -1 F λ -F 2 2 + 2(C -σ 2 ) + tr(A λ ) n + Cσ -2 -1 2 1 C≤σ 2 σ 2 θ ( 1 -4θ ) + K Ω C + 3 4 K Ω D θ + K Ω E θ -1 1 -4θ ln(n)γσ 2 n . (63)
and

n -1 F λopt(C) -F 2 2 ≤ 1 + 4θ 1 -4θ inf λ∈Λ n -1 F λ -F 2 2 + Cσ -2 -1 2 σ 2 θ ( 1 -4θ ) + K Ω C + K Ω D θ + K Ω E θ -1 1 -4θ ln(n)γσ 2 n . (64)
Corollary 12. Under assumptions (HA λ ), (HΛ) and (HN σ 2 ), for every γ ≥ 2 , with probability at least 1 -( 6 Card(Λ 0 ) + N r Λ exp ( 1027 + ln(n) ) ) n -γ , for every C > 0, for every θ ∈ (0, 1/4) , Eq. We can now prove Theorem 2:

Proof of Theorem 2. The proof is similar to the one of Theorem 1, starting from Corollary 12 instead of Proposition 10. In addition, we remark that ∀θ ∈ (0, 1/8) ,

1 + 2θ 1 -4θ ≤ 1 + 4θ 1 -4θ ≤ 1 + 16θ
and we take θ = η/16 . Choosing γ = α Λ + δ ≥ 2 in Corollary 12, Eq. ( 63) and (64) become Eq. ( 15) and ( 16), which holds with probability at least 1 -6C r Λ + C d Λ n -δ , assuming that n is larger than some numerical constant n 1 = exp(1027) .

Let us now prove Proposition 11 and Corollary 12. The proof is organized is as follows:

1. In Section E.1, standard algebraic manipulations reduce the problem to bounding ∆(λ) := -2δ 1 (λ) + δ 4 (λ) uniformly over λ ∈ Λ.

2. Section E.2 make use of the definition of the event Ω γ ln(n) (Λ, C Ω ) for bounding ∆(λ).

3. In Section E.3, remainder terms proportional to tr(A λ ) are upper bounded in terms of tr(A ⊤ λ A λ ), so they can be compared to the risk of F λ .

E.1 General starting point

Combining Eq. ( 24) and ( 14), we obtain that for every C > 0 and every λ ∈ Λ ,

F λopt(C) -F 2 2 + 2(C -σ 2 ) tr(A λopt(C) ) + ∆( λ opt (C)) ≤ inf λ∈Λ F λ -F 2 2 + 2(C -σ 2 ) tr(A λ ) + ∆(λ) . (65)
where ∀λ ∈ Λ , ∆(λ) := -2δ 1 (λ) + δ 4 (λ) .

Inequality (65) implies an oracle inequality as soon as ∆(λ) is small compared to F λ -F 2 2 and Cσ 2 is small enough.

E.2 With concentration inequalities

On the event Ω γ ln(n) , using Eq. ( 27) and ( 30) with 2θ 1 = θ 4 = θ ∈ (0, 1] , we get that for every θ ∈ (0, 1] and λ ∈ Λ ,

∆(λ) ≤ θ [ b(λ) + v 2 (λ) ] + K Ω C 2 + K Ω E 2θ γ ln(n)σ 2 (66)
Using also Eq. ( 23), ( 28) and ( 29) with θ 2 = θ 3 = 1/2 , we get that for every λ ∈ Λ ,

F λ -F 2 = b(λ) + v 2 (λ) + δ 2 (λ) + δ 3 (λ) ≥ 1 2 ( b(λ) + v 2 (λ) ) - K Ω D 8 γ ln(n)σ 2 (67) so that b(λ) + v 2 (λ) ≤ 2 F λ -F 2 + K Ω D 4 γ ln(n)σ 2 . ( 68
)
Combining Eq. ( 66) and (68), we get

∆(λ) ≤ 2θ F λ -F 2 + K Ω C 2 + θK Ω D 4 + K Ω E 2θ γ ln(n)σ 2 so that Eq. (65) implies that (1 -2θ) F λopt(C) -F 2 2 + 2(C -σ 2 ) tr(A λopt(C) ) ≤ inf λ∈Λ (1 + 2θ) F λ -F 2 2 + 2(C -σ 2 ) tr(A λ ) + K Ω C + θK Ω D 2 + K Ω E θ γ ln(n)σ 2 . (69)
E.3 Handling the small terms proportional to tr(A λ )

We will now make use of Lemma 3 for handling the terms (C -σ 2 ) tr(A λ ) that appear in Eq. (69). By Eq. ( 33) with x = 2 Cσ -2 -1 1 C≤σ 2 and Eq. ( 68), for every λ ∈ Λ,

2 C -σ 2 tr(A λ )1 C≤σ 2 ≤ θv 2 ( λ ) + n Cσ -2 -1 2 1 C≤σ 2 σ 2 θ ≤ 2θ F λ -F 2 2 + θK Ω D 4 γ ln(n)σ 2 + n Cσ -2 -1 2 σ 2 θ 1 C≤σ 2 . ( 70
)
Applying Eq. ( 70) with λ = λ opt (C), Eq. ( 69) implies

(1 -4θ) F λopt(C) -F 2 2 ≤ inf λ∈Λ (1 + 2θ) F λ -F 2 2 + 2(C -σ 2 ) tr(A λ ) + n Cσ -2 -1 2 σ 2 θ 1 C≤σ 2 + K Ω C + 3θK Ω D 4 + K Ω E θ γ ln(n)σ 2 , (71)
which proves Eq. (63) since θ ∈ (0, 1/4) . Applying again Eq. (68) and Eq. ( 33) with x = 2 Cσ -2 -1 1 C≥σ 2 , Eq. ( 71) implies

(1 -4θ) F λopt(C) -F 2 2 ≤ inf λ∈Λ (1 + 4θ) F λ -F 2 2 + n Cσ -2 -1 2 σ 2 θ + K Ω C + θK Ω D + K Ω E θ γ ln(n)σ 2 ,
which proves Eq. (64) since θ ∈ (0, 1/4) .

E.4 Proof of Corollary 12

The reasoning is the same as for proving the second part of Proposition 10: we take C Ω according to Lemmas 8 and 9, so that the probability of Ω(Λ, C Ω ) can be lower-bounded by the union bound.

F Proof of Theorem 3

Theorem 3 is a straightforward consequence of Theorems 1 and 2. Indeed, let us first remark the events defined by Theorems 1 and 2 are the same, namely Ω ( α Λ +δ) ln(n) (Λ, C Ω ) for some well-chosen C Ω . So, on Ω ( α Λ +δ) ln(n) (Λ, C Ω ) , by Eq. ( 12) and ( 13),

Cσ -2 -1 ≤ max { β 1 , β 2 } ( α Λ + δ) ln(n) n .
Since Eq. ( 16) also holds on Ω ( α Λ +δ) ln(n) (Λ, C Ω ) , we get Eq. ( 17) with some numerical constant

β 5 ≥ M -2 32 max { β 1 , β 2 } 2 + β 3 + β 4 2 .
We deduce from Eq. ( 17) an oracle inequality in expectation by noting that if n

-1 F λ -F 2 2 ≤ R n,δ on Ω ( α Λ +δ) ln(n) , then E 1 n F λ -F 2 2 = E 1 Ω ( α Λ +δ) ln(n) n F λ -F 2 2 + E 1 Ω c ( α Λ +δ) ln(n) n F λ -F 2 2 ≤ E [ R n,δ ] + 1 n P(Ω c ( α Λ +δ) ln(n) ) E F λ -F 4 2 ≤ E [ R n,δ ] + 1 n C Λ n -δ E F λ -F 4 2 (72)
by Cauchy-Schwarz inequality. Now, remark that for every λ ∈ Λ ,

F λ -F 2 2 ≤ 2 A λ ε 2 + 2 (I -A λ )F 2 ≤ 2M 2 ε 2 + 2 ( 1 + M ) 2 F 2
where we used that |||A λ ||| ≤ M by assumption (HA λ ). So,

E F λ -F 4 2 ≤ E sup λ∈Λ F λ -F 4 2 ≤ 4E M 2 ε 2 + ( 1 + M ) 2 F 2 2 = 4 M 4 E ε 4 + 2 ( 1 + M ) 2 M 2 F 2 E ε 2 + ( 1 + M ) 4 F 4 = 4 M 4 (n 2 + 2n)σ 4 + 2 ( 1 + M ) 2 M 2 F 2 nσ 2 + ( 1 + M ) 4 F 4 ≤ 4 (n + 1)σ 2 M 2 + ( 1 + M ) 2 F 2 2 .
Using also Eq. ( 72) and ( 17), Eq. ( 18) follows, taking δ = 2 .

G Proof of the concentration inequalities G.1 Proof of Proposition 5

The proof of Proposition 5 relies on Corollary 14, which is itself a consequence of a general concentration result (Lemma 13). Both results, which are proved at the end of the subsection, rely on a rather classical argument: a concentration inequality for the supremum of a Gaussian process, and an upper bound for its expectation in terms of entropy. Then, the proof reduces to bounding the length of a C 1 path inside the unit Euclidean ball, which is done in Eq. (74) under the assumptions of Lemma 13. so that Corollary 14 can be applied with D R = 0 and D S = 1 , hence Z = 3n -3 : for every y ≥ 0, an event of probability at least 1e -y on which ∀λ ∈ [0, +∞] ,

|δ 4 (λ)| ≤ 2σ (I n -A λ )F 2y + 12 ln(2 + 4n(3n -2)) + 6 √ π ≤ 2σ (A λ -I n )F √ 2 √ y + 12 2 ln(n) + 6 √ π + 12 ln(12) ≤ 2σ (A λ -I n )F √ 2 + 288 + 1 y + ln(n) + 6 √ π + 12 ln(12) 2 ≤ 35σ (A λ -I n )F y + ln(n) + 874 .
So, for every x ≥ 0 , taking y = xln(n) -874 , an event of probability at least

L(T ) = +∞ 0 n j=1 u ′ 2 j (t) dt ≤ n j=1 +∞ 0 u ′ j (t) dt ≤ 2n(Z + 1) . (74)
Indeed, for every j = 1, . . . , n , either u ′ j ≡ 0 so that +∞ 0 u ′ j (t) dt = 0, or u ′ j has at most Z zeros, so +∞ 0 u ′ j (t) dt is the sum of the amplitudes of variation of u j over at most (Z + 1) intervals, each term being smaller or equal to 2 since |u j (t)| ≤ 1 for every t > 0 by assumption.

Eq. (74) also implies u j (t) has finite limits when t → 0 and when t → +∞ for every j, so u(0) and u(+∞) can be defined by continuity and L(T ) = L(T ) with T := { u(t) s.t. t ∈ [0, +∞] } .

For any set S, let H(δ, S) = ln(N (δ, S)) be the metric entropy of S w.r.t. • . Since T is a continuous path,

∀δ > 0 , N (δ, T ∪ (-T )) ≤ 2N (δ, T ) ≤ 2 L(T ) δ ≤ 2 + 2L(T ) δ . (75)
In particular, H(•, T ∪ (-T )) is integrable at 0, so Theorem 3.18 in [START_REF] Massart | Concentration Inequalities and Model Selection[END_REF] yields

E sup z∈T | ξ, z | = E sup z∈T ∪(-T ) { ξ, z } ≤ 12 1 0 H(δ, T ∪ (-T ))dδ . (76)
Combining Eq. ( 74), ( 75) and (76), we get that Finally, by assumption (Hp), sup z∈T z ≤ 1 , so by Proposition 3.19 in [START_REF] Massart | Concentration Inequalities and Model Selection[END_REF], with probability 1e -x ,

E sup z∈T | ξ, z | ≤ 12
sup z∈T | ξ, z | ≤ E sup z∈T | ξ, z | + √ 2x , (77)
hence the result.

Proof of Corollary 14. First, x(t) is well-defined for every t > 0 since S j has no positive root for all j = 1, . . . , n . Second, x(t) = 0 for every t > 0 since the R j have no common positive root, so that u is well-defined on (0, +∞) . For every t > 0 , let N (t) := x(t) > 0 . Each coordinate x j of x is of class C 1 because it is a well-defined rational fraction, so N also is of class C 1 , as well as each coordinate u j of u and for every t ∈ (0, +∞) and j ∈ { 1, . . . , n } ,

N ′ (t) = x(t), x ′ (t) N (t) u ′ j (t) =
x ′ j (t)N (t)x j (t)N ′ (t)

N (t) 2 = 1 N (t) 3 x ′ j (t) ( N (t) ) 2 -x(t), x ′ (t) x j (t) = 1 N (t) 3 x ′ j (t) n k=1
x k (t) 2x j (t)

n k=1 x k (t)x ′ k (t) = 1 N (t) 3 R ′ j (t)S j (t) -R j (t)S ′ j (t) S j (t) 2 n k=1 R k (t) 2 S k (t) 2 - R j (t) S j (t) n k=1 R k (t)R ′ k (t)S k (t) -( R k (t) ) 2 S ′ k (t) S k (t) 3 = P j (t)
( N (t) ) 3 S j (t) ( n k=1 S k (t) ) 3 for some polynomial P j ∈ R[X], either equal to the null polynomial, or of degree smaller or equal to Z = max { 0 , 3D R + (3n -2)D S -1 } , which proves (Hp) holds true.

G.2 Proof of Proposition 6

The case where M is a diagonal matrix is Lemma 1 in [START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF]. Let us prove how the general case can be reduced to the diagonal case. Let B = 1 2 M ⊤ + M so that Z = X, BXtr(B) . Since B is symmetric, it can be diagonalized in an orthonormal basis: where ξ = P X ∈ R n is a standard Gaussian vector. By Lemma 1 in [START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF], we get that for every x ≥ 0,

P Z ≥ 2 tr(B ⊤ B)x + 2 |||B||| x ≤ e -x .
(It is assumed that d i ≥ 0 in [START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF], but the proof actually does not use it for proving the above inequality.) The result follows since , so that Card(Λ 1 ) ≤ 2n and for every λ ∈ Λ , some λ + , λ -∈ Λ 1 exist such that

|||B| || = 1 2 M ⊤ + M ≤ 1 2 M ⊤ + |||M ||| =
λ -≤ λ ≤ λ + (78)
tr(A λ -) -1 ≤ tr(A λ + ) ≤ tr(A λ ) ≤ tr(A λ -) ≤ tr(A λ + ) + 1 (79)

tr(A ⊤ λ -A λ -) -1 ≤ tr(A ⊤ λ + A λ + ) ≤ tr(A ⊤ λ A λ ) ≤ tr(A ⊤ λ -A λ -) ≤ tr(A ⊤ λ + A λ + ) + 1 . (80)
Using the notation introduced in Section A.4, let ξ = P ε ∼ N (0, σ 2 I n ) , so that Let us now assume the event Ω x Λ 1 , C Ω is realized, so that Eq. ( 27) and ( 28) hold for any λ ∈ Λ 1 . For any λ ∈ Λ , let λ -, λ + ∈ Λ 1 such that Eq. ( 78), (79) and (80) hold true. Then, since λ → A λ ε 2 is non-increasing, for every θ 1 ∈ (0, 1] ,

δ 1 (λ) = A λ ε 2 -σ 2 tr(A ⊤ λ A λ ) ≥ A λ + ε 2 -σ 2 tr(A ⊤ λ A λ )
by Eq. ( 78) So, for every θ 1 ∈ (0, 1] , Eq. ( 38) holds true.

≥ A λ + ε 2 -σ 2 tr(A ⊤ λ + A λ + ) -
Similarly, since λ → ε, A λ ε is non-increasing, for every θ 2 ∈ (0, 1] ,

δ 2 (λ) ≥ -θ 2 σ 2 tr(A ⊤ λ A λ ) -C Ω 3 + C Ω 4 θ -1 2 xσ 2 -σ 2 and δ 2 (λ) ≤ θ 2 σ 2 tr(A ⊤ λ A λ ) + (1 + θ 2 )σ 2 + C Ω 3 + C Ω 4 θ -1 2 xσ 2
So, for every θ 2 ∈ (0, 1] , Eq. ( 39) holds true.

G.4 Proof of Lemma 8

Since Λ is finite by assumption (HΛdis), we use a union bound over λ ∈ Λ. For each λ ∈ Λ, using assumption (HN σ 2 ), σ -1 ε is a standard Gaussian vector.

• By Proposition 6 in Section B.2 with M = ±σ 2 A λ and M = ±σ 2 A ⊤ λ A λ , we deduce that for every x ≥ 0,

P ∀θ > 0, |δ 1 (λ)| ≤ θσ 2 tr(A ⊤ λ A λ ) + 2 |||A λ ||| + θ -1 xσ 2 ≥ 1 -2e -x P ∀θ > 0, |δ 2 (λ)| ≤ θσ 2 tr(A ⊤ λ A λ ) + 2 + θ -1 |||A λ ||| 2 xσ 2 ≥ 1 -2e -x ,
where we used Eq. ( 20), A ⊤ λ A λ ≤ |||A λ ||| 2 , and that tr((A ⊤ λ A λ ) 2 ) ≤ |||A λ ||| 2 tr(A ⊤ λ A λ ) . Eq. ( 27) and (28) follow, using that |||A λ ||| ≤ M by assumption (HA λ ).

• Since δ 3 (λ) = σ -1 ε, 2σA ⊤ λ (I n -A λ )F and δ 4 (λ) = σ -1 ε, 2σ(I n -A λ )F , Proposition 4 in Section B.1 shows, for every x ≥ 0 ,

P ∀θ > 0, |δ 3 (λ)| ≤ θ (I n -A λ )F 2 2 + 2 |||A λ ||| 2 xσ 2 θ ≥ 1 -e -x
and P ∀θ > 0,

|δ 4 (λ)| ≤ θ (I n -A λ )F 2 2 + 2xσ 2 θ ≥ 1 -e -x ,
using Eq. [START_REF] Juditsky | Nonparametric denoising of signals with unknown local structure. I. Oracle inequalities[END_REF]. Eq. ( 29) and (30) follow, using that |||A λ ||| ≤ M by assumption (HA λ ).

G.5 Proof of Lemma 9

Since (Hridge) holds true, we can apply Proposition 7: some Λ 1 exists such that Card(Λ 1 ) ≤ 2n and for every x ≥ 2/3, Ω x-2/3 Λ 1 , C Ω ⊂ Ω x Λ, C Ω . (81)

Figure 1 :

 1 Figure 1: Bias-variance decomposition of the generalization error, and minimal/optimal penalties.

Figure 2 :

 2 Figure2: Selected degrees of freedom vs. penalty strength log(C/σ 2 ) , for a a fixed design problem and kernel ridge regression (top), Nadaraya-Watson estimator (middle) and K-nearest neighbor regression: note that when penalizing by the minimal penalty, there is a strong jump at C = σ 2 , while when using half the optimal penalty, this is not the case. Left: Y i = sin(25πX i ) + ε i , Right: Y i = sin(25πX 3 i ) + ε i .

Figure 3 :

 3 Figure 3: Comparison of various smoothing parameter selection (minimal with two types of jump selection, GCV, Mallows) for various values of numbers of observations. Left:Y i = sin(25πX i ) + ε i , Right: Y i = sin(25πX 3 i ) + ε i .

Lemma 2 .

 2 If assumption (Hridge) holds true, then, tr(A λ ) , tr(A ⊤ λ A λ ) and 2 tr(A λ )tr(A ⊤ λ A λ ) are decreasing continuous functions of λ over [0, +∞] , all equal to n for λ = 0 and to 0 for λ = +∞ ; b(λ) is a nondecreasing continuous function of λ, with b(0) = 0 and b(+∞) = F 2 .

2 .

 2 Section D.2 considers the case C < σ 2 , showing that if A λ 2 = I and λ ∈ Λ satisfies df(λ) ≤ a n , then crit C (λ 2 ) ≤ crit C (λ), hence λ 0 (C) ≥ a n . 3. Section D.3 considers the case C > σ 2 , showing that if λ ∈ Λ satisfies df(λ) ≥ b n , then crit C (λ 1 ) < crit C (λ), hence λ 0 (C) ≤ b n .

  (63) and (64) hold true, with (K Ω C , K Ω D , K Ω E ) replaced by (β 11 , β 12 , β 13 ) where β 11 = 8M β 12 = 8 4M 2 + max 4M 2 , 612.5 and β 13 = 620.5 .

d i ξ 2 i - 1

 1 ∃P ∈ O(n) s.t. B = P ⊤ DP with D = diag ( d 1 , . . . , d n ) . Hence, Z = X ⊤ BXtr(B) = (P X) ⊤ D(P X)tr(D) = n i=1

7 Proposition 1

 71 shows that (Hridge) implies (HA λ ) with M = K df = 1. Let us now consider the concentration inequalities[START_REF] Solnon | Multi-task regression using minimal penalties[END_REF] and[START_REF] Stone | Cross-validatory choice and assessment of statistical predictions[END_REF] for δ 1 and δ 2 . By Lemma 2, a sequenceλ a 1 > • • • > λ a n-1 ∈ Λ exists such that for every j ∈ { 1, . . . , n -1 } , tr(A λ a j ) = j . Similarly, a sequence λ b 1 > • • • > λ b n-1 ∈ Λ exists such that for every j ∈ { 1, . . . , n -1 } , tr(A ⊤ λ b j A λ b j ) = j . Let Λ 1 = 0, λ a 1 , . . . , λ a n-1 , λ b 1 , . . . , λ b n-1

A λ ε 2

 2 nλ both are non-increasing functions of λ since µ j ≥ 0 .

= δ 1 (λ + ) -σ 2 ≥ -θ 1 σ 2 - 1 1xσ 2 - 1 1xσ 2 2 ≤ θ 1 σ 2 - 1 1xσ 2

 12212122212 tr(A ⊤ λ + A λ + ) -C Ω 1 + C Ω 2 θσ 2by Eq. (27)≥ -θ 1 σ 2 tr(A ⊤ λ A λ ) -C Ω 1 + C Ω 2 θσ 2 by Eq. (80)andδ 1 (λ) = A λ ε 2σ 2 tr(A ⊤ λ A λ ) ≤ A λ -ε 2σ 2 tr(A ⊤ λ A λ )by Eq. (78)≤ A λ -ε 2σ 2 tr(A ⊤ λ -A λ -) + σ 2 by Eq. (80) = δ 1 (λ -) + σ tr(A ⊤ λ -A λ -) + C Ω 1 + C Ω 2 θ + σ 2by Eq. (27)≤ θ 1 σ 2 tr(A ⊤ λ A λ ) + (1 + θ 1 )σ 2 + C Ω 1

  Assumption (HA λ ). It holds true with K df = 1 in all the main examples detailed in Section 2.2, as proved by Proposition 1. Note that |||A λ ||| ≤ M barely is an assumption. With M = 1, it means that A λ actually shrinks Y , which holds true for all examples except nearestneighbors and Nadaraya-Watson. In general, since |||A λ ||| is observable, one only has to check that M := sup λ∈Λ |||A λ ||| is not much larger than 1, as we observed in all our simulation experiments. Note that |||A λ ||| ≤ M < +∞ is assumed in[START_REF] Li | Asymptotic optimality for C p , C L , cross-validation and generalized crossvalidation: discrete index set[END_REF] for proving asymptotic optimality results when selecting among nearest-neighbors or Nadaraya-Watson estimators.Assumption (Abias). It holds if b(λ) ≤ nσ 2 c df(λ) -d for some c ≥ 0 and d ≥ 1 (and some λ ∈ Λ exists with df(λ) ≤ √ n close to √ n), a standard assumption in the context of model selection. Besides, (Abias) is much less restrictive and can even be relaxed, see Appendix D. For instance, it is sufficient to have b(λ) ≤ nσ 2 c df(λ) -d for one among several families of estimators, without having to know which one it is.

Acknowledgments

We would like to thank Matthieu Solnon for helping us to improve an earlier version of the paper. We also acknowledge the support of the French Agence Nationale de la Recherche (ANR) under reference ANR-09-JCJC-0027-01 (Detect project) as well as the European Research Council (SIERRA starting grant 239993).

In the kernel ridge regression case, we get a similar result uniformly over Λ = [0, +∞]. Up to the best of our knowledge, Proposition 7 is a new result that could be useful for studying kernel ridge regression in a more general framework. Proposition 7. Assume that (Hridge) holds true. Then, assumption (HA λ ) is satisfied with M = K df = 1, and some Λ 1 ⊂ Λ exists such that Card(Λ 1 ) ≤ 2n and for every C Ω ∈ [0, +∞) 6 and x ≥ 0 , on Ω x Λ 1 , C Ω , for every θ 1 , θ 2 ∈ (0, 1] , for every λ ∈ Λ ,

Remark 9. Proposition 7 does not rely on any assumption on the distribution of the noise ε . Therefore, it can be used in the Gaussian case (combined with Lemma 8), but also under any alternative assumption for which concentration inequalities for δ 1 (λ) and δ 2 (λ) can be proved.

Proposition 7 is proved in Section G.3.

B.3 Lower bounds on the probability of Ω x (Λ)

We are now in position to state lower bounds on the probability of Ω x (Λ, C Ω ) provided C Ω is well-chosen. First, we consider the case of a finite Λ.

Lemma 8. Under assumptions (HΛdis), (HA λ ) and (HN σ 2 ),

Lemma 8, a consequence of Propositions 4 and 6, is proved in Section G.4.

In the kernel ridge regression example, we prove a similar concentration result (with slightly larger constants) uniformly over the continuous set Λ = [0, +∞]. Lemma 9. Under assumptions (Hridge) and (HN σ 2 ),

Lemma 9, a consequence of Propositions 5, 6 and 7, is proved in Section G.5.

C Proof of Proposition 1

We consider separately the examples to which Proposition 1 applies.

C.1 Case (i)

Since A is symmetric, it can be diagonalized in an orthonormal basis, with eigenvalues a 1 , . . . , a n ∈ [0, 1] (by assumption), so that

In particular, in example (ia), A is an orthogonal projection matrix, so A is symmetric with Sp(A) ⊂ [0, 1] and A ⊤ A = A implies tr(A ⊤ A) = tr(A) . For example (ib), by Eq. (31), A is symmetric and Sp(A) ⊂ [0, 1] .

D.1 General starting point

Combining Eq. [START_REF] Cao | On oracle inequalities related to smoothing splines[END_REF] with Eq. ( 23) and [START_REF] Li | Asymptotic optimality for C p , C L , cross-validation and generalized crossvalidation: discrete index set[END_REF], for every C ≥ 0 , λ 0 (C) also minimizes over

On the event Ω γ ln(n) (Λ, C Ω ), using Eq. ( 27), ( 28), ( 29) and [START_REF] Nadaraya | On estimating regression[END_REF], we get for every

and

Taking θ 1 = θ 2 = θ/3 for some θ ∈ (0, 3] , and θ 3 = θ 4 = 1/3 , this implies:

D.2 Below the minimal penalty

We assume in this subsection that C ∈ [0, σ 2 ) and a n ∈ [0, n/2) . Let λ ∈ Λ . Three cases can be distinguished:

First condition on C: case 1 vs. case 3. Comparing Eq. ( 46) and Eq. ( 48), we get that

The right-hand side of the above inequality is smaller than

where we used that a n < n/2 and γ ≥ 2 , and we assumed that n/ ln(n) ≥ L 0 for some L 0 > 0 to be chosen later. Hence, Eq. ( 49) holds as soon as n/ ln(n) ≥ L 0 and

Second condition on C: case 2 vs. case 3. Comparing Eq. ( 47) and Eq. ( 48), we get that

if

The right-hand side of the above inequality is smaller than

where we used that γ ≥ 2 and we assumed that n/ ln(n) ≥ L 0 . Hence, Eq. (51) holds as soon as n/ ln(n) ≥ L 0 and

Combining the two conditions. Finally, we have proved that df( λ 0 (C)) > a n if n/ ln(n) ≥ L 0 and conditions (50) and (52) are both satisfied, hence if

D.3 Above the minimal penalty

We assume in this subsection that C > σ 2 . Let λ ∈ Λ . As in Section D.2, we consider three cases.

1. If K Ω B γ ln(n)/2 ≤ df(λ) ≤ c n , then, using assumption (HA λ ) in Eq. ( 45) yields

2. If df(λ) ≤ K Ω B γ ln(n)/2 , then, using assumption (HA λ ) in Eq. ( 45) with θ = 1 yields

3. If df(λ) ≥ b n , then, using assumption (HA λ ) in Eq. ( 44) yields

Let λ = λ 1 given by assumption (Abiais ′ ). Two cases can occur:

Comparing Eq. (57) and Eq. ( 56), we get that

Using in addition that γ ≥ 2 and β n ≥ n ln(n) , the right-hand side of the above equation is smaller than

assuming that n/ ln(n) ≥ L 2 for some L 2 > 0 to be chosen later. Now, since b n ≥ 20c n /K df , K df b n -2c n ≥ 9K df b n /10 and Eq. ( 58) holds as soon as

Comparing Eq. (60) and Eq. ( 56), we get that

The right-hand side of the above equation is smaller than

B γ ln(n)/K df , so that Eq. (61) holds as soon as

Lemma 13. Let n ∈ N\ { 0 }, Z ≥ 0 . Let ξ be a standard Gaussian vector in R n , and u : (0, +∞) → R n be some function such that

and either u ′ j ≡ 0 or Card t ∈ (0, +∞)

Then, u admits a continuous extension to [0, +∞], and for every x ≥ 0,

Corollary 14. Let D R , D S ∈ N , and for every j ∈ { 1, . . . , n } , let R j ∈ R[X] be a polynomial of degree at most D R , and S j ∈ R[X] be a polynomial of degree at most D S with no positive root. If the polynomials (R j ) 1≤j≤n have no common positive root, then

is well-defined and non-zero, so that u : t → x(t) -1 x(t) is well-defined on (0, +∞) . Moreover, u satisfies the assumption (Hp) with Z = (3D R + (3n -2)D S -1) + , so that Eq. (73) holds true.

We can now prove Proposition 5.

Proof of Proposition 5. Let P be an orthogonal matrix such that Eq. ( 31) holds true (that is, P is an orthogonal matrix which diagonalizes K), ξ = σ -1 P ε and P F = (f j ) 1≤j≤n . Then, ξ is a standard Gaussian vector in R n and for every λ ∈ (0, +∞) ,

Therefore, Corollary 14 can be applied with D R = 0 and D S = 2 , hence Z = 6n -5 : for every y ≥ 0, an event of probability at least 1e -y exists on which ∀λ ∈ [0, +∞] ,

by Cauchy-Schwarz inequality. So, for every x ≥ 0 , taking y = xln(n) -1025.8 , an event of probability at least 1exp(ln(n) + 1025.8) exp(-x) exists on which Eq. ( 34) holds true for every λ ∈ [0, +∞] .

Similarly, for every λ ∈ [0, +∞] ,

Since Λ 1 is finite, and assumptions (HN σ 2 ) and (HA λ ) hold true with M = K df = 1, we get by the first part of proof of Lemma 8 that for every x ≥ 2/3,

Combining Eq. ( 81), ( 82), ( 83) and an union bound, we get for every x ≥ 2/3,

a bound also valid when 0 ≤ x < 2/3 (since it is negative).

H Supplementary material Therefore, the deviation term 2x(tr(M 2 ) + tr(M ⊤ M )) cannot be improved in Eq. (36).

M 2 i,i + tr M 2 + tr M ⊤ M + ( tr(M ) ) 2 so that Eq. (85) holds true (using Lemma 15).