Sylvain Arlot
email: sylvain.arlot@u-psud.fr

Minimal penalties and the slope heuristics: a survey Titre: Pénalités minimales et heuristique de pente

Keywords: model selection, estimator selection, penalization, slope heuristics, minimal penalty, residual-variance estimation, L-curve heuristics, elbow heuristics, scree test, overpenalization sélection de modèles, sélection d'estimateurs, pénalisation, heuristique de pente, pénalité minimale, estimation de la variance résiduelle, heuristique de courbe en L, heuristique de coude, test scree, surpénalisation AMS 2000 subject classifications: 62-02, 62G05, 62J05

the slope heuristics as a way to choose optimally from data an unknown multiplicative constant in front of a penalty. It is built upon the notion of minimal penalty, and it has been generalized since to some "minimal-penalty algorithms". This article reviews the theoretical results obtained for such algorithms, with a self-contained proof in the simplest framework, precise proof ideas for further generalizations, and a few new results. Explicit connections are made with residual-variance estimators -with an original contribution on this topic, showing that for this task the slope heuristics performs almost as well as a residual-based estimator with the best model choice-and some classical algorithms such as L-curve or elbow heuristics, Mallows' C p , and Akaike's FPE. Practical issues are also addressed, including two new practical definitions of minimal-penalty algorithms that are compared on synthetic data to previously-proposed definitions. Finally, several conjectures and open problems are suggested as future research directions.

Résumé : Birgé et Massart ont proposé en 2001 l'heuristique de pente, pour déterminer à l'aide des données une constante multiplicative optimale devant une pénalité en sélection de modèles. Cette heuristique s'appuie sur la notion de pénalité minimale, et elle a depuis été généralisée en "algorithmes à base de pénalités minimales". Cet article passe en revue les résultats théoriques obtenus sur ces algorithmes, avec une preuve complète dans le cadre le plus simple, des idées de preuves précises pour généraliser ce résultat au-delà des cadres déjà étudiés, et quelques résultats nouveaux. Des liens sont faits avec les méthodes d'estimation de la variance résiduelle (avec une contribution originale sur ce thème, qui démontre que l'heuristique de pente produit un estimateur de la variance quasiment aussi bon qu'un estimateur fondé sur les résidus d'un modèle oracle) ainsi qu'avec plusieurs algorithmes classiques tels que les heuristiques de coude (ou de courbe en L), C p de Mallows et FPE d'Akaike. Les questions de mise en oeuvre pratique sont également étudiées, avec notamment la proposition de deux nouvelles définitions pratiques pour des algorithmes à base de pénalités minimales et leur comparaison aux définitions précédentes sur des données simulées. Enfin, des conjectures et problèmes ouverts sont proposés comme pistes de recherche pour l'avenir.

Introduction

Model selection attracts much attention in statistics since more than forty years [START_REF] Akaike | Information theory and an extension of the maximum likelihood principle[END_REF][START_REF] Mallows | Some comments on C p[END_REF][START_REF] Burnham | Model Selection and Multimodel Inference[END_REF][START_REF] Massart | Concentration Inequalities and Model Selection[END_REF]. A related and crucial question for machine learning is the data-driven choice of hyperparameters of learning algorithms. Both are particular instances of the estimator-selection problem: given a family of estimators, how to choose from data one among them whose risk is as small as possible? One of the main strategies proposed for estimator (or model) selection is penalization, that is, choosing the estimator minimizing the sum of its empirical risk -how well it fits the data-and some penalty term -whose role is to avoid overfitting. Optimal penalties often depend on at least Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019 one parameter whose data-driven choice is challenging. In the early 2000s, Birgé andMassart (2001b, 2007) pointed out two key facts leading to a novel approach for an optimal data-driven choice of multiplicative constants in front of penalties. Birgé and Massart were considering a rather theoretical question: what is the minimal amount of penalization needed for avoiding a strong overfitting? For least-squares estimators in regression, they noticed that (i) the minimal penalty is equal to half the optimal penalty, and (ii) the minimal penalty is observable. These two facts are called "the slope heuristics"2 and lead to an algorithm for choosing multiplicative constants in front of penalties.

These ideas and the corresponding algorithm have been generalized since to several frameworks (see Section 3-4 and 8), with numerous applications in various fields such as biology [START_REF] Reynaud-Bouret | Adaptive estimation for Hawkes processes; application to genome analysis[END_REF][START_REF] Akakpo | Estimating a discrete distribution via histogram selection[END_REF][START_REF] Bontemps | Clustering and variable selection for categorical multivariate data[END_REF][START_REF] Rau | Co-expression analysis of highthroughput transcriptome sequencing data with Poisson mixture models[END_REF][START_REF] Devijver | Nonlinear network-based quantitative trait prediction from transcriptomic data[END_REF][START_REF] Devijver | Block-diagonal covariance selection for high-dimensional Gaussian graphical models[END_REF], energy [START_REF] Michel | Modélisation de la production d'hydrocarbures dans un bassin pétrolier[END_REF][START_REF] Devijver | Clustering electricity consumers using high-dimensional regression mixture models[END_REF], or text analysis [START_REF] Derman | Clustering and model selection via penalized likelihood for different-sized categorical data vectors[END_REF]; Section 8.3 provides more examples of applications.

In particular, for linear estimators in regression, the original slope heuristics does not work directly and can be modified successfully into a more general "minimal-penalty algorithm" (Arlot andBach, 2009, 2011) detailed in Section 3.

For least-squares regression with projection or linear estimators, the slope heuristics also provides a residual-variance estimator with nice properties (Section 6.1). In the general setting, the slope heuristics can also be seen as a way to give proper mathematical grounds to "L-curve" or "elbow-heuristics" algorithms that are used for choosing regularization parameters in ill-posed problems [START_REF] Hansen | The use of the L-curve in the regularization of discrete ill-posed problems[END_REF], as explained in Sections 6.4-6.5.

Goals

The goals of this survey are the following:

1. to review recent theoretical results about the slope heuristics, and more generally about all minimal-penalty algorithms (Sections 2-4);

2. to help identifying how -and under which assumptions-such results could be generalized to other settings, possibly with new algorithms, by giving a precise account of existing proofs (Sections 2.7, 4.1, and 5), and by identifying several conjectures and open problems suggested by experimental results (Section 8);

3. to make connections between minimal penalties and other classical procedures for residualvariance estimation and for model or estimator selection (Section 6).

Practical issues are only briefly mentioned in Section 7, since more details can be found on these in the survey by [START_REF] Baudry | Slope heuristics: overview and implementation[END_REF].

There is currently no final answer to the question of generalizing minimal-penalty algorithms as much as possible, but we hope that this survey will motivate further theoretical and empirical work in this direction, which could have a great practical impact in statistics, machine learning, and data science in general.

Contributions Let us finally point out some original results appearing in this article. In the framework of least-squares fixed-design regression with projection estimators and Gaussian noise, Theorem 1 validates the slope heuristics in a stronger sense compared to previous results [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF]; it is inspired by [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF] but makes weaker assumptions. Its extension to sub-Gaussian noise (Remark 1 in Section 2.5) is original. As a corollary, Proposition 3 in Section 6.1 is the first precise statement on a slope-heuristics-based residual-variance estimator -more precise than the result that can be derived from [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF]-, showing that it is minimax optimal (up to log(n) factors) under mild assumptions. Proposition 3 provides non-asymptotic bounds (in expectation and with high probability) on this residual-variance estimator, that can be seen as some kind of oracle inequality for residual-variance estimation, which is interesting independently from the slope heuristics.

In the general framework, Propositions 1-2 in Section 5.2 propose two general approaches for justifying minimal-penalty algorithms. These approaches were previously proposed in specific settings [START_REF] Lerasle | Sharp oracle inequalities and slope heuristic for specification probabilities estimation in discrete random fields[END_REF][START_REF] Garivier | Oracle approach and slope heuristic in context tree estimation[END_REF], but their generalization to the setting of Section 3.1 is new. For instance, the application of Proposition 1 to general minimumcontrast estimators with a bounded contrast is new, to the best of our knowledge.

On the practical side, as a complement to the survey by [START_REF] Baudry | Slope heuristics: overview and implementation[END_REF], Section 7 shows original numerical experiments on synthetic data, assessing the performance of the slope heuristics in the least-squares regression framework, for both residual-variance estimation and model selection. Two new practical definitions of the slope heuristics (called 'median' and 'consensus') are proposed and compared to the classical ones. An efficient implementation of one previously-proposed definition is also provided and proved (Algorithm 8 and Proposition 6 in Appendix B.2).

The slope heuristics

This section presents the original "slope heuristics" (Birgé andMassart, 2001b, 2007) in the framework of fixed-design regression, with the least-squares risk and projection estimators. By focusing on this framework, we get most of the flavor of the slope heuristics while keeping the exposition simple.

Framework

The framework considered in Section 2 is the following. We observe

Y = F + ε ∈ R n (1)
where ε 1 , . . . , ε n are independent and identically distributed with mean 0 and variance σ 2 , and F ∈ R n is some (deterministic) signal of interest. For instance, F can be equal to ( f (x i )) 1 i n for some deterministic design points x 1 , . . . , x n ∈ X and f some unknown measurable function X → R, with no assumption on the set X .

The goal is to reconstruct F from Y , that is, to find some t ∈ R n such that its quadratic risk is small, where for every u ∈ R n , u 2 = ∑ n i=1 u 2 i . To this end, for every linear subspace S of R n , the projection estimator or least-squares estimator on S is defined as

F S ∈ argmin t∈S 1 n t -Y 2
where n -1 t -Y 2 is called the empirical risk of t. Since S is a linear subspace, F S exists and is unique: F S = Π S Y where Π S : R n → R n denotes the orthogonal projection onto S. In the following, any linear subspace S of R n is called a model. Let (S m ) m∈M be some collection of models, and for every m ∈ M , let

F m = F S m = Π S m Y and Π m = Π S m .
In this survey, we assume that the goal of model selection is to choose from data some m ∈ M such that the quadratic risk of F m is minimal. The best choice would be the oracle:

m ∈ argmin m∈M 1 n F m -F 2 ,
which cannot be used since it depends on the unknown signal F. Therefore, the goal is to define a data-driven m satisfying an oracle inequality

1 n F m -F 2 K n inf m∈M 1 n F m -F 2 + R n (2)
with large probability, where the leading constant K n should be close to 1 -at least for large nand the remainder term R n should be small compared to the oracle risk inf m∈M {n -1 F m -F 2 }.

Optimal penalty

Many classical selection methods are built upon the "unbiased risk estimation" heuristics: If m minimizes a criterion crit(m) such that

∀m ∈ M , E crit(m) ≈ E 1 n F m -F 2 ,
then m satisfies with large probability an oracle inequality such as Eq. ( 2) with an optimal constant K n = 1 + o(1). This can be proved by showing a concentration inequality for Π m ε 2 and ε, (I n -Π m )F around their expectations for all m ∈ M , where I n denotes the identity matrix of R n , see Section 2.7. For instance, cross-validation [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 of minimizing the sum of the empirical risk and a penalty term, that is, using a criterion of the form:

crit(m) = 1 n F m -Y 2
+ pen(m) .

(3) The unbiased risk estimation heuristics, also called Mallows' heuristics, then leads to the optimal (deterministic) penalty pen opt,0 (m

) := E 1 n F m -F 2 -E 1 n F m -Y 2 . ( 4
)
When F m = Π m Y , we have

F m -F 2 = (I n -Π m )F 2 + Π m ε 2 (5)
and

F m -Y 2 = F m -F 2 + ε 2 -2 ε, Π m ε + 2 ε, (I n -Π m )F , (6)
where ∀t, u ∈ R n , t, u = ∑ n i=1 t i u i . Since the ε i are independent, centered, with variance σ 2 , Eq. ( 5) and Eq. ( 6) imply that

E 1 n F m -F 2 = 1 n (I n -Π m )F 2 + σ 2 D m n , (7)
E 1 n F m -Y 2 = 1 n (I n -Π m )F 2 + σ 2 (n -D m ) n , (8)
and pen opt,0 (m) + σ 2 = 2σ 2 D m n =: pen opt (m) ,

where D m := dim(S m ). Note that the optimal penalties (9) and ( 4) differ by an additive constant σ 2 , which does not change the argmin of the penalized criterion (3); this choice simplifies formulas involving pen opt . Eq. ( 7) is classically known as a bias-variance decomposition of the risk: the first termcalled approximation error or bias-decreases when S m gets larger, while the second termcalled estimation error or variance-increases when S m gets larger, see Figure 1 left. Eq. ( 8) shows that the expectation of the empirical risk decreases when S m gets larger, as expected since F m is defined as a minimizer of the empirical risk, see Figure 1 left.

The expression of the optimal penalty in Eq. ( 9) leads to Mallows' C p [START_REF] Mallows | Some comments on C p[END_REF], where σ 2 is replaced by some estimator σ 2 . Several approaches exist for estimating σ 2 , see Section 6.1.

The slope heuristics provides a data-driven estimation of the unknown constant σ 2 in front of the penalty shape D m /n thanks to the notion of minimal penalty.

Minimal penalty and the slope heuristics

Eq. ( 9) shows that the shape pen 1 (m) = D m /n of the optimal penalty is known, even when σ 2 is unknown. A natural question is to determine the minimal value of the constant that should be put in front of pen 1 (m). More precisely, if for every C 0

m(C) ∈ argmin m∈M 1 n F m -Y 2 +C D m n , (10)
what is the minimal value of C such that m(C) stays a "reasonable" choice, that is, avoids strong overfitting, or equivalently, satisfies an oracle inequality like Eq. ( 2) with K n = O(1) as n tends to infinity? In order to understand how m(C) behaves as a function of C, let us consider, for every C 0,

m (C) ∈ argmin m∈M E 1 n F m -Y 2 +C D m n = argmin m∈M crit C (m) with crit C (m) := 1 n (I n -Π m )F 2 + (C -σ 2 )D m , (11)
by Eq. ( 8). Provided that we can prove some uniform concentration inequalities for F m -Y 2 , m ∈ M , we can expect m (C) to be close to m(C). Let us assume that for D m large enough the approximation error n -1 (I n -Π m )F 2 is almost constant. For simplicity, let us also assume that the approximation error is a decreasing function of D m -which holds for instance if the S m are nested. Then, two cases can be distinguished with respect to C : -if C < σ 2 , then crit C (m) is a decreasing function of D m , and D m (C) is huge: m (C) overfits.

-if C > σ 2 , then crit C (m) increases with D m for D m large enough, so D m (C) is much smaller. This behavior is illustrated on the right part of Figure 1. In other words, pen min (m) := σ 2 D m n (12)

seems to be the minimal amount of penalization needed so that a minimizer m of the penalized criterion (3) does not clearly overfit. The above arguments are made rigorous in Section 2.5, showing that σ 2 D m /n is indeed a minimal penalty in the current framework.

We can now summarize the slope heuristics into two major facts. First, from Eq. ( 9) and ( 12), we get a relationship between the optimal and minimal penalties: pen opt (m) = 2 pen min (m) .

(13)

Second, the minimal penalty is observable, since D m(C) decreases "smoothly" as a function of C everywhere except around C = σ 2 where it jumps.

Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

Data-driven penalty algorithm

The two major facts of the slope heuristics described above directly lead to a data-driven penaltization algorithm, which can be formalized in two ways.

Dimension jump

First, we can estimate the minimal penalty by looking for a jump of C → D m(C) , and make use of Eq. ( 13) to get an estimator of the optimal penalty.

Algorithm 1 (Slope-heuristics algorithm, jump formulation). Input: F m -Y 2 m∈M . 1. Compute ( m(C)) C 0 , where m(C) is defined by Eq. (10).

2. Find C jump > 0 corresponding to the "unique large jump" of C → D m(C) .

Select m

Alg.1 ∈ argmin m∈M n -1 F m -Y 2 + 2 C jump D m /n . Output: m Alg.1 .
The left part of Figure 2 shows one instance of the plot of C → D m(C) , with one clear jump corresponding to C jump . Computational issues are discussed in Section 7.2; in particular, step 1 of Algorithm 1 can be done efficiently, see Appendix B.1. Step 2 of Algorithm 1 can be done in several ways, see Section 7.1. The practical problems arising with step 2 of Algorithm 1 can motivate the use of an alternative algorithm that we detail below.

Slope estimation

As explained in Section 2.3, the reason why D m(C) jumps around C ≈ σ 2 is that by Eq. ( 8), where a(m) := (I n -Π m )F 2 + nσ 2 . Let us assume that a(m) -or equivalently, the approximation error-is almost constant for all m such that D m is large enough. Then, considering only models with a large dimension, the empirical risk approximately has a linear behavior as a function of D m , with slope -σ 2 /n. Since the empirical risk is observable, one can estimate this slope in order to get an estimator of σ 2 , and plug it in the optimal penalty given by Eq. ( 9).

1 n E F m -Y 2 = a(m) -σ 2 D
Algorithm 2 (Slope-heuristics algorithm, slope formulation). Input: ( F m -Y 2 ) m∈M .

1. Estimate the slope S of F m -Y 2 as a function of D m for all m ∈ M with D m "large enough", for instance by (robust) linear regression, and define C slope = -n S.

2. Select m Alg.2 ∈ argmin m∈M {n -1 F m -Y 2 + 2 C slope D m /n}.

Output: m Alg.2 .

The right part of Figure 2 shows an instance of the plot of n -1 F m -Y 2 as a function of D m . Algorithm 2 relies on the choice of what is a "large enough" dimension, on how the slope C slope is estimated, and on the assumption that the approximation error is almost constant among large models -otherwise it can fail strongly, as shown in Section 7.1. Therefore, Algorithms 1 and 2 both have pros and cons, and there is no universal choice between them. The links between Algorithms 1 and 2, as well as their differences, are discussed in Section 7.1.

What can be proved mathematically

A major interest of the slope heuristics is that it can be made rigorous. For instance, we prove in Section 2.7 the next theorem.

Theorem 1. In the framework described in Section 2.1, assume that M is finite, contains at least one model of dimension at most n/20, and that

∃m 1 ∈ M , S m 1 = R n (HId)
and ε ∼ N (0, σ 2 I n ) .

(HG)

Recall that for every C 0, m(C) is defined by Eq. (10). Then, for every γ 0, some n 0 (γ) exists such that if n n 0 (γ), with probability at least 1 -4 card(M )n -γ , the following inequalities hold simultaneously:

∀C 1 -η - n σ 2 , D m(C) 9n 10 , ( 14
) ∀C 1 -η - n σ 2 , 1 n F m(C) -F 2 7σ 2 8 , (15)
∀C 1 + η + n σ 2 , D m(C) n 10 , ( 16
) ∀C > σ 2 , 1 n F m(C) -F 2 h C σ 2 inf m∈M 1 n F m -F 2 + 20σ 2 γ log(n) n , (17)
Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

and for every η ∈ (0, 1/2] and C ∈ (2η)σ 2 , (2 + η)σ 2 ,

1 n F m(C) -F 2 (1 + 3η) inf m∈M 1 n F m -F 2 + 880σ 2 γ log(n) ηn , (18)
where

σ 2 η + n = 40 inf m∈M / D m n/20 1 n (I n -Π m )F 2 + 82σ 2 γ log(n) n , η - n = 41 γ log(n) n , and ∀u > 1 , h(u) = 10 (u -1) 4 1 u∈(1,2) + u 3 1 u 2 .
Theorem 1 revisits results first obtained by [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF], formulating them similarly to [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF] but with milder assumptions.

What Theorem 1 proves about Algorithms 1-2 Eq. ( 14) and ( 16) do not show exactly that there is a single large jump in C → D m(C) , as in the heuristic reasoning of Section 2.3. We cannot hope to prove it since numerical experiments show that the global jump of D m(C) can be split into several small jumps within a small interval of values of C, see Figure 5 in Section 7.1. Nevertheless, Eq. ( 14) and ( 16) imply that the variation of D m(C) over a geometric window of C is extremely strong around σ 2 : if C jump in Algorithm 1 is defined as

C window = C window (η) ∈ argmax C>0 D m(C/[1+η]) -D m(C[1+η]) (19)
with η = max{η - n , η + n }, then C window is close to σ 2 -see Proposition 3 in Section 6.1 for a precise statement-, and Eq. ( 18) implies a first-order optimal oracle inequality for the modelselection procedure of Algorithm 1. Note that C window can be computed efficiently, see Section 7.2 and Appendix B.2. In addition, Eq. ( 14) and ( 16) imply that

C thr. = C thr. (T n ) := inf C 0 / D m(C) T n (20)
is close to σ 2 when T n ∈ [n/10, 9n/10] -precise statements are provided by Proposition 3 in Section 6.1-, and Eq. ( 18) implies a first-order optimal oracle inequality for the corresponding model-selection procedure. See Section 7.1 for practical comments about these variants of Algorithm 1. Theorem 1 does not prove that Algorithm 2 works, and it seems difficult to prove such a result without adding some assumptions. Indeed, the key heuristics behind Algorithm 2 is a linear behavior of the empirical risk as a function of the dimension, at least for large models. In the proof of Theorem 1, we control the deviations of the empirical risk around its expectation, but this is not sufficient for justifying Algorithm 2 without a strong uniform control on the approximation errors of the models, an assumption much stronger than the ones of Theorem 1.

Note finally that Eq. ( 15) and ( 17) are not necessary for justifying Algorithm 1, but they are interesting for theory since they justify the term "minimal penalty". Eq. ( 15) is a straightforward consequence of Eq. ( 14), and results like Eq. ( 17) are easier to obtain than Eq. ( 18), see Section 4.4. Variant of Theorem 1 If M contains at least one model of dimension at most c n ∈ [0, n), on the event defined in Theorem 1, we can actually prove that more results hold true: we can change Eq. ( 14) and ( 16) respectively into

∀a n < n , ∀C 1 -η - n (a n ) σ 2 , D m(C) a n (21) ∀b n > c n , ∀C 1 + η + n (b n , c n ) σ 2 , D m(C) b n (22)
where

σ 2 η + n (b n , c n ) := n b n -c n 2B(c n ) + 4.1σ 2 γ log(n) n , B(c n ) := inf m∈M / D m c n 1 n (I n -Π m )F 2 , and η - n (a n ) := 4.1 1 - a n n -1 γ log(n) n .
In particular, under the assumptions of Theorem 1, taking a n ∈ (9n/10, n), b n ∈ (n/20, n/10) and c n = n/20, we get a larger jump of D m(C) -hence easier to detect-by considering a larger window of values of C, hence reducing the precision of the estimation of σ 2 .

Relaxation of the noise assumption Assumption (HG) is a classical noise model for proving non-asymptotic oracle inequalities. In Theorem 1, it is only used for proving some concentration inequalities at the beginning of the proof -Eq. ( 23)-( 24) in Section 2.7-, so it could be changed into any noise assumption ensuring that similar concentration inequalities hold true. For instance, Theorem 1 can be generalized to the case of sub-Gaussian noise, as formalized below.

Remark 1 (Generalization of Theorem 1 to sub-Gaussian noise). Assume that the (ε i ) 1 i n are centered, independent, and (φ 2 σ 2 )-sub-Gaussian for some φ > 0 -with any definition of sub-Gaussianity among the classical ones since they are all equivalent up to numerical constants (Boucheron et al., 2013, Section 2.3). Then, by the Cramér-Chernoff method [START_REF] Boucheron | Concentration Inequalities: A Nonasymptotic Theory of Independence[END_REF], Section 2.2), Eq. (24) holds true with probability at least 1 -2 exp(x/φ 2 ). In addition, Bellec (2019, Theorem 3) shows that Eq. (23) holds true with probability at least 1 -2 exp[x/(Lφ 2 )] for some numerical constant L. Therefore, the event Ω Lφ 2 x defined in the proof of Theorem 1 has a probability at least 1 -4 card(M )e -x . So, the result of Theorem 1 holds true with x (resp. γ) replaced by Lφ 2 x (resp. Lφ 2 γ) in n 0 , η - n , η + n , and in the risk bounds (17)-( 18). The same generalization holds for Eq. ( 21)-( 22) and for consequences of Theorem 1 such as Proposition 3.

Comments on the assumptions on M Assumption (HId) is barely an assumption since we can always add such a model to the collection considered (and it will never be selected by the procedure). It is used in the proof of Eq. ( 14) where we need to make sure that a model of large dimension and small bias exists.

Theorem 1 implicitly assumes that M contains a model of dimension at most n/20 with a small approximation error. This is much milder than the assumption of the corresponding results of Arlot andBach (2009, 2011) and [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF], which is that M contains a model of dimension at most √ n with an approximation error upper bounded by σ 2 log(n)/n. Here, having a model of dimension n/20 with approximation error σ 2 / log(n) is sufficient to get a consistent estimation of σ 2 and a first-order optimal model-selection procedure. Note however that such an assumption seems almost necessary for Algorithm 1 to work: if the approximation error never vanishes for a (not too) large model, and if it is not almost constant among large models -which can happen in practice-, we conjecture that the slope heuristics fails.

Finally, M is assumed to be finite, but Theorem 1 implicitly assumes a little more, since the event on which the result holds has a large probability only if card(M )n -γ is small, which requires to take γ large enough. Since γ appears in all the bounds, assuming that it can be chosen fixed as n grows is equivalent to assuming that card(M ) grows at most like a power of n, which excludes model collections of exponential complexity -that is, card(M ) ∝ a n for some a > 0. The case of exponential collections is discussed in Sections 4.7 and 8.3.4.

Bibliographical remarks

Algorithms The slope heuristics and the corresponding data-driven penalty were first proposed by Birgé and Massart in a preprint [START_REF] Birgé | A generalized Cp criterion for Gaussian model selection[END_REF] and the subsequent article [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF]. They are also exposed by [START_REF] Massart | A non-asymptotic theory for model selection[END_REF], Blanchard and Massart (2006, Section 2), Massart (2007, Section 8.5.2) and [START_REF] Massart | Sélection de modèles: de la théorie à la pratique[END_REF].

The term "slope" corresponds to the linear behavior of the empirical risk as a function of the dimension, as Algorithm 2 exploits.

The first implementation of data-driven penalties built upon the slope heuristics was expressed as a slope estimation, as in Algorithm 2; it was done by Letué (2000, Section A.4) for penalized maximum likelihood, inspired by a preliminary version of the preprint by [START_REF] Birgé | A generalized Cp criterion for Gaussian model selection[END_REF].

Several practical issues with Algorithm 2 were underlined in the context of change-point detection by Lebarbier (2002, Chapter 4), who then suggested to prefer the "dimension jump" formulation of Algorithm 1 which was present in the final version of the preprint by [START_REF] Birgé | A generalized Cp criterion for Gaussian model selection[END_REF], as well as in the articles by [START_REF] Massart | A non-asymptotic theory for model selection[END_REF] and [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF]. The drawbacks of Algorithm 1 were also underlined by [START_REF] Lebarbier | Quelques approches pour la détection de ruptures à horizon fini[END_REF][START_REF] Lebarbier | Detecting multiple change-points in the mean of a Gaussian process by model selection[END_REF] where some automatic ways to detect the dimension jump were proposed and tested on some synthetic data. Later on, [START_REF] Baudry | Slope heuristics: overview and implementation[END_REF] studied more deeply the practical use of Algorithms 1 and 2, with several variants (see also Section 7). The first proposition of detecting a jump over some sliding window was made by [START_REF] Bontemps | Clustering and variable selection for categorical multivariate data[END_REF], who considered only a finite set of values of C; to the best of our knowledge, the continuous formulation for C window is new, as well as the corresponding algorithm in Appendix B.2.

Theory The first theoretical results about the slope heuristics were proved in the setting of the present section, that is, regression on a fixed design with the least-squares risk and projection (least-squares) estimators. In the articles by Birgé andMassart (2001b, 2007), the first results obtained were similar to Eq. ( 14), ( 15), (17), and (18), making slightly stronger assumptions. A result similar to Eq. ( 15) was even published previously by Birgé and Massart (2001a), but only in the restrictive case F = 0.

The first result showing the existence of a jump -that is, Eq. ( 14) and ( 16) holding simultaneously for all C on the same large-probability event-was obtained for least-squares regression on a random design with regressogram estimators [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF]. It was then proved in the fixed-design setting with more general estimators including projection estimators (Arlot andBach, 2009, 2011).

