Rejoinder on: Minimal penalties and the slope heuristics: a survey <s> R.4.5. Large collections of models (Section 8.3.4) <s> This paper tackles the problem of selecting among several linear estimators in non-parametric 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. <s> BIB001 </s> Rejoinder on: Minimal penalties and the slope heuristics: a survey <s> R.4.5. Large collections of models (Section 8.3.4) <s> We consider the problem of selecting the best estimator among a family of Tikhonov regularized estimators, or, alternatively, to select a linear combination of these regularizers that is as good as the best regularizer in the family. Our theory reveals that if the Tikhonov regularizers share the same penalty matrix with different tuning parameters, a convex procedure based on $Q$-aggregation achieves the mean square error of the best estimator, up to a small error term no larger than $C\sigma^2$, where $\sigma^2$ is the noise level and $C>0$ is an absolute constant. Remarkably, the error term does not depend on the penalty matrix or the number of estimators as long as they share the same penalty matrix, i.e., it applies to any grid of tuning parameters, no matter how large the cardinality of the grid is. This reveals the surprising "cost-free" nature of optimally tuning Tikhonov regularizers, in striking contrast with the existing literature on aggregation of estimators where one typically has to pay a cost of $\sigma^2\log(M)$ where $M$ is the number of estimators in the family. The result holds, more generally, for any family of ordered linear smoothers. This encompasses Ridge regression as well as Principal Component Regression. The result is extended to the problem of tuning Tikhonov regularizers with different penalty matrices. <s> BIB002
Model selection among a "large" collection (using the terminology introduced in Section 4.7) appears at several places of the discussion. For change-point detection, Émilie Lebarbier provides numerical experiments that support the conjecture of problem (a) in Section 8.3.4, with C ⋆ = σ 2 , which would be a useful result for reasons detailed in Section 8.3.4. For orthonormal variable selection by hard thresholding, Sylvain Sardy suggests that quantile universal thresholding (QUT;  can work well. I conjecture that minimalpenalty algorithms can also work well in such a setting with a large collection of models, because the richness of the collection makes the minimal penalty much larger, as shown by partial theoretical results and numerical experiments reported in Sections 4.7 and 8.3.4). Nevertheless, a major difficulty for the analysis and the practical use of minimal penalties with large collections of models is that the minimal and optimal penalties certainly depend strongly on the noise distribution, which should be added to the conjectures formulated in Section 8.3.4. This is explained well by Lucien Birgé, who points out the role of large-deviation arguments for the analysis of minimal and optimal penalties in this context. David Donoho and Matan Gavish show that a similar phenomenon appears in a slightly different context (factor analysis), as detailed above in Section R.2.2. From the practical point of view, the key problem is that minimal-penalty algorithms can only be used if the relationship between the minimal and optimal penalty is known before observing the data. In particular, if this relationship depends on the (unknown) noise distribution, and if it cannot be easily estimated from the data, then minimal-penalty algorithms are useless. In such cases, the only hope would be to have a universal relationship between the minimal penalty and a suboptimal (but good) penalty, that is, a penalty satisfying an oracle inequality with a bounded leading constant. Hopefully, this seems to be possible in the settings respectively mentioned by David Donoho and Matan Gavish and by Lucien Birgé. R.4.6. Infinite estimator collections (Section 8.3.5) Pierre Bellec shows the noticeable fact that some infinite estimator collections -ordered linear smoothers-can be tuned optimally -with an oracle inequality with leading constant equal to 1 and a remainder term of order σ 2 /n-by an aggregation procedure BIB002 . This phenomenon can be related to the result by BIB001 on kernel ridge regression, that is mentioned in Section 8.3.5. Let me nevertheless point out three important differences. First, the result by BIB002 makes a milder assumption on the estimator collection: kernel ridge regressors form a family of ordered linear smoothers, but other examples exist (see for instance Kneip, 1994, Section 2) . Second, the result by BIB002 does not rely on some explicit discretization of the estimator collection -chaining arguments make such a discretization only implicitly-, hence it could be easier to generalize further, for instance to multivariate families of kernel ridge regressors. Third, the key deviation bound proved by BIB002 includes a non-negative term c (A λ − A * ) 2 , while generalizing the results of BIB001 would require a similar uniform deviation bound without this term. The first two differences make the result of BIB002 quite interesting for generalizing the analysis of minimal-penalty algorithms, but the third difference make me join Pierre Bellec's interrogative statement at the end of his discussion. At least, this should motivate further work on the topic. At a broader level, this underlines that analyzing penalization and aggregation procedures require similar concentration inequalities. Therefore, solving the open problems mentioned in Section 8.6 would have consequences far beyond minimal-penalty algorithms, including the theoretical analysis of aggregation procedures such as Q-aggregation.