Eq. ( 17) is a corollary of a classical non-asymptotic oracle inequality for C p -like penalties; similar results were known before the introduction of the slope heuristics (see for instance [START_REF] Barron | Risk bounds for model selection via penalization[END_REF]. Eq. ( 18) is more precise because of the constant 1 + o(1) in front of the oracle risk, which was first obtained by Birgé andMassart (2001b, 2007).

The extension of Theorem 1 to sub-Gaussian noise (Remark 1 in Section 2.5) is new, to the best of our knowledge.

Proof of Theorem 1

The proof mixes ideas from [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF] and [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF]. We split it into three main steps, the last two ones being split themselves into several substeps: (1) using concentration inequalities, (2) proving the existence of a dimension jump (Eq. ( 14)-( 16)), and (3) proving risk bounds thanks to a general oracle inequality (Eq. ( 17)-( 18)).

We define n 0 (γ) as the smallest integer such that γ log(n)/n 1/80 2 for every n n 0 (γ). At various places in the proof (in steps 2.3, 3.2, and 3.3), we make use of the inequality: for all a, b, θ > 0, 2 √ ab θ a + θ -1 b.

Step 1: concentration inequalities As explained in Section 2.3, the slope heuristics relies on the fact that F m -Y 2 is close to its expectation. Let x 0 be fixed. Given Eq. ( 5)-( 6), for every m ∈ M , we consider the event Ω m,x on which the following two inequalities hold simultaneously:

ε, Π m ε -σ 2 D m 2σ 2 √ xD m + 2xσ 2 (23) ε, (I n -Π m )F σ √ 2x (I n -Π m )F . (24)
Under (HG), by standard Gaussian concentration results (for instance, Arlot and Bach, 2011, Propositions 4 and 6)-, we have

P (Ω m,x ) 1 -4e -x .
Then, defining Ω x := m∈M Ω m,x , the union bound gives

P (Ω x ) 1 -4 card(M )e -x
and it is sufficient to prove that Eq. ( 14)-( 18) hold true on Ω x with x = γ log(n).

From now on, we restrict ourselves to the event Ω x .

Step 2: existence of a dimension jump For proving Eq. ( 14) and ( 16 Step 2.1: control of the difference between crit C (m) and the quantity minimized by m(C) Let C 0. By Eq. ( 10), ( 5), and (6), since ε 2 does not depend from m, m(C) minimizes over

M the function G C : M → R defined by ∀m ∈ M , G C (m) := 1 n F m -Y 2 +C D m n - 1 n ε 2 = 1 n (I n -Π m )F 2 - 1 n ε, Π m ε +C D m n + 2 n ε, (I n -Π m )F = crit C (m) - 1 n ε, Π m ε -σ 2 D m + 2 n ε, (I n -Π m )F
where crit C is defined by Eq. ( 11). Therefore, by Eq. ( 23)-( 24) and using D m n, for every

m ∈ M , G C (m) -crit C (m) 2σ 2 x n + x n + 2σ √ 2x n (I n -Π m )F . ( 25
)
Step 2.2: lower bound on D m(C) when C is too small (proof of Eq. ( 14)

) Let C ∈ [0, σ 2 ). Since m(C) minimizes G C (m) over m ∈ M , it is sufficient to prove that if C (1 -η - n )σ 2 , G C (m 1 ) < inf m∈M , D m <9n/10 G C (m) (26)
where m 1 is given by (HId). On the one hand, by Eq. ( 25),

G C (m 1 ) crit C (m 1 ) + 2σ 2 x n + x n = C -σ 2 + 2σ 2 x n + x n . ( 27
)
On the other hand, by Eq. ( 25), for any m ∈ M such that D m < 9n/10,

G C (m) (C -σ 2 )D m n -2σ 2 x n + x n + 1 n (I n -Π m )F 2 - 2σ √ 2x n (I n -Π m )F > 9 10 (C -σ 2 ) -2σ 2 x n + 2x n . ( 28
)
To conclude, the upper bound in Eq. ( 27) is smaller than the lower bound in Eq. ( 28) when 14). Remark that the same reasoning with 9n/10 replaced by any a n ∈ [0, n) proves that D m(C) a n for every

C σ 2 1 -40 x n -60 x n =: C 1 (x) . ( 29
) Taking x = γ log(n), for n n 0 (γ), we have C 1 (x) σ 2 (1 -η - n ) hence Eq. (
C σ 2 1 - 4 x n + 6 x n 1 -a n n =: C 1 (x; a n ) . (30)
We get Eq. ( 21) by taking x = γ log(n) and using that x/n 1/60 2 since n n 0 (γ). Step 2.3: upper bound on D m(C) when C is large enough (proof of Eq. ( 16)) Let C > σ 2 . Similarly to the proof of Eq. ( 14), it is sufficient to prove that if

C (1 + η + n )σ 2 , G C (m 2 ) < inf m∈M , D m >n/10 {G C (m)} (31)
where m 2 ∈ argmin m∈M / D m n/20 (I n -Π m )F 2 exists by assumption. For any c n ∈ [0, n], let us define

B(c n ) := inf m∈M / D m c n 1 n (I n -Π m )F 2 ,
so that m 2 has an approximation error equal to B(n/20). On the one hand, by Eq. ( 25),

G C (m 2 ) crit C (m 2 ) + 2σ 2 x n + x n + 2σ √ 2x n (I n -Π m 2 )F 2 n (I n -Π m 2 )F 2 + (C -σ 2 )D m 2 n + 2σ 2 x n + 2x n 2B n 20 + (C -σ 2 ) n/20 n + 2σ 2 x n + 2x n . ( 32
)
On the other hand, by Eq. ( 25), for any

m ∈ M such that D m > n/10, G C (m) > n/10 n (C -σ 2 ) -2σ 2 x n + 2x n . (33)
To conclude, the upper bound in Eq. ( 32) is smaller than the lower bound in Eq. ( 33) when

C σ 2 1 + 80 x n + 2x n + 40B n 20 =: C 2 (x) . (34)
Taking x = γ log(n), for n n 0 (γ), we have C 2 (x) σ 2 (1 + η + n ) hence Eq. ( 16). Remark that if M contains a model of dimension at most c n ∈ [0, n), the same reasoning with n/10 replaced by any b n ∈ (c n , n] and n/20 replaced by c n proves that D m(C) b n for every

C σ 2 1 + 4n b n -c n x n + 2x n + 2n b n -c n B(c n ) =: C 2 (x; b n ; c n ) . (35)
We get Eq. ( 22) by taking x = γ log(n) and using that x/n 1/80 2 since n n 0 (γ).

Until the end of the proof, we fix x = γ log(n).

Step 2.4: lower bound on the risk of large models (proof of Eq. ( 15)) This is a straightforward consequence of Eq. ( 14). Indeed, on Ω x , for any m ∈ M such that D m 9n/10,

1 n F -F m 2 = 1 n (I n -Π m )F 2 + 1 n ε, Π m ε σ 2 n D m -2 √ xD m -2x = σ 2 n √ D m - √ x 2 -3x 7σ 2 8 ,
where we use that x/n 1/77 2 since n n 0 (γ). Step 3: upper bounds on the risk For proving Eq. ( 17)-( 18), we prove a slightly more general oracle inequality -Eq. ( 43)-using the classical approach used for instance by Birgé and Massart (2001a), [START_REF] Massart | Concentration Inequalities and Model Selection[END_REF] and [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF].

Step 3.1: general approach for proving an oracle inequality Following Section 2.2, an ideal penalty is

pen id (m) := 1 n F m -F 2 - 1 n F m -Y 2 + ε 2
which has expectation 2σ 2 D m /n = pen opt (m). A key argument for getting an oracle inequality is that pen id (m) concentrates around its expectation. Indeed, let us define

∆(m) := pen id (m) - 2σ 2 D m n = 2 n ε, Π m ε -σ 2 D m - 2 n ε, (I n -Π m )F , (36)
where the second formulation is a consequence of Eq. ( 6). Then, by Eq. ( 10), for any C 0 and

m ∈ M , 1 n F m(C) -Y 2 + CD m(C) n 1 n F m -Y 2 + CD m n which is equivalent to 1 n F m(C) -F 2 -∆ m(C) + (C -2σ 2 )D m(C) n 1 n F m -F 2 -∆(m) + (C -2σ 2 )D m n . (37)
It remains to show that ∆(m) and (C -2σ 2 )D m /n are small compared to n -1 F m -F 2 for all m ∈ M . Recall that we restrict ourselves to the event Ω x until the end of the proof, with x = γ log(n).

Step 3.2: control of ∆(m) By Eq. ( 23), (24), and (36), for every m ∈ M and θ > 0,

∆(m) 2 n 2σ 2 √ xD m + 2σ 2 x + σ √ 2x (I n -Π m )F 2θ E 1 n F m -F 2 + σ 2 x n 3θ -1 + 4 . ( 38
)
Step 3.3: upper bound on the expected risk in terms of risk By Eq. ( 5) and ( 24), for every m ∈ M and θ > 0,

F m -F 2 = E F m -F 2 + ε, Π m ε -σ 2 D m E F m -F 2 -σ 2 2 √ xD m + 2x 1 -θ E F m -F 2 -xσ 2 2 + θ -1
so that, for every θ ∈ (0, 1), Step 3.4: control of the remainder terms appearing in Eq. (37) Combining Eq. ( 38) and ( 39), we get on the one hand that for every m ∈ M , θ > 0, θ ∈ (0, 1),

E F m -F 2 1 1 -θ F m -F 2 + κ(θ )xσ 2 with κ(θ ) := 2 + 1 θ 1 -θ . ( 39
)
∆(m) + (2σ 2 -C)D m n 2θ + 2 - C σ 2 + E 1 n F m -F 2 + σ 2 x n 3 θ + 4 2θ + 2 -C σ 2 + 1 -θ 1 n F m -F 2 + σ 2 x n 3 θ + 4 + κ(θ ) 2θ + 2 - C σ 2 + . ( 40
)
On the other hand, similarly, for every m ∈ M , θ > 0, θ ∈ (0, 1),

-∆(m) + (C -2σ 2 )D m n 2θ + C σ 2 -2 + 1 -θ 1 n F m -F 2 + σ 2 x n 3 θ + 4 + κ(θ ) 2θ + C σ 2 -2 + . ( 41
)
Step 3.5: proof of a general oracle inequality Combining Eq. ( 37), (40), and (41) above with θ = 2θ ∈ (0, 1), we get that for every θ ∈ (0, 1/2) and m ∈ M ,

1 - 2θ + 2 -C σ 2 + 1 -2θ 1 n F m(C) -F 2 1 + 2θ + C σ 2 -2 + 1 -2θ 1 n F m -F 2 + σ 2 x n R 1 (θ ,Cσ -2 ) (42) with R 1 (θ ,Cσ -2 ) := 6 θ + 8 + κ(2θ ) 4θ + C σ 2 -2 .
Let us assume C > σ 2 . For any δ ∈ (0, 1], we choose

θ = θ (δ ,Cσ -2 ) := δ 4 1 -2 -C σ 2 + 2 1 + C σ 2 -2 + + δ 1 -2 -C σ 2 + < δ 4 1 4 . So, if C (1 + δ )σ 2 , we have C > (1 + 4θ
)σ 2 hence we can divide both sides of Eq. ( 42) by where the last equality uses θ = θ (δ ,Cσ -2 ). So, if C (1 + δ )σ 2 , Eq. ( 42) leads to

1 - 2θ + 2 -C σ 2 + 1 -2θ > 0 . Remark that 1 + 2θ + C σ 2 -2 + 1 -2θ × 1 - 2θ + 2 -C σ 2 + 1 -2θ -1 = 1 + C σ 2 -2 + 1 -4θ -2 -C σ 2 + = 1 + C σ 2 -2 + 1 -2 -C σ 2 + +δ
1 n F m(C) -F 2 1 + C σ 2 -2 + 1 -2 -C σ 2 + + δ inf m∈M 1 n F m -F 2 + σ 2 x n R 2 δ , C σ 2 (43)
where for every δ ∈ (0, 1] and u ∈ (1, +∞),

R 2 (δ , u) = R 1 θ (δ , u), u 10 + 2|u -2| θ (δ , u) -1 .
Therefore, for every

C (1 + δ )σ 2 , R 2 δ , C σ 2 8 δ 5 + |Cσ -2 -2| max 2 + (Cσ -2 -2) + , 2 1 -(2 -Cσ -2 ) + 2 .
Step 3.6: risk bound for m(C) when C is large enough (proof of Eq. ( 17)) In this step, we assume C > σ 2 . When C/σ 2 ∈ (1, 2], Eq. ( 43) with

δ = Cσ -2 -1 ∈ (0, 1] yields 1 n F m(C) -F 2 2 C σ 2 -1 -1 inf m∈M 1 n F m -F 2 + 96σ 2 x n C σ 2 -1 -3
.

When C/σ 2 2, Eq. ( 43) with δ = 1 yields

1 n F m(C) -F 2 C σ 2 inf m∈M 1 n F m -F 2 + 20σ 2 x n C σ 2 2 .
Eq. ( 17) follows.

Step 3.7: oracle inequality for m(C) when C is close to 2σ 2 (proof of Eq. ( 18)) Now, we assume

C/σ 2 ∈ [2 -η, 2 + η] with η ∈ [0, 1/2]. Taking δ = η in Eq. (43) yields 1 n F m(C) -F 2 max 1 + η , 1 1 -η + η × inf m∈M 1 n F m -F 2 + σ 2 x n 8 η (5 + η) max 2 + η , 2 (1 -η) 2 (1 + 3η) inf m∈M 1 n F m -F 2 + σ 2 x n 8 η (1 + 3η) (5 + η) max 2 + η , 2 (1 -η) 2 (1 + 3η) inf m∈M 1 n F m -F 2 + 880σ 2 x ηn ,
using that 1/(1η) 1 + 2η for every η ∈ [0, 1/2]. Eq. ( 18) follows.

Generalizing the slope heuristics

The slope heuristics has first been formulated and theoretically validated in the framework of Section 2. Then, it rapidly became a more general heuristics for building data-driven optimal penalties. This section discusses two possible formulations for its generalization.

General framework

Before going any further, we need to introduce a general model/estimator-selection framework.

Let S be some set, R : S → [0, +∞) be some risk function, and assume that our goal is to build from data some estimator s ∈ S such that R( s ) is as small as possible. Let ( s m ) m∈M be a collection of estimators. The goal of estimator selection is to choose from data some m ∈ M such that the risk of s m is as small as possible, that is, satisfying an oracle inequality

R ( s m ) -R(s ) K n inf m∈M R( s m ) -R(s ) + R n ( 44
)
with large probability, where R(s ) := inf t∈S R(t). In the following, K n is called "the leading constant" of the oracle inequality (44). Let R n : S → [0, +∞) be the empirical risk associated with R, that is, we assume throughout Sections 3-

5 that ∀t ∈ S, E[ R n (t)] = R(t).
This framework includes the one of Section 2 by taking

S = R n , R(t) = n -1 t -F 2 + σ 2 , s m = F m
the projection estimator associated with some model S m for every m ∈ M , and the L 2 empirical risk R n (t) = n -1 t -Y 2 . Many other classical settings also fit into this framework, such as density estimation with the Kullback risk or the L 2 risk, random-design regression with the L 2 risk, and classification with the 0-1 risk (see [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF], Section 1, for details).

Penalties known up to some constant factor

The most natural extension of the slope heuristics is to generalize it to all frameworks where a penalty is known up to some multiplicative constant [START_REF] Massart | A non-asymptotic theory for model selection[END_REF][START_REF] Blanchard | Discussion: "Local Rademacher complexities and oracle inequalities in risk minimization[END_REF], that is, if theoretical results show that a good penalty is C pen 1 (m) with pen 1 known but C unknown. Penalties known up to a constant factor appear in several frameworks, for four main reasons:

1. A penalty satisfying an optimal oracle inequality -that is, an oracle inequality with leading constant 1 + o(1)-is theoretically known, but involves unknown quantities in practice, such as the noise-level σ 2 for Mallows' C p and C L [START_REF] Mallows | Some comments on C p[END_REF], see Sections 2 and 3.3.

2. An optimal penalty pen 1 is known theoretically and in practice, but only asymptotically, that is, the (unknown) non-asymptotic optimal penalty is C n pen 1 with C n → 1 as the sample size n tends to infinity, but C n is unknown and can be far from 1 for finite sample sizes. For instance, AIC [START_REF] Akaike | Information theory and an extension of the maximum likelihood principle[END_REF] and BIC [START_REF] Schwarz | Estimating the dimension of a model[END_REF] penalties for maximum likelihood rely on asymptotic computations. Section 8.4 explains why such a problem can arise in almost any framework. 3. An optimal penalty is obtained by resampling, hence depending on some multiplicative factor that might depend on unknown quantities or be correct only for n large enough, see Remark 3 in Section 4.2 and the article by [START_REF] Arlot | Model selection by resampling penalization[END_REF].

4. A penalty C pen 1 satisfying an oracle inequality with a leading constant O(1) when C is well chosen is known theoretically, but theoretical results are not precise enough to specify the optimal value C of C. This occurs for instance for change-point detection [START_REF] Comte | A new algorithm for fixed design regression and denoising[END_REF][START_REF] Lebarbier | Detecting multiple change-points in the mean of a Gaussian process by model selection[END_REF], density estimation with Gaussian mixtures [START_REF] Maugis | A non asymptotic penalized criterion for gaussian mixture model selection[END_REF], and local Rademacher complexities in classification [START_REF] Bartlett | Local Rademacher complexities[END_REF][START_REF] Koltchinskii | Local Rademacher complexities and oracle inequalities in risk minimization[END_REF]. In some frameworks, some partial information is available about the optimal value of the constant: in binary classification, global Rademacher complexities differ by a factor 2 between theory [START_REF] Koltchinskii | Rademacher penalties and structural risk minimization[END_REF] and practice [START_REF] Lozano | Model selection using Rademacher penalization[END_REF]. Note that in such cases, it might happen that C pen 1 is not exactly an optimal penalty, so that no oracle inequality with leading constant 1 + o(1) can be obtained; nevertheless, choosing the constant C in the penalty C pen 1 remains an important practical problem.

Then, if for every m ∈ M , C m measures the "complexity" of s m , the slope heuristics suggests to generalize Algorithm 1 into the following.

Algorithm 3 (Slope-heuristics algorithm, jump formulation, general setting). Input: R n ( s m ) m∈M , pen 1 (m) m∈M , and (C m ) m∈M .

1. Compute m 1 (C) C 0 , where for every C 0,

m 1 (C) ∈ argmin m∈M R n ( s m ) +C pen 1 (m) . ( 45
)
2. Find C jump > 0 corresponding to the "unique large jump" of C → C m 1 (C) .

3. Select m Alg.3 ∈ argmin m∈M { R n ( s m ) + 2 C jump pen 1 (m)}.

Output: m Alg.3 .

Algorithm 3 relies on two ideas: (i) Eq. ( 13), that is, pen opt = 2 pen min , is valid in a more general framework than least-squares regression and projection estimators, and (ii) if a proper complexity measure C m is used instead of the dimension D m of the models, the minimal penalty can be characterized empirically by a jump of C m 1 (C) .

Algorithm 3 fails for linear-estimator selection

We now illustrate on an example why Algorithm 3 can fail, before showing how to correct it in Section 3.4. Let us consider the fixed-design regression framework of Section 2.1 with linear estimators instead of projection estimators, that is, for every m ∈ M ,

F m = A m Y
for some deterministic linear mapping A m : R n → R n . For instance, projection estimators are linear estimators since the orthogonal projection A m = Π m onto a linear space S m is linear. Other examples include kernel ridge regression or spline smoothing, nearest-neighbor regression, and Nadaraya-Watson estimators (Arlot and Bach, 2011, provide more examples and references).

Similarly to Section 2.2, expectations of the risk and empirical risk of a linear estimator can be computed as follows:

E 1 n F m -F 2 = 1 n (I n -A m )F 2 + σ 2 tr A m A m n , (46)
E 1 n F m -Y 2 = 1 n (I n -A m )F 2 + σ 2 n + tr A m A m -2 tr(A m ) n , (47)
and

pen opt (m) = E 1 n F m -F 2 -E 1 n F m -Y 2 + σ 2 = 2σ 2 tr(A m ) n . (48)
Eq. ( 46) can be interpreted as a bias-variance decomposition similarly to Eq. ( 7). The optimal penalty given by Eq. ( 48) has been called C L by [START_REF] Mallows | Some comments on C p[END_REF] and is similar to C p , with the dimension D m replaced by the degrees of freedom tr(A m ). It also depends on σ 2 which is unknown, so one could think of using Algorithm 3 with

s m = F m , R n (t) = n -1 t -Y 2 , pen 1 (m) = tr(A m )/n

Minimal-penalty heuristics for linear estimators

Following Arlot andBach (2009, 2011) Indeed, as in Section 2.3, let us consider, for every C 0,

m lin min (C) ∈ argmin m∈M 1 n F m -Y 2 +C 2 tr(A m ) -tr A m A m n , (49)
and

m lin min (C) ∈ argmin m∈M E 1 n F m -Y 2 +C 2 tr(A m ) -tr A m A m n = argmin m∈M crit lin C (m) with crit lin C (m) := 1 n (I n -A m )F 2 + (C -σ 2 ) 2 tr(A m ) -tr(A m A m ) ,
by Eq. ( 47). Let us assume that the approximation error term n -1 (I n -A m )F 2 , which appears in Eq. ( 46), is a decreasing function of the degrees of freedom C m = tr(A m ); let us also assume for simplicity that 0 tr(A m A m ) tr(A m ) for every m ∈ M . Then, we can distinguish two cases: Theorem 1 can be extended to Algorithm 4, up to some minor changes in the assumptions and results (Arlot andBach, 2009, 2011). For kernel ridge regression, Algorithm 4 is proved to work also for choosing over a continuous set M [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF], provided the kernel is fixed.

-if C < σ 2 ,
Note that when tr(A m A m ) = tr(A m ), pen opt (m) = 2 pen lin min (m). This occurs for least-squares estimators -for which A m = A m A m = Π m , and we recover the setting of Section 2 and Algorithm 1-and for k-nearest neighbors estimators.

General minimal-penalty algorithm

We now go back to the general setting of Section 3.1, and propose a generalization of Algorithms 1 and 4. Here, we suggest to take C jump = C window , but any other formal definition of C jump could be used instead.

Algorithm 5 (General minimal-penalty algorithm, jump formulation). Input: R n ( s m ) m∈M , pen 0 (m) m∈M , pen 1 (m) m∈M , (C m ) m∈M , and η 0. (50)

2. Find C jump > 0 corresponding to the "unique large jump" of C → C m (0) min (C) , for instance,

C window ∈ argmax C>0 C m (0) min (C/[1+η]) -C m (0) min (C[1+η]) .
3. Select m Alg.5 ∈ argmin m∈M R n ( s m ) + C jump pen 1 (m) .

Output: m Alg.5 .

Algorithm 5 implicitly assumes that the minimal and the optimal penalty are respectively equal to C pen 0 and C pen 1 , with pen 0 and pen 1 known, but C unknown. We refer to Section 7.1 for practical remarks about the choice of C jump . Computational issues are discussed in Section 7.2.

In the "slope heuristics" setting (Section 2), pen 1 = 2 pen 0 , and Algorithm 5 reduces to Algorithm 3.

Similarly to Algorithm 2, we can also propose a "slope" formulation of Algorithm 5.

Algorithm 6 (General minimal-penalty algorithm, slope formulation).

Input: R n ( s m ) m∈M , pen 0 (m) m∈M , pen 1 (m) m∈M , and (C m ) m∈M .

1. Estimate the slope C slope of -R n ( s m ) as a function of pen 0 (m) for all m ∈ M with C m "large enough", for instance by (robust) linear regression.

2. Select m Alg.6 ∈ argmin m∈M R n ( s m ) + C slope pen 1 (m) .

Output: m Alg.6 .

What remains now is to identify natural candidates for being a minimal or an optimal penalty in the general setting.

Optimal and minimal penalties

In the general setting, the unbiased risk estimation heuristics [START_REF] Akaike | Statistical predictor identification[END_REF][START_REF] Stein | Estimation of the mean of a multivariate normal distribution[END_REF] suggests the following optimal (deterministic) penalty

pen gal opt (m) := E R( s m ) -R n ( s m ) (51)
which generalizes formula (4). If R( s m ) -R n ( s m ) is concentrated around its expectation uniformly over m ∈ M -which excludes too large collections M -, one can prove an oracle inequality for the penalty (51), or for any penalty which differs from Eq. ( 51) by an additive term independent from m, as in Eq. ( 9) and (48). Building a minimal penalty in the general setting is more difficult. For every m ∈ M , let C m be some "complexity measure" associated with s m , that is, we assume that the empirical risk R n ( s m ) (or its expectation) is (approximately) a decreasing function of C m . Algorithm 6 suggests that the minimal penalty is a quantity which exactly compensates this decreasing trend, such as pen gal min,0 (m) := -E R n ( s m ) .

(52)

Nevertheless, in most cases including least-squares and linear estimators, pen gal min,0 is unknown, even up to a multiplicative factor, so that we need another candidate for being a minimal penalty.

For every m ∈ M , let s m be a well-chosen element of S -see Remark 2 below-such that R(s m )-inf t∈S R(t) decreases to zero as C m → ∞. As argued below, a natural choice for the minimal penalty is pen

gal min (m) := E R n (s m ) -R n ( s m ) . (53)
Indeed, for every C 0 let Let us emphasize that for making use of the fact that pen gal min is a minimal penalty, we must assume that pen gal min ≈ C pen 0 and pen gal opt ≈ C pen 1 for some unknown C > 0 and some known penalty shapes pen 0 and pen 1 . Remark that we could generalize this assumption to the existence of some known function f such that pen gal min ≈ C pen 0 and pen gal opt ≈ f (C ) pen 1 , but such a generalization has not been proved useful yet.

crit gal C (m) := E R n ( s m ) +C pen gal min (m) = CR(s m ) + (1 -C)E R n ( s m ) (54
Remark 2 (Choice of s m ). Overall, the above heuristics makes two assumptions on s m ∈ S. First, R(s m )-inf t∈S R(t) is small when C m is large. Second, pen gal min (m) is known up to a multiplicative constant, whose value can be used for deriving an optimal penalty. When s m ∈ argmin t∈S m R n (t) is an empirical risk minimizer over some model S m ⊂ S, a natural choice is s m ∈ argmin t∈S m R(t), so that R(s m )inf t∈S R(t) is the approximation error. For linear estimators, the decomposition (46) of the risk suggests to take s m = A m F. By analogy, we call R(s m )inf t∈S R(t) the approximation error associated with s m in the general case. Choosing s m might be difficult in general; when this makes sense, an option is the expectation of s m .

Bibliographical remarks

Algorithms The slope-heuristics algorithm for calibrating penalties was first proposed in the Gaussian least-squares regression setting of Section 2 with a penalty proportional to the dimension [START_REF] Birgé | A generalized Cp criterion for Gaussian model selection[END_REF], as in Algorithms 1-2. Then, it was generalized to a penalty function of the dimension [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF], and to a general penalty shape [START_REF] Massart | A non-asymptotic theory for model selection[END_REF][START_REF] Blanchard | Discussion: "Local Rademacher complexities and oracle inequalities in risk minimization[END_REF][START_REF] Massart | Concentration Inequalities and Model Selection[END_REF], as in Algorithm 3.

The first implementations of the slope heuristics were done directly with Algorithm 3 (or its "slope" version) with C m = D m , instead of Algorithms 1-2, since they were outside the setting of Section 2: maximum-likelihood estimators (Letué, 2000, Section A.4), and change-point detection (Lebarbier, 2002, Chapter 4).

The proposition of using a general complexity measure C m instead of a dimension D m (as in Algorithms 3, 5-6) was first made in density estimation [START_REF] Lerasle | Rééchantillonnage et sélection de modèles optimale pour l'estimation de la densité de variables indépendantes ou mélangeantes[END_REF], with the suggestion of estimating C m by resampling if necessary.

The failure of Algorithm 3 for linear estimators in regression was noticed by [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF], where Algorithm 4 was proposed and theoretically justified. The general Algorithm 5 has only been formalized by Arlot (2011, Section 2.5), while its "slope estimation" version (Algorithm 6) is new, even if the (approximate) equivalence between "jump" and "slope" algorithms is not. Up to now, the general formulation of Algorithms 5-6 has only been proved useful in the case of linear estimators in regression (Arlot andBach, 2009, 2011) and in density estimation [START_REF] Magalhães | Cross-Validation and Penalization for Density Estimation[END_REF]Lerasle et al., 2016), with different shapes for pen 0 and pen 1 . It can also be useful in a few other settings where pen 1 is proportional to pen 0 but the ratio between optimal and minimal penalty might be different from 2, for selecting among a rich collection of models or estimators. For instance, for pruning a decision tree, the "max" variant considered by Bar-Hen et al. (2018, Section 5.4) is equivalent to Algorithm 5 with pen 1 = pen 0 , hence selecting the estimator "just after" the maximal jump.

Theory The first (partial) theoretical result proved outside the setting of Section 2 was for maximum-likelihood estimators (histograms) in density estimation, assuming that the true density s is the uniform density over [0, 1] [START_REF] Castellan | Modified Akaike's criterion for histogram density estimation[END_REF]. Other theoretical results outside the setting of Section 2 are reviewed in Section 4.

The first theoretical result proved for Algorithm 3 with a penalty shape pen 1 (m) not function of a dimension D m was obtained in heteroscedastic least-squares regression [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF], where the penalty shape can be estimated by resampling [START_REF] Arlot | Model selection by resampling penalization[END_REF].

The general heuristics "pen opt ≈ 2 pen min " underlying Algorithm 3 was formulated by Blanchard and Massart (2006, Section 2) and Massart (2007, Section 8.5.2), together with a heuristic argument for suggesting

p 2 (m) := R n (s m ) -R n ( s m )
as a minimal penalty, when s m is an empirical risk minimizer and s m is defined according to Remark 2. In these papers, p 2 (m) is called v m since it can be interpretated as a variance. Here, the general minimal penalty that we propose is pen gal min (m) = E[p 2 (m)], as in the PhD dissertation of Arlot (2007, Chapter 3) for instance. Another formulation of the heuristics behind Algorithm 3 is "p 1 (m) ≈ p 2 (m)", where

p 1 (m) := R( s m ) -R(s m ) ,
as for instance written in a binary classification framework by Zwald (2005, Section 6.4.3), together with "p 2 (m) ∝ D m for D m large enough".

Theoretical results: a review

This section collects all theoretical results that are directly related to minimal-penalty algorithms, to the best of our knowledge. First, the proof of Algorithm 5 is split into several subproblems (Section 4.1). Then, we present full proofs of Algorithm 5 (Section 4.2) and partial results . Note that some related results outside the setting of Section 3 are reported in conclusion (Sections 8.3.6 and 8.5).

In this section, all partial or full proofs of Algorithm 5 that we present define C jump as C thr. (T n ) or C window (η) for some well-chosen T n or η. For the sake of simplicity, we do not discuss anymore the exact definition chosen for C jump , until we tackle this question in Section 7.1.

General approach for proving Algorithm 5

Following Theorem 1 and its proof, let us suggest a general approach towards a theoretical justification of Algorithm 5, that we split into several subproblems.

(α) The minimal and optimal penalties are known up to some common multiplicative factor: Find two penalty functions pen 0 , pen 1 , and a complexity measure (C m ) m∈M , such that for some (unknown) C > 0, C pen 0 is a minimal penalty and C pen 1 is an optimal penalty. (β ) C pen 0 is actually a minimal penalty: η - n , η + n > 0 exist such that, on a large-probability event,

∀C < 1 -η - n C , C m (0) min (C) C overfit ∝ max m∈M C m (β -) ∀C > 1 + η + n C , C m (0) min (C) C small max m∈M C m (β + )
where ∀C 0 , m The above statements about C m (0) min (C) are vague on purpose, since the range of (C m ) m∈M is not specified. When C m is the dimension D m ∈ [1, n] of some model, one can specify C overfit and C small similarly to Eq. ( 14) and ( 16), respectively. (γ) C pen 1 is actually an optimal penalty: there exists η > 0 such that, on a large-probability event, for every

C ∈ ([1 -η]C , [1 + η]C ), ∀ m (1) opt (C) ∈ argmin m∈M R n ( s m ) +C pen 1 (m) , R s m (1) opt (C) -R(s ) 1 + ε n (η) inf m∈M R( s m ) -R(s ) + R n (η) (γ)
where lim η→0, n→+∞ ε n (η) = 0 and the remainder term R n (η) is negligible in front of the oracle risk inf m∈M {R( s m ) -R(s )}. As in the PhD dissertation of [START_REF] Arlot | Resampling and Model Selection[END_REF], we use in this section the following notation:

p 1 (m) := R( s m ) -R(s m ) , (55)
p 2 (m) := R n (s m ) -R n ( s m ) , (56)
and In particular, with the notation of Section 3.6, pen gal opt (m) = E p 1 (m) + δ (m) + p 2 (m) and pen gal min (m) = E p 2 (m) .

δ (m) := R(s m ) -R n (s m ) . ( 57
)

Full proofs of Algorithm 5

Few settings exist where a full proof of Algorithm 5 is available, that is, a proof that (β -), (β + ), and (γ) hold true on a large-probability event for some known pen 0 , pen 1 , (C m ) m∈M and some (unknown) C . In this article, M is always assumed to be finite with card(M ) L 1 n L 2 for some L 1 , L 2 > 0, except in Section 4.7.

We first collect results assuming that pen 1 = 2 pen 0 , so that Algorithm 5 reduces to Algorithm 3. Without explicit mention of the contrary, for all results reviewed in the list below, the noise is assumed independent and identically distributed, s m ∈ argmin t∈S m R n (t) is an empirical risk minimizer, so we take s m ∈ argmin t∈S m R(t) for defining p 2 (m), and the complexity used is C m = D m the dimension of S m . Full proofs of Algorithm 5 exist in the following settings:

-Regression on a fixed design, homoscedastic (sub-)Gaussian noise, least-squares risk and estimators: [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF] and Theorem 1 (and Remark 1 for the sub-Gaussian case) prove it with pen 0 (m) = D m /n and C = σ 2 the (constant) noise level. Note that

p 1 (m) = p 2 (m) = n -1 Π m ε 2 in this setting.
-Regression on a random design, heteroscedastic noise (not necessarily Gaussian), leastsquares risk, with various least-squares estimators: regressograms with moment assumptions on the noise [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF], piecewise polynomials with bounded noise [START_REF] Saumard | Optimal model selection in heteroscedastic regression using piecewise polynomial functions[END_REF] with key concentration results for p 1 and p 2 proved by [START_REF] Saumard | Optimal upper and lower bounds for the true and empirical excess risks in heteroscedastic least-squares regression[END_REF], or more general models satisfying a "strongly-localized basis" assumption with bounded noise (Saumard, 2010a;[START_REF] Navarro | Slope heuristics and V-fold model selection in heteroscedastic regression using strongly localized bases[END_REF]. Contrary to the previous setting, E[p 1 (m)] ≈ E[p 2 (m)] holds true only for most models and for n large enough.

The penalty shape pen 0 (m) = E[p 2 (m)] is unknown in general and C = 1. For regressograms, the results remain true when pen 0 (m) is a resampling-based estimation of E[p 2 (m)] (see [START_REF] Arlot | Model selection by resampling penalization[END_REF]. For piecewise polynomials, the same holds when pen 0 (m) is a hold-out estimation of E[p 2 (m)] (see [START_REF] Saumard | Optimal model selection in heteroscedastic regression using piecewise polynomial functions[END_REF]. For strongly localized bases, the (approximate) closed-form formula for E[p 1 (m)] and E[p 2 (m)] provided by Navarro and Saumard (2017, Theorem 6.3) might be used for estimating pen 0 (m) without resampling; another option is V -fold penalization (Navarro and Saumard, 2017, Section 5). -Density estimation, least-squares risk and estimators, i.i.d. [START_REF] Lerasle | Optimal model selection in density estimation[END_REF] or mixing data [START_REF] Lerasle | Optimal model selection for stationary data under various mixing conditions[END_REF]. The penalty shape pen 0 (m) = E[p 2 (m)] is approximately known for some specific models (regular histograms), in general it can be estimated by resampling as previously. In this setting, the complexity C m can either be the dimension of S m or the resampling-based estimator of E[p 2 (m)] itself. Note that in least-squares density estimation, we have p 1 (m) = p 2 (m) almost surely. -Density estimation, Kullback risk and maximum-likelihood estimators, histogram models [START_REF] Saumard | Nonasymptotic quasi-optimality of AIC and the slope heuristics in maximum likelihood estimation of density using histogram models[END_REF]. This result is the first one obtained without the least-squares risk. The penalty shape pen 0 (m) = D m /(2n) is known, C = 1, and the optimal penalty is AIC.

A partial result, for the uniform density over [0, 1] only, has previously been proved by [START_REF] Castellan | Modified Akaike's criterion for histogram density estimation[END_REF]. -Specification probabilities in general random fields (that is, graphical models), least-squares or Kullback risks, estimators that are empirical distributions conditionally to the values observed on a subset m of the field [START_REF] Lerasle | Sharp oracle inequalities and slope heuristic for specification probabilities estimation in discrete random fields[END_REF]. The shape of the penalty and the complexity pen 0 (m) = C m = p 2 (m) are unknown. The authors suggest to use instead the shape of a theoretical upper bound on E [p 2 (m)], dropping off pessimistic constants, with convincing experimental results. The above results for least-squares regression on a random design, least-squares density estimation (i.i.d. case), and maximum-likelihood density estimation can all be recovered (sometimes up to minor differences) as a corollary of a general result which holds for all "regular estimators" (Saumard, 2010b, Chapters 7-8).

Full proofs of Algorithm 5 (or a slight modification of it) also exist in two settings where pen 1 = 2 pen 0 in general:

-Regression on a fixed design, independent and identically distributed (homoscedastic) Gaussian noise, least-squares risk, linear estimators: Arlot andBach (2009, 2011) prove that Algorithm 4 works, while Algorithm 3 fails in general, as detailed in Sections 3.2-3.

(m) = E[p 2 (m)], pen 1 (m) = E[p 1 (m)] + E[p 2 (m)], C m = E[p 1 (m)], and C = 1.
This result implies the one of [START_REF] Lerasle | Optimal model selection in density estimation[END_REF] for least-squares estimators. A noticeable fact in this framework is that pen min -and sometimes even pen opt , surprisingly-can be negative, making the terminology "minimal" penalty questionable (Lerasle et al., 2016, Sections 4.3 and 5). Note that pen opt here can be negative because s m is not an empirical risk minimizer, hence R n ( s m ) is not necessarily biased downards as an estimator of R( s m ). Nevertheless, for most usual estimators, pen min and pen opt are always positive. Theoretical results for choosing among Parzen density estimators with slightly different minimal-penalty algorithms -closer to Goldenshluger-Lepski's method-are discussed in Section 8.5.

Remark 3 (Minimal penalties with resampling-based estimators of E[p 2 (m)]). In several papers mentioned above, theoretical results validate Algorithm 5 with pen 0

(m) = C m = p 2 (m) or E [p 2 (m)]
, pen 1 (m) = 2 pen 0 (m), and C = 1. Such results might seem useless since (i) pen 0 is unknown, and (ii) C is known, that is, the exact opposite of the motivation for Algorithm 5 exposed in Section 3.2. Nevertheless, problem (i) can be solved by taking pen 0 (m) = C m equal to a resampling-based estimator p W 2 (m) of E [p 2 (m)] (Lerasle, 2012, for instance). Then, as usual with resampling, it remains to find the constant C m)] for all m ∈ M . When such a constant C W exists, it usually depends on the resampling scheme W , the sample size, and the particular setting considered [START_REF] Arlot | Model selection by resampling penalization[END_REF]. As a consequence, we recover a setting where pen 0 (m) = C m = p W 2 (m) is known and C = C W is unknown, for which Algorithm 5 can be useful. Note that we here propose to take

W such that C W E p W 2 (m) ≈ E [p 2 (
C m = p W 2 (m), which does not estimate E [p 2 (m)] but E [p 2 (m)] /C W ;
this is not a problem since the complexity jump is independent from the rescaling by C W . According to simulation experiments, the above strategy of combining resampling penalties with the slope heuristics can be better [START_REF] Lerasle | Optimal model selection in density estimation[END_REF], least-squares density estimation) or worse [START_REF] Garivier | Oracle approach and slope heuristic in context tree estimation[END_REF], context-tree estimation) compared to using the penalty C W p W 2 (m), where C W derives from asymptotic theoretical results and does not depend on any unknown quantity in the settings of these two articles.

Partial proofs: uncertainty on the optimal penalty

An optimal oracle inequality like (γ) in Section 4.1 has not been proved in many frameworks, and it is quite difficult to obtain a leading constant 1 + ε n (η) = 1 + o(1) while keeping the remainder term negligible in front of the oracle risk. A much more usual result in the modelselection literature is the following weakened version of (γ): on a large-probability event, for every

C ∈ ([1 -η]C , [1 + η]C ) with η > 0 small enough, R s m (1) opt (C) -R(s ) K n (η) inf m∈M R( s m ) -R(s ) + R n (η) ( γ )
for some K n (η), R n (η) < ∞. Note that (γ) with ε n = 0 and R n inf m∈M {R( s m ) -R(s )} should be understood as ( γ ) with K n 2. Similarly, a classical way to write an oracle-type inequality is

R s m (1) opt (C) -R(s ) inf m∈M R( s m ) -R(s ) + R n (m) . ( γ ) When R n (m) is comparable to R( s m ) -R(s )
, or even larger, (for instance, R n (m) pen(m)), ( γ ) should be understood as ( γ ) with K n 2. Proving only ( γ ) instead of (γ) is a significant limitation: ( γ ) does not show that C pen 1 is an optimal penalty if we cannot prove that K n (η) is first-order optimal, which is very difficult to prove unless K n (η) = 1 + o(1) as in (γ). As a consequence, in such cases, C pen 1 might not be optimal, and the optimal penalty might be C pen 1 with C = C , or even have a completely different shape than pen 1 . For instance, in the setting of Section 3.4, the optimal penalty is 2σ 2 tr(A m )/n, but taking 2σ 2 [tr(A m ) + tr(A m A m )]/n as a penalty, we could have an oracle inequality ( γ ) with a penalty having a suboptimal shape.

Results Nevertheless, proving (β ) and ( γ ) still shows that Algorithm 5 provides a data-driven estimator satisfying an oracle inequality. Such a result exists for context-tree estimation with the Kullback risk, φ -mixing processes, and maximum-likelihood estimators [START_REF] Garivier | Oracle approach and slope heuristic in context tree estimation[END_REF], with pen 0 (m) = C m = p 2 (m) and pen 1 (m) = 2 pen 0 (m). Simulation experiments suggest that p 2 (m) can be replaced by a BIC-type penalty or a resampling-based estimator of E [p 2 (m)],

Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019 see Remark 3 in Section 4.2. What is missing to get a proof of (γ) is a tight concentration inequality for δ (m)δ (m ), that is, to have Eq. ( 60) satisfied with ε δ = o(1) as required in Proposition 2, see Section 5.2.2. Simulation experiments suggest that pen 1 = 2 pen 0 is indeed an optimal choice here.

Minimal penalty in terms of risk: (β )

Another way to define a minimal penalty is in terms of the risk of s m (0) min (C) , which is theoretically interesting but does not prove the presence of a complexity jump as expected by Algorithm 5:

∀C < (1 -η - n )C , R s m (0) min (C) -R(s ) κ max m∈M R( s m ) -R(s ) (β -) ∀C > (1 + η + n )C , R s m (0) min (C) -R(s ) K C C inf m∈M R( s m ) -R(s ) + R n C C (β + )
where for every

x > 1, K(x) ∈ [1, ∞) and R n (x) inf m∈M {R( s m )-R(s )
} in general, and κ > 0 is an absolute constant. When (β ), which is defined in Section 4.1, is replaced by (β ) above, the justification of Algorithm 5 is far from being complete, since there might be no complexity jump as required in the definition of C window . Nevertheless, once (β ) is proved, one can reasonably conjecture that (β ) holds true under similar assumptions, provided that C m is well chosen. Moreover, (β ) and (β ) are closely related if

∀x > 0 , inf m∈M / C m x R( s m ) -R(s ) g(x) > 0 (58)
for some increasing function g. Indeed, assuming (58), (β -) implies (β -) with

κ = g(C overfit ) max m∈M {R( s m ) -R(s )} ,
and (β + ) implies (β + ) with

C small = g -1 K C C inf m∈M R( s m ) -R(s ) + R n C C .
Note that Eq. ( 58) holds true with g

(x) = x/α if C m ≈ α p 1 (m); for instance, for least-squares estimators and risk, α = σ 2 /n since C m = D m and p 1 (m) ≈ σ 2 D m /n.
Let us remark finally that the proof of (β -) usually relies on a proof of (β -), sometimes hidden by technical details.

Results

To the best of our knowledge, a full proof of (β ) currently exists only in settings where (β ) is proved to hold, except one result that we report in Section 4.7. Some partial proofs of (β ) are reviewed in the next subsections.

Partial proofs: uncertainty on the minimal penalty

A result weaker than (β ) can be proved about the complexity jump: for some C 1 < C 2 (that remain distinct even when n → +∞),

∀C < C 1 , (β -) holds true, and ∀C > C 2 , (β + ) holds true. ( β
)
In other words, C 1 pen 0 is a too small penalty, while C 2 pen 0 is a sufficiently large penalty.

From the theoretical point of view, proving ( β ) instead of (β ) is a serious limitation: for reasons similar to the ones explained in Section 4.3 for ( γ ), it can happen that pen 0 is not the shape of a minimal penalty. For instance, in the setting of Section 3.3, ( β ) holds true with pen 0 (m) = tr(A m ) although this quantity is not always proportional to the minimal penalty, as shown by Figure 3.

Nevertheless, from the practical point of view, one can still derive from ( β ) a way to get from data some C ∈ [C 1 ,C 2 ], for instance by taking a large η in the definition of C window (η). If (C 2 /C 1 ) is not too large and if ( γ ) holds true for some C ∈ [C 1 ,C 2 ], this leads to an estimator satisfying an oracle inequality.

Results One full proof of ( β ) and ( γ ) is available for prediction in a Gaussian graphical model via neighborhood selection, with conditional least-squares risk and estimators, a minimal-penalty shape pen 0 (m) = C m = D m , and an optimal penalty shape pen 1 proportional to pen 0 [START_REF] Verzelen | Data-driven neighborhood selection of a Gaussian field[END_REF]. The proof of ( β ) assumes in addition that the graph is a square lattice. Simulation experiments suggest that there is indeed a jump around C and that Algorithm 5 works well.

Partial proofs: for some specific s only

The weakest partial proofs of (β ) are the ones only valid for some particular s , which often is s = 0. Then, although C pen 0 is a minimal penalty for this particular s , the general shape of the minimal penalty can differ from pen 0 . For instance, in the Lasso case, an empirical study shows that the shape of E [p 2 (m)] depends on s and on some other features of the distribution of the data [START_REF] Connault | Calibration d'algorithmes de type Lasso et analyse statistique de données métallurgiques en aéronautique[END_REF].

Nevertheless, such weak results still are a good way to guess pen 0 for a practical use of Algorithm 5, and they can be a first step towards a full theoretical justification.

Results Such partial proofs exist in the case of multiplicative penalties, an apparently different setting that can still be cast into the framework of Algorithm 5. The principle, as exposed by [START_REF] Baraud | Gaussian model selection with an unknown variance[END_REF] for least-squares regression, is to replace the penalized criterion (3) by the product of the empirical risk by some penalty term, that is, choosing This can actually be seen as an additive penalization method as in Eq. ( 3), with the penalty

m ∈ argmin m∈M R n ( s m ) 1 + pen mult (m) n -D m . ( 59
)
pen(m) := R n ( s m ) pen mult (m) n -D m .
So, choosing a multiplicative factor in front of pen mult (m) is equivalent to choosing a multiplicative factor in front of an additive penalty of a particular form. For fixed-design regression with least-squares risk and estimators, [START_REF] Baraud | Gaussian model selection with an unknown variance[END_REF] prove that (β -) holds true if s = 0, while (β + ) and ( γ ) hold true in general, with C pen mult 0 (m) = D m and pen mult 1 ∝ pen mult 0 . In addition, in the setting of multivariate regression on a fixed design with the least-squares risk and low-rank least-squares estimators, ( γ ) and (β + ) are proved in a general case, while (β -) is proved only for s = 0 [START_REF] Giraud | Low rank multivariate regression[END_REF]; remark that (β + ) can certainly be proved in a general case, although its proof is not written in the article by [START_REF] Giraud | Low rank multivariate regression[END_REF]. Note also that these results are valid both for additive penalties and for multiplicative penalties as the ones of [START_REF] Baraud | Gaussian model selection with an unknown variance[END_REF].

Partial proofs: richer collections of models

Throughout the article, we assume (at least implicitly) that M is not too large, that is, card(M ) grows at most polynomially with the sample size n, or M can be well approximated by such a polynomial set of estimators -e.g., kernel ridge regression with one continuous parameter λ [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF]. Nevertheless, the case where M is larger deserves attention, and we review in this subsection the partial results about minimal penalties in such settings. Note that each of them suffers from some of the limitations emphasized in Sections 4.3-4.6.

Let us consider the fixed-design regression setting, with least-squares risk and estimators on finite-dimensional vector spaces S m . Assuming as [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF] that the penalty is a function of the dimension, the selected estimator

s m with m ∈ argmin m∈M R n ( s m ) + pen(D m )
can be rewritten as s D where

∀D ∈ N, s D ∈ argmin t∈S D R n (t) , S D := m∈M D m =D S m , and D ∈ argmin D∈N R n ( s D ) + pen(D) .
Then, discarding all models of dimension D > n, s m = s D is a penalized empirical risk minimizer over a collection (S D ) 0 D n of cardinality at most n + 1. The difference with the initial formulation is that the models S D are not vector spaces (in general), and the complexity of S D strongly depends on f (D) := card{m ∈ M / D m = D}. Three cases can be distinguished, following [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF]:

(i) M is "small" or "polynomial" when f (D) CD ω for some C, ω > 0. Then, card(M ) grows polynomially with n (since models of dimension D m > n can safely be discarded), and the complexity of S D is essentially the same as the one of a D-dimensional vector space. (ii) M is "large" or "exponential" when f (D) grows much faster -typically of order n D -, which implies in particular that card(M ) grows exponentially with n. Then, S D is much more complex than a D-dimensional vector space. A typical example is (full) variable selection among p n variables, for which f (D) = p The current subsection focuses on cases (ii) and (iii); all other results mentioned in this article correspond to case (i).

Results for case (ii): large number of models

In fixed-design regression with least-squares risks and estimators, (β ) and ( γ ) are proved by [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF] for the (full) variable-selection problem with p orthonormal variables, assuming that the noise is Gaussian, and defining

pen 0 (m) = D m n 1 + 2 log p D m , C = σ 2 ,
and pen 1 (m) = C pen 0 with any C > 1. Note that (β -) can be derived from the proof by Birgé and Massart (2007, Proposition 2), but it is not written in the article by [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF]. Similar theoretical results are proved by Sorba (2017, Chapter 8) for Gaussian variable selection with p = n and a more general collection of models, that can be smaller than full variable selection but still exponentially large. Formally, Sorba (2017, Section 8.1) assumes that M satisfies a "completion rule", which holds for instance for the collection of regressograms over a partition whose cells are hyperrectangles of R d . Then, (β -) and ( γ ) hold true, with pen 0 (m) proportional to D m n log en D m -showing that a log(n) factor is still necessary here-and (β -) is proved when the target signal is null. Compared to the results of [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF], a gap of a multiplicative constant remains between minimal and sufficient penalties.

Sorba (2017, Chapter 9) proves similar theoretical results about histogram selection for density estimation by penalized log-likelihood, with the Kullback risk, for any large collection of subpartitions of a regular partition of [0, 1] into N + 1 pieces, assuming N n/(log n) 2 . A sufficient penalty ∝ D m n log(N) satisfies ( γ ). If the target density is uniform over [0, 1], (β -) holds true with a minimal penalty level of the same order of magnitude. As a consequence, when log(N) ∼ log(n), this proves that a log(n) factor must be added to the penalty compared to the case of a polynomial collection M .

Two partial results are available with multiplicative penalties, which are introduced in Section 4.6. In the same setting as [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF], (β -) -assuming s = 0 and a specific "exponential" collection M with f (D) ≈ n D -, (β + ), and ( γ ) are proved by [START_REF] Baraud | Gaussian model selection with an unknown variance[END_REF], with pen mult 0 (m) = 2D m log(n). For estimation of a Gaussian graph -that is, in a Gaussian graphical model, predict the value at each vertex of the graph given its neighbors, by linear regression-, with least-squares risk and estimators, (β -) -assuming that s = 0 and M contains some specific "exponential" collection with f (D) ≈ p D for some p > n-, (β + ), and ( γ ) are proved by [START_REF] Giraud | Estimation of Gaussian graphs by model selection[END_REF], with pen mult 0 (m) = 2D m log(p). In both articles by [START_REF] Baraud | Gaussian model selection with an unknown variance[END_REF] and [START_REF] Giraud | Estimation of Gaussian graphs by model selection[END_REF] Finally, several other arguments can be found for the necessity of a penalty larger than

σ 2 D m n 1 + log n D m
-up to a numerical constant-for change-point detection, which is an instance of variable selection with p = n -1. Minimax lower bounds (Durot et al., 2009, Theorem 2) and general oracle inequalities [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF] prove that for the true model m ,

pen(m ) κσ 2 D m n 1 + log n D m
is necessary for some constant κ > 0. Abramovich et al. ( 2006, Section 1.9) provide several other reasons why the optimal penalty should be close to 2σ 2 D m n log n D m .

Results for case (iii): moderate number of models

In fixed-design regression with least-squares risks and estimators, ( γ ) holds true in general, and ( β ) is proved assuming that s = 0 and all models of the same dimension D are orthogonal [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF], Proposition 3), with

pen 0 (m) = λ D m n 1 + 2 f (D m ) + 2 f (D m ) , f (D) = a + b log(D + 1) D , and C = σ 2
under some condition on the constants λ , a, b. By ( β ), we mean ( β ) with a jump in the risk instead of the complexity; here, the gap in (

β ) is C 2 /C 1 = 6/5.
Results of the same flavor exist for a toy problem close to the above setting (Sorba, 2017, Chapter 10), and for a Gaussian linear process and a b-ary tree partition collection -with no assumption on s for proving (β -) and (β -)- (Sorba, 2017, Chapter 6). All these results show that "intermediate" collections of models can require a penalty strictly larger than the minimal penalty σ 2 D m n of "polynomial" collections.

Towards new theoretical results on minimal penalties

We now describe some strategies for proving that Algorithm 5 works in other settings. This section is a bit more abstract and technical than the rest of the article, so it can be skipped at first reading. As in Section 4.1, whose notation is used throughout the section, we consider separately subproblems (α), (β ), and (γ).

5.1. Hints for (α): how to find pen 0 , pen 1 , and C m ?

Using the notation defined by Eq. ( 55), (56), and (57), Section 3.6 suggests that p 1 (m) + p 2 (m) or its expectation pen gal opt (m) should be an optimal penalty, and p 2 (m) or its expectation pen gal min (m) should be a minimal penalty.

In both cases, computing (approximately) E[p i (m)], i = 1, 2, or deriving an asymptotic expansion of p i (m), i = 1, 2, at least for C m large enough, can lead to formulas for pen 0 (m) and Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019 pen 1 (m). For instance, for fixed-design regression with the least-squares risk, exact formulas for E[p i (m)] lead to Algorithm 1 for least-squares estimators, and to Algorithm 4 for linear estimators. The main difficulty here is to have no unknown quantity inside pen 0 or pen 1 . For general estimators in the fixed-design regression setting, an exact formula for pen gal opt (m) is given by covariance penalties [START_REF] Efron | The estimation of prediction error: covariance penalties and cross-validation[END_REF], which can be expressed using the degrees of freedom when the noise is Gaussian and the loss is quadratic. For maximum-likelihood estimators and risk, a partial asymptotic solution is given by the formula of the AIC criterion [START_REF] Akaike | Information theory and an extension of the maximum likelihood principle[END_REF], which derives from some version of the Wilks phenomenon (see also Section 5.2). In both cases, only a formula for pen 1 is available, and pen 0 remains unknown, even if one can sometimes conjecture that pen 0 = pen 1 /2. For random-design regression with the quadratic risk, Navarro and Saumard (2017, Theorem 6.3) provide an (approximate) closed-form formula for E[p 1 (m)] and E[p 2 (m)] -by proving that p 1 (m) and p 2 (m) concentrate around some deterministic quantity, which is not necessarily equal to their expectation-that is not directly useful because it depends on the unknown distribution of the (X i ,Y i ).

Another option is to define pen 0 (m), resp. pen 1 (m), as some resampling-based estimator of E[p 2 (m)], resp. E[p 2 (m)+ p 1 (m)], and to use Algorithm 5 for estimating the common (unknown) multiplicative factor C such that

C E pen 0 (m) ≈ E p 2 (m)
and

C E pen 1 (m) ≈ E p 1 (m) + p 2 (m) ,
see Remark 3 in Section 4.2. In addition to the papers mentioned in Section 4.2, let us mention here that a concentration result for the resampling estimate of E[p 2 (m)] is proved by Arlot (2007, Chapter 7), for empirical risk minimizers and a general bounded risk.

If no natural quantity arises as a complexity measure C m , such as the number of parameters in regression, E [p 2 (m)] (or a resampling-based estimator of it) can be a good guess for C m , see the article by [START_REF] Lerasle | Optimal model selection in density estimation[END_REF] and Remark 3. 5.2. Hints for (β ): how to prove that C pen 0 is a minimal penalty?

Following the results mentioned in the previous subsections, two general approaches can be used for proving (β ), assuming either that C pen 0 (m) = E [p 2 (m)] as in Theorem 1, or that pen 0 (m) = C m = p 2 (m) as done by [START_REF] Lerasle | Sharp oracle inequalities and slope heuristic for specification probabilities estimation in discrete random fields[END_REF]. This section details these two approaches for proving (β -) and (β + ), before focusing on the concentration inequalities they both require. Recall that ∀C 0, m Following the proof of Theorem 1 When C pen 0 (m) = E[p 2 (m)], similarly to the proof of Eq. ( 14) in Theorem 1, one can prove (β -) by showing that for some well-chosen

m 1 ∈ M , ∀C < (1 -η - n )C , inf m∈M / C m <C overfit G C (m) > G C (m 1 )
where

G C (m) := R n ( s m ) +C pen 0 (m) = R(s m ) -δ (m) -p 2 (m) + C C E p 2 (m)
is the quantity minimized by m (0) min (C). Then, in addition to the arguments sketched in Section 3.5, we only need here tight concentration inequalities for δ (m)δ (m 1 ) and for p 2 (m), see Section 5.2.3. A natural choice for m 1 is a minimizer of the approximation error R(s m ) -R(s ) over m ∈ M .

Generalizing the strategy of [START_REF] Lerasle | Sharp oracle inequalities and slope heuristic for specification probabilities estimation in discrete random fields[END_REF] and [START_REF] Garivier | Oracle approach and slope heuristic in context tree estimation[END_REF] When pen 0 (m) = C m ∝ p 2 (m), the approach3 used by [START_REF] Lerasle | Sharp oracle inequalities and slope heuristic for specification probabilities estimation in discrete random fields[END_REF] and [START_REF] Garivier | Oracle approach and slope heuristic in context tree estimation[END_REF] can be summarized into the following proposition.

Proposition 1. Let us consider the general framework of Section 3.1 and use the notation of Section 4.1. Let ε δ ∈ [0, 1], ε δ 0, and assume that for every m ∈ M , pen 0 (m) = p 2 (m) and

∀m, m ∈ M , δ (m) -δ (m ) ε δ R(s m ) -R(s ) + R(s m ) -R(s ) + ε δ . (60)
Then, for every C ∈ [0, 1),

p 2 m (0) min (C) sup m∈M p 2 (m) - 2 1 -C R(s m ) -R(s ) - ε δ 1 -C , ( 61
)
and if R(s m 1 ) = R(s ) for some m 1 ∈ M with p 2 (m 1 ) > 0, for any α ∈ (0, 1),

∀C 1 -η α , p 2 m (0) min (C) (1 -α)p 2 (m 1 ) with η α = ε δ α p 2 (m 1 ) . ( 62
)
Assume in addition that the data ξ 1 , . . . , ξ n ∈ X are i.i.d. and some contrast function γ :

Ξ × S → R and constants A, L > 0 exist such that ∀t ∈ S , R n (t) = 1 n n ∑ i=1 γ(ξ i ,t) and R(t) = E R n (t) = E γ(ξ 1 ,t) , ( 63
) ∀t ∈ S , γ(ξ 1 ,t) A a.s. , (64) and ∀m ∈ M , var γ(ξ 1 , s m ) -γ(ξ 1 , s ) L R(s m ) -R(s ) . ( 65
)
Then, for every x 0, with probability at least 1 -2 card(M )e -x , for any θ > 0, Eq. (60) holds true with

ε δ = θ and ε δ = L θ + 4A 3 x n .
Proposition 1 is proved in Appendix A.1. Eq. ( 62) proves that (β -) holds true if p 2 (m 1 ) is close to sup m∈M p 2 (m), which is a reasonable assumption. For instance, in the setting of Section 2, m 1 is given by assumption (HId) leading to s m 1 = Y , hence

p 2 (m 1 ) = 1 n Y -F m 1 2 -Y -F m 1 2 = 1 n ε 2 ≈ σ 2 .
The proof of Proposition 1 also works when assuming only that p 2 (m) 0 for every m ∈ M and

(1

-ε 0 )p 2 (m) pen 0 (m) (1 + ε 0 )p 2 (m) ,
which can be used when pen 0 (m) is a resampling estimate of E[p 2 (m)] for instance. Then, we loose a factor in the "rate" η α of estimation of C in Eq. ( 62), see Appendix A.1. Proposition 1 is new -apart from the fact that its proof relies heavily on the proof technique proposed by [START_REF] Lerasle | Sharp oracle inequalities and slope heuristic for specification probabilities estimation in discrete random fields[END_REF]-but rather abstract in its general form. Under the additional conditions ( 63)-( 65), it can be used for minimum-contrast estimators

s m ∈ argmin t∈S m R n (t)
with a bounded contrast γ, so that one automatically has p 2 (m) 0 and Eq. ( 63)-( 64) as requested. Then, Eq. ( 65) is a classical assumption [START_REF] Massart | Risk bounds for statistical learning[END_REF] which holds for bounded regression with the least-squares contrast -with L = A = 8M 2 if data are bounded by M, according to [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF]-, and for binary classification with the 0-1 loss under the margin condition [START_REF] Mammen | Smooth discrimination analysis[END_REF][START_REF] Massart | Risk bounds for statistical learning[END_REF]. Let us emphasize that Algorithm 5 has never been justified for binary classification with the 0-1 loss up to now, so Proposition 1 is of significant interest even if it only provides a partial justification -with (β -) only, in a rather abstract form.

Above the minimal penalty: (β + )

Before detailing two approaches for proving (β + ), let us recall that if an oracle inequality like (β + ) is available, a simple way to prove (β + ) is to use the connection from (β + ) to (β + ) explained in Section 4.4.

Following the proof of Theorem 1 When C pen 0 (m) = E [p 2 (m)], following the proof of Eq. ( 16) in Theorem 1, (β + ) can be proved by showing that for some well-chosen m 2 ∈ M ,

∀C > (1 + η + n )C , inf m∈M / C m >C small G C (m) > G C (m 2 ) ,
which requires concentration inequalities for δ (m)δ (m 2 ) and for p 2 (m), see Section 5.2.3. Two natural choices are Generalizing the strategy of [START_REF] Lerasle | Sharp oracle inequalities and slope heuristic for specification probabilities estimation in discrete random fields[END_REF] and [START_REF] Garivier | Oracle approach and slope heuristic in context tree estimation[END_REF] When pen 0 (m) = C m ∝ p 2 (m), the approach used by [START_REF] Lerasle | Sharp oracle inequalities and slope heuristic for specification probabilities estimation in discrete random fields[END_REF] and [START_REF] Garivier | Oracle approach and slope heuristic in context tree estimation[END_REF] can be summarized into the following proposition.

m 2 ∈ argmin m∈M / C m C small R(s m ) -R(s ) and m 2 ∈ argmin m∈M E R( s m ) -R(s
Proposition 2. Let us consider the general framework of Section 3.1 and use the notation of Section 4.1. Let ε δ , ε p ∈ [0, 1), ε δ 0, assume that Eq. (60) holds true and that for every m ∈ M , pen 0 (m) = p 2 (m) and

p 1 (m) -p 2 (m) ε p p 1 (m) . ( 66
)
Then, for every C > 1, we have

R s m (0) min (C) -R(s ) K(C) inf m∈M R( s m ) -R(s ) + K (C) (67) and p 2 m (0) min (C) K(C)(1 + ε p ) inf m∈M R( s m ) -R(s ) + K (C)(1 + ε p ) , (68)
where

K(C) := max (C -1)(1 + ε p ) , 1 + ε δ min (C -1)(1 -ε p ) , 1 -ε δ and K (C) := ε δ min (C -1)(1 -ε p ) , 1 -ε δ .
Proposition 2 is proved in Appendix A.2. Now, assume that Eq. ( 60) and ( 66) hold on a large-probability event. Then, taking C = 1 + η with η > 0, we get K(C) O(1)/η if η is small enough, and Eq. ( 67) implies (β + ). If in addition p 2 (m 1 ) stays bounded away from zero as n tends to infinity, Eq. ( 62) implies (β -). If moreover the oracle risk tends to zero and ε δ = o(1), then, Eq. ( 68) implies (β + ). Assuming also that max{ε δ , ε p } = o(1), then K(2) = 1 + o(1) hence Eq. ( 67) with C = 2 implies a first-order optimal oracle inequality (γ) with pen 1 = 2 pen 0 .

The conditions of Proposition 2 can be relaxed. First, pen 0 (m) = p 2 (m) can be replaced by (1ε 0 )p 2 (m) pen 0 (m) (1 + ε 0 )p 2 (m) for some ε 0 0 with C(1ε 0 ) > 1, which can be used when pen 0 (m) is a resampling estimate of E [p 2 (m)] for instance. Second, Eq. ( 66) can be replaced by ∀m ∈ M , -ε p + ε - p p 1 (m) p 2 (m) ε + p p 1 (m) + ε p for some ε - p , ε + p > 0 and ε p 0. Then, K(C) and K (C) are slightly enlarged, as well as the bound in Eq. ( 68), see Appendix A.2. In particular, Proposition 2 can justify (γ) with pen 1 = (1 + α -1 ) pen 0 provided that both ε - p and ε + p converge to α > 0, and ε p is small enough. Assumption ( 66) is strong and we do not expect that it can be proved as generally as assumption (60) in Proposition 1. Nevertheless, it holds when p 1 (m) and p 2 (m) both concentrate around

E [p 1 (m)] ≈ E [p 2 (m)]
for every m ∈ M , and it can be satisfied in other cases. For instance, for least-squares estimators in least-squares fixed-design regression (Section 2) or in least-squares density estimation [START_REF] Lerasle | Optimal model selection in density estimation[END_REF], p 1 (m) = p 2 (m) almost surely. Bounding |p 1 (m)p 2 (m)| also turns out to be easier to get than a concentration inequality for p 1 and p 2 separately in some settings where p 1 (m) = p 2 (m) in general [START_REF] Garivier | Oracle approach and slope heuristic in context tree estimation[END_REF].

Whatever the proof technique used -through (β + ), as in the proof of Theorem 1 or as in the article by [START_REF] Lerasle | Sharp oracle inequalities and slope heuristic for specification probabilities estimation in discrete random fields[END_REF]-, proving that the upper bound on the complexity in (β + ) is much smaller than the lower bound in (β -) is done by assuming that the oracle risk tends to zero as n → ∞, or at least that some estimator of "not too large" complexity has a small approximation error (as in Theorem 1). We conjecture that such an assumption is unavoidable in general.

Concentration inequalities

The proof techniques summarized in Sections 5.2.1-5.2.2 require some concentration inequalities for δ (m)δ (m ) and p 2 (m), and some deviation inequalities for |p 1 (m)p 2 (m)|/p 1 (m). This section provides some ways to obtain such results.

Concentration of δ (m)δ (m ) As explained in the proof of Proposition 1, δ (m)δ (m ) is a sum of independent and identically distributed random variables, so it can be concentrated with Bernstein's inequality (Boucheron et al., 2013, Theorem 2.10), leading to a result like Eq. ( 60) if a boundedness assumption (64) and some margin-type condition (65) are satisfied. In the unbounded case, other kinds of concentration inequalities can be used. For instance, for density estimation with the Kullback risk and maximum-likelihood estimators on histogram models -that is, the setting of [START_REF] Saumard | Nonasymptotic quasi-optimality of AIC and the slope heuristics in maximum likelihood estimation of density using histogram models[END_REF] without the boundedness assumption on the target density-, Saumard and Navarro (2018, Sections 4.2-4.3) use a modified version of Bernstein's inequality for controlling δ (m)δ (m ). Note that [START_REF] Saumard | Finite sample improvement of Akaike's information criterion[END_REF] only prove (β + ) and a first-order optimal oracle inequality (γ), but the proofs of [START_REF] Saumard | Finite sample improvement of Akaike's information criterion[END_REF] can be adapted to get a full proof of the slope heuristics, that is, a result similar to the one of [START_REF] Saumard | Nonasymptotic quasi-optimality of AIC and the slope heuristics in maximum likelihood estimation of density using histogram models[END_REF] when the density can be unbounded.

Concentration of p 2 (m)

The problem is much harder for p 2 (m). It can be seen as proving a non-asymptotic version of the Wilks phenomenon [START_REF] Wilks | The large-sample distribution of the likelihood ratio for testing composite hypotheses[END_REF] in a nonparametric setting with model misspecification [START_REF] Boucheron | A high dimensional Wilks phenomenon[END_REF], which makes this problem interesting beyond minimal-penalty algorithms. In addition to the settings mentioned in Section 4.2, concentration results for p 2 are available in two cases. For bounded-contrast minimizers, a concentration inequality is proved in a general setting including bounded regression and classification with Vapnik-Chervonenkis classes [START_REF] Boucheron | A high dimensional Wilks phenomenon[END_REF]. This result can be used for proving that Algorithm 5 works with regressogram estimators [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF]. For maximum-likelihood estimators, in a parametric setting [START_REF] Spokoiny | Parametric estimation. finite sample theory[END_REF], in a semiparametric setting [START_REF] Andresen | Critical dimension in profile semiparametric estimation[END_REF] and in a nonparametric setting with a quadratic penalty [START_REF] Spokoiny | Penalized maximum likelihood estimation and effective dimension[END_REF], p 2 is close to some quadratic form with high probability, and this quadratic form itself satisfies some concentration properties. Nevertheless, these results have not been used yet for proving that Algorithm 5 works. Note also that a concentration inequality for p 2 (m), with histogram (maximum-likelihood) density estimators and the Kullback risk, have been obtained by [START_REF] Saumard | Finite sample improvement of Akaike's information criterion[END_REF], improving previous results by [START_REF] Saumard | Nonasymptotic quasi-optimality of AIC and the slope heuristics in maximum likelihood estimation of density using histogram models[END_REF].

Proof of Eq. (66) Apart from the specific approaches mentioned in Section 5.2.2, we do not know any result for bounding directly |p 1 (m)p 2 (m)|/p 1 (m) as required in Eq. ( 66).

Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019 5.3. Hints for (γ): how to prove that C pen 1 is an optimal penalty?

When C pen 1 (m) = E [p 1 (m) + p 2 (m)],
oracle inequalities (γ) or ( γ ) usually rely on some concentration inequality for the ideal penalty R( s m ) -R n ( s m ) = p 1 (m) + δ (m) + p 2 (m), as in step 3 of the proof of Theorem 1. One actually needs only concentration for

R( s m ) -R n ( s m ) -R( s m ) -R n ( s m )
for all m, m ∈ M . Concentration results for δ (m)δ (m ) and for p 2 (m) are reviewed in Section 5.2 since they are usually required for proving (β ). Therefore, we now focus on p 1 (m).

Concentration of the excess risk p 1 (m) What remains is to concentrate p 1 (m) -or equivalently R( s m ) -R(s ) or R( s m )around its expectation, a difficult problem that has not been solved except in a few settings: the ones for which a full proof of the slope heuristics exists -see Section 4.2-, and the ones listed below.

Several papers recently tackled the case of fixed-design linear regression with the least-squares risk, when s m minimizes a (penalized) least-squares criterion over a convex set, assuming that the penalty Ω is convex. Concentration inequalities for

R( s m ) -R(s ) or R( s m ) -R(s ) + Ω( s m )
are available under different assumptions on the noise (Gaussian or not) and on Ω [START_REF] Chatterjee | A new perspective on least squares under convex constraint[END_REF][START_REF] Bellec | Optimistic lower bounds for convex regularized least-squares[END_REF][START_REF] Bellec | Bounds on the prediction error of penalized least squares estimators with convex penalty[END_REF][START_REF] Muro | Concentration behavior of the penalized least squares estimator[END_REF]. They apply to various examples such as the Lasso (in its constrained formulation) and isotonic regression [START_REF] Chatterjee | A new perspective on least squares under convex constraint[END_REF], the Lasso and the group Lasso in their usual regularization formulation [START_REF] Bellec | Optimistic lower bounds for convex regularized least-squares[END_REF][START_REF] Bellec | Bounds on the prediction error of penalized least squares estimators with convex penalty[END_REF], splines and total-variation regularization [START_REF] Muro | Concentration behavior of the penalized least squares estimator[END_REF].

When Ω is a semi-norm, [START_REF] Bellec | The noise barrier and the large signal bias of the lasso and other convex estimators[END_REF] proves upper and lower bounds on E[R( s m )]. The article by [START_REF] Chen | A note on the approximate admissibility of regularized estimators in the Gaussian sequence model[END_REF] also is related to this topic.

For general losses, high-probability upper and lower bounds on R( s m ) -R(s ) -sometimes plus a regularization term Ω( s m )are proved by [START_REF] Bartlett | Empirical minimization[END_REF] for general empirical minimizers -with a rather abstract result-, by [START_REF] Saumard | Estimation par Minimum de Contraste Régulier et Heuristique de Pente en Sélection de Modèles[END_REF] for "regular" estimators and losses, and by van de Geer and Wainwright (2017) for regularized empirical risk minimizers -with precise applications provided for "linear losses" such as linearized least-squares regression, maximum-likelihood estimators on an exponential model, and log-linear regression. Note that the general approaches of [START_REF] Bartlett | Empirical minimization[END_REF], [START_REF] Saumard | Estimation par Minimum de Contraste Régulier et Heuristique de Pente en Sélection de Modèles[END_REF] and van de Geer and Wainwright (2017) are closely related; Chatterjee (2014), [START_REF] Bellec | Optimistic lower bounds for convex regularized least-squares[END_REF], [START_REF] Bellec | Bounds on the prediction error of penalized least squares estimators with convex penalty[END_REF] and [START_REF] Muro | Concentration behavior of the penalized least squares estimator[END_REF], which are mentioned above for linear regression, use a similar technique that is exposed clearly by Bellec (2017, Section 2) for instance. [START_REF] Saumard | A concentration inequality for the excess risk in least-squares regression with random design and heteroscedastic noise[END_REF] proves a concentration inequality for the quadratic risk R( s m ) of a leastsquares estimator over a convex set, in the heteroscedastic random-design regression setting; this result requires to handle specifically the quadratic part of the empirical process, which cannot be concentrated tightly with the general approach of van de Geer and Wainwright (2017) for instance. Note also that the result obtained by [START_REF] Saumard | A concentration inequality for the excess risk in least-squares regression with random design and heteroscedastic noise[END_REF] applies to more general models than the ones of [START_REF] Navarro | Slope heuristics and V-fold model selection in heteroscedastic regression using strongly localized bases[END_REF] for which a full proof of the slope heuristics exist. For histogram (maximum-likelihood) estimators and the Kullback risk in density estimation, in addition to the result obtained by [START_REF] Saumard | Nonasymptotic quasi-optimality of AIC and the slope heuristics in maximum likelihood estimation of density using histogram models[END_REF] and mentioned in Section 4.2, concentration inequalities for R( s m ) have been obtained by [START_REF] Castellan | Modified Akaike's criterion for histogram density estimation[END_REF], and [START_REF] Saumard | Finite sample improvement of Akaike's information criterion[END_REF] have recently improved them.

Let us also recall that Proposition 2 in Section 5.2.2 provides an alternative approach for proving (γ) when pen 1 (m) ∝ p 2 (m).

Related procedures

Minimal-penalty algorithms are primarily made for model/estimator selection, but in the fixeddesign regression setting (Algorithms 1 and 4) they also provide an estimator C jump of the noise variance σ 2 . This section compares minimal penalties to its main alternatives for both tasks, starting by residual-(co)variance estimation.

Residual-variance estimation

Let us consider the fixed-design regression setting of Sections 2 and 3.3-3.4 and their notation. An example of interest is when ∀i ∈ {1, . . . , n} , F i = f (x i ) for some smooth f and some design points

x i ∈ R d . ( 69
)
Literature on residual-variance estimation Many estimators exist for the residual variance σ 2 in nonparametric regression. An exhaustive list is beyond the scope of this article; for more references, we refer to the articles by Hall et al. (1990), [START_REF] Dette | Estimating the variance in nonparametric regression-what is a reasonable choice?[END_REF], [START_REF] Spokoiny | Variance estimation for high-dimensional regression models[END_REF], [START_REF] Müller | Estimating the error variance in nonparametric regression by a covariate-matched U-statistic[END_REF], [START_REF] Liitiäinen | Residual variance estimation in machine learning[END_REF] and [START_REF] Ramosaj | Consistent estimation of residual variance with random forest out-of-bag errors[END_REF], and to the articles by [START_REF] Belloni | Pivotal estimation via square-root Lasso in nonparametric regression[END_REF], [START_REF] Chatterjee | High dimensional regression and matrix estimation without tuning parameters[END_REF], [START_REF] Reid | A study of error variance estimation in Lasso regression[END_REF] and [START_REF] Giacobino | Quantile universal threshold[END_REF] for the high-dimensional variable-selection case. A related problem is noise-variance estimation in heteroscedastic regression (see [START_REF] Brown | Variance estimation in nonparametric regression via the difference sequence method[END_REF]Levine, 2007, Gendre, 2008, andreferences therein). This section focuses on minimal-penalty based estimators and on estimators that are quadratic forms of the data vector Y ∈ R n , that is,

σ 2 B := Y, BY tr(B) ( 70
)
where B is some n × n symmetric matrix. Eq. ( 70) actually covers several, if not all, classical residual-variance estimators -in particular the ones suggested in the context of model/estimator selection with C p or C L -, which allows their common non-asymptotic analysis [START_REF] Dette | Estimating the variance in nonparametric regression-what is a reasonable choice?[END_REF].

Residual-based estimators

The most classical variance estimators are based upon the residuals -through the empirical risk-on some model S m 0 : Remark that σ 2 m 0 = σ 2 B with B = I n -Π m 0 . When σ 2 must be estimated in the formula of the C p penalty, the classical suggestions are of the form σ 2 m 0 [START_REF] Mallows | Some comments on C p[END_REF][START_REF] Efron | How biased is the apparent error rate of a prediction rule?[END_REF][START_REF] Baraud | Model selection for regression on a fixed design[END_REF].

σ 2 m 0 := 1 n -D m 0 Y -F m 0 2 . ( 71
)
The bias of σ 2 m 0 as an estimator of σ 2 can be derived from Eq. ( 8):

E σ 2 m 0 -σ 2 = 1 n -D m 0 (I n -Π m 0 )F 2 . ( 72
)
If F ∈ S m 0 , then σ 2 m 0 is unbiased, and otherwise it suffers some upward bias, depending on the approximation error and on the dimension of S m 0 . Proposition 4 in Appendix A.4 provides a general formula for the variance and MSE of σ 2 m 0 . For instance, assuming for simplicity that the noise is Gaussian,

E σ 2 m 0 -σ 2 2 = 2σ 4 n -D m 0 + 4σ 2 (I n -Π m 0 )F 2 (n -D m 0 ) 2 + (I n -Π m 0 )F 4 (n -D m 0 ) 2 . ( 73
)
Choosing the model S m 0 without prior knowledge is a difficult question. For minimizing the MSE, one must trade off terms depending on 1/(n -D m 0 ) and on the approximation error, that vary differently as functions of S m 0 ; this can be as difficult as the model-selection problem. When some unbiased model S m 0 is known with D m 0 = o(n), taking it for the estimation of σ 2 is a reasonable choice. This matches the suggestion of [START_REF] Mallows | Some comments on C p[END_REF] and [START_REF] Efron | How biased is the apparent error rate of a prediction rule?[END_REF] in the variable-selection setting with a full model of dimension p = o(n). In the setting given by Eq. (69), when contiguous x i are close enough, a natural choice for S m 0 is the linear span of (e 2i + e 2i-1 ) 1 i n/2 where (e 1 , . . . , e n ) denotes the canonical basis of R n . Then, assuming for simplicity that n is even,

σ 2 m 0 = 1 n n/2 ∑ i=1 (Y 2i -Y 2i-1 ) 2 (74)
is a consistent estimator of σ 2 if f is uniformly continuous and max 1 i n x ix i+1 = o(1).

Note that for high-dimensional variable selection, several residual-based estimators on a datadriven model m 0 -for instance, chosen by cross-validation-are available, but theoretical guarantees are still lacking for several of them [START_REF] Reid | A study of error variance estimation in Lasso regression[END_REF][START_REF] Giacobino | Quantile universal threshold[END_REF].

Variance estimation with minimal penalties The problem of choosing m 0 for σ 2 m 0 can be solved (bypassed in fact) by using the slope heuristics. Let us state non-asymptotic risk bounds for C thr. and C window as estimators of σ 2 , that derive from Theorem 1 and its proof in Section 2.

Proposition 3. In the framework described in Section 2.1, assume that M is finite, contains at least one model of dimension at most c n ∈ [0, n/3), and that (HId) and (HG) hold true -see Section 2.5. Let C thr. (T n ) be defined by Eq. (20) with T n ∈ (c n , n), and C window (η) be defined by Eq. ( 19) with η > 0. For any x 0 and T ∈ (c n , n), let us define

C 1 (x; T ) := σ 2 1 - 4 x n + 6 x n 1 -T n and C 2 (x; T ; c n ) := σ 2 1 + 4n T -c n x n + 2x n + 2n T -c n B(c n ) where B(c n ) := inf m∈M / D m c n 1 n (I n -Π m )F 2 .
Then, an event Ω x of probability at least 1 -4 card(M )e -x exists on which

C 1 x; 2n 3 1 + η C window (η) C 2 x; n 3 (1 + η) if η > C 2 x; n 3 C 1 x; 2n 3 -1 and x ∈ 0, n 180 , (75)
and

C 1 (x; T n ) C thr. (T n ) C 2 (x; T n ; c n ) . ( 76
)
If we assume in addition that c n T n /2, then,

E C thr. -σ 2 2 739 max 1 - T n n -2 , T n 2n -2 × B T n 2 2 + σ 4 log(4 card M ) n + σ 4 log(4 card M ) n 2 . ( 77
)
Proposition 3 is proved in Appendix A.3. Note that the constant 739 in Eq. ( 77) can be strongly reduced under mild additional assumptions, see Appendix A.3. Proposition 3 can also be extended to (φ 2 σ 2 )-sub-Gaussian noise, at the price of replacing x by Lφ 2 x in Eq. ( 75)-( 76) and log(4 card M ) by Lφ 2 log(4 card M ) in Eq. ( 77), where L is a numerical constant; see Remark 1 in Section 2.5.

If B(c n ) tends to 0 as n tends to +∞ -which is a mild assumption-, by Proposition 3 with x = 2 log(n) + log(4 card M ), we get that C thr. (T n ) and C window (η) estimate consistently σ 2 , with deviation bounds of order

B(c n ) + σ 2 log(n) + log(card M ) n ,
provided that c n τn with τ < 1/3,

T n = ρn with ρ ∈ (0, 1) , and
σ 2 η ∝ B(c n ) + σ 2 log(n) + log(card M ) n .
These deviation bounds for C thr. and C window can be interpreted as an oracle inequality, since they coincide with the best possible risk of σ 2 m 0 with D m 0 c n , without any prior knowledge except the choice of (S m ) m∈M . Indeed, Eq. ( 73) shows that when D m 0 c n τn with τ < 1, up to constants depending on τ only,

E ( σ 2 m 0 -σ 2 ) 2 1 n (I n -Π m 0 )F 2 + σ 2 √ n B(c n ) + σ 2 √ n .
Soumis The bound (77) on the mean squared error (MSE) of C thr. can be compared to the minimax optimal rate ∝ n -min{1,8/d} for the MSE in the setting of Eq. ( 69) when f has a bounded secondorder derivative [START_REF] Spokoiny | Variance estimation for high-dimensional regression models[END_REF]. Assuming that log(card M ) = o(n 1/9 ), that the approximation error B(c n ) is minimax optimal hence of order c -4/d n , and that c n τn with τ < 1, we get that C thr. is optimal when d 9 up to constants and within a factor log(card M ) of the minimax risk when d 8. Similar risk bounds can easily be obtained from Proposition 3 under different assumptions on the signal. For instance, when Eq. ( 69) holds true with f that is α-Hölderian for some α > 0, an approximation error of order D -2α/d m can be obtained with local polynomials of maximal degree α . We conjecture that these residual-variance estimation bounds are minimaxoptimal up to logarithmic factors provided that (S m ) m∈M has a cardinality at most polynomial in n and achieves the minimax approximation error bounds. These consequences of Proposition 3 have the flavor of adaptive risk bounds derived from oracle inequalities [START_REF] Birgé | From model selection to adaptive estimation[END_REF], which is new for residual-variance estimation to the best of our knowledge. Therefore, the additional log(card M ) factor -coming from the union bound over m ∈ M and typically of order log(n)-seems a mild price for the versatility of C thr. and C window .

Residual-based estimators vs. the slope heuristics In addition to the risk bounds comparison above, we can compare the definition of σ 2 m 0 with the one of C slope in Algorithm 2. On the one hand, σ 2 m 0 estimates the asymptotic slope of -Y -F m 2 as a function of D m from two points: m 0 and m 1 such that S m 1 = R n . On the other hand, Algorithm 2 makes a (robust) linear regression over, say, all m such that D m ∈ [n/2, n]. An illustration is provided by Figure 10 in Appendix C. This confirms that minimal penalties -here, the slope heuristics-allow to avoid the choice of a single m 0 ∈ M by making use of the full collection (S m ) m∈M for estimating the residual variance. Intuitively, this difference makes Algorithm 2 more stable and less dependent on some strong assumption about S m 0 . The numerical experiments of Figure 6b in Section 7.1 and Figure 10 in Appendix C indeed show that when S m 0 happens to be a bad model, σ 2 m 0 can suffer from a large error, whereas C thr. is much more robust.

Residuals of linear estimators

Residual-based estimators have also been proposed with several other linear estimators F m 0 = A m 0 Y of F, that is, defined as σ 2 B in Eq. ( 70) with a matrix B = (I n -A m 0 ) (I n -A m 0 ). For instance, A m 0 can correspond to some Nadaraya-Watson fit (also known as kernel-based estimator; [START_REF] Hall | On variance estimation in nonparametric regression[END_REF] or to spline smoothing [START_REF] Carter | A comparison of variance estimators in nonparametric regression[END_REF]; the article by [START_REF] Dette | Estimating the variance in nonparametric regression-what is a reasonable choice?[END_REF] provides more references. In the setting given by Eq. ( 69), the challenging case d > 1 can be tackled with k-nearest neighbors [START_REF] Liitiäinen | Residual variance estimation using a nearest neighbor statistic[END_REF] or a local linear fit of f [START_REF] Spokoiny | Variance estimation for high-dimensional regression models[END_REF]. All these estimators suffer from the same drawback as σ 2 m 0 , that is, they rely on the choice of a single matrix A m 0 , hence requiring to specify the regularization parameter m 0 . On the contrary, the minimal-penalty approach of Algorithm 4 avoids this choice in a principled way.

Difference-based estimators Difference-based estimators are an important family of residualvariance estimators, which are designed for the setting of Eq. ( 69) when x ix i+1 = o(1) and f is smooth, often assuming d = 1. The first example has been proposed by [START_REF] Rice | Bandwidth choice for nonparametric regression[END_REF], which is close to the residual-based estimator defined by Eq. ( 74). More generally, differencesequence estimators of order m 1 are defined by

σ 2 Rice := 1 2(n -1) n-1 ∑ i=1 (Y i+1 -Y i ) 2 ,
σ 2 (d 0 ,...,d m ) = 1 n -m n-m ∑ i=1 m ∑ j=0 d j Y i+ j 2 where m ∑ j=0 d j = 0 and m ∑ j=0 d 2 j = 1 .
The only admissible sequence (d j ) j=0,1 for m = 1 leads to σ 2 Rice . For a general order m, when x i ∈ R, the optimal sequence (d j ) j=0,...,m in terms of MSE does not depend on f asymptotically and can be computed explicitly (Hall et al., 1990), although the picture can be quite different in a non-asymptotic setting [START_REF] Dette | Estimating the variance in nonparametric regression-what is a reasonable choice?[END_REF].

Assuming x i ∈ R, difference-based estimators of order m 1 are suboptimal by a constant factor 1 + 1/(2m) in terms of MSE for normal data (Hall et al., 1990), while for instance the residual-based estimator of [START_REF] Hall | On variance estimation in nonparametric regression[END_REF] attains the optimal rate var(ε 2 1 )/n. This issue is corrected for instance with covariate matching [START_REF] Müller | Estimating the error variance in nonparametric regression by a covariate-matched U-statistic[END_REF][START_REF] Du | A covariate-matched estimator of the error variance in nonparametric regression[END_REF], which in the case of order m = 1 consists in replacing σ 2

Rice by

1 2n(n -1) ∑ i = j W i, j (Y i -Y j ) 2
with some well-chosen weights W i, j 0 [START_REF] Müller | Estimating the error variance in nonparametric regression by a covariate-matched U-statistic[END_REF]. Another variant of difference-based estimators, which is asymptotically optimal, is studied by [START_REF] Tong | Optimal variance estimation without estimating the mean function[END_REF].

Choosing m and the sequence (d j ) j=0,...,m is also a difficult problem with no prior knowledge [START_REF] Dette | Estimating the variance in nonparametric regression-what is a reasonable choice?[END_REF]. But the main drawback of such estimators is that, when f is not continuous, they can be severely biased in an unpredictable way. An empirical method for detecting whether the bias is small enough is proposed by [START_REF] Buckley | A graphical method for estimating the residual variance in nonparametric regression[END_REF] and might be useful.

Estimation of the residual covariance matrix

Assume now that several regression problems such as (1) must be solved simultaneously, a framework known as "multi-task regression", "multivariate regression", "multiple linear regression", and "seemingly unrelated regression"; the article by [START_REF] Solnon | Multi-task regression using minimal penalties[END_REF] and the PhD dissertation of [START_REF] Solnon | Apprentissage statistique multi-tâches[END_REF] provide references on this topic. One observes Y j = F j + ε j ∈ R n for j = 1, . . . , p, assuming that the noise vectors E i := (ε j i ) j=1,...,p ∈ R p are independent and identically distributed, with zero mean and covariance matrix Σ ∈ M p (R). Then, a natural extension of the residual-variance estimation problem is the estimation of Σ with as few prior knowledge on the F j as possible, which is often required for the multi-task problem of estimating (F j ) j=1,...,p . For instance, [START_REF] Solnon | Multi-task regression using minimal penalties[END_REF] make use of the prior knowledge that the F j are close, in combination with kernel ridge regression, and selects regularization parameters with a penalty generalizing C L which depends on the full matrix Σ.

An estimator Σ of Σ based upon minimal penalties is proposed by [START_REF] Solnon | Multi-task regression using minimal penalties[END_REF]. It satisfies (1η)Σ Σ (1 + η)Σ with large probability, with η ∝ p log(n)/nc(Σ) 2 where c(Σ) is the condition number of Σ. The construction of Σ goes as follows:

(i) For every j ∈ {1, . . . , p}, apply Algorithm 4 to the one-dimensional regression problem Y j = F j + ε j , and store a j = C jump which estimates a j := Σ j, j . (ii) For every i = j ∈ {1, . . . , p}, apply Algorithm 4 to the one-dimensional regression problem (Y i + Y j ) = (F i + F j ) + (ε i + ε j ), and store a i, j = C jump which is an estimator of a i, j := Σ i,i + Σ j, j + 2Σ i, j . (iii) Denote by J the linear map on R p(p+1)/2 that sends ((a j ) 1 j p , (a i, j ) 1 i = j p ) to Σ, and define Σ = J(( a j ) 1 j p , ( a i, j ) 1 i = j p ). This construction can actually be generalized to any other one-dimensional residual-variance estimator σ 2 that satisfies (1η 0 )σ 2 σ 2 (1 + η 0 )σ 2 with large probability for all the above one-dimensional problems, leading to a similar result with η ∝ c(Σ)pη 0 . The remarkable property of the minimal-penalty-based estimator Σ of [START_REF] Solnon | Multi-task regression using minimal penalties[END_REF] is that it suffices to assume that an estimator of small complexity has a small approximation error -with slightly stronger constraints compared to Theorem 1, see the exact assumptions of Arlot and Bach ( 2011)for each one-dimensional problem Y j to get this assumption automatically satisfied for all the Y i +Y j , i = j. For selecting among linear estimators with the least-squares risk, a popular penalization approach is Mallows' C L [START_REF] Mallows | Some comments on C p[END_REF], as described in Section 3.3:

m C L ∈ argmin m∈M 1 n F m -Y 2 + pen C L (σ 2 , m) with pen C L (σ 2 , m) := 2σ 2 tr(A m ) n . (78)
In the particular case of projection estimators, tr(A m ) = D m the dimension of the corresponding model, and C L reduces to C p which is described in Section 2.2. Both C p and C L penalties assume that the noise-level σ 2 is known, so in general it must be replaced by some data-driven estimation of it. Minimal-penalty algorithms provide an estimator of σ 2 specially built for this estimatorselection task (Algorithms 1 and 4), which can be plugged into Eq. ( 78) and for which theoretical guarantees can be proved, as shown by Theorem 1 and [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF]. This subsection reviews some classical ways to estimate σ 2 inside Eq. ( 78), as well as other estimator-selection procedures that are closely related, in the framework of Section 3.3 (linear estimator selection) and with its notation.

Fixed variance estimator A first option is to replace σ 2 by some fixed estimator σ 2 of this quantity, for instance chosen among the estimators described in Section 6.1. The most classical choice is to take a residual-based estimator σ 2 m 0 as defined by Eq. ( 71), for some m 0 ∈ M (Mallows, 1973; [START_REF] Efron | How biased is the apparent error rate of a prediction rule?[END_REF][START_REF] Baraud | Model selection for regression on a fixed design[END_REF]. For projection estimators, this option is often named "C p " and called "C p (L 0 , L )" by Efron (1986, Table 4). As discussed in Section 6.1, choosing m 0 can then be as difficult as the original estimator-selection problem.

When using the penalty pen C L ( σ 2 , m), theoretical guarantees can be obtained if one can prove that σ 2 is close to σ 2 with large probability, in combination with Theorem 1 or its analogous for linear estimators. For instance, Baraud (2000, Theorem 6.1) does it for projection estimators with σ 2 m 0 such that D m 0 = n/2; the approximation error of m 0 then appears as an additive term in the right-hand side of the oracle inequality. Nevertheless, even if such guarantees imply some asymptotic-optimality result -provided that the approximation error of m 0 tends to zero-, they might not help for choosing the best possible estimator σ 2 in terms of estimator selection, since these only are upper bounds. Indeed, the best bound is obtained when σ 2 is well concentrated around σ 2 , but it is known that overpenalizing a bit -that is, taking σ 2 slightly larger than σ 2 -empirically improves the estimatorselection performance (see Section 8.4). Residual-based estimators do overpenalize, because of the approximation error of m 0 , but the overpenalization factor is unknown in practice and cannot be controlled without strong assumptions on the target F; the consequences of a bad choice of m 0 with σ 2 m 0 are illustrated in the numerical experiments of Section 7.1, see Figures 67. On the contrary, minimal-penalty algorithms are more than a simple "plug in" of an estimator of σ 2 -independent of the estimator-selection problem-inside pen C L . As detailed in Section 8.4, minimal-penalty algorithms seem to overpenalize slightly, by design, but a formal proof of this phenomenon remains an open problem.

Variance estimator depending on m Another approach is to plug into Eq. ( 78) a different variance estimator for each m ∈ M , by considering the residuals on the model m for which the penalty is computed. In other words, assuming that D m < n for all m ∈ M , m is chosen by penalization with the penalty pen C L ( σ 2 m , m). Let us consider projection estimators for simplicity. Then m minimizes over m ∈ M the criterion

crit FPE (m) := 1 n F m -Y 2 + 2 σ 2 m D m n = 1 n F m -Y 2 1 + 2D m n -D m (79)
which has been proposed by [START_REF] Akaike | Fitting autoregressive models for prediction[END_REF][START_REF] Akaike | Statistical predictor identification[END_REF] under the name FPE -final prediction errorand is called "naive C p " or "C p (L 0 , L 0 )" by Efron (1986, Table 4). The FPE criterion (79) actually is a particular case of the multiplicative penalties defined by Eq. ( 59) in Section 4.6. More references and non-asymptotic oracle inequalities satisfied by such multiplicative penalties can be found in the article by [START_REF] Baraud | Gaussian model selection with an unknown variance[END_REF], which explains in particular how the FPE criterion (79) should be enlarged, depending on the size of the collection M . The main drawback of multiplicative penalties is probably that they need to deal carefully with the largest models.

For instance, for FPE, the results of Baraud et al. (2009, Theorem 1) assume that for all m ∈ M , D m 0.39(n + 2) -1, an assumption that can be weakened into D m ρn for some ρ < 1 when considering a modified multiplicative penalty (Baraud et al., 2009, Corollary 1).

Generalized cross-validation For choosing the regularization parameter of some smoothing methods, [START_REF] Wahba | A survey of some smoothing problems and the method of generalized cross-validation for solving them[END_REF] proposed the criterion called "generalized cross-validation" (GCV) defined as a rotationally invariant form of the cross-validation estimate, that is,

crit GCV (m) := 1 n F m -Y 2 1 n tr(I n -A m ) -2 . ( 80
)
GCV can also be seen as a reweighted cross-validation estimate, which takes into account the asymmetry of the design [START_REF] Craven | Smoothing noisy data with spline functions. Estimating the correct degree of smoothing by the method of generalized cross-validation[END_REF]. Nevertheless, as remarked by Efron (1986, Remark W), "Despite its name, GCV is (nearly) a member of the C p family of estimates". Indeed, considering projection estimators only, where the approximation holds true when D m n. Theoretical guarantees for GCV are available in various settings [START_REF] Li | From Stein's unbiased risk estimates to the method of generalized cross validation[END_REF][START_REF] Li | Asymptotic optimality for C p , C L , cross-validation and generalized cross-validation: discrete index set[END_REF][START_REF] Cao | On oracle inequalities related to smoothing splines[END_REF], with the same limitation as the ones of FPE and other multiplicative penalties. For instance, Cao and Golubev (2006, Theorem 2) consider a truncated version of GCV where all m ∈ M such that tr(A m ) > √ n are discarded, and some examples exist 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]. Let us finally mention that an empirical comparison of GCV and minimal penalties (Algorithm 4) is done by Arlot andBach (2009, 2011) for several kinds of linear estimators, showing that either Algorithm 4 clearly outperforms GCV or the two methods perform similarly, depending on the setting.

crit GCV (m) = 1 n F m -Y 2 n n -D m 2 ≈ 1 n F m -Y 2 n + D m n -D m = crit FPE (m) (81)

L-curve, corner, and elbow heuristics

Minimal-penalty algorithms, in particular Algorithms 1-3, can be related to some "L-curve", "corner" or "elbow" heuristics, which are often used for choosing hyperparameters in the statistics and machine-learning communities.

The L-curve is defined as a plot of the size of the residuals versus the size or the estimator complexity. Using the notation of Section 3, when the goal is to select an estimator among ( s m ) m∈M , the L-curve can be defined as (C m , R n ( s m )) m∈M . For instance, the right part of Figure 2 in Section 2.4 shows an L-curve (the black dots); Figure 11 in Appendix C provides another illustration. The practical use of the L-curve has been suggested by [START_REF] Miller | Least squares methods for ill-posed problems with a prescribed bound[END_REF] and Lawson and Hanson (1974, Chapters 25-26). Some precise heuristic choice of a regularization parameter -often called "the L-curve method"-has first been proposed by [START_REF] Hansen | Analysis of discrete ill-posed problems by means of the L-curve[END_REF] and [START_REF] Hansen | The use of the L-curve in the regularization of discrete ill-posed problems[END_REF] for some inverse problem with Tikhonov regularization. The main idea is that the L-curve has three main parts:

(i) a straight part where the residuals R n ( s m ) decrease fastly while C m is almost constant, where the regularization is too strong, (ii) a flat part where C m increases much while the residuals R n ( s m ) decrease slowly, where some overfitting occurs, and (iii) in between, a "corner" or "elbow", where the regularization parameter is of the correct order. Therefore, the L-curve is L-shaped -hence its name, given by [START_REF] Hansen | The use of the L-curve in the regularization of discrete ill-posed problems[END_REF]and the L-curve method suggests to choose m corresponding to the corner of the "L".

Several definitions of the corner can be proposed, as well as several measures of "size" and "complexity" can be considered when plotting the L-curve [START_REF] Hansen | The use of the L-curve in the regularization of discrete ill-posed problems[END_REF]. The most common choice is to define the corner as the location where the L-curve has a maximal curvature [START_REF] Hansen | The use of the L-curve in the regularization of discrete ill-posed problems[END_REF] -hence the name "maximum-curvature criterion" [START_REF] Grodzevich | Regularization using a parameterized trust region subproblem[END_REF] often used for this heuristics-and to look at the L-curve in log-log scale [START_REF] Hansen | The use of the L-curve in the regularization of discrete ill-posed problems[END_REF], although several variants exist [START_REF] Regińska | A regularization parameter in discrete ill-posed problems[END_REF]. Additional practical problems need also to be solved, especially when M is discrete (how to define the curvature of a finite set of points?) and when some computational issues arise, for instance because computing every single point of the L-curve is expensive [START_REF] Hansen | The use of the L-curve in the regularization of discrete ill-posed problems[END_REF][START_REF] Castellanos | The triangle method for finding the corner of the L-curve[END_REF][START_REF] Hansen | An adaptive pruning algorithm for the discrete L-curve criterion[END_REF][START_REF] Heng | Model functions in the modified L-curve method-case study: the heat flux reconstruction in pool boiling[END_REF]. Another option, proposed for a change-point detection problem [START_REF] Lung-Yut-Fong | Homogeneity and change-point detection tests for multivariate data using rank statistics[END_REF], relies on performing two linear regressions on the L-curve in order to identify its parts (i) and (ii); it can therefore be directly related with the "slope" formulation of minimal-penalty algorithms. Empirical or theoretical studies of L-curve algorithms are available mostly for inverse problems with Tikhonov regularization [START_REF] Hansen | Analysis of discrete ill-posed problems by means of the L-curve[END_REF], truncated SVD [START_REF] Hansen | The use of the L-curve in the regularization of discrete ill-posed problems[END_REF][START_REF] Reichel | Old and new parameter choice rules for discrete ill-posed problems[END_REF], or conditional-gradient regularization [START_REF] Castellanos | The triangle method for finding the corner of the L-curve[END_REF], showing reasonably good empirical performance. Several of the papers mentioned in this subsection show that L-curve algorithms compare favorably to generalized cross-validation (GCV) on simulated examples; for instance, [START_REF] Hansen | Analysis of discrete ill-posed problems by means of the L-curve[END_REF] show some similarity between GCV and L-curve algorithms, and report a tendency of GCV to overregularize. Nevertheless, the L-curve method is proved to be not consistent in several families of realistic examples (Engl and Grever, 1994;[START_REF] Vogel | Non-convergence of the L-curve regularization parameter selection method[END_REF][START_REF] Hanke | Limitations of the L-curve method in ill-posed problems[END_REF], when the noise tends to zero or when the sample size tends to infinity. According to [START_REF] Hanke | Limitations of the L-curve method in ill-posed problems[END_REF], the reason for this inconsistency is that the corner seems to correspond to the minimal level of regularization -the minimal penalty, with the words of the present survey-more than to the optimal level; hence choosing m at the corner leads to some overfitting.

The L-curve can also be used similarly in unsupervised learning for choosing the number of clusters, where it is defined as a plot of the within-cluster dispersion as a function of the number of clusters. Indeed, as written by [START_REF] Tibshirani | Estimating the number of clusters in a data set via the gap statistic[END_REF], "Statistical folklore has it that the location of such an 'elbow' indicates the appropriate number of clusters". Various methods actually use a similar idea [START_REF] Tibshirani | Estimating the number of clusters in a data set via the gap statistic[END_REF][START_REF] With Discussion By | Finding the number of clusters in a dataset: an information-theoretic approach[END_REF][START_REF] Matias | Statistical clustering of temporal networks through a dynamic stochastic block model[END_REF], although they are not straightforward applications of the method of [START_REF] Hansen | The use of the L-curve in the regularization of discrete ill-posed problems[END_REF]. Remark that procedures choosing the number of clusters using the slope heuristics show good experimental results, according to Baudry (2009, Section 4.4), Maugis and Michel (2011a), [START_REF] Bontemps | Clustering and variable selection for categorical multivariate data[END_REF] and [START_REF] Baudry | Estimation and model selection for model-based clustering with the conditional classification likelihood[END_REF].

Comparison with minimal-penalty algorithms Let us start with their common points. Both corner/elbow heuristics and minimal-penalty algorithms are based on the L-curve: directly in Algorithm 2, indirectly in Algorithm 1 since (D m(C) ) C 0 can be seen as a reparametrization of the convex hull of the L-curve. Both rely on the idea of detecting a sharp variation of an observable quantity (the curvature / the selected dimension in D m(C) ) in some region of interest (the optimal value of regularization parameters / the minimal value of the constant in front of the penalty). For both methods, a visual check (of the presence of an elbow / a jump) is possible, and strongly encouraged [START_REF] Hansen | The use of the L-curve in the regularization of discrete ill-posed problems[END_REF][START_REF] Baudry | Slope heuristics: overview and implementation[END_REF]. The strength of the connection between elbow heuristics and minimal penalties is emphasized in the following three works. For choosing the constant in front of the penalty for change-point detection, Lavielle (2005, Remark 2) suggests an algorithm close to (but slightly different from) the slope-heuristics algorithm of [START_REF] Lebarbier | Detecting multiple change-points in the mean of a Gaussian process by model selection[END_REF], which can be formulated as a maximal-curvature criterion on the L-curve. For Hawkes-process estimation via model selection, when the model collection is large, Reynaud-Bouret and Schbath (2010) remark that the true model generally corresponds to a sharp angle of the L-curve, hence propose an algorithm between the slope and elbow heuristics, which consists in choosing m( C) with pen(m) = C m and C equal to the opposite of the slope of the segment joining the first and the last point of the L-curve. For choosing the bandwidth of a Gaussian kernel for quantile estimation with one-class support vector machines, Vert (2006, Section 6.2.2) points out an "elbow effect" and locates the elbow region with a "maximal jump" procedure similar to Algorithm 1. Nevertheless, several important differences must be pointed out between the two approaches. First, the elbow heuristics tries to localize directly the optimal m whereas the slope heuristics localizes it in two steps: first, it estimates the minimal penalty, then, it uses an estimated optimal penalty for selecting some m. Second, the assumptions made on the shape of the L-curve are different. The L-curve must be exactly L-shaped for elbow heuristics, since otherwise the curvature can be large far from the "true" elbow. On the contrary, the slope heuristics assumes a linear behavior of the empirical risk as a function of D m (or C m ) only for large models (Algorithms 2 and 6), and makes an even milder assumption with its jump formulation (Algorithms 1 and 5; see Theorem 1). Third, theoretical grounds are much stronger for the slope heuristics (with strong optimality results like Theorem 1 in several settings) than for the elbow heuristics which is even proved inconsistent in some realistic cases (Engl and Grever, 1994;[START_REF] Vogel | Non-convergence of the L-curve regularization parameter selection method[END_REF][START_REF] Hanke | Limitations of the L-curve method in ill-posed problems[END_REF].

Overall, we consider the slope heuristics and its generalization (minimal penalties) as a simple and principled way to localize an elbow on the L-curve (when there is one), and to make use of it for optimal model/estimator selection. In particular, a natural answer to the problem of choosing the scale at which the L-curve should be considered on the x-axis is given by Section 3.6: it should be (the shape of) the minimal penalty.

Scree test and related methods

For choosing the number of factors in factor analysis, or the number of components in principal components analysis, some classical methods can be related to minimal-penalty and L-curve algorithms.

Scree test

The most popular one -named the scree test-has been proposed by Cattell for factor analysis [START_REF] Cattell | The scree test for the number of factors[END_REF][START_REF] Cattell | A comprehensive trial of the scree and k.g. criteria for determining the number of factors[END_REF]. It is based upon the "scree plot", that is, a plot of the eigenvalues versus their rank (in decreasing order), which can be seen as an L-curve for factor analysis. The key remark made by [START_REF] Cattell | The scree test for the number of factors[END_REF] is that the scree plot ends with a linear part -a scree-, and that the beginning of the linear part corresponds to the "correct" number of factors. Overall, the scree test chooses a number of factors equal to the rank of the starting point of the linear part at the end of the scree plot.

This idea is close to the "slope" formulation of minimal-penalty algorithms (Algorithms 2 and 6). By analogy, we can say that the starting point of the linear part in the scree plot is a "minimal regularization level" -an upper bound on the number of factors that should be kept at the end. This fits well the goal of the initial paper by [START_REF] Cattell | The scree test for the number of factors[END_REF], which is not to find the exact true number of factors -a quantity which might be impossible to define formally-, but only to keep a number of factors which explain 95% to 99% of the "substantive variance". Nevertheless, the scree test seems to be often used for estimating the "true number of factors" itself [START_REF] Jackson | Stopping rules in principal components analysis: a comparison of heuristical and statistical Soumis au[END_REF].

Similarly to minimal-penalty and L-curve algorithms, making use of the scree test requires to overcome practical issues: Cattell remarks that "even a test as simple as this requires the acquisition of some art in administering it" [START_REF] Cattell | The scree test for the number of factors[END_REF]. For instance, it seems important to normalize the data [START_REF] Cattell | The scree test for the number of factors[END_REF], and sometimes the scree plot ends with two or three linear parts -then, one should cut at the beginning of the first linear part [START_REF] Cattell | The scree test for the number of factors[END_REF]. Variants Several variants of the scree test exist. The number of factors can for instance be given by the intersection of the scree plot with some reference curve, which corresponds to some "average scree plot" obtained with "pure noise", as proposed by [START_REF] Horn | A rationale and test for the number of factors in factor analysis[END_REF] and [START_REF] Horn | Cattell's scree test in relation to Bartlett's chi-square test and other observations on the number of factors problem[END_REF], and by Frontier's broken stick method [START_REF] Frontier | Étude de la décroissance des valeurs propres dans une analyse en composantes principales: Comparaison avec le modèle du bâton brisé[END_REF].

Another variant exists for estimating the intrinsic dimension of some data set, inside a classification procedure [START_REF] Bouveyron | Kernel discriminant analysis and clustering with parsimonious Gaussian process models[END_REF]. Given a decreasing sequence of eigenvalues (λ ( j) ) 1 j n , the estimated intrisic dimension is the smallest j such that λ ( j)λ ( j+1) T for some threshold T , which can be chosen by cross-validation in the article by [START_REF] Bouveyron | Kernel discriminant analysis and clustering with parsimonious Gaussian process models[END_REF]. The underlying assumption is that the scree plot is L-shaped, and that the point where the discrete derivative goes below T corresponds to the "elbow", or to the beginning of the linear part.

Results All these methods are only validated by numerical experiments [START_REF] Cattell | A comprehensive trial of the scree and k.g. criteria for determining the number of factors[END_REF]. For instance, for principal component analysis, [START_REF] Jackson | Stopping rules in principal components analysis: a comparison of heuristical and statistical Soumis au[END_REF] concludes that the broken stick method is one of the two best methods for choosing the number of components. The scree test tends to overestimate by one the number of components according to [START_REF] Jackson | Stopping rules in principal components analysis: a comparison of heuristical and statistical Soumis au[END_REF], which is consistent with our remark above that it corresponds to a "minimal regularization level" -not an optimal one. Note however that some theoretical results are proved for the closely related problem of lowrank matrix recovery from noisy data by hard-thresholding of singular values. In an asymptotic framework, when the goal is to minimize the asymptotic mean squared error in some specific asymptotic regime, [START_REF] Gavish | The optimal hard threshold for singular values is 4/ √ 3[END_REF] show that the optimal hard threshold can be written λ (m/n) √ nσ when the matrix to recover is of size m × n. Interestingly, the "minimal threshold", which corresponds to the largest singular value obtained from pure noise, is asymptotically equal to (1 + m/n) √ nσ . In the framework of [START_REF] Gavish | The optimal hard threshold for singular values is 4/ √ 3[END_REF], the scree test would correspond to using the "minimal hard threshold", and it seems indeed reasonable to use it for estimating the rank (the number of factors). On the contrary, when the goal is to minimize some quadratic error, the optimal threshold is a bit larger: Gavish and Donoho (2014, Figure 4) show that ∀m n, λ m n > 1 + m n .

Thresholding under the null

A related approach, for choosing the threshold λ of thresholding estimators, starts by considering the minimal value λ min of the threshold such that the estimator is equal to zero. Under the null hypothesis -that is, when the true signal is zero-, λ min = λ null min corresponds to the minimal thresholding level, and any good threshold must be larger than λ null min . For instance, in the setting of the previous paragraph -that is, singular-values hard thresholding-, λ null min is of order (1 + m/n) √ nσ , and Gavish and Donoho (2014) provide an explicit formula for the optimal threshold, which can be written c(m/n) λ null min for some c(m/n) > 1. In a general setting, [START_REF] Giacobino | Quantile universal threshold[END_REF] define the quantile universal threshold (QUT) λ QUT as the (1α)-quantile of λ null min for some α ∈ (0, 1). It turns out that QUT corresponds to the universal threshold proposed for wavelet thresholding [START_REF] Donoho | Wavelet shrinkage: asymptopia?[END_REF], and it can be used much more generally, beyond hard or soft thresholding. For instance, for choosing the regularization parameter λ of the Lasso and related procedures in high-dimensional regression, good performance can be obtained with λ = cλ QUT for some c > 1 (Giacobino et al., 2017, Section 4.2).

QUT and Algorithm 1 have common points: they both start by identifying a minimal value for the parameter of interest (λ or C), then multiply it by a constant factor to get an optimal value of the parameter. Their main difference lies in the definition of the minimal parameter value: it is obtained from data under the null-hypothesis for QUT, hence requiring to know -or at least to approximate-the null-hypothesis distribution, while Algorithm 1 defines it directly from the data, whatever their distribution.

Note that Section 7.5 details a procedure by [START_REF] Rozenholc | Statistical base jumping: A simple and fully data-driven answer to penalized model selection[END_REF], that is a variant of minimalpenalty algorithms for change-point detection, and can also be seen as a null-hypothesis based calibration procedure, hence similar to QUT.

Other model/estimator-selection procedures

Many other model/estimator-selection procedures exist and are studied. A detailed account on these is far beyond the scope of this survey. This subsection only mentions a few of them, that are of interest in relation with minimal-penalty algorithms.

Unknown variance First, in addition to the procedures based upon C p and C L that are listed in Section 6.3, some procedures are specially built for dealing with the problem of not knowing the noise variance in regression, which is also what minimal-penalty algorithms do in the regression case. For instance, [START_REF] Baraud | Estimator selection with respect to Hellinger-type risks[END_REF] provides an abstract general-purpose estimator-selection procedure, which leads to the model-selection procedure of [START_REF] Baraud | Estimator selection in the Gaussian setting[END_REF] for Gaussian model selection with unknown variance. We refer to the article by [START_REF] Giraud | High-dimensional regression with unknown variance[END_REF] for a detailed survey on high-dimensional variable-selection methods when the variance is unknown.

Cross-validation and resampling An important family of general-purpose estimator-selection procedures is cross-validation [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF], and more generally all resamplingbased selection procedures -e.g., resampling-based penalties (see Arlot, 2009, and references therein). Comparing them to minimal-penalty algorithms is interesting at least in two distinct situations.

First, when Algorithm 5 works with pen 0 and pen 1 known but C is unknown -for instance, for linear estimators in regression with the least-squares risk-resampling-based procedures are natural competitors, that can be used either for choosing the constant in front of pen 1 , or directly for the initial estimator-selection problem. Then, minimal-penalty algorithms have a clear advantage over resampling, because of their much smaller computational cost (see Section 7.2), while they have comparable or better statistical performance according to both theoretical and experimental results, as shown for instance by [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF].

Second, when Algorithm 5 works with some unknown pen 0 and/or pen 1 , an option mentioned in Remark 3 in Section 4.2 is to estimate them by resampling. Then, the computational cost of Algorithm 5 is comparable to that of cross-validation and other resampling strategies applied to the initial estimator-selection problem. In such cases, the interest of using minimal penalties is the precise non-asymptotic calibration of the constant in front of the resampling-based penalty, which is not guaranteed when using the theoretical value for this constant, since it is often based upon asymptotic considerations. In addition, the conjecture detailed in Section 8.4 suggests another reason for combining resampling and minimal penalties in such frameworks.

Some practical remarks

This section discusses several practical questions about the use of minimal-penalty algorithms.

A more detailed study of some of them can be found in the survey by [START_REF] Baudry | Slope heuristics: overview and implementation[END_REF].

Several definitions for C

The minimal-penalty estimator C of the constant that should be put in front of the penalty pen 1 can be defined in several ways, which leads to the practical issue of choosing one among these definitions. Two main approaches are proposed in the previous sections.

Jump approach First, C can be defined as the position C jump of "the unique large jump" of C → C m (0) min (C) , as in Algorithms 1, 3, 4, and 5. Section 2.5 suggests two ways to formally define C jump : choosing the maximal jump C window (η) over a geometric window [C/(1 + η),C(1 + η)], and choosing the value C thr. (T n ) of C for which C m (0) min (C) goes under some threshold T n . Another natural option is to choose the position of the maximal jump

C max j. ∈ argmax C 0 C m (0) min (C -) -C m (0) min (C + ) ,
that is, taking lim η→0 C window (η).

Slope approach Second, C can be defined as C slope , the opposite of the estimated value of the slope of the empirical risk as a function of pen 0 , as in Algorithms 2 and 6. This approach can be formalized in several ways, using ordinary or robust linear regression, either over a fixed range [p min , p max ] of values of pen 0 , or with the method m CAPUSHE proposed by Baudry et al. (2012, Section 4.2), which is based upon a stability study of the selected estimator and depends on some parameter pct ∈ (0, 1].

Note that C window , C thr. , and C slope all depend on some hyperparameter (η, T n , p min and p max , pct). We refer to Appendix D.2 for more details on each definition of C considered in this section. as illustrated by Figure 2 in Section 2.4, reasonable choices for T n and η make C window (η) very close to C max j. = C thr. (T n ). On the contrary, when the phase transition around the minimal penalty yields several jumps of medium size in

Theoretical comparison

C → C m (0) min (C) ,
as in Figure 5 for instance, C max j. , C thr. (T n ), and C window (η) can take quite different values and lead to selecting different models. Theoretical guarantees such as Theorem 1 in Section 2.5 do not exclude such a situation, even asymptotically, so they only apply to C thr. (T n ) and C window (η) with T n and η of the correct order of magnitude. Yet, the maximal jump and threshold definitions with T n = C := (max m C m + min m C m )/2 coincide when the largest jump is of size at least (max m C mmin m C m )/2. This condition always holds true if no m ∈ M has a complexity C m ∈ (C ; max m C m ), which often occurs for computational reasons, since estimators with complexity C m > C usually are hard to compute and known to be suboptimal.

For the slope approach, no theoretical guarantee is available, but the linear behavior of R n ( s m ) as a function of pen 0 (m) is supported theoretically from expectation computations, as detailed in Sections 2.2-2.3 and 3.3-3.4.

The jump and slope approaches can seem quite different at first sight, but they actually are the two sides of the same coin. Section 2 shows that reasoning from the same computations, Eq. ( 7)-( 8), can lead to a heuristic justification of both approaches. Another argument enlightens the similarity of the jump and slope approaches. By Proposition 5 and its proof in Appendix B.1, the path ( m

(0) min (C)) C>0 is piecewise constant, m (0) min (C) = m i for C ∈ [C i ,C i+1 )
, and the sequences (m i ) 0 i i max and (C i ) 0 i i max can be visualized on the L-curve (pen 0 (m), R n ( s m )) m∈M : the angles of the lower convex envelope of the L-curve exactly correspond to the m i , 0 i i max , and

C i = R n ( s m i ) -R n ( s m i-1 ) pen 0 (m i-1 ) -pen 0 (m i )
is the opposite of the slope of the segment joining m i-1 to m i on the L-curve. So, C max j. can be visualized on the L-curve, as illustrated by Figure 4. Given the L-curve (black dots), draw its (piecewise linear) lower convex envelope (green squares), localize the widest segment -in terms of values of C m , which is usually proportional to pen 0 (m)-: its slope is -C max j. . Then, one clearly see why C max j. is often close to C slope in the setting of Figure 4: for a random point cloud with a linear trend of slope ≈ -C for large abscissa values, estimating its slope by linear regression is almost equivalent to looking at the slope of the longest segment of its lower convex envelope. Note that C thr. can be visualized on the L-curve similarly to C max j. . This direct comparison emphasizes the respective drawbacks of C max j. and C slope . When the amplitude of the largest jump is small, C max j. is not a reliable estimation of C , see Figure 9b in Appendix C.

When some large models have a significantly positive approximation error, as in the 'hard' setting described in Appendix D -see the right of Figure 10-they pollute the slope estimation and make C slope biased, unless only a few such models are present and robust regression is used. In the latter case, since C jump ∈ { C max j. , C window , C thr. } only depends on the lower convex envelope of the L-curve, even a large number of "polluting" models will not influence C jump at all, making it more robust. This difference between C jump and C slope also appears in the assumptions made for their theoretical and heuristic justifications. In Section 2, C slope requires the approximation error to be almost constant over all large models -which makes sense when (S m ) m∈M is a family of models with increasing complexity, for instance, but can be violated in some other contexts-, whereas C jump only assumes that two models exist with a small approximation error, one of moderate complexity and one of large complexity.

Experimental comparison

In addition to the above theoretical comparison, we report the results of new simulation experiments for variable selection in least-squares regression. We consider two settings: in the 'easy' setting, the order between variables is known, while in the 'hard' setting, two possible orders (the correct one and its converse) are considered alternatively, making half of the models very bad. The 'hard' setting is the archetype of a setting where the approximation error is not constant over large models; it does not aim to be realistic. All details about simulation experiments -data generation, model collection, and exact implementation for each definition of Care given in Appendix D.

First, since the beginning of this section outlines strong theoretical connections between the different definitions of C, a natural question is: how different are the models finally selected, depending on the definition taken for C? Table 1 shows that they all coincide most of the time in the 'easy' setting -with a clear single large jump, as for the sample of Figures 2 and4-, and they globally agree at least 90% of the time or more in both settings. The probability of a total disagreement is very small (less than 0.1%) even if it sometimes occurs, as illustrated by Figure 5, where C max j. , C thr. , and C window respectively lead to selecting m = 14, 11, and 7; Figure 9b in Appendix C shows a similar configuration. Similar conclusions are obtained by Arlot and Massart (2009, Section 3.3) about C max j. and C thr. . Second, since our experiments consider projection estimators in least-squares regression, all minimal-penalty based C estimate σ 2 , so they can be compared to σ 2 m 0 -defined by Eq. ( 71)-as estimators of the residual variance σ 2 . Results are provided in Figure 6, as well as Tables 2-3 in Appendix C, where several values of parameters of the C are compared. In the 'easy' setting (Figure 6a), all methods behave similarly and as expected from theoretical arguments: the distribution of C is asymmetric around σ 2 , with smaller deviations below σ 2 than above σ 2 , as in the bounds of Proposition 3. Such an asymmetry is a good property in terms of model-selection performance, as suggested by Figure 8 in Section 8.4 for instance. The order of magnitude of the deviations The most variable C clearly is C CAPUSHE , but to be completely fair, we must notice that the procedure proposed by [START_REF] Baudry | Slope heuristics: overview and implementation[END_REF] only outputs a selected model m CAPUSHE and we make an arbitrary choice for defining some C CAPUSHE from the definition of m CAPUSHE (see Appendix D.2). Among other definitions of C, C max j. , and C window are slightly more variable than the others but the difference is mild.

Interesting differences occur in the 'hard' setting, which is designed as a case example for difficult situations for C slope , C CAPUSHE , and σ 2 m 0 . As expected, C slope completely fails because of the wide amplitude of the approximation error among large models, and σ 2 m 0 behaves totally differently depending on the parity of m 0 : σ 2 m 0 is worse than C slope when S m 0 is one of the 'bad' models, while it works well when S m 0 is one of the 'good' models (see Figure 10 and Table 3 in Appendix C). This failure of C slope and C CAPUSHE -when (S m ) m∈M is the union of subcollections having different approximation properties-is also reported by Baudry (2009, Section 4.5), Devijver (2017b, Figures 34) and Devijver et al. (2019, Figure 6) in realistic settings. The nested algorithm presented in Section 7.3 might be a way to fix this issue, even if it has not been tested yet in such situations.

More generally, depending on the setting, choosing the parameter for one definition of C can be a big practical issue. For instance, Tables 2-3 in Appendix C show that C thr. (T n ) is sensitive to the choice of T n . Even if T n = n/2 works well for the 'easy' and 'hard' settings, it is certainly not a universally good choice, and changing F, n or σ 2 could easily make it fail compared to other definitions of C. Similarly, the performance of C slope strongly depends on the parameters p min , p max and choosing them from data is not an easy task, a problem also reported in the changepoint detection setting (Lebarbier, 2002, Chapter 4). A reasonable option is given by m CAPUSHE (Baudry et al., 2012, Section 4.2), and it works reasonably well in the 'easy' setting, but it fails in the 'hard' setting as expected.

Third, the model-selection performance of all these procedures is assessed by Figure 7 and by Tables 2-3 in Appendix C.

At first order, the conclusions are similar to the ones obtained for estimating σ 2 . All definitions of C work well in the 'easy' setting. In the 'hard' setting, σ 2 m 0 completely fails, while m CAPUSHE and C slope do slightly worse than the other formulations of the slope-heuristics algorithm.

The detailed comparison of the procedures that work well is a bit different: the model-selection performance (risk ratios) are not ordered exactly as the mean-squared errors in Tables 23. The main reason is that risk estimation -which reduces to estimating σ 2 in our setting-is different from model selection [START_REF] Breiman | Submodel Selection and Evaluation in Regression. The X-Random Case[END_REF]. Figure 8 in Section 8.4 shows at least one reason for this difference: overpenalizing slightly, that is, overestimating σ 2 a bit, improves the model-selection performance. According to Figure 8, the best overpenalization factor is 1.12 in the 'easy' setting. For instance, Table 2 shows that taking D m 0 = n/10 for σ 2 m 0 leads to better model-selection performance than D 0 = n/2 in the 'easy' setting, even if D 0 = n/2 yields a much better estimator of σ 2 .

Note however that for a given bias (as an estimator of σ 2 ), the best model-selection performance is obtained when the variance is the smallest: compare for instance C slope with D 0 = n/2 and CAPUSHE in the 'easy' setting (Table 2 in Appendix C).

Let us finally mention that previous simulation experiments in various settings have compared some of the definitions of C. In short, almost all of them report that C max j. is less reliable -because of the event on which there is not a single large jump (Maugis, 2008, Figure 8.11;Baudry et al., 2012, Section 5), which happens more or less often-compared to C thr. [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF][START_REF] Solnon | Multi-task regression using minimal penalties[END_REF], C window [START_REF] Bontemps | Clustering and variable selection for categorical multivariate data[END_REF], and C slope or C CAPUSHE (Baudry, 2009, Section 3.2;Maugis and Michel, 2011a;[START_REF] Connault | Calibration d'algorithmes de type Lasso et analyse statistique de données métallurgiques en aéronautique[END_REF]Baudry et [START_REF] Devijver | Block-diagonal covariance selection for high-dimensional Gaussian graphical models[END_REF] report similar performances for C max j. and C CAPUSHE . Nevertheless, C max j. remains useful for confirming the choice made with another definition of C [START_REF] Connault | Calibration d'algorithmes de type Lasso et analyse statistique de données métallurgiques en aéronautique[END_REF][START_REF] Baudry | Slope heuristics: overview and implementation[END_REF], with a visual check that there is a single large jump. The slope approach can also fail for reasons detailed previously in this subsection [START_REF] Baudry | Model selection for clustering. Choosing the number of classes[END_REF][START_REF] Devijver | Model-based regression clustering for high-dimensional data: application to functional data[END_REF][START_REF] Devijver | Clustering electricity consumers using high-dimensional regression mixture models[END_REF]. [START_REF] Lebarbier | Detecting multiple change-points in the mean of a Gaussian process by model selection[END_REF] even shows that C max j. and C slope can both fail, which motivates a modified algorithm -called "calibrated method"-for change-point detection; note that [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF] fix this precise failure by using the slope heuristics with a penalty shape depending on two constants, as detailed in Section 7.4.

Conclusion on the choice of C First, it is not surprising to have to choose among several definitions of C or to choose some hyperparameter such as η, T n or p min , because of no free lunch theorems: no fully automatic estimation procedure can work uniformly well over all statistical problems (Devroye et al., 1996, Chapter 7). An expert advice is always necessary at some point. For minimal-penalty algorithms, our suggests join the ones of [START_REF] Baudry | Slope heuristics: overview and implementation[END_REF] and [START_REF] Connault | Calibration d'algorithmes de type Lasso et analyse statistique de données métallurgiques en aéronautique[END_REF]: never use a single definition of C in a blind way, either by considering several definitions for C or by checking visually that there is a clear complexity jump and/or that the L-curve exhibits a clear linear trend on the data. When computing all values of ( R n ( s m ), pen 0 (m), pen 1 (m), C m ) m∈M is too expensive, one should also take into account the computational cost of the procedure, as discussed in Section 7.2.

We propose the following (semi-automatic) approach for using several definitions C max j. , C thr. , C window , C slope , and C CAPUSHE of C simultaneously. If the goal is to estimate σ 2 , take their median. If the goal is estimator selection, compute the five corresponding estimator choices m, and make a majority vote: if at least three over five coincide, take their common value, otherwise, output a warning and ask the user to look at the complexity jump and the L-curve. When the five methods disagree, using a completely different approach remains a good option, for instance, cross-validation. The results of using this strategy (in a fully automatic way since our experiments need to be reproducible) are reported in Figures 67above as well as Tables 2-3 in Appendix C, showing good performance in all settings.

Finally, the above comparison also points out several risky choices for C (in addition to σ 2 m 0 ): C max j. without checking that there is indeed a single large jump, C thr. with a bad choice for T n , the "naive" version C slope of the slope approach, and C slope or C CAPUSHE when selecting among a union of subcollection of estimators that may have different approximation properties.

Algorithmic cost

When all empirical risks can be computed Let us assume that the values of the empirical risk R n ( s m ), the minimal and optimal penalty shapes pen 0 (m) and pen 1 (m), and the complexity C m for all m ∈ M are stored in memory. Then, the computational complexity of minimal-penalty algorithms is the following.

For Algorithm 5, computing the full path ( m the cardinality of this path -which must be smaller than card(M )-, it can be computed with O(i max card M ) operations.

Furthermore, depending on the definition of C jump , it might not be necessary to compute the full path. For instance, with the threshold approach, using the notation of Appendix B.1

, if i(T n ) is such that C thr. (T n ) = C i(T n ) , only O(i(T n ) card M )
operations are necessary, and usually we have i(T n ) i max card(M ).

Computing C window as defined in Algorithm 5 might seem costly at first sight. Appendix B.2 shows that given the path ( m (0) min (C)) C 0 , of cardinality i max + 2, computing C window can be done with at most O(i max log i max ) operations.

Finally, step 3 of Algorithm 5 requires at most O(card M ) operations. Overall, Algorithm 5 always has a complexity

O(i max card M ) O([card M ] 2 ).
For Algorithm 6, step 1 is a (robust) linear regression -hence it has a computational cost O(card M )and step 2 can be done with O(card M ) operations. Note that m CAPUSHE has a larger computational cost since it requires to run O(card M ) times Algorithm 6, hence a total cost of O([card M ] 2 ).

When computing all empirical risks is not tractable In general, most of the computational complexity of computing m Alg.5 or m Alg.6 corresponds to computing R n ( s m ) for all m ∈ M . For instance, for density estimation with Gaussian mixture models (Maugis and Michel, 2011a), performing maximum-likelihood estimation in several large models involves a large computational cost, while we know that all corresponding estimators are always bad. Can we remove from the collection ( s m ) m∈M most estimators with C m "large", without degrading too much the performance of Algorithms 5-6?

For the jump approach, two estimators having a small approximation error are needed to get a jump, as with the assumptions of Theorem 1: one of large complexity, one much less complex. If we are not sure of which estimators have a small enough approximation error, considering more than two of them can be helpful; otherwise, this does not hurt -and we conjecture that this slightly decreases the variance of C jump -, without being mandatory.

For the slope approach, the picture is different. Having only two estimators with a small approximation error implies making a linear regression over the corresponding two points, which is very close to the residual-based estimator σ 2 m 0 defined by Eq. ( 71), as shown by Figure 10 in Appendix C. Therefore, C slope with only a few large-complexity estimators faces the risk that some of them have a large approximation error, to which it will be quite sensitive, unlike C jump (see Figure 10b). Using a robust regression in C slope decreases the risk but does not exclude it totally, as shown by the poor results of m CAPUSHE in our experiments in the 'hard' setting in Section 7.1.

A more reliable strategy for the slope approach -at least for settings a bit less difficult than our 'hard' setting-is to consider only estimators of complexity up to C max , and to carefully check that C max is large enough by visualizing the linear relation between the empirical risk and pen 0 . This can be done easily with the CAPUSHE package [START_REF] Baudry | Slope heuristics: overview and implementation[END_REF]. The experiments of Baudry et al. (2012, Section 5) show as expected that C slope is better -more stable-when C max is large enough. Similarly, for change-point detection, Lebarbier (2002, Chapter 4;2005, Section 4.2) studies the influence of such a bound C max on C max j. and propose a heuristic method Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019 -called "calibrated"-for choosing C max from data.

Note finally that in some frameworks, well-chosen large-complexity estimators are easy to compute. For instance, in fixed-design regression, the estimator equal to the original data always has an empirical risk and an approximation error equal to zero -see assumption (HId) in Theorem 1.

Nested minimal-penalty algorithm

In a framework where M is a cartesian product M 1 × M 2 , [START_REF] Devijver | Nonlinear network-based quantitative trait prediction from transcriptomic data[END_REF] propose a "nested slope heuristics" algorithm, that we here generalize to Algorithms 5-6. The idea is to choose m = ( m 1 , m 2 ) ∈ M 1 × M 2 in two steps. First, for every m 1 ∈ M 1 , select one estimator among ( s (m 1 ,m 2 ) ) m 2 ∈M 2 with a minimal-penalty algorithm; the selected index is denoted by m 2 (m 1 ). Then, select one estimator among ( s (m 1 , m 2 (m 1 )) ) m 1 ∈M 1 with a minimal-penalty algorithm. The numerical experiments of [START_REF] Devijver | Nonlinear network-based quantitative trait prediction from transcriptomic data[END_REF] on some transcriptomic data-analysis problem show that such a nested algorithm can work, for choosing a number m 1 of clusters (of individuals) and a partitioning m 2 of the features (the genes) used for inferring a cluster-dependent gene regulatory network.

Estimation of several unknown constants in the penalty

When the optimal penalty involves several unknown constants, that is, ∀m ∈ M , pen opt (m) = C 1 pen

(1)

1 (m) + • • • +C k pen (k) 1 (m) (82)
for some known pen

(1) 1 , . . . , pen

(k)
1 , the slope approach can be generalized, using linear regression for estimating simultaneously C 1 , . . . ,C k . The idea has first been proposed with Algorithm 2 by Lebarbier (2002, Section 4.3.2) in the case of change-point detection, where the optimal penalty depends on k = 2 constants.

It has since been used -with good numerical performance-in several settings: changepoint detection [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF], joint variable selection and clustering via Gaussian mixture models [START_REF] Meynet | A sparse variable selection procedure in model-based clustering[END_REF], principal curves estimation [START_REF] Biau | Parameter selection for principal curves[END_REF], and unsupervised segmentation of spectral images via piecewise-constant Gaussian mixture models [START_REF] Cohen | Unsupervised segmentation of spectral images with a spatialized Gaussian mixture model and model selection[END_REF].

Nevertheless, no theoretical guarantees are currently available for such an algorithm. In addition to the practical issues already mentioned for the slope approach, this procedure is difficult to apply when there is not a single natural complexity measure C m but several of them -pen

(1)

1 (m), . . . , pen (k)
1 (m) can be k complexity measures-, which have to be combined wisely for defining what are the "complex enough" m ∈ M over which the (robust) linear regression should be done. Another major difficulty is when card(M ) or n are not large enough to allow a good estimation of several constants C 1 , . . . ,C k simultaneously.

Another option is to make use of a simplified penalty shape -depending on a single multiplicative constant-, even when we know that it differs from the optimal shape given by Eq. ( 82). Several articles make use of such a simplified penalty, instead of trying to calibrate k = 2 constants, with satisfactory numerical results: for density estimation / clustering with Gaussian mixture models (Maugis and Michel, 2011a; see also Michel, 2008, App. C.2) or multinomial mixture models [START_REF] Derman | Clustering and model selection via penalized likelihood for different-sized categorical data vectors[END_REF], for choosing a simplicial complex in the computational geometry field [START_REF] Caillerie | Model selection for simplicial approximation[END_REF], and for selecting jointly the rank and a set of variables in a high-dimensional finite mixture regression model (Devijver, 2017a).

A numerical comparison between simplified penalty shape and calibration of two constants is done in a few other papers, with various conclusions: favorable to the simplified shape (Lebarbier, 2002, Section 4.3.2, for change-point detection with Gaussian noise), similar for both methods [START_REF] Devijver | Block-diagonal covariance selection for high-dimensional Gaussian graphical models[END_REF], for inference of a high-dimensional Gaussian graphical model), or favorable to the calibration of two constants -for change-point detection with Laplace noise and a simplified shape derived from experiments with Gaussian noise (Lebarbier, 2002, Section 4.6.4), for change-point detection with positive-definite kernels [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF], and for curve clustering [START_REF] Meynet | A sparse variable selection procedure in model-based clustering[END_REF], Figure 5). As a conclusion, choosing between these two strategies should be done carefully, depending on the framework.

Variants for change-point detection

For change-point detection seen as a model-selection problem, three approaches closely related to minimal penalties have been proposed, without being exactly of the form of Algorithm 5. The first is the "calibrated method" (Lebarbier, 2005, Section 4.2) mentioned in Section 7.2.

Second, Lavielle (2005, Section 2.3) remarks that C max j. often leads to underestimating the number of changes. Then, using the notation of Appendix B.1, it is proposed instead to define m as the largest m i = m(C i ) corresponding to a jump whose height C i -C i-1 is much larger than the one of the largest subsequent jump, that is, max j>i {C j -C j-1 }. This approach might be closer to an elbow heuristics (see Section 6.4) than to a minimal-penalty algorithm.

Statistical Base Jumping Third, an unpublished idea by [START_REF] Rozenholc | Statistical base jumping: A simple and fully data-driven answer to penalized model selection[END_REF] is the following. Assume that change-point detection is cast as a model-selection problem in fixed-design regression, so that we can use the notation of Section 2. Take some D "large" but, say, smaller than n/2, for instance D = n/ log(n) or D = √ n. Compute F D the empirical risk minimizer over the set of piecewise-constant signals with D pieces (which is a union of n-1 D-1 vector spaces of dimension D). Consider the residual vector Y = Y -F D and apply the penalization approach to this pseudo-data, that is, compute

∀C > 0 , m(C) ∈ argmin m∈M chpt n 1 n Y -Π m Y 2 +C pen 0 (m) + pen 0 (m) (83)
where the model collection M

chpt n

is the one adapted to change-point detection, and the penalty shape C pen 0 (m) + pen 0 (m) is a simplified version of the penalties proposed by [START_REF] Comte | A new algorithm for fixed design regression and denoising[END_REF], [START_REF] Lavielle | Using penalized contrasts for the change-point problem[END_REF] and [START_REF] Lebarbier | Detecting multiple change-points in the mean of a Gaussian process by model selection[END_REF], such as

CD m , CD m + log n -1 D m -1 or C log n -1 D m -1 + D m .
Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

Define C SBJ as the minimal value of C > 0 such that D m(C) = 1, and finally select

m SBJ ∈ argmin m∈M chpt n 1 n Y -Π m Y 2 + 2 C SBJ 1 + D n pen 0 (m) + pen 0 (m) .
Note that F D , ( m(C)) C 0 and m SBJ can all be computed efficiently, in particular using dynamic programming. The heuristics behind this method is that if D is large enough to catch all true change-points of F in F D , then Y does not contain any signal anymore, and C SBJ pen 0 is the minimal penalization level needed to recover with Eq. ( 83) the unique model of dimension one (constant signal). The factor 1 + D n dividing C SBJ corrects for the variance of the pseudo-sample Y . Unpublished experiments [START_REF] Rozenholc | Statistical base jumping: A simple and fully data-driven answer to penalized model selection[END_REF] suggest that m SBJ provides very good segmentations, much better than with the original slope heuristics -that is, Algorithm 1 or 2, as done by [START_REF] Lebarbier | Detecting multiple change-points in the mean of a Gaussian process by model selection[END_REF] for instance.

Other uses of minimal penalties

Let us finish this section by mentioning two other uses of a minimal-penalty algorithm in the literature.

Choice of a penalty shape Algorithm 5 can be used for choosing among several penalty shapes, by detecting bad ones, which are the ones that do not lead to a clear dimension jump, as illustrated by Baudry et al. (2012, Section 3 of supplementary material) in the setting of [START_REF] Caillerie | Model selection for simplicial approximation[END_REF].

Minimal-penalty assisted experiments For estimating a good deterministic constant C to be put in front of the penalty, [START_REF] Chagny | Penalization versus Goldenshluger-Lepski strategies in warped bases regression[END_REF] computes on 100 samples the constant C chosen by a slope heuristics algorithm, and defines C as the maximal value of C observed over the 100 samples. The main interest of this approach is to require less computations than the standard one -which would be to compute, for every C in a grid, the average over the 100 samples of the risk of the estimator selected with the penalty C pen 1 , and then to take C that minimizes the average risks over C in the grid-, even if the value C might not be the optimal one.

Conclusion, conjectures, and open problems

As a conclusion of this survey, we sketch what is known theoretically for minimal-penalty algorithms, as well as several conjectures and open problems of high interest. Let us recall that Section 5 provides some hints for tackling many of these conjectures and open problems.

Settings and losses where minimal-penalty algorithms apply

Let us sketch the set of frameworks for which minimal-penalty algorithms are theoretically justified, at least partially (see Section 4).

The typical situation is a polynomial collection of minimum-contrast estimators (also called empirical risk minimizers) with a regular contrast [START_REF] Saumard | Estimation par Minimum de Contraste Régulier et Heuristique de Pente en Sélection de Modèles[END_REF] (for instance, the leastsquares contrast), the corresponding risk (expected value of the contrast), and (almost) i.i.d. data. Then, all obtained results show that pen opt ≈ 2 pen min . In other terms, the slope heuristics holds true in several frameworks "close to" choosing among a polynomial collection of projection estimators with the least-squares risk and i.i.d. data.

The general result proved by Saumard (2010b, Chapters 7-8) for regular contrasts suggests that the slope heuristics is probably valid in all frameworks that are close enough to this ideal situation -e.g., least-squares estimators in regression or (conditional) density estimation with the least-squares risk-, under appropriate assumptions.

Two results, in regression [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF] and in density estimation (Lerasle et al., 2016), show that linear estimators can be considered instead of minimum-contrast estimators, at the price of changing the slope heuristics (Section 2) into a minimal-penalty heuristics (Section 3). A similar extension can probably be done in other settings for estimators that are (close to) linear functions of (part of) the data.

More generally, using the notation introduced in Section 4.1, it is probably often true that E[p 2 (m)] is a minimal penalty and E[p 1 (m) + p 2 (m)] an optimal penalty. But unless these expectations are (approximately) known up to a multiplicative constant, applying such results requires to estimate E[p 2 (m)] and E[p 1 (m) + p 2 (m)] by resampling (see Remark 3 in Section 4.2), and we then loose a nice feature of Algorithm 5 which is its small computational cost compared to cross-validation.

Unavoidable assumptions

Even in settings for which a full proof of a minimal-penalty algorithm is known, a natural question to ask is which assumptions are unavoidable for this algorithm to work.

Based upon existing proofs -in particular the one of Theorem 1, which is typical-, we conjecture that at least three assumptions are (almost) needed.

First, a "complex" estimator should be present in the collection, similarly to (HId). Note that such an estimator can often be added on purpose to a predefined collection.

Second, one "less complex" but "good" estimator should also be present in the collection, similarly to what Theorem 1 assumes implicitly. The exact definition of "good" can depend on the context. In general, being consistent should suffices; note that assuming that the oracle estimator is consistent is a mild assumption for estimator selection, since otherwise the problem is not much interesting. In the setting of Theorem 1, it suffices to have a model with a small approximation error, even if the corresponding estimator is not consistent. Note however that such an assumption can be violated in practice, for instance when the estimator collection has not been well chosen, so that the approximation error never vanishes.

Third, it seems reasonable to make some mild moment assumption on the data so that the key quantities p 1 and p 2 concentrate around their expectations, at least when using deterministic penalty shapes. Nevertheless, a Gaussian assumption such as (HG) is not necessary [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF][START_REF] Saumard | Optimal model selection in heteroscedastic regression using piecewise polynomial functions[END_REF]; see also Remark 1 in Section 2.5. Independence of data is not necessary either [START_REF] Lerasle | Optimal model selection for stationary data under various mixing conditions[END_REF][START_REF] Garivier | Oracle approach and slope heuristic in context tree estimation[END_REF]. Risk bounds could be obtained under much weaker moment assumptions -for instance, when the noise only has a finite moment of order two-, for empirical risk minimizers [START_REF] Mendelson | Learning without concentration for general loss functions[END_REF] or for robust estimators (Audibert and Catoni, 2011, for instance). Nevertheless, we are not aware of any theoretical result Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019 on minimal penalties in such a setting.

Other settings, losses, estimators

Numerical experiments show that minimal-penalty algorithms can be used fruitfully in many other settings such as supervised classification [START_REF] Zwald | Statistical performances of learning algorithm : Kernel Projection Machine and Kernel Principal Component Analysis[END_REF], model-based clustering (Maugis and Michel, 2011a;[START_REF] Baudry | Estimation and model selection for model-based clustering with the conditional classification likelihood[END_REF], high-dimensional inference [START_REF] Devijver | Block-diagonal covariance selection for high-dimensional Gaussian graphical models[END_REF], change-point detection [START_REF] Lebarbier | Detecting multiple change-points in the mean of a Gaussian process by model selection[END_REF][START_REF] Bardet | Multiple breaks detection in general causal time series using penalized quasi-likelihood[END_REF], topological data analysis [START_REF] Caillerie | Model selection for simplicial approximation[END_REF], functional linear models [START_REF] Roche | Statistical modeling for functional data: non-asymptotic approaches and adaptive methods[END_REF] or Hawkes-process intensity estimation (Reynaud-Bouret and Schbath, 2010), with applications in various domains such as biology -genomics [START_REF] Akakpo | Estimating a discrete distribution via histogram selection[END_REF][START_REF] Reynaud-Bouret | Adaptive estimation for Hawkes processes; application to genome analysis[END_REF], transcriptomics [START_REF] Rau | Co-expression analysis of highthroughput transcriptome sequencing data with Poisson mixture models[END_REF][START_REF] Devijver | Block-diagonal covariance selection for high-dimensional Gaussian graphical models[END_REF], quantitative trait prediction from genomic data [START_REF] Devijver | Nonlinear network-based quantitative trait prediction from transcriptomic data[END_REF], population genetics (Bontemps and Toussile, 2013)-, energy -electricity consumption prediction [START_REF] Devijver | Clustering electricity consumers using high-dimensional regression mixture models[END_REF], oil production modelization (Michel, 2008, Chapter 6)-, hyperspectral image segmentation [START_REF] Cohen | Unsupervised segmentation of spectral images with a spatialized Gaussian mixture model and model selection[END_REF]), text analysis [START_REF] Derman | Clustering and model selection via penalized likelihood for different-sized categorical data vectors[END_REF], and bike sharing systems (Bouveyron et al., 2015a;[START_REF] Godichon-Baggioni | Clustering transformed compositional data using K-means, with applications in gene expression and bicycle sharing system data[END_REF]. Combining these numerical experiments -especially the ones showing that the empirical risk is indeed close to a linear function of some known pen 0 for large-complexity estimators-with the partial theoretical results available (Section 4), several settings can be identified where we conjecture that a minimal-penalty algorithm such as Algorithms 5-6 could be used fruitfully. Among them, we select below the most challenging ones, in terms of both practical applications and theoretical interest.

Supervised classification

A classical setting where minimal-penalty algorithms would be quite useful is supervised classification with the 0-1 loss and corresponding empirical risk minimizers. No theoretical result is available up to now, and it seems tough to prove any because the 0-1 contrast is far from being regular. Nevertheless, [START_REF] Boucheron | A high dimensional Wilks phenomenon[END_REF] provide a key ingredient of the proof, that is, a concentration inequality for p 2 (m) that applies easily to 0-1 classification, even when fast learning rates are possible. Given Proposition 1 and the general strategy detailed in Section 5, what remains is to prove a similar concentration inequality for p 1 (m), and to be able to estimate (up to the same unknown constant)

E[p 1 (m)] and E[p 2 (m)].
A probably easier open problem is to provide theory for the case of classification with a convex loss, such as the logistic loss -at the basis of logistic regression-or the hinge loss -at the basis of support vector machines. At least, for the hinge loss, the numerical experiments reported by Zwald (2005, Section 6.4.3) suggest that minimal-penalty algorithms can work with pen 0 (m) = C m = D m and pen 1 (m) = 2D m .

Model-based clustering, choice of the number of clusters

Estimating the number of clusters for (unsupervised) clustering is another problem where fine tuning of penalties is a major challenge. A classical approach -called model-based clustering-Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019 is to estimate the data density by maximum-likelihood on a mixture model, and to define clusters by a maximum a posteriori rule. Then, the number of clusters can be chosen by maximizing the penalized log-likelihood. Minimal-penalty algorithms with pen 0 (m) = C m = D m and pen 1 (m) = 2D m are shown successful by experiments on synthetic and real data, for various problems following this strategy (up to modifications that are specified below):

-clustering with Gaussian [START_REF] Baudry | Estimation and model selection for model-based clustering with the conditional classification likelihood[END_REF], Poisson [START_REF] Rau | Co-expression analysis of highthroughput transcriptome sequencing data with Poisson mixture models[END_REF], multinomial [START_REF] Derman | Clustering and model selection via penalized likelihood for different-sized categorical data vectors[END_REF], or some functional (Bouveyron et al., 2015a) mixture models. -clustering with Gaussian mixtures and the conditional log-likelihood instead of the loglikelihood, which leads to slightly different kinds of clusters [START_REF] Baudry | Estimation and model selection for model-based clustering with the conditional classification likelihood[END_REF]. -joint clustering and variable selection -that is, identifying which features are relevant for clustering-with mixtures of Gaussian (Maugis and Michel, 2011a) or multinomial [START_REF] Bontemps | Clustering and variable selection for categorical multivariate data[END_REF] variables. -efficient joint clustering and high-dimensional variable selection with maximum-likelihood estimators trained on data-driven models obtained by a first step of L 1 penalization [START_REF] Meynet | A sparse variable selection procedure in model-based clustering[END_REF]; here, the shape of the minimal penalty seems to be close to a linear combination of D m and D m log p D m (Meynet and Maugis-Rabusseau, 2012, Figure 6), and the algorithm described in Section 7.4 can be used.

-when an additional feature vector is provided for each observation, clustering a mixture of Gaussian regression models, jointly done with feature selection [START_REF] Devijver | Model-based regression clustering for high-dimensional data: application to functional data[END_REF][START_REF] Devijver | Clustering electricity consumers using high-dimensional regression mixture models[END_REF] or partitioning [START_REF] Devijver | Nonlinear network-based quantitative trait prediction from transcriptomic data[END_REF], via two-steps procedures similar to the one of [START_REF] Meynet | A sparse variable selection procedure in model-based clustering[END_REF].

We conjecture that minimal-penalty algorithms indeed work in these settings, that is, as one can observe on synthetic or real data: (i) p 2 (m) is (close to) a linear function of the number of parameters D m , (ii) Algorithm 5 or 6 with pen 0 (m) = D m and pen 1 (m) = αD m provides an estimator with a small Kullback-Leibler risk, for some α > 1 to be determined, and (iii) the number of clusters selected by this algorithm is equal to the true one K with large probability when n is large and the data distribution is close to a mixture with K components. Note that (ii) is a density estimation guarantee -hence, slightly different from clustering, but classical for justifying theoretically a penalty shape [START_REF] Maugis | A non asymptotic penalized criterion for gaussian mixture model selection[END_REF][START_REF] Meynet | A sparse variable selection procedure in model-based clustering[END_REF][START_REF] Bontemps | Clustering and variable selection for categorical multivariate data[END_REF][START_REF] Derman | Clustering and model selection via penalized likelihood for different-sized categorical data vectors[END_REF]Devijver, 2017a)-and that (ii) and (iii) may require different values of α since estimation and model identification are different goals for model selection, see Section 8.3.6. When variable selection is done jointly with clustering, (iii) can be completed by the fact that the true set of relevant variables is selected with large probability.

Up to now, only oracle inequalities with theoretical penalties are available in some of these settings. Of course, proving the above conjecture would be less difficult for pure model-based clustering [START_REF] Baudry | Estimation and model selection for model-based clustering with the conditional classification likelihood[END_REF]Bouveyron et al., 2015a;[START_REF] Rau | Co-expression analysis of highthroughput transcriptome sequencing data with Poisson mixture models[END_REF][START_REF] Derman | Clustering and model selection via penalized likelihood for different-sized categorical data vectors[END_REF] than for the two-steps algorithm using L 1 -penalized maximum-likelihood for defining data-driven models [START_REF] Meynet | A sparse variable selection procedure in model-based clustering[END_REF][START_REF] Devijver | Model-based regression clustering for high-dimensional data: application to functional data[END_REF][START_REF] Devijver | Clustering electricity consumers using high-dimensional regression mixture models[END_REF].

Note also that variable selection, without any order among variables, means that the model collection considered is large -with the terminology of Section 4.7-, at least implicitly; this fact raises specific issues that are addressed in Section 8.3.4.

High-dimensional statistics

Hyperparameter tuning is a major issue for high-dimensional statistics (Giraud, 2014, Chapter 5), which can often be addressed by penalization. Despite several positive numerical results, providing a full theoretical proof of a minimal-penalty algorithm in this context remains an open problem.

Clustering Numerical results about minimal-penalty algorithms for joint (model-based) clustering and variable selection are reviewed in Section 8.3.2. For block-diagonal estimation of the covariance matrix of a high-dimensional Gaussian vector (graphical model), [START_REF] Devijver | Block-diagonal covariance selection for high-dimensional Gaussian graphical models[END_REF] provide positive numerical results for a similar algorithm -maximum likelihood on data-driven models obtained by thresholding the empirical covariance matrix. Nevertheless, given the difficulty of proving an oracle inequality [START_REF] Devijver | Block-diagonal covariance selection for high-dimensional Gaussian graphical models[END_REF], for instance), it seems hard to obtain a full theoretical validation of the minimal-penalty algorithms of [START_REF] Meynet | A sparse variable selection procedure in model-based clustering[END_REF], [START_REF] Devijver | Model-based regression clustering for high-dimensional data: application to functional data[END_REF] and [START_REF] Devijver | Block-diagonal covariance selection for high-dimensional Gaussian graphical models[END_REF].

Regression: the Lasso and related algorithms One of the most classical high-dimensional statistics problem is variable selection in linear regression, for which the (group) Lasso and related algorithms are popular. Penalized least-squares can be used for choosing their parameters, thanks to covariance penalties [START_REF] Efron | The estimation of prediction error: covariance penalties and cross-validation[END_REF], which have a simple expression of the form σ 2 df/n when the noise is Gaussian, where σ 2 denotes the residual noise-level and df are the degrees of freedom. Easy-to-compute estimators of df exist for the Lasso [START_REF] Tibshirani | Degrees of freedom in lasso problems[END_REF][START_REF] Dossal | The degrees of freedom of the lasso for general design matrix[END_REF] and group Lasso [START_REF] Vaiter | The Degrees of Freedom of the Group Lasso[END_REF], among others. The remaining issue is to estimate σ 2 without knowing any small correct model, for which minimal penalties are a natural approach (see Section 6.1).

The PhD dissertation of [START_REF] Connault | Calibration d'algorithmes de type Lasso et analyse statistique de données métallurgiques en aéronautique[END_REF] provides an extensive numerical study of minimal penalties for calibrating either the Lasso or least-squares estimators trained on models selected by the Lasso ('Lasso+LS'). In short, the major difficulty is that the natural candidate for pen 0 (m), that is E[p 2 (m)]/σ 2 , cannot be used because it depends on the (unknown) signal β . Simplified penalty shapes -that is, E[p 2 (m)]/σ 2 for a zero signal, or for a zero signal and an identity design matrix-often work for Lasso+LS, and sometimes for the Lasso, depending on the signal-tonoise ratio and on the sparsity of the signal. This is not satisfactory because these minimalpenalty algorithms sometimes fail for the Lasso or Lasso+LS, and [START_REF] Connault | Calibration d'algorithmes de type Lasso et analyse statistique de données métallurgiques en aéronautique[END_REF] proposes "antidotes" for detecting the failure but nothing for correcting it, except using cross-validation.

It nevertheless seems possible to solve the case of an orthogonal design matrix, when the Lasso is soft thresholding and Lasso+LS is hard thresholding. Taking the number of selected variables k as tuning parameter, [START_REF] Loubes | Discussion: "Least angle regression[END_REF]

, Section 2) conjecture that for soft thresholding, E[p 2 (k)] ≈ 3 2 σ 2 k n .
If one could prove this conjecture, a minimal-penalty algorithm could be used for estimating σ 2 -hence for calibrating soft (or hard) thresholding. Section 8.3.4 discusses the case of hard thresholding.

For a general design matrix and for other estimators, we think that the key question is to find the good parametrization of the estimator to be calibrated. For instance, the Lasso can be parametrized by the regularization parameter or by the number of selected variables, and [START_REF] Connault | Calibration d'algorithmes de type Lasso et analyse statistique de données métallurgiques en aéronautique[END_REF] shows that the theoretical minimal penalty E[p 2 (m)] and the performance of Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019 minimal-penalty algorithms strongly depend on the chosen parametrization. We also conjecture that the solution might not come from a direct application of Algorithms 5-6, but by the more general approach of identifying an observable phase transition -with respect to some wellchosen parameter-that provides the key information for an optimal calibration of the algorithm considered -for instance, an estimation of σ 2 for the (group) Lasso. This idea has already been proposed in a few settings that are detailed in Section 8.5. For high-dimensional regression, theoretical results prove the existence of phase transitions in the risk of the Lasso (Bellec, 2017, Section 4;Bellec, 2018, Section 4.3) and of the constrained formulation of the Lasso (Chatterjee, 2014, Section 2.1). Nevertheless, it is not clear whether these phase transitions are observable, so they might not be useful for choosing hyperparameters. The approach of Section 6.6 seems to be another promising direction for tackling this problem.

Let us finally mention that concentration inequalities for p 1 (m) are available for the Lasso and some related algorithms -see Section 5.3 for details. They can be useful for validating minimal-penalty algorithms.

Large collection of models

As recalled in Section 4.7, the nature of the model-selection problem depends on the size of the model collection. All full proofs and almost all partial results available for minimal-penalty algorithms are for small collections, for which optimal model selection can be obtained with the unbiased risk estimation heuristics. For large collections, only a few partial theoretical results are available, as reported in Section 4.7. Therefore, the case of large collections remains a widely open problem of major interest.

The most classical situation is variable selection among p n variables, which amounts to select among a collection of 2 p models. Let us start by focusing on the two settings where minimal-penalty algorithms are best understood: (i) variable selection with p = n and an orthonormal design -so that penalizing the least-squares criterion by a function of the number of variables is equivalent to hard thresholding-, and (ii) change-point detection -finding the locations of abrupt changes in the distribution of a sequence of n observations-which can be casted as a variable-selection problem with p = n -1 variables -the possible breakpoint locationsand solved by penalized least-squares.

Let us also recall that the notation (β ), (β -), (β + ), (β ), (γ), and ( γ ) refer to partial results about minimal-penalty algorithms; they are defined in Sections 4.1-4.4.

Orthonormal variable selection by hard thresholding For variable selection with an orthonormal design and Gaussian noise, Birgé and Massart (2007, Proposition 2) prove (β ) and ( γ ) with a minimal penalty of order 2σ 2 D m n log n D m -at least for 1 D m n. We conjecture that (β ) holds true in the same setting: a proof of (β -) derives from the proof written by Birgé and Massart (2007, Proposition 2), and (β + ) seems easy to get given the results obtained by [START_REF] Birgé | Minimal penalties for Gaussian model selection[END_REF]. Then, (β ) and ( γ ) would prove that Algorithm 5, with pen 0 (m) ≈ D m log n D m and pen 1 (m) given by Birgé and Massart (2007, Section 3.1.3), provides a good data-driven variable-selection procedure, satisfying an oracle inequality close to being optimal.

The main remaining challenge for having a full proof of a first-order optimal procedure is problem (γ): find a first-order optimal penalty of the form σ 2 pen 1 (m) with pen 1 (m) known. We think that this is a hard problem, whose resolution would have a great impact on model-selection theory in general, since even the value of the optimal excess risk of such a variable-selection procedure is not exactly known at first order. We only know by minimax arguments that it should be of order log n D m times the oracle excess risk, up to a constant factor. Another open problem for orthonormal variable selection is to determine the minimal penalty for non-Gaussian noise. Contrary to small model collections, this is not a straightforward extension of Gaussian results since the experiments of Lebarbier (2005, Section 5) for another large collection problem -change-point detection-suggest that the minimal penalty then is different for Laplace and for Gaussian noise.

Change-point detection Penalized least-squares is a classical approach to change-point detection, for which an oracle inequality ( γ ) holds true for Gaussian noise and a penalty of the form σ 2 D m n c 1 log n D m + c 2 where c 1 , c 2 > 0 are two numerical constants and σ 2 is the residual noise-level [START_REF] Lebarbier | Detecting multiple change-points in the mean of a Gaussian process by model selection[END_REF]; a similar result in a slightly different setting is proved by [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF]. The numerical experiments of [START_REF] Lebarbier | Detecting multiple change-points in the mean of a Gaussian process by model selection[END_REF], [START_REF] Sorba | Minimal penalties for model selection[END_REF], [START_REF] Garreau | Change-point Detection and Kernels Methods[END_REF], Section 4.1), Cabrieto et al. (2018, Figure 4, for instance) and [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF], as well as the partial theoretical results of Sorba ( 2017 (or close to it, according to Birgé and[START_REF] Massart | Concentration Inequalities and Model Selection[END_REF][START_REF] Sorba | Minimal penalties for model selection[END_REF] should work well in this setting. Given the numerical experiments of [START_REF] Lebarbier | Detecting multiple change-points in the mean of a Gaussian process by model selection[END_REF] and [START_REF] Arlot | A kernel multiple change-point algorithm via model selection[END_REF], we conjecture that the ratio between the optimal and minimal penalty belongs to (1, 2]; it may be model-dependent.

Proving these conjectures formally would require to solve two open problems: (a) prove the existence of a dimension jump for some known pen 0 -or, equivalently, prove that step 2 of Algorithm 6, or its generalization of Section 7.4, works well-, and (b) prove an optimal oracle inequality for a penalty C pen 1 that can be derived from the minimal penalty. Problem (b) is very hard, as for orthonormal variable selection. Problem (a) seems less difficult: Sorba (2017, Chapter 8) is close to proving it, but there is still a gap between "large enough" and "too small" penalties, which leaves open the possibility of having no clear dimension jump. It remains a challenge, as emphasized by the fact that the shape of the minimal penalty seems to depend on the noise distribution not only through its variance (Lebarbier, 2005, Section 5). Note that proving (a) with C = σ 2 would be sufficient to get a good data-driven penalty for change-point detection, since an oracle inequality -maybe suboptimal-is already available for a penalty depending on σ 2 and known quantities.

To conclude on change-point detection via penalized least-squares, let us recall that Rozenholc (2012) proposes a related but different approach to penalty tuning -see Section 7.5-that might be even more efficient than minimal-penalty algorithms for change-point detection with penalized least-squares. Justifying it theoretically would therefore be of great interest.

Beyond penalized least-squares, slope-heuristics algorithms empirically work well for changepoint detection with dependent data in two settings: causal processes with the maximizer of a penalized log-likelihood [START_REF] Bardet | Multiple breaks detection in general causal time series using penalized quasi-likelihood[END_REF], and long-memory processes with the minimizer of a local Whittle contrast [START_REF] Bardet | Semi-parametric detection of multiple changes in long-range dependent processes[END_REF]. [START_REF] Bardet | Multiple breaks detection in general causal time series using penalized quasi-likelihood[END_REF] even show the remarkable fact that minimal penalties numerically adapt to variations of the optimal constant C Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019 -which can be of order log(n) or √ nwhen the dependence structure varies. A theoretical validation of these results seems quite a challenge, since handling small model collections in the same settings already is an open problem.

General setting Understanding minimal-penalty algorithms for more general variable-selection problems seems a too high theoretical challenge for the next few years. We nevertheless conjecture that minimal-penalty algorithms work well beyond orthonormal variable selection and change-point detection, given the successful experiments of Maugis and Michel (2011a) and [START_REF] Bontemps | Clustering and variable selection for categorical multivariate data[END_REF] for joint variable selection and model-based clustering (see Section 8.3.2).

Minimal-penalty algorithms experimentally work well in several other settings mentioned previously, where large model collections are implicitly considered through L 1 penalization or thresholding: model-based clustering [START_REF] Meynet | A sparse variable selection procedure in model-based clustering[END_REF], multivariate regression with a mixture of linear models [START_REF] Devijver | Model-based regression clustering for high-dimensional data: application to functional data[END_REF][START_REF] Devijver | Nonlinear network-based quantitative trait prediction from transcriptomic data[END_REF], and Gaussian graphical model estimation [START_REF] Devijver | Block-diagonal covariance selection for high-dimensional Gaussian graphical models[END_REF].

Infinite estimator collections

Throughout the article, the estimator collection ( s m ) m∈M is assumed to be finite. Nevertheless, Algorithms 5-6 can still be used (at least theoretically, due to computational issues) for some infinite collections that behave as small (finite) collections, with the terminology of Sections 4.7 and 8.3.4.

Indeed, [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF] prove that Algorithm 5 can be used for selecting a tuning parameter within a continuous set M . The proof of [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF] for kernel ridge regression mostly relies on two facts: (i) Algorithm 5 would work for a collection of L 1 n L 2 such estimators for any fixed L 1 , L 2 > 0, (ii) the collection of kernel ridge regressors can be well approached by a finite collection of L 1 n L 2 estimators for some fixed L 1 , L 2 > 0. We conjecture that a similar approach can be used for proving that Algorithm 5 works with some other continuous collections, starting by multiple-kernel ridge regression with a fixed number of kernels.

Model selection for identification of the true model

Throughout this survey, we assume that the goal is to choose a data-driven m ∈ M such that the risk of s m is minimal, that is, satisfies a non-asymptotic oracle inequality (2). Model selection can target a different goal, which is to identify the smallest true model m ∈ M with probability one asymptotically, assuming that some true model exists; a procedure m achieving this goal is said "model-consistent". Then, the exact same procedure cannot achieve the two goals in general [START_REF] Yang | Can the strengths of AIC and BIC be shared? A conflict between model indentification and regression estimation[END_REF]. Can minimal-penalty algorithms still be useful for identification? Some experiments and theoretical arguments suggest a positive answer.

Role of the size of the model collection For large collections -see Section 8.3.4-, it turns out that both estimation and identification require to overpenalize compared to the unbiased risk estimation principle. Therefore, the minimal-penalty algorithms suggested in Section 8.3.4

Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019 should also work for identification. This conjecture is supported by the experiments of Bontemps and Toussile (2013, Figure 2) about variable selection in multinomial mixture models, and by those of Arlot et al. (2019, Figure 2) and Garreau and Arlot (2018, Figure 5-6) about changepoint detection.

For small collections, the picture is different. A typical example is least-squares fixed-design regression with projection estimators, as in Section 2. Let us focus on this setting here for simplicity. The slope heuristics then leads to a model-selection procedure equivalent to C p , which is first-order optimal for estimation but inconsistent for identification (Shao, 1997, Theorem 1). A simple way to fix this failure is to replace the factor 2 between minimal and optimal penalties in the slope heuristics by, say, a log(n) factor, in order to get a BIC-type penalty, hence consistent for identification (Shao, 1997, Theorem 2). Such a correction of the slope heuristics may seem unsatisfactory, so one may consider to combine it with a procedure choosing from data between AIC and BIC-type penalties [START_REF] Yang | Can the strengths of AIC and BIC be shared? A conflict between model indentification and regression estimation[END_REF][START_REF] Van Erven | Catching up faster by switching sooner: a predictive approach to adaptive estimation with an application to the AIC-BIC dilemma[END_REF].

Change-point detection For change-point detection with well-chosen small collections of models, [START_REF] Gey | Using CART to Detect Multiple Change Points in the Mean for large samples[END_REF], [START_REF] Durot | Estimating the joint distribution of independent categorical variables via model selection[END_REF] and [START_REF] Akakpo | Estimating a discrete distribution via histogram selection[END_REF] propose specific hybrid procedures for identification of the change-point locations. In short, they consist of twosteps procedures, with minimal-penalty algorithms in both steps. The first step selects within a small model collection, providing an oversegmentation of the data sequence. The second step removes the unnecessary change-points. Proving the consistency of these procedures -including the minimal-penalty algorithms-is an open problem. Another natural question is to generalize such two-steps procedures to other model-selection problems with an identification goal.

Minimal penalties for consistent identification Let us finally mention some theoretical results about the minimal level of penalization needed for model consistency, that is, for having m = m a.s. asymptotically. Even without a corresponding calibration algorithm -since the minimal penalty is not observable here-, this question remains of interest for theory.

In least-squares regression, Shao (1997, Theorem 1 (iii)) shows that C p is not model consistent, assuming only that some true model m ∈ M exists with D m < D m D m + κ for some fixed κ > 0. Such a result actually holds for any penalty of the form CD m /n with C 0 fixed as n grows, which can be proved from arguments used in the proof of Theorem 1. Conversely, using a penalty of the form λ n D m /n with λ n → +∞ and λ n /n → 0 as n tends to infinity provides a modelconsistent procedure (Shao, 1997, Theorem 2). Therefore, the minimal level of penalization for identification is of the form λ n D m /n with λ n → +∞.

For maximum-likelihood estimators, at least two results are available. BIC-type penalties are minimal for estimating the order of a Markov chain without any prior upper bound on its order [START_REF] Van Handel | On the minimal penalty for Markov order estimation[END_REF]. For density estimation with i.i.d. data, identifying the true model among a nested family by minimizing the log-likelihood penalized by pen(m) = f (m)g(n) requires that g(n) > C (s ) log log n for some constant C (s ) > 0 [START_REF] Gassiat | Consistent order estimation and minimal penalties[END_REF].

Miscellaneous

Model selection Numerical experiments suggest that minimal-penalty algorithms work well for several other model-selection problems. We list them below, in order to help identifying settings where new theoretical results could be proved: 1. Heteroscedastic regression when the residual variance is known up to a constant -which can occur for inverse problems-, with least-squares risk and estimators (Villers, 2007, Section 2.6.2), beyond regressograms and strongly localized bases for which theoretical results are already known for a random design [START_REF] Arlot | Data-driven calibration of penalties for least-squares regression[END_REF][START_REF] Navarro | Slope heuristics and V-fold model selection in heteroscedastic regression using strongly localized bases[END_REF]. The fixed-design case can be handled similarly to the results of [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF]. The random-design case with general models is clearly more challenging.

2. Estimation of two kinds of geometrical objects, with least-squares risk and estimators: simplicial complices [START_REF] Caillerie | Model selection for simplicial approximation[END_REF] and principal curves [START_REF] Biau | Parameter selection for principal curves[END_REF].

3. Least-squares risk and estimators for clustering of compositional data [START_REF] Godichon-Baggioni | Clustering transformed compositional data using K-means, with applications in gene expression and bicycle sharing system data[END_REF], Hawkes-process intensity estimation (Reynaud-Bouret and Schbath, 2010), and in a functional linear model (Roche, 2014, Section 2.4).

4. Maximum-likelihood estimators with the Kullback-Leibler loss for semiparametric regression with censored data via the Cox model [START_REF] Letué | Modèle de Cox: estimation par sélection de modèle et modèle de chocs bivarié[END_REF], point-process intensity estimation (Michel, 2008, Section 6.3 and Appendix D.1.2), regression for counting processes under a proportional-hazard assumption [START_REF] Oueslati | A proportional hazards regression model with change-points in the baseline function[END_REF], and segmentation of spectral images via spatialized Gaussian mixtures [START_REF] Cohen | Unsupervised segmentation of spectral images with a spatialized Gaussian mixture model and model selection[END_REF].

Estimator selection We emphasize in this survey that minimal-penalty algorithms can be useful for estimator selection in general. Beyond the few theoretical results pointed out in Section 4.2, we conjecture that Algorithms 5-6 work for several estimator-selection problems. First, numerical experiments suggest that they can be used for selecting among maximumlikelihood or least-squares estimators trained on data-driven models, obtained by L 1 penalization in a variable-selection setting [START_REF] Meynet | A sparse variable selection procedure in model-based clustering[END_REF][START_REF] Devijver | Model-based regression clustering for high-dimensional data: application to functional data[END_REF], by thresholding the empirical covariance matrix [START_REF] Devijver | Nonlinear network-based quantitative trait prediction from transcriptomic data[END_REF][START_REF] Devijver | Block-diagonal covariance selection for high-dimensional Gaussian graphical models[END_REF], by k-means [START_REF] Caillerie | Model selection for simplicial approximation[END_REF], or by (kernel) PCA in classification (Zwald, 2005, Section 6.4.3) or functional data analysis (Roche, 2014, Section 2.4). Some of these results are detailed above in Sections 8.3.2 and 8.3.3.

Second, minimal-penalty algorithms can be used successfully for the pruning step of CART in regression [START_REF] Gey | Using CART to Detect Multiple Change Points in the Mean for large samples[END_REF] and of a spatial variant of CART [START_REF] Bar-Hen | Spatial CART Classification Trees[END_REF], according to numerical experiments.

Finally, Algorithms 5-6 certainly cannot succeed for any kind of estimator collection. Section 8.5 describes a natural and promising way to generalize the minimal-penalty approach beyond Algorithms 5-6.

Overpenalization

It is known empirically that a better model-selection performance can be obtained by overpenalizing a bit: the penalty C pen gal opt (m) = CE R( s m ) -R n ( s m ) has optimal performance when C is slightly above 1, as shown for instance by [START_REF] Arlot | Report about the paper "Gaussian model selection[END_REF], Arlot (2007, Chapter 11) and Arlot (2009, Section 6.3.2) in the regression setting, and by Arlot and Lerasle (2016, Figure 3) Error bars are so small that they would not be visible on the graph. The optimal overpenalization factor is C = 1.12, leading to an improvement by a factor 1.015 compared to taking C = 1.

and [START_REF] Saumard | Finite sample improvement of Akaike's information criterion[END_REF] propose a natural way to overpenalize automatically, which leads to a new corrected version of the AIC criterion. Nevertheless, choosing from data an appropriate overpenalization factor remains an open problem.

For reasons detailed below, we conjecture that minimal penalties can help solving this issue. More precisely, when Algorithms 5-6 are known to be first-order optimal, we conjecture that they automatically overpenalize -by a factor close to 1 when n is large-, and that this overpenalization decreases the risk of the final estimator compared to penalization by pen gal opt (m). Another way to formulate this conjecture, following [START_REF] Lacour | Minimal penalty for Goldenshluger-Lepski method[END_REF] and Lacour et al. (2017, Section 2.4), is to state that the optimal constant C depends on n differently from what first-order asymptotics suggest, and that Algorithm 5 estimates well the finite-sample value of C . Section 2 certainly provides the less difficult setting for proving this conjecture, even if the challenge is high: it requires to analyze penalization procedures at a precision level an order of magnitude higher than ever.

Several results support the above conjecture. First, several simulation experiments show that minimal-penalty algorithms overpenalize slightly in most settings: this is reported by Villers (2007, Section 2.6.2.4), [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF] and Solnon et al. (2012, Section 6), and this holds for the experiments of Section 7.1 (see Figure 6 in Section 7.1 and Tables 2-3 in Appendix C).

Second, Theorem 1 is consistent with the fact that C jump might overestimate σ 2 . Taking for instance T n = n/2, Theorem 1 implies that on a large-probability event,

(1 -η - n )σ 2 C thr. (T n ) (1 + η + n )σ 2
with η + n > η - n ; Proposition 3 in Section 6.1 provides a precise statement. If these bounds are tight, it means that C thr. is slightly biased upwards as an estimator of σ 2 , which corresponds to overpenalization.

Third, minimal-penalty algorithms take into account the full collection of estimators ( s m ) m∈M in their definition, and Section 8.3.4 details why they should automatically adapt to the richness of the collection M . We claim that the need for overpenalization might be mostly related to the richness of M , so that the conjectures of Section 8.3.4 could help solving the above overpenalization conjecture. Let us explain briefly why, by considering fixed-design regression with projection estimators, using some results and the vocabulary of Section 4.7. When M is small -say, one model per value of the dimension-, pen C p (m) = 2σ 2 D m /n is an (asymptotically) optimal penalty and the minimal penalty is σ 2 D m /n. When M is large -say, n D models of dimension D-, the minimal amount of penalization required is multiplied by 1 + 2 log(n/D m ), which is of order 2 log(n) 1 (except for the largest models), and good performance can be obtained with some penalties of the same order of magnitude. For a given sample size n, between these two extreme settings, there is a continuum of collections M of increasing sizes, for which the optimal amount of penalization is C n (M ) pen C p for some C n (M ) between 1 and 2 log(n), approximately: this is an instance of the overpenalization phenomenon. So, if a minimal-penalty algorithm adapts to the size of M , it would capture the need for overpenalization by C n (M ) in the constant C jump . At least, C jump would be asymptotically of the correct order for both small and large M , which cannot be done with some estimator σ 2 that does not take into account the collection M . 8.5. Beyond Algorithms 5-6: phase transitions for estimator selection Most, if not all, nonparametric estimators depend on one or several parameters, whose optimal data-driven choice is often a challenge. In this survey, we focus on a single parameter C that is a multiplicative constant in front of a penalty, and we show that in several settings: (i) an observable phase transition occurs for the estimator s m (0) min (C) around C = C , and (ii) C can be used for the optimal calibration of s m (1) opt (C) through Algorithm 5. If a similar phenomenon occurs for other types of tuning parameters, this would lead to highly interesting generalizations of Algorithm 5. This subsection collects partial theoretical resultsusing the notation (β ), (β ), (γ) and ( γ ) defined in Sections 4.1-4.4-and experiments going into this direction, as well as several conjectures and open problems.

Goldenshluger-Lepski's and related procedures

Goldenshluger-Lepski's method [START_REF] Goldenshluger | Bandwidth selection in kernel density estimation: oracle inequalities and adaptive minimax optimality[END_REF][START_REF] Bertin | Adaptive pointwise estimation of conditional density function[END_REF]) is a classical estimator-selection procedure, which does not rely on penalization of an empirical risk but on pairwise comparisons between estimators.

Goldenshluger-Lepski's method For choosing the bandwidth h of kernel density estimators with a fixed kernel, in order to minimize the least-squares risk, [START_REF] Lacour | Minimal penalty for Goldenshluger-Lepski method[END_REF] study a slightly simplified version of Goldenshluger-Lepski's method, that depends on a single parameter a that can be interpreted as a constant in front of a penalty. If we define the complexity by C h = K 2 /(nh), as usual for kernel density estimation, Lacour and Massart (2016, Theorem 3) prove an equivalent of (β -) and (β -) if a < 1, and ( γ ) if a > 1. Simulation experiments suggest that there is indeed a phase transition for the selected bandwidth around some value a of a -hence, (β + ) should also hold true-and that the optimal value of a is slightly above a .

Despite the theoretical results showing that a → 1 as n → +∞, for a finite sample size a is not necessarily close to 1. This leads to a minimal-penalty algorithm for estimating a , hence calibrating (a simplified version of) Goldenshluger-Lepski's method. The numerical experiments of two papers show the interest of this algorithm, with a defined similarly to C max j. : for estimating the stationary distribution of a bifurcating Markov chain on R d (Bitseki Penda and Roche, 2017), and for state-by-state inference of the emission densities of a hidden Markov model [START_REF] Lehéricy | State-by-state minimax adaptive estimation for nonparametric hidden Markov models[END_REF]. Although [START_REF] Lehéricy | State-by-state minimax adaptive estimation for nonparametric hidden Markov models[END_REF] takes a penalty multiplied by a = 2 a for defining the final estimator -similarly to the slope heuristics-, Bitseki Penda and Roche (2017) take a just above a, by selecting the estimator immediately after the jump of C h . This choice is supported by the fact that the minimal and optimal penalties are almost equal in the results of [START_REF] Lacour | Minimal penalty for Goldenshluger-Lepski method[END_REF].

Penalized comparison to overfitting (PCO) In the same framework, with a possibly multivariate bandwidth h ∈ R d , [START_REF] Lacour | Estimator selection: a new method with applications to kernel density estimation[END_REF] propose a new procedure called penalized comparison to overfitting (PCO), which lies between penalization and Goldenshluger-Lepski's method. PCO depends on a parameter λ which is a multiplicative factor in front of one of the two terms of some kind of penalty. Considering again the complexity C h = K 2 /(nh), PCO satisfies an equivalent of (β -) if λ < 0 (Lacour et al., 2017, Theorems 3-4), (β + ) if λ > 0, and (γ) around λ = λ = 1 (Lacour et al., 2017, Theorems 2 and 5). The optimality of λ = 1 is assessed by numerical experiments on synthetic data [START_REF] Varet | Numerical performance of penalized comparison to overfitting for multivariate kernel density estimation[END_REF].

Although PCO does not seem to require a data-driven calibration of λ according to the above result, λ = 1 may not always be a good choice outside the least-squares density estimation setting. Therefore, the theoretical results of [START_REF] Lacour | Estimator selection: a new method with applications to kernel density estimation[END_REF] suggest the following minimalpenalty algorithm for calibrating PCO: first, detect λ around which λ → C h(λ ) jumps, then, take

(a) λ = λ + 1 or (b) λ = 2( λ + 1) -1 = 2 λ + 1
for defining the final estimator. Option (a) is suggested by the fact that the difference between the minimal λ -zero-and the optimal λ -one-is equal to 1 (Varet et al., 2019, Remark 3.1). Option (b) is suggested by the slope heuristics, since the penalty λ pen 0 is equivalent to C pen 0pen 0 with C = λ + 1, for which the minimal penalty occurs at C = 1 and the (asymptotically) optimal penalty occurs for C = 2 -hence a factor 2 between the minimal and the optimal penalty. The experiments of Comte et al. (2017, Section 5) suggest that a similar way to calibrate PCO works well for selecting the bandwidth of a kernel estimator of the stationary density of the solution of a stochastic differential equation. For state-by-state inference of the emission densities of a hidden Markov model, Lehéricy (2018, Section 4.3.2) proposes a variant of PCO that can be well calibrated by a minimal-penalty algorithm according to numerical experiments.

A full theoretical validation of this calibration strategy remains an open problem. Providing theoretical guidelines for choosing between options (a) and (b) would also be interesting. Another natural question is to generalize PCO to other settings where Goldenshluger-Lepski's method applies, such as density estimation with the L p risk or regression; to the best of our knowledge, this remains an open problem.

Choice of a threshold

For some thresholding estimators, with a threshold depending (non-linearly) on some parameter γ ∈ (0, +∞), an equivalent of (β ) is proved -for a particular basis and assuming that s is equal to 1 [0,1] -, as well as an equivalent of ( γ ) in the general case, in two settings: density estimation on R [START_REF] Reynaud-Bouret | Adaptive density estimation: a curse of support?[END_REF] and estimation of a Poisson intensity on R (Reynaud-Bouret and Rivoirard, 2010).

For some Dantzig estimator (given some dictionary), with a parameter γ > 0 appearing in the Dantzig constraints, [START_REF] Bertin | Adaptive Dantzig density estimation[END_REF] prove an equivalent of (β ) -for a particular dictionary and assuming that s = 1 [0,1] -, as well as an equivalent of ( γ ) in the general case.

In all the above results (Reynaud-Bouret and Rivoirard, 2010; [START_REF] Bertin | Adaptive Dantzig density estimation[END_REF][START_REF] Reynaud-Bouret | Adaptive density estimation: a curse of support?[END_REF], an equivalent of Algorithm 5 is proposed for a data-driven choice of γ, and numerical experiments suggest that the optimal γ is often very close to the minimal γ. Therefore, a generalization of the slope heuristics (γ opt ≈ 2γ min ) probably does not hold here.

Generalization

The above results, obtained for two different kinds of problems, suggest that phase transitions could be used much more generally for estimator selection, including the optimal calibration of learning algorithms. Section 8.3.3 proposes it for the Lasso and related procedures. We conjecture that the same idea can be used fruitfully in several other settings.

The key question is to find the good parametrization of the estimator collection. The successes of minimal-penalty algorithms rely on the parametrization by the constant C in front of a wellchosen penalty shape pen 0 -that is, chosen following the theoretical guidelines of Section 5.1, possibly combined with the practical hints referenced in Section 7.6.

Finding an appropriate parametrization for the Lasso, for instance, remains an open problem to the best of our knowledge.

Related challenges in probability theory

Addressing the statistical open problems listed above mostly relies on a few corresponding open problems in probability theory. As detailed in Section 5, for each estimator s m considered, given some deterministic s m -which can be the best estimator in the associated model, or the expectation of s m , for instance-, the key theoretical quantities are the following:

-the excess risk p

1 (m) = R( s m ) -R(s m ), -the excess empirical risk p 2 (m) = R n (s m ) -R n ( s m ), -the empirical process at s m , δ (m) = R(s m ) -R n (s m ).
Since the empirical process is well understood in general, the main challenges are about p 1 (m) and p 2 (m). One either has to show that |p 1 (m)p 2 (m)|/p 1 (m) is small on a large-probability event -using Proposition 2 in Section 5.2.2-, or to show non-asymptotic concentration inequalities for p 1 (m) and p 2 (m) around deterministic quantities that are known up to a multiplicative factor.

We strongly encourage further work on these questions, especially on the concentration of the excess risk p 1 (m) and the excess empirical risk p 2 (m), which are difficult theoretical problems of interest for statisticians beyond minimal penalties. Indeed, concentrating the excess risk provides lower bounds on the risk of the estimator s m for a given statistical problem -and not in the minimax sense, as most statistical lower bounds-, which can be much informative for practicioners. This problem has attracted some attention in the last few years, and we review the recent work on this topic in Section 5.3. When s m is the empirical risk minimizer over some model S m , the excess empirical risk can be rewritten as the supremum of an empirical process

p 2 (m) = sup t∈S m R n (s m ) -R n (t) ,
which is an object of interest for empirical process theory in general. Its concentration can also be seen as a non-asymptotic version of the Wilks phenomenon, which is another reason for tackling the theoretical challenge of proving that p 2 (m) concentrates around some deterministic quantity. Section 5.2.3 reviews such theoretical results.

Handling large collections of estimators -see Sections 4.7 and 8.3.4-induces additional issues, since we cannot expect p 1 (m), p 2 (m), and δ (m) to concentrate tightly uniformly over all m ∈ M . This raises the challenge of understanding precisely their uniform deviations among such large collections, with high-probability upper and lower bounds on these deviations. In the case of model selection, by grouping models of the same dimension as explained in Section 4.7, this problem reduces to concentrating p 1 (m) and p 2 (m) for empirical risk minimizers over models that are unions of a large number of vector spaces of the same dimension. Note that the same probabilistic challenge arises in the problem of understanding the overpenalization phenomenon -see Section 8.4-, for both large and small collections of estimators.

that is,

1 -max 1 -(C -1)(1 -ε p ) , ε δ R s m (0) min (C) -R(s ) 1 + max (C -1)(1 + ε p ) -1 , ε δ inf m∈M R( s m ) -R(s ) + ε δ
which proves Eq. ( 67). Using again Eq. ( 66), we get

p 2 m (0) min (C) (1 + ε p )p 1 m (0) min (C) (1 + ε p ) R s m (0) min (C) -R(s ) K(C)(1 + ε p ) inf m∈M R( s m ) -R(s ) + K (C)(1 + ε p ) . Extension Note that if pen 0 (m) = p 2 (m) is replaced by (1 -ε 0 )p 2 (m) pen 0 (m) (1 + ε 0 )p 2 (m)
for some ε 0 0 with C(1ε 0 ) > 1, and if Eq. ( 66) is replaced by

∀m ∈ M , -ε p + ε - p p 1 (m) p 2 (m) ε + p p 1 (m) + ε p (84)
for some ε - p , ε + p > 0 and ε p 0, the same proof shows that Eq. ( 67) holds true with

K(C) := max [C(1 + ε 0 ) -1]ε + p , 1 + ε δ min [C(1 -ε 0 ) -1]ε - p , 1 -ε δ and K (C) := ε δ + 2(C -1)ε p min [C(1 -ε 0 ) -1]ε - p , 1 -ε δ ,
and Eq. ( 68) replaced by

p 2 m (0) min (C) K(C)ε + p inf m∈M R( s m ) -R(s ) + K (C)ε + p + ε p . (85)

A.3. Proof of Proposition 3

We first state two general lemmas for C thr. and C window , as defined by Eq. ( 20) and ( 19) in Section 2.5, respectively. These lemmas do not assume a specific definition for m(C) and D m , so they apply to Algorithms 1, 3, 4, and 5 (possibly up to a rescaling of C m for Lemma 2 and Algorithm 5).

Lemma 1. Let T n ∈ R, m : [0, +∞) → M some function, and C thr.

(T n ) := inf C 0 / D m(C) T n . If Γ 1 0 and D m(C) > T n for all C < Γ 1 , then, C thr. (T n ) Γ 1 . If Γ 2 0 and D m(Γ 2 ) T n , then, C thr. (T n ) Γ 2 .
Proof. The proof is straightforward from the definition of C thr. . Lemma 2. Let η > 0, m : [0, +∞) → M some function, and

C window (η) ∈ argmax C 0 D m(C/[1+η]) -D m(C[1+η]) .
Assume that 0 D m n for every m ∈ M . Assume in addition that a n , b n ∈ R and

Γ 2 > Γ 1 > 0 exist such that a n -b n > max{n -a n , b n }, ∀C Γ 1 , D m(C) a n , ∀C Γ 2 , D m(C) b n , and
(1 + η) 2 Γ 2 Γ 1 .
Then, we have

Γ 1 1 + η < C window (η) < Γ 2 (1 + η) . Proof. First, for C = √ Γ 1 Γ 2 , we have C/(1 + η) Γ 1 and C(1 + η) Γ 2 , hence we obtain D m(C/[1+η]) -D m(C[1+η]) a n -b n . Second, for every C Γ 1 /(1 + η), we have the inequality D m(C/[1+η]) -D m(C[1+η]) n -a n . Third, for any C Γ 2 (1 + η), D m(C/[1+η]) -D m(C[1+η]) b n . The result follows since a n -b n > max{n -a n , b n }.
Let us now prove Proposition 3. By Eq. ( 30) and Eq. ( 35) in the proof of Theorem 1, for all x 0, on the event Ω x which has a probability larger than 1 -4 card(M )e -x , we have

∀C C 1 (x; a n ), D m(C) a n and ∀C C 2 (x; b n ; c n ), D m(C) b n , (86)
whatever 0 c n < b n n and 0 a n < n, provided that M contains at least one model of dimension at most c n .

Proof of Eq. (75) First, note that

C 1 x; 2n 3 = σ 2 1 -12 x n + 18 x n > 0 since x/n ( √ 6 -
2)/6. Therefore, by continuity of C 1 and using that c n < n/3, there exists some ε 86) holds true, we get that

1 ∈ (0, min{1/2, 1 -3c n /n}) such that C 1 (x; 2n 3 (1 + ε)) > 0 for any ε ∈ [0, ε 1 ]. Let us take any ε ∈ (0, ε 1 ], a n = 2n 3 (1 + ε) ∈ (2n/3, n), and b n = n 3 (1 -ε) ∈ (c n , n/3). By Lemma 2 with a n , b n as above, Γ 1 = C 1 (x; a n ), and Γ 2 = C 2 (x; b n ; c n ), on Ω x , since Eq. (
∀η C 2 x; n 3 (1 -ε); c n C 1 x; 2n 3 (1 + ε) -1 , C 1 x; 2n 3 (1 + ε) 1 + η < C window (η) < C 2 x; n 3 (1 -ε); c n (1+η
some ε 2 ∈ (0, ε 1 ] exists such that ∀ε ∈ (0, ε 2 ] , η C 2 x; n 3 (1 -ε); c n C 1 x; 2n 3 (1 + ε) -1 .
So, for such η, on Ω x , for every ε ∈ (0, ε 2 ],

C 1 x; 2n 3 (1 + ε) 1 + η < C window (η) < C 2 x; n 3 (1 -ε); c n (1 + η) .
Making ε tend to zero in the above inequality yields the result.

Proof of Eq. (76) For any a n ∈ (T n , n), by Eq. ( 86), on Ω x , we have D m(C) a n > T n for every

C C 1 (x; a n ), hence C thr. (T n ) C 1 (x; a n ) by Lemma 1 with Γ 1 = C 1 (x; a n ). So, on Ω x , C thr. (T n ) sup a n ∈(T n ,n) C 1 (x; a n ) = C 1 (x; T n ) .
By Eq. ( 86) with b

n = T n > c n , on Ω x we have D m(C) T n for every C C 2 (x; T n ; c n ), hence C thr. (T n ) C 2 (x; T n ; c n ) by Lemma 1 with Γ 2 = C 2 (x; T n ; c n ).
Proof of Eq. (77) Let α = log(4 card M ) log( 8), since card(M ) 2 under the assumptions of Proposition 3. For every z 0, by Eq. ( 76) with x = z + α and c n replaced by T n /2,

P C thr. -σ 2 2 4 max 1 - T n n -2 , T n 2n -2 × B T n 2 + 2σ 2 z + α n + 2(z + α) n 2   e -z . (87)
Then, integrating Eq. ( 87) with respect to z -that is, using Lemma 3 below-we get that Eq. ( 77) holds true. Note that much smaller constants can be obtained by assuming that card(M ) is large enough, or that log(card M )/n is small enough. For instance, under the assumption that 100 card(M ) exp(n/100), we get

E C thr. -σ 2 2 max 1 - T n n -2 , T n 2n -2 12B T n 2 2 + 102σ 4 log(card M ) n .
Lemma 3. For a real-valued random variable Z, if some a, b, c 0 exist such that for every z 0,

P Z a + bz + cz 2 e -z , then, E[Z] a + 2b + 4c .
Lemma 3 is a classical integration exercise. Lemma 4. Let F ∈ R n , M ∈ M n (R) a symmetric matrix, ε ∈ R n some random vector with independent components such that for all i ∈ {1, . . . , n},

E[ε i ] = 0 , E ε 2 i = σ 2 , E ε 3 i = m 3 , and E ε 4 i = m 4 . Then, if Z = F + ε, M(F + ε) , var (Z) = W + 4 MF 2 σ 2 + 4 F, M diag(M)1 m 3 ( 92
)
where

W := tr diag(M) 2 m 4 -3σ 4 + 2 tr(M 2 )σ 4 satisfies 0 W 2σ 4 + m 4 tr(M 2 ) . ( 93
)
Proof of Lemma 4. First note that

Z = F, MF + ε, Mε + 2 MF, ε . Then, E[Z] = F, MF + E ε, Mε = F, MF + σ 2 tr(M) .
Furthermore,

E Z 2 = F, MF 2 + E ε, Mε 2 + 4E MF, ε 2 + 2 F, MF σ 2 tr(M) + 4E ε, Mε MF, ε = F, MF 2 + n ∑ i=1 M 2 i,i m 4 -3σ 4 + tr(M) 2 + 2 tr(M M) σ 4 + 4 MF 2 σ 2 + 2 F, MF σ 2 tr(M) + 4 n ∑ i, j=1 M i,i M i, j F j m 3
where we used that

E ε, Mε 2 = E   ∑ i, j ε i M i, j ε j 2   = ∑ i, j,k, M i, j M k, E[ε i ε j ε k ε ] = n ∑ i=1 M 2 i,i m 4 -3σ 4 + tr(M) 2 + tr(M 2 ) + tr(M M) σ 4 and for any G ∈ R n (here, G = MF), E G, ε 2 = G 2 σ 2 and E ε, Mε G, ε = E ∑ i, j,k ε i M i, j ε j G k ε k = n ∑ i=1 M i,i G i m 3 .
Eq. ( 92) follows since M is symmetric, var One can formulate the first step in Algorithms 1, 3, 4, and 5 as computing, for every C 0,

(Z) = E[Z 2 ] -E[Z] 2 , n ∑ i, j=1 M i,i M i, j F j = F, M diag(M)1 and n ∑ i=1 M 2 i,i = tr diag(M) 2 .
m(C) ∈ argmin m∈M f (m) +Cg(m) (94)
for some functions f , g : M → R, where M is assumed to be finite. In the most general case (Algorithm 5), f (m) = R n ( s m ) and g(m) = pen 0 (m). Particular cases (Algorithms 1, 3, and 4) follow. This subsection explains how to compute the full path ( m(C)) C 0 defined by Eq. ( 94), given ( f (m)) m∈M and (g(m)) m∈M , with at most O([card M ] 2 ) operations, and much less in practice. The material presented here is adapted from Arlot and Massart (2009, Section 3.2). Similar results -with a bit less details and formulated in specific frameworks where M ⊂ N-have been proved earlier by Lebarbier (2002, Lemma 4.4.1), Lavielle (2005, Proposition 2.1) and Zwald (2005, Section 6.4.3).

First, remark that the definition (94) of m(C) can be ambiguous. Let us choose a strict total order ≺ on M such that g is non-decreasing, which is always possible since M is finite. Then, by convention, for every C 0, m(C) is defined as

m(C) = min ≺ E (C) where E (C) := argmin m∈M f (m) +Cg(m) . (95)
The main reason why the whole trajectory ( m(C)) C 0 can be computed efficiently is its particular shape. Indeed, the proof of Proposition 5 below shows that C → m(C) is piecewise constant and non-increasing for ≺. Then, the whole trajectory ( m(C)) C 0 can be written as

∀i ∈ {0, . . . , i max } , ∀C ∈ [C i ,C i+1 ) , m(C) = m i (96)
where i max ∈ {0, . . . , card(M ) -1} is the number of jumps, (C i ) 0 i i max +1 is an increasing sequence of non-negative reals (the location of the jumps) with C 0 = 0 and C i max +1 = +∞, and (m i ) 0 i i max is a non-increasing sequence of elements of M .

Algorithm 7. Input: ( f (m)) m∈M , (g(m)) m∈M , and ≺ some strict total order on M such that g is non-decreasing. Initialization: C 0 := 0 and m 0 := min ≺ argmin m∈M f (m) .

Step i, i 1: Let

G (m i-1 ) := m ∈ M s.t. f (m) > f (m i-1
) and g(m) < g(m i-1 ) . If G (m i-1 ) = / 0, then put C i = +∞, i max = i -1 and stop. Otherwise, define

C i := min f (m) -f (m i-1 ) g(m i-1 ) -g(m) s.t. m ∈ G (m i-1 ) (97)
and m i := min

≺ F i with F i := argmin m∈G (m i-1 ) f (m) -f (m i-1 ) g(m i-1 ) -g(m) .
Output: (C i ) 0 i i max +1 and (m i ) 0 i i max , which describe according to Eq. (96) the full trajectory ( m(C)) C 0 defined by Eq. (95).

Proposition 5 (Correctness of Algorithm 7). For every C 0, let m(C) be defined by Eq. ( 95).

Assume M is finite. Then, Algorithm 7 terminates and i max card(M ) -1. Furthermore, Algorithm 7 is correct, that is,

(C i ) 0 i i max +1 is increasing and ∀i ∈ {0, . . . , i max -1}, ∀C ∈ [C i ,C i+1 ), m(C) = m i .
Proposition 5 also gives an upper bound on the computational complexity of Algorithm 7: since the complexity of each step is O(card M ), the complexity of Algorithm 7 is upper-bounded by O(i max card M ) O([card M ] 2 ). In general, this upper bound is pessimistic since we usually have i max card(M ) in practice.

Proof of Proposition 5. First, since M is finite, G (m i-1 ) is also finite and m i is well-defined as soon as G (m i-1 ) = / 0, which holds for every i i max . Moreover, by construction, g(m i ) decreases with i, so that all the m i ∈ M are different; hence, Algorithm 7 terminates and we have the inequality i max + 1 card(M ). Notice also that C i can always be defined by Eq. ( 97) with the convention min / 0 = +∞. We now prove by induction that the following property holds true for every i ∈ {0, . . . , i max }, which implies that Proposition 5 holds true: which contradicts the definition of m(C). Therefore, P 0 holds true.

P i : C i < C i+1 and ∀C ∈ [C i ,C i+1 ), m (
P i ⇒ P i+1 for every i ∈ {0, . . . , i max -1} Assume that P i holds true. First, we have to prove that C i+2 > C i+1 . If i = i max -1, this is clear since C i max +1 = +∞. Otherwise, C i+2 < +∞ and m i+2 exists. Then, by definition of m i+2 and C i+2 (resp. m i+1 and C i+1 ), we have Moreover, m i+2 ∈ G (m i+1 ) ⊂ G (m i ) and m i+2 ≺ m i+1 (because g is non-decreasing). Using again the definition of C i+1 , we have

f (m i+2 ) -f (m i+1 ) = C i+2 g(m i+1 ) -g(m i+2 ) (98) f (m i+1 ) -f (m i ) = C i+1 g(m i ) -g(m i+1
f (m i+2 ) -f (m i ) > C i+1 g(m i ) -g(m i+2 ) (100)
(the inequality is strict: otherwise, we would have m i+2 ∈ F i+1 and m i+2 ≺ m i+1 = min ≺ F i+1 , which is not possible). The difference of Eq. ( 100) and (99) yields

f (m i+2 ) -f (m i+1 ) > C i+1 g(m i+1 ) -g(m i+2
) .

By Eq. ( 98), we deduce that

C i+2 g(m i+1 ) -g(m i+2 ) > C i+1 g(m i+1 ) -g(m i+2 ) , hence C i+2 > C i+1 since g(m i+1 ) > g(m i+2
).

Second, we prove that m(C i+1 ) = m i+1 . From P i , we know that for every m ∈ M , for every C ∈ [C i ,C i+1 ), f (m i )+Cg(m i ) f (m)+Cg(m). Taking the limit when C tends to C i+1 , it follows that m i ∈ E (C i+1 ). By Eq. ( 99

Summing Eq. ( 101) and ( 102) gives (C -C)g(m ) (C -C)g(m) so that g(m ) g(m) .

Since C 0, Eq. ( 101) and ( 103) give f (m) +Cg(m) f (m ) +Cg(m), that is

f (m) f (m ) . ( 104
)
If g(m) = g(m ), Eq. ( 102) and ( 104) imply f (m ) = f (m) hence (a) is satisfied. Otherwise, g(m) > g(m ) by Eq. ( 103), and Eq. ( 101 Step 2 of Algorithms 1, 3, 4, and 5 require to localize a jump in the trajectory (C m(C) ) C 0 , given the path ( m(C)) C 0 and some complexity measure (C m ) m∈M . Although the maximal jump is straightforward to localize, Theorem 1 suggests to look for the largest jump over a geometrical window of values of C, that is, C window as defined by Eq. ( 19) in Section 2.5. This section explains how C window can be computed efficiently given the path (C m(C) ) C 0 , with a complexity O(i max log i max ) = O(card M log(card M )).

Let us consider a slightly more general problem: given some α > β > 0, compute (105)

Note that E gal window is usually not reduced to a singleton, but can be an interval or a finite union of intervals.

From Eq. ( 96) in Appendix B.1, the path (C m(C) ) C 0 is piecewise constant and can be fully described with a small number of parameters: writing

C i = C m i , ∀i ∈ {0, . . . , i max } , ∀C ∈ [C i ,C i+1 ) , C m(C) = C i . ( 106
)
Given this description of (C m(C) ) C 0 , Algorithm 8 below determines the set E gal window , as proved by Proposition 6 . Algorithm 8. Input: (C i ) 0 i i max +1 an increasing sequence of non-negative reals with C 0 = 0 and C i max +1 = +∞, and (C i ) 0 i i max a sequence of real numbers.

1. If i max = 0, define E 2. Otherwise, proceed and compute C = (C 1 /β , . . . ,C i max /β ,C 1 /α, . . . ,C i max /α) ∈ R 2i max and ∆ = (C 1 -C 0 , . . . , C i max -C i max -1 , C 0 -C 1 , . . . , C i max -1 -C i max ) ∈ R 2i max . 3. Sort C and ∆ according to C, that is, find some permutation σ of {1, . . . , 2i max } such that C σ (1) • • • C σ (2i max ) and compute C σ = (C σ (i) ) 1 i 2i max and ∆ σ = (∆ σ (i) ) 1 i 2i max .

4. Compute W := cumsum(∆ σ ) ∈ R 2i max , that is, for every i ∈ {1, . . . , 2i max },

W i = i ∑ j=1 ∆ σ j .
5. Compute V ∈ R 2i max such that, for every i ∈ {1, . . . , 2i max }, V i = W i if C σ i < C σ i+1 , and otherwise V i = -∞. 6. Determine K := argmax i∈{1,...,2i max } V i . 106) can be rewritten as

Define E

∀C 0 , C m(C) = C 0 + i max ∑ i=1 (C i -C i-1 )1 C C i
hence, for every C 0, using the notation of Algorithm 8,

C m(βC) -C m(αC) = i max ∑ i=1 (C i -C i-1 )1 βC C i - i max ∑ i=1 (C i -C i-1 )1 αC C i = 2i max ∑ i=1 ∆ i 1 C C i = 2i max ∑ i=1 ∆ σ i 1 C C σ i = 2i max ∑ i=1 W i 1 C∈[C σ i ,C σ i+1 ) = 2i max ∑ i=1 V i 1 C∈[C σ i ,C σ i+1 ) (107)
with the conventions C σ 2i max +1 = +∞ and ∞1 C∈ / 0 = 0. For the last equality, we use the fact that when [C σ i ,C σ i+1 ) is empty -which corresponds to values of C σ i that are equal to C j /β = C k /α for some j, k ∈ {1, . . . , i max }-, the value of W i 1 C∈[C σ i ,C σ i+1 ) is zero whatever W i , hence W i can be changed into V i .

By Eq. ( 107), sup

C 0 C m(βC) -C m(αC) = max 1 i 2i max V i
and the supremum is attained exactly at the values of C belonging to some interval [C σ k ,C σ k+1 ) with k ∈ K = argmax i V i . In other words, Algorithm 8 is correct. The red star shows the position of the oracle (minimum of the risk n -1 F -F λ 2 ). The "elbow" is clearly localized for n = 2 000 (and close to the oracle), but not for n = 100. the Laplace kernel, with α = 8. In the experiments, only a finite set {λ 0 , . . . , λ n } of values of λ is considered, chosen such that the degrees of freedom tr(K(K + nλ i I n ) -1 ) are equal to i for every i = 0, . . . , n.

C

D.2. Procedures

The exact definitions of all procedures considered in the experiments for computing some C or choosing some model m are the following. For the procedures depending on some parameter, its default value is used everywhere except in Tables 23. Note that the choice of the default values was made prior to the simulations: we can check afterwards on Tables 2-3 that these choices provide reasonably good results (which fortunately happened), so that results using only the default values of the parameters (for instance, Table 1) are meaningful.

Maximal jump ( C max j. , 'Max. jump', 'max j.' or 'max') In Section 7.1, we define

C max j. ∈ argmax C 0 D m (0) min (C -) -D m (0) min (C + ) ,
that is, the location of the maximal jump of C → D m (0) min (C) , assuming it is unique. In our experiments, when the argmax contains several values of C, we choose the largest one, that is, the last largest jump; this choice is natural, since it means taking the less complex model among those corresponding to a maximal jump, and it matches the choice made by [START_REF] Lerasle | An oracle approach for interaction neighborhood estimation in random fields[END_REF].

Note that for change-point detection, Lebarbier (2005, Section 4.2) suggests an opposite convention -taking the smallest value of C in the argmax-, arguing from simulation experiments that otherwise too small models are selected. Nevertheless, Lebarbier (2005, Section 4.2) also reports that the latter convention can lead to taking C max j. too small, so a rather complicated method is suggested for choosing some threshold α thr and imposing C max j. α thr .

Threshold ( C thr. or 'thr') Eq. ( 20) in Section 2.5 defines C thr. (T n ) := min C 0 / D m(C) T n , which depends on some parameter T n . The default value of T n is n/2.

Note that Theorem 1 suggests that T n = ρn works for any ρ ∈ (0, 1), and previous theoretical results (Arlot and Massart, 2009, Section 3.3) suggest to take T n ∝ n/ log(n) or n/(log n) 2 . Nevertheless, all these theoretical results involve pessimistic constants (as shown by the simulation experiments), so they cannot be used for a fine tuning of T n . It turns out that n/2 does very good in the experiments of Tables 23, while other choices lead to much worse performance.

Window ( C window or 'win') Eq. ( 19) in Section 2.5 defines

C window (η) ∈ argmax C 0 D m(C/[1+η]) -D m(C[1+η]) ,
which depends on some parameter η > 0. Similarly to C max j. , the argmax is usually not reduced to a single point, so a more precise definition must be given for C window . Actually, when η > 0, Note that at step 4, it can happen that no platform is large enough. In such cases, we consider the last platform among the ones of largest size, that is, ı = max i ∈ {1, . . . , I} / N i = max j N j .

We always take pct = 0.15 in our experiments, that is, the default value proposed by [START_REF] Baudry | Slope heuristics: overview and implementation[END_REF]. Note that [START_REF] Baudry | Slope heuristics: overview and implementation[END_REF] only provide a model-selection procedure m CAPUSHE , and not a value C of the constant in front of the penalty. In order to help understanding better m CAPUSHE , we also report in our experiments the distribution of C CAPUSHE that we define as some median of C s (D ı ), . . . , C s (D ı+1 -1) .

This choice is arbitrary among many others that all lead to having m CAPUSHE = m(2 C CAPUSHE ).

Median ('med') As defined in the caption of Figure 6 Remark that the set of procedures considered is arbitrary, and other choices could be made. Nevertheless, it seems wise to keep an equilibrium between the jump and slope formulations; here, the jump approach is slightly favored, but the slope definitions come into play when C max j. , C thr. , and C window do not exactly coincide.

The idea of considering some median of several values of C could also be used when there is some uncertainty about the parameter of some procedure (say, T n for C thr. ), by considering the median of the set of values obtained on a grid of values of the parameter. Residuals ( σ 2 m 0 , 'Residuals on m 0 ' or 'resid') The residual-based variance estimator σ 2 m 0 is defined by Eq. ( 71) in Section 6.1:

σ 2 m 0 := 1 n -D m 0 Y -F m 0 2
for some model m 0 . In the experiments, there is one model per dimension, so m 0 is given by the value of its dimension D m 0 and the default choice is D m 0 = n/2. Since n = 100, the default choice is D m 0 = 50 which is even, so the definition of S hard m -in which models of odd dimension are good and models of even dimension are very poor-is made on purpose.

Note that in Tables 23, the line "D m 0 = n/ log(n)" means "D m 0 = 21" (hence, for the 'hard' setting, it is a reasonably good model).

Consensus ('cons') As defined in the caption of Figure 7, the "consensus" procedure performs a majority vote among m(2 C max j. ), m(2 C thr. ), m(2 C window ), m(2 C slope ), m CAPUSHE with their default parameters values. If no majority emerges (that is, if we do not have at least three of these procedures that agree), the default choice is m(2 C window ). Remark that Table 1 shows that an agreement occurs for more than 96% of the samples in the 'easy' setting, and for more than 89% of the samples in the 'hard' setting.

Consensus when no reject ('no rej') This actually refers to the same procedure as 'consensus', but showing results (a boxplot or an estimation of the expectation of the loss ratio) only for the samples for which a majority emerged. Again, Table 1 shows that this only removes a small fraction of the N = 10 4 independent samples generated in our experiments.

Mallows' C p When the variance σ 2 is known, a natural model-selection procedure for the framework of Section 2 is Mallows' C p [START_REF] Mallows | Some comments on C p[END_REF], that is, selecting

m = m(2σ 2 ) = argmin m∈M 1 n F m -Y 2 + 2σ 2 D m n .
Its performance is shown in Tables 2-3 for comparison. Mallows' C p is also considered for illustrating the overpenalization phenomenon in Figure 8 in Section 8.4. On the graph of Figure 8, what is plotted is, for C ∈ [0, 4], the estimated value (from N = 10 4 independent samples) of the expected risk ratio

E    F m(2Cσ 2 ) -F 2 inf m∈M F m -F 2   
when using Mallows' C p penalty multiplied by C; we recall that m(•) is defined by Eq. ( 10) in Section 2.3. For plotting the graph of Figure 8, a linear grid of values of C with stepsize 1/100 is considered. The optimal performance is obtained for C = 1.12 in the 'easy' and 'hard' settings, and it is also included in Tables 23. Illustrations made on a single sample in the least-squares framework are showed in Figures 2, 4, 5, 9, 10. The samples considered have been chosen manually in order to illustrate either typical or rare (but still possible) configurations. The graphs of Figure 2, Figure 4, and Figure 10a are made on the same sample (they correspond to a "typical" situation). The graph of Figure 5 is made on a second sample (corresponding to a "rare" situation). The two graphs of Figure 9 are made on a third sample (also corresponding to a "rare" situation, similar to the one shown in Figure 5).

1

  Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 The slope heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1 Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Optimal penalty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

FIGURE 2 .

 2 FIGURE 2. Illustration of Algorithms 1 and 2 on the same sample ('easy' setting, see Appendix D for details). Left: Plot of C → D m(C) and visualization of C jump . Right: Plot of D m → n -1 Y -F m 2 and visualization of -C slope /n.

  ), we show that m(C) minimizes a quantity G C (m) close to crit C (m), and then we show that G C (m 1 ) (resp. G C (m 2 ), for some well-chosen m 2 ∈ M ) is smaller than G C (m) for any model m with D m < 9n/10 (resp. D m > n/10).

  , and C m = tr(A m ). Then, plotting C m 1 (C) as a function of C, what we typically get is shown in Figure 3 (black curve / diamonds): no clear jump of the complexity is observed around σ 2 , contrary to what Algorithm 3 predicts.

  m∈M R n ( s m ) +C pen 0 (m) .

  ) so that m gal min (C) ∈ argmin m∈M {crit gal C (m)} is a proxy for m gal min (C) ∈ argmin m∈M R n ( s m ) +C pen gal min (m) .Let us assume for simplicitythat R n ( s m ) is a decreasing function of C m . Then, when C < 1, crit gal C (m) is a decreasing function of C m , so that C m gal min (C) ≈ max m∈M C m which corresponds to overfitting. On the contrary, when C > 1, (1 -C)E[ R n ( s m )] is an increasing function of C m while CR(s m ) is approximately constant for C m large enough, so that C m gal min (C) max m∈M C m .Therefore, if concentration inequalities show that m

  s m ) +C pen 0 (m) .

  3. -Density estimation, independent and identically distributed data, least-squares risk, linear estimators (for instance, Parzen density estimators and weighted least-squares estimators): Lerasle et al. (2016) -after a preliminary version in the PhD dissertation of Magalhães (2015, Chapter 2)-define some theoretical quantities pen 0 (m) ≈ E[p 2 (m)] and C m ≈ E[p 1 (m)] -easy to estimate in general, and known for several examples such as Parzen density estimators-such that m(C) ∈ argmin m∈M R n ( s m ) + pen 0 (m) +CC m overfits for C < 0 and satisfies an oracle inequality for all C > 0, first-order optimal when C = C = 1. In other words, Lerasle et al. (2016) almost prove that Algorithm 5 works with pen 0

  M is "moderate" in the intermediate situation, when D -1 log f (D) stays bounded away from 0 and ∞ for n D 1.

  , ( γ ) holds with pen mult 1 = C pen mult 0 for any C > 1.Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  min (C) ∈ argmin m∈M R n ( s m ) +C pen 0 (m) . Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019 5.2.1. Below the minimal penalty: (β -)

  6.3. Model/estimator-selection procedures based on C p /C L Let us go back to the model/estimator-selection problem in the fixed-design regression setting.

  Let us first compare theoretically the various definitions of C. For C jump , when there is a single large jump in C → C m (0) min (C) , Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

FIGURE 4 .

 4 FIGURE 4. Connection between Algorithms 1 and 2: Plot of D m → n -1 Y -F m 2 and visualization of C slope . Setting called 'easy' in Appendix D.

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019 max j. thr. win. slope CAP. med. cons. no rej. resid. 'Easy' setting. max j. thr. win. slope CAP. med. cons. no rej. resid.

FIGURE 7 .

 7 FIGURE 7. Distribution over 10 000 independent samples of F m -F 2 / inf m∈M F m -F 2 for m = m(2 C) with C among the seven estimators C compared in Figure 6, and for m obtained by majority vote among { m(2 C max j. ), m(2 C thr. ), m(2 C window ), m(2 C slope ), m CAPUSHE } with m(2 C window ) as a default choice ('cons.') or considering only the samples on which such a majority exists ('no rej.'). See Appendix D for details.

  ) C 0 requires at most O([card M ] 2 ) operations -as shown in Appendix B.1-and much less in practice. Indeed, denoting by i max + 2 Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  ) -see Section 4.7-, suggest that a minimal-penalty algorithm with C m = D m and pen 0 (m) proportional to a linear combination of D m and D m log n D m

FIGURE 8 .

 8 FIGURE 8. Overpenalization with Mallows' C p penalty, 'easy' setting (see Appendix D.2 for details). Error bars are so small that they would not be visible on the graph. The optimal overpenalization factor is C = 1.12, leading to an improvement by a factor 1.015 compared to taking C = 1.

For

  proving Eq. (93), we remark thatW = tr diag(M) 2 m 4σ 4 + 2 tr(M 2 )tr diag(M) 2 σ 4 ,m 4 σ 4 , and 0 tr diag(M) 2 tr(M 2 ) since M is symmetric. Appendix B: Algorithms B.1. Computation of the full path ( m(C)) C 0 in Algorithms 1, 3, 4, and 5

  C) = m i . P 0 holds true By definition of C 1 , since M is finite, C 1 > 0. Note that C 1 may be equal to +∞ if G (m 0 ) = / 0. For C = C 0 = 0, the definition of m 0 is the one of m(0), so that m(C) = m 0 . For C ∈ (0,C 1 ), Lemma 5 below shows that either m(C) = m(0) = m 0 or m(C) ∈ G (m 0 ). In the latter case, by definition of C 1 , f m(C)f (m 0 ) g(m 0 )g m(C) C 1 > C hence f m(C) +Cg m(C) > f (m 0 ) +Cg(m 0 )

  ), we then have m i+1 ∈ E (C i+1 ). Now, let m be any element of E (C i+1 ). By Lemma 5 withC = C i , m = m i = m(C i ) ∈ E (C i ) and C = C i+1 > C i , we have either (a) f (m ) = f (m i ) and g(m ) = g(m i ) or (b) m ∈ G (m i ); case (c) is excluded since m i = m(C i ). In case (a), g(m ) = g(m i ) > g(m i+1 ), hence m i+1 ≺ m because g is non-decreasing. In case (b), notice that m i , m ∈ E (C i+1 ) implies f (m ) +C i+1 g(m ) = f (m i ) +C i+1 g(m i ). Since m ∈ G (m i ),we get that m ∈ F i+1 . Then, by definition of m i+1 , we have m i+1 m . Overall, we have proved that m i+1 belongs to E (C i+1 ) and is smaller than any element m of E (C i+1 ), which proves thatm i+1 = min ≺ E (C i+1 ) = m(C i+1 ). Let C ∈ (C i+1 ,C i+2). It remains to prove m(C ) = m i+1 . From the last statement of Lemma 5 with C = C i+1 , we have either m(C ) = m(C i+1 ) = m i+1 or m(C ) ∈ G ( m(C i+1 )) = G (m i+1 ). In the latter case (in which G (m i+1 ) = / 0 hence C i+2 < ∞), by definition of C i+2 , f m(C )f (m i+1 ) g(m i+1 )g m(C ) C i+2 > C so that f m(C ) +C g m(C ) > f (m i+1 ) +C g(m i+1 )which contradicts the definition of m(C ). Therefore, m(C ) = m i+1 , which ends proving P i+1 .The following lemma is used in the proof of Proposition 5 above.Lemma 5. With the notation of Proposition 5 and its proof, if we have 0 C < C , m ∈ E (C), and m ∈ E (C ), then one of the following statements holds true:(a) f (m) = f (m ) and g(m) = g(m ).

  (b) f (m) < f (m ) and g(m) > g(m ).

  (c) C = 0, f (m) = f (m ) and g(m) > g(m ), hence m = m(0). In particular, for any 0 C < C , we have either m(C) = m(C ) or m(C ) ∈ G ( m(C)). Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019 Proof of Lemma 5. By definition of E (C) and E (C ), f (m) +Cg(m) f (m ) +Cg(m ) (101) and f (m ) +C g(m ) f (m) +C g(m) .

  ) implies f (m) < f (m ) or C = 0. If f (m) < f (m ), (b) holds true. Otherwise, f (m) = f (m ) and C = 0. Since g(m ) < g(m), we get m ≺ m hence m = m(0).The last statement follows by taking m = m(C) and m = m(C ), which excludes case (c). In case (a),E (C) = E (C ) hence m(C) = m(C ). In case (b), m(C ) ∈ G ( m(C)).B.2. Computation of C window in step 2 of Algorithms 1, 3, 4, and 5

  βC) -C m(αC) .

  gal window := [0, +∞) and stop.Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  gal window := k∈K [C σ k ,C σ k+1 ) with C σ 2i max +1 = +∞. Output: E gal window .Proposition 6 (Correctness of Algorithm 8). Algorithm 8 is correct, that is, it terminates and its output E gal window actually satisfies Eq. (105) provided Eq. (106) holds true. Proof of Proposition 6. If i max = 0, C → C m(C) is constant over [0, +∞) so Algorithm 8 is correct. Otherwise, Eq. (

  FIGURE 11. L-curve (log 10 Y -F λ , log 10 F λ ) λ >0 in the 'kernel ridge' framework. See Appendix D for details. The red star shows the position of the oracle (minimum of the risk n -1 F -F λ 2 ). The "elbow" is clearly localized for n = 2 000 (and close to the oracle), but not for n = 100.

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019Then, m 1 , . . . , m n-2 is piecewise constant, and some 1= D 1 < . . . < D I+1 = n -1 and m 1 , . . . , m I+1 ∈ M exist such that ∀i ∈ {1, . . . , I} , ∀D ∈ [D i , D i+1 -1] , m D = m iwith m 1 = m 2 , . . ., m I = m I+1 . The intervals [D i , D i+1 -1] are called "plateau" (platforms) byBaudry et al. (2012, Section 4.2) and their size is denoted byN i = D i+1 -D i .-Step 4: Keep only the platforms of size N i larger than pct times the total size ∑ N = n -2, and among these, define ı the last platform, that is,ı = max i ∈ {1, . . . , I} / N i > pct × (n -2)and select m CAPUSHE = m ı .

  , 'median' refers to taking C as the median of C max j. , C thr. , C window , C slope , C CAPUSHE (with their default parameter values for C thr. , C window , and C slope : T n = n/2, η = n -1/2 , D 0 = n/2), and m = m(2 C).

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019D.3. Additional remarksRepeated experiments show results obtained from N = 10 4 independent samples.

Figure 3

 3 is taken from the article byArlot and Bach (2011, top right graph of Figure 2). It is made from a single sample generated as in the kernel-ridge framework (see Appendix D.1), with a sample size n = 200. Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  The minimal penalty is not proportional to tr(A m ) for kernel ridge estimators (Figure taken from the article by Arlot and Bach (2011), 'kernel ridge' framework, see Appendix D for details): C → C m 1 (C) for Algorithm 3 with pen 1 (m) = tr(A m )/n and C m = tr(A m ) (black curve / diamonds), and C → tr(A m lin min (C) ) for Algorithm 4 (red curve / crosses) with linear estimators (kernel ridge).

	selected degrees of freedom	0 50 100 150 200	-2	0 log(C/σ 2 )	2 min. pen. opt. pen. / 2
	FIGURE 3.
	Soumis au Journal de la Société Française de Statistique
	File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13
	date: October 23, 2019

  Alg.4 ∈ argmin m∈M n -1 F m -Y 2 + 2 C jump tr(A m )/n .

	overfits.	then crit lin C (m) is a decreasing function of C m , and C m lin min (C) is huge: m lin min (C)
	-if C > σ 2 , then crit lin C (m) increases with C m for C m large enough, so C m lin min (C) is much smaller than when C < σ 2 .
	This behavior is also the one of m lin min (C), as illustrated in Figure 3 (red curve / crosses), which
	leads to the following algorithm.
	Algorithm 4 (Minimal-penalty algorithm for linear estimators).
	Input: F m -Y 2	m∈M , tr(A m ) m∈M , and tr(A m A m ) m∈M .
	1. Compute m lin min (C) C 0 , where m lin min (C) is defined by Eq. (49).
	2. Find C jump > 0 corresponding to the "unique large jump" of C → tr A m lin min (C) .
	3. Select m Output: m Alg.4 .

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

Table 1 )

 1 but illustrates well the differences between C max j. , C window , and C thr. . Setting called 'easy' in Appendix D.

	Soumis au Journal de la Société Française de Statistique
	File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13
	date: October 23, 2019

TABLE 1 .

 1 Frequency of various configurations for the set of five models m respectively selected by Algorithm 1 with C max j. ('max'), C thr. ('thr'), C window ('win'), by Algorithm 2 ( C slope ) and by m CAPUSHE . 'Easy' and 'hard' settings, see Appendix D for details.

	Soumis au Journal de la Société Française de Statistique
	File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13
	date: October 23, 2019

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019 Distribution over 10 000 independent samples of C/σ 2 for seven estimators C of σ 2 : C max j.

		3				12
		2.5				10
		2				8
	C / σ 2	1.5			C / σ 2	6
		1				4
		0.5				2
		0	max j.	thr.	win. slope CAP. med. resid.	0	max j.	thr.	win. slope CAP. med. resid.
					(a) 'Easy' setting.				(b) 'Hard' setting.
	FIGURE 6.

('max j.'), C thr. ('thr.'), C window ('win.'), C slope in Algorithm 2 ('slope'), C CAPUSHE ('CAP.'), the median of { C max j. , C thr. , C window , C slope , C CAPUSHE } ('med.'), and σ 2 m 0 defined by Eq. (71) ('resid.'). See Appendix D for details. of C jump /σ 2 from Proposition 3 is B(c n )/σ 2 + log(n)/n with c n = n/3 (for C window ) or T n /2 (for C thr. ); in our experiments, with n = 100 and T n = n/2, we get B(c n )/σ 2 ∈ [0.04, 0.08], and log(n)/n ≈ 0.2, so the constants appearing in Proposition 3 here are pessimistic.

  al., Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019 2012; Roche, 2014, Table 2.1). Only

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

  ) .

	Now, since z → C 1 (x; z) is continuous and different from zero at z = 2n/3, and since the mapping
	z → C 2 (x; z; c n ) is continuous at z = n/3 (using that c n < n/3), for any
	η >	C 2 x; n 3 ; c n 3 C 1 x; 2n	-1 ,
	Soumis au Journal de la Société Française de Statistique
	File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13
	date: October 23, 2019

  ) .

	(99)

Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

TABLE 2 .

 2 Algorithms 1-2, 'easy' setting: distribution of C and model-selection performance, with various definitions for C and various parameters for each definition. The risk ratio isE[ F m -F 2 / inf m∈M F m -F 2 ].Reported values are empirical estimates obtained from N = 10 000 independent samples. For the risk ratio, error bars are equal to the standard deviation of the ratio F m -F 2 / inf m∈M F m -F 2 divided by √ N.Soumis auJournal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

	C	E C/σ 2	var( C)/σ 2 E ( C -σ 2 ) 2 /σ 4	risk ratio
	C max j.	1.09	0.257	0.0749	1.309 ± 0.003
	C thr. , T n = n/10	3.12	1.281	6.140	1.647 ± 0.004
	C thr. , T n = n/ log(n)	1.60	0.469	0.584	1.310 ± 0.002
	C thr. , T n = n/2	1.13	0.229	0.0683	1.278 ± 0.003
	C thr. , T n = 9n/10	0.84	0.239	0.0826	1.621 ± 0.083
	C window , η = 1/n C window , η = 1/ √ n C window , η = 1.5/ √ n	1.09 1.10 1.10	0.257 0.256 0.258	0.0745 0.0752 0.0776	1.309 ± 0.003 1.308 ± 0.003 1.307 ± 0.003
	C window , η = log(n)/n	1.12	0.263	0.0829	1.304 ± 0.003
	C window , η = 2 log(n)/n	1.17	0.286	0.110	1.294 ± 0.003
	C slope , D 0 = n/10	1.15	0.181	0.0544	1.243 ± 0.002
	C slope , D 0 = n/ log(n)	1.09	0.188	0.0437	1.260 ± 0.002
	C slope , D 0 = n/2	1.05	0.228	0.0543	1.313 ± 0.003
	C slope , D 0 = 9n/10	1.02	0.478	0.229	1.672 ± 0.009
	CAPUSHE	1.05	0.291	0.0873	1.410 ± 0.005
	median	1.08	0.229	0.0588	1.301 ± 0.003
	consensus	-	-	-	1.306 ± 0.003
	consensus when no reject	-	-	-	1.298 ± 0.003
	σ 2 m 0 , D m 0 = n/10 σ 2 m 0 , D m 0 = n/ log(n) σ 2 m 0 , D m 0 = n/2 σ 2 m 0 , D m 0 = n/2 + 1 σ 2 m 0 , D m 0 = 9n/10	1.23 1.12 1.05 1.05 1.02	0.180 0.176 0.211 0.213 0.455	0.0862 0.0443 0.0469 0.0478 0.2080	1.237 ± 0.002 1.241 ± 0.002 1.304 ± 0.003 1.305 ± 0.003 1.641 ± 0.008
	C p (known σ 2 )	-	-	-	1.269 ± 0.003
	C p ×1.12 (known σ 2 )	-	-	-	1.251 ± 0.002

TABLE 3 .

 3 E C/σ 2 var( C)/σ 2 E ( Cσ 2 ) 2 /σ 4risk ratio Same as Table 2 for the 'hard' setting. Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

	C max j.	1.10	0.259	0.076	1.291 ± 0.003
	C thr. , T n = n/10	3.38	1.390	7.57	1.661 ± 0.004
	C thr. , T n = n/ log(n)	1.59	0.462	0.563	1.285 ± 0.002
	C thr. , T n = n/2	1.13	0.231	0.0703	1.258 ± 0.002
	C thr. , T n = 9n/10	0.86	0.236	0.077	1.566 ± 0.008
	C window , η = 1/n C window , η = 1/ √ n C window , η = 1.5/ √ n	1.09 1.10 1.11	0.257 0.257 0.258	0.0746 0.0762 0.078	1.292 ± 0.003 1.288 ± 0.003 1.288 ± 0.003
	C window , η = log(n)/n	1.12	0.263	0.0827	1.287 ± 0.003
	C window , η = 2 log(n)/n	1.17	0.285	0.109	1.275 ± 0.003
	C slope , D 0 = n/10	1.54	0.188	0.328	1.268 ± 0.002
	C slope , D 0 = n/ log(n)	1.65	0.193	0.46	1.291 ± 0.002
	C slope , D 0 = n/2	2.36	0.231	1.89	1.437 ± 0.003
	C slope , D 0 = 9n/10	20.2	2.07	374	3.68 ± 0.016
	CAPUSHE	2.77	1.66	5.87	1.562 ± 0.005
	median	1.16	0.253	0.0911	1.260 ± 0.002
	consensus	-	-	-	1.285 ± 0.003
	consensus when no reject	-	-	-	1.266 ± 0.003
	σ 2 m 0 , D m 0 = n/10 σ 2 m 0 , D m 0 = n/ log(n) σ 2 m 0 , D m 0 = n/2 σ 2 m 0 , D m 0 = n/2 + 1 σ 2 m 0 , D m 0 = 9n/10	5.44 1.12 8.94 1.05 38.9	0.473 0.176 0.828 0.213 3.95	19.9 0.0443 63.7 0.0478 1450	2.055 ± 0.006 1.223 ± 0.002 2.577 ± 0.006 1.285 ± 0.003 6.11 ± 0.011
	C p (known σ 2 )	-	-	-	1.252 ± 0.003
	C p ×1.12 (known σ 2 )	-	-	-	1.232 ± 0.002

  Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

In "the slope heuristics", the word "heuristics" is an uncountable noun, following the Oxford Advanced Learner's Dictionary. One could also write "the slope heuristic", according to some other English dictionaries in which "heuristic" appears as a noun. We use the former spelling throughout this article, but some other articles make use of the latter spelling (without the final s).

Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

It should be noticed here that the article by[START_REF] Lerasle | Sharp oracle inequalities and slope heuristic for specification probabilities estimation in discrete random fields[END_REF] was prepublished on June 2011 (arXiv preprint number 1106.2467), a few months before the preprint by[START_REF] Garivier | Oracle approach and slope heuristic in context tree estimation[END_REF], despite what the publication date of the former paper suggests.Soumis auJournal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

Acknowledgments

The author acknowledges the support of the French Agence Nationale de la Recherche (Blanc SIMI 1 2011 projet Calibration). Part of this work was done while the author was financed by CNRS and member of the Sierra team in the Département d'Informatique de l'École normale supérieure (CNRS / ENS / Inria UMR 8548), 45 rue d'Ulm, 75005 Paris, France.

I thank the successive editors of the Journal de la Société Française de Statistique, Philippe Besse and Gilles Celeux, for their patience and kindness as they waited for me to submit this invited paper.

I warmly thank the numerous colleagues who kindly answered my questions about their own works related with minimal penalties, during the (long) period of preparation of this article or before. Special thanks to Matthieu Lerasle and Pascal Massart for many inspiring discussions on the topic, to Yves Rozenholc for a long discussion at a CIRM workshop about his "statistical base jumping" idea that is described in Section 7.5, and to Gilles Celeux and Adrien Saumard for a careful reading of a preliminary version of this work.

Finally, I deeply thank Patricia Reynaud-Bouret who introduced me to the topic quite early (at the beginning of 2002!) -I owe her my first numerical experiments on the slope heuristics (Arlot and Baudry, 2002)-, and my coauthors on the minimal-penalty related articles I wrote: Pascal Massart, Francis Bach, Matthieu Solnon, Alain Celisse, Zaïd Harchaoui, and Damien Garreau. Soumis au Journal de la Société Française de Statistique File: survey_penmin.tex, compiled with jsfds, version : 2018/06/13 date: October 23, 2019

which implies, using Eq. ( 60), that

hence Eq. ( 61) by dividing by (1 -C). Eq. ( 62) is a straightforward consequence of Eq. ( 61) since p 2 (m 1 ) > 0.

General proof of Eq. (60) Let us assume that ξ 1 , . . . , ξ n ∈ X are i.i.d. and some contrast function γ : Ξ × S → R and constants A, L > 0 exist such that Eq. ( 63)-(65) hold true. Then, for every x 0, with probability at least 1 -2 card(M )e -x , for every θ > 0, Eq. ( 60) holds with

x n . Indeed, for every fixed m ∈ M ,

Soumis au

are i.i.d. random variables satisfying |X i,m | 2A almost surely. Therefore, by Bernstein's inequality (Boucheron et al., 2013, Theorem 2.10), for every x 0, with probability at least 1

x n and the result follows by the union bound.

Extension Note that assuming only that (1 61) we get that

If in addition some m 1 ∈ M exists such that R(s m 1 ) = R(s ) and p 2 (m 1 ) > 0, we get that for any α ∈ (0, 1),

.

A.2. Proof of Proposition 2

By definition of m (0)

hence, using Eq. (66),

By Eq. ( 60), we get that for every m ∈ M and C > 1, The following proposition gives a general formula for the variance and MSE of the residualvariance estimator σ 2 m 0 defined by Eq. ( 71) in Section 6.1. Note that Proposition 4 and Lemma 4 below are classical results (see for instance Ullah and Zinde-Walsh, 1992, Eq. ( 5), or Dette et al., 1998, Eq. ( 6)). We state and prove them here for completeness.

In this subsection, for any matrix M ∈ M n (R), diag(M) denotes the diagonal matrix of the diagonal elements of M and 1 = (1, . . . , 1) ∈ R n .

Proposition 4. Let Π ∈ M n (R) some orthogonal projection matrix such that D = tr(Π) < n, ε ∈ R n some random vector with independent components, and F ∈ R n . Assume that for all i ∈ {1, . . . , n},

Then,

where

In particular, if the ε i are Gaussian,

Proof of Proposition 4. Applying Lemma 4 below with M = I n -Π yields Eq. ( 88), since we have σ 2 = Z/(n -D) and M is an orthogonal projection matrix with tr(M) = n -D. Eq. ( 89) follows, in combination with Eq. ( 72), since

In the Gaussian case, m 3 = 0 and m 4 = 3σ 4 , hence

which leads to Eq. ( 90) and ( 91). (a) L-curve (as in Figure 4). This section provides all details necessary to reproduce the figures and simulation experiments reported throughout the article.

D.1. Data and estimators

All experiments are made within the fixed-design regression framework described in Section 2.1, with two main kinds of estimator collections and data.

Least-squares framework ('easy'/'hard') All figures and tables, except Figures 3 and11, consider data and estimators as follows. Data satisfy

The estimators considered are least-squares (projection) estimators with one among the following two collections of models (S m ) 1 m n :

-'easy' setting: for every m ∈ {1, . . . , n}, S m = S easy m is the linear span of the first m vectors of the canonical basis of R n . -'hard' setting: for every m ∈ {1, . . . , n}, S m = S hard m is the linear span of the first m vectors of the canonical basis of R n if m is odd, and S m = S hard m is the linear span of the last m vectors of the canonical basis of R n if m is even. Both settings correspond to (ordered) variable selection with an orthogonal design, after having transformed the data conveniently according to the design matrix. In the easy case, the variables are ordered by decreasing order of magnitude. In the hard case, some uncertainty remains about the correct order (ascending or descending), and the two options are considered alternatively (depending on the parity of n). Of course, models S hard m with m even are very poor, but this can be unknown before seeing the data.

Kernel ridge framework Figures 3 and 11 consider data and estimators as follows. Data satisfy

The family of estimators considered is the family of kernel ridge estimators ( F λ ) λ >0 where for every λ > 0,

window ) the last of these intervals -that is, the one corresponding to the largest values of Cwe define

Of course, other choices could be possible and we do not claim that our (arbitrary) choice is the best one.

In Figures 5 and9b, the interval represented by the two red vertical lines is [ C

(1)

window ). Note that this interval often looks like [ C window /(1 + η), C window (1 + η)) but it can also be quite different.

Taking the limit η → 0 + in the definition of C window , we recover C max j. . Theorem 1 suggests to take η ∝ η + n log(n)/n, that we consider in our experiments (see Tables 23). In our experiments, the default value for η is n -1/2 , a choice made to get a slightly smaller value than log(n)/n ≈ 0.22 (we recall that n = 100 in the least-squares framework).

Slope ( C slope or 'slope') In Algorithm 2, the definition of C slope is rather vague; it is a bit more precise in Section 7 where the range of models considered in the regression is defined by pen 0 (m) ∈ [p min , p max ] for some p min < p max to be chosen. In the experiments, since pen 0 (m) is equal to D m /n in the least-squares framework, we choose p min = D 0 /n and p max = 1 for some parameter

In other words, given D 0 ∈ [1, n), we consider only models of dimension D m D 0 and we perform a (standard) linear regression of the empirical risk n -1 F m -F 2 against -D m /n, that is, we solve