Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
59,797 characters · 23 sections · 51 citation commands
High-Dimensional $L_2$-Boosting: Rate of Convergence
\editor{N.N.}
In this paper we consider $L_2$Boosting algorithms for regression which are coordinatewise greedy algorithms that estimate the target function under $L_2$ loss. Boosting algorithms represent one of the major advances in machine learning and statistics in recent years. Freund and Schapire's AdaBoost algorithm for classification (freund:1997) has attracted much attention in the machine learning community as well as in statistics. Many variants of the AdaBoost algorithm have been introduced and proven to be very competitive in terms of prediction accuracy in a variety of applications with a strong resistance to overfitting. Boosting methods were originally proposed as ensemble methods, which rely on the principle of generating multiple predictions and majority voting (averaging) among the individual classifiers (cf nr:buhlmann.hothorn:2007). An important step in the analysis of Boosting algorithms was Breiman's interpretation of Boosting as a gradient descent algorithm in function space, inspired by numerical optimization and statistical estimation (nr:breiman:1996, nr:breiman:1998). Building on this insight, nr:friedman.hastie.ea:2000 and nr:friedman:2001 embedded Boosting algorithms into the framework of statistical estimation and additive basis expansion. This also enabled the application of boosting for regression analysis. Boosting for regression was proposed by nr:friedman:2001, and then nr:buhlmann.yu:2003 defined and introduced $L_2$Boosting. An extensive overview of the development of Boosting and its manifold applications is given in the survey nr:buhlmann.hothorn:2007.
In the high-dimensional setting there are two important but unsolved problems on $L_2$Boosting. First, the convergence rate of the $L_2$Boosting has not been thoroughly analyzed. Second, the pattern of the variables selected at each step of $L_2$Boosting is unknown.
In this paper, we show that these two problems are closely related. We establish results on the sequence of variables that are selected by $L_2$Boosting. At any step of $L_2$Boosting, we call this step "revisiting" if the variable chosen in this step has already been selected in previous steps. We analyze the revisiting behavior of $L_2$Boosting, i.e., how often $L_2$Boosting revisits. We then utilize these results to derive an upper bound of the rate of convergence of the $L_2$Boosting.\footnote{Without analyzing the sequence of variables selected at each step of $L_2$Boosting, only much weaker results on convergence speed of $L_2$Boosting are available based on DeVore1996 and Livshitz2003.} We show that frequency of revisiting, as well as the convergence speed of $L_2$Boosting, depend on the structure of the design matrix, namely on a constant related to the minimal and maximal restricted eigenvalue. Our bounds on convergence rate of $L_2$Boosting are in general slower than that of $LASSO$.
We also introduce in this paper the so--called \textquotedblleft post-Boosting\textquotedblright, and the orthogonal boosting variant.\footnote{Orthogonal boosting has also similarities with forward step-wise regression.} For orthogonal boosting see also Section 3.1 in LaiYuan2021. We show that both algorithms achieve the same rate of convergence as LASSO in a sparse, high-dimensional setting.
Compared to LASSO, boosting uses a somewhat unusual penalization scheme. The penalization is done by \textquotedblleft early stopping\textquotedblright\ to avoid overfitting in the high-dimensional case. In the low-dimensional case, $L_2$Boosting without stopping converges to the ordinary least squares (OLS) solution. In a high-dimensional setting early stopping is key for avoiding overfitting and for the predictive performance of boosting. We give a new stopping rule that is simple to implement and also works very well in practical settings as demonstrated in the simulation studies. We prove that such a stopping rule achieves the best bound obtained in our theoretical results.
In a deterministic setting, which is when there is no noise or error term in the model, boosting methods are also known as greedy algorithms (the pure greedy algorithm (PGA) and the orthogonal greedy algorithm (OGA)). In signal processing, $L_2$Boosting is essentially the same as the matching pursuit algorithm of ms:mallatzhang:1993. We will employ the abbreviations post-BA (post-$L_2$Boosting algorithm) and oBA (orthogonal $L_2$Boosting algorithm) for the stochastic versions we analyze.
The rate of convergence of greedy algorithms has been analyzed in DeVore1996 and Livshitz2003. Temlyakov:2011 is an excellent survey of recent results on the approximation theory of greedy approximation. To the best of our knowledge, with an additional assumption on the design matrix, we establish the first results on revisiting in the deterministic setting and greatly improve the existing results of DeVore1996. These results, being available in the appendix, are essential for our analysis for $L_2$Boosting, but might also be of interest in their own right.
As mentioned above, Boosting for regression was introduced by nr:friedman:2001. $L_2$-Boosting was defined in nr:buhlmann.yu:2003. Its numerical convergence, consistency, and statistical rates of convergence of boosting with early stopping in a low-dimensional setting were obtained in nr:zhang.yu:2005. Consistency in prediction norm of $L_2$Boosting in a high-dimensional setting was first proved in nr:buhlmann:2006. The numerical convergence properties of Boosting in a low-dimensional setting are analyzed in FGM15. The orthogonal Boosting algorithm in a statistical setting under different assumptions is analyzed in ms:inglai:2011. The rates for the PGA and OGA cases are obtained in ms:barron:2008.
In this paper we consider linear basis functions. Classification and regression trees, and the widely used neural networks, involve non-linear basis functions. We hope that our results can serve as a starting point for the analysis of non-linear basis functions which is left for future research.
The structure of this paper is as follows: In Section 2 the $L_2$Boosting algorithm (BA) is defined together with its modifications, the post-$L_2$Boosting algorithm (post-BA) and the orthogonalized version (oBA). In Section 3 we present a new approximation result for the pure greedy algorithm (PGA later) and an analysis of the revisiting behavior of the boosting algorithm. In Section 4 we present the main results of our analysis, namely an analysis of the boosting algorithm and some of its variants. The proofs together with some details of the new approximation theory for PGA are provided in the Appendix. Section 5 contains a simulation study that offers some insights into the methods and also provides some guidance for stopping rules in applications. Section 6 discusses two applications and provides concluding observations.
Notation: Let $z$ and $y$ be $n$-dimensional vectors. We define the empirical $L_2$-norm as $\mathbb{E}_n[z]=1/n \sum_{i=1}^n z_i$. Define $\lvert \lvert z\rvert\rvert$ to be the Euclidean norm, and $\lvert \lvert z\rvert\rvert_{2,n}:= \sqrt{\mathbb{E}_n[z^2]}$. Define $<\cdot,\cdot>_n$ to be the inner product defined by: $<z,y>_n=1/n \sum_{i=1}^n z_i y_i$.
For a random variable $X$, $\mathbb{E}[X]$ denotes its expectation. The correlation between the random variables $X$ and $Y$ is denoted by $corr(X,Y)$.
We use the notation $a\vee b=\max\{a,b\}$ and $a \wedge b=\min\{a,b\}$. We also use the notation $a \precsim b$ to mean $a \leq cb$ for some constant $c>0$ that does not depend on $n$; and $a \precsim_P b$ to mean $a=\mathcal{O}_P(b)$. For a set $U$, $supp(U)$ denotes the set of indices of which the corresponding element in $U$ is not zero. Given a vector $\beta \in \mathbb{R}^p$ and a set of indices $T \subset \{1,\ldots,p\}$, we denote by $\beta_T$ the vector in which $\beta_{T_j}=\beta_j$ if $j \in T$, $\beta_{T_j}=0$ if $j \notin T$.
To define the boosting algorithm for linear models, we consider the following regression setting:
with vector $x_i=(x_{i,1},\ldots,x_{i,p_n})$ consisting of $p_n$ predictor variables, $\beta$ a $p_n$-dimensional coefficient vector, and a random, mean-zero error term $\varepsilon_i$, $\mathbb{E}[\varepsilon_i|x_i]=0$. Further assumptions will be employed in the next sections.
We allow the dimension of the predictors $p_n$ to grow with the sample size $n$, and is even larger than the sample size, i.e., $dim(\beta)=p_n\gg n$. But we will impose a sparsity condition. This means that there is a large set of potential variables, but the number of variables which have non-zero coefficients, denoted by $s$, is small compared to the sample size, i.e. $s \ll n$. This can be weakened to approximate sparsity, to be defined and explained later. More precise assumptions will also be made later. In the following, we will drop the dependence of $p_n$ on the sample size and denote it by $p$ if no confusion will arise.
$X$ denotes the $n \times p$ design matrix where the single observations $x_i$ form the rows. $X_j$ denotes the $j$th column of design matrix, and $x_{i,j}$ the $j$th component of the vector $x_i$. We consider a fixed design for the regressors. We assume that the regressors are standardized with mean zero and variance one, i.e., $\mathbb{E}_n[x_{i,j}]=0$ and $\mathbb{E}_n[x_{i,j}^2]=1$ for $j=1,\ldots,p$,
The basic principle of Boosting can be described as follows. We follow the interpretation of nr:breiman:1998 and nr:friedman:2001 of Boosting as a functional gradient descent optimization (minimization) method. The goal is to minimize a loss function, e.g., an $L_2$-loss or the negative log-likelihood function of a model, by an iterative optimization scheme. In each step the (negative) gradient which is used in every step to update the current solution is modelled and estimated by a parametric or nonparametric statistical model, the so-called base learner. The fitted gradient is used for updating the solution of the optimization problem. A strength of boosting, besides the fact that it can be used for different loss functions, is its flexibility with regard to the base learners. We then repeat this procedure until some stopping criterion is met.
The literature has developed many different forms of boosting algorithms. In this paper we consider $L_2$Boosting with componentwise linear least squares, as well as two variants. All three are designed for regression analysis. \textquotedblleft $L_2$\textquotedblright refers to the loss function, which is the typical sum-of-squares of the residuals $Q_n(\beta)=\sum_{i=1}^n (y_i - x_i' \beta)^2$ typical in regression analysis. In this case, the gradient equals the residuals. \textquotedblleft Componentwise linear least squares\textquotedblright refers to the base learners. We fit the gradient (i.e. residuals) against each regressor ($p$ univariate regressions) and select the predictor/variable which correlates most highly with the gradient/residual, i.e., decreases the loss function most, and then update the estimator in this direction. We next update the residuals and repeat the procedure until some stopping criterion is met. We consider $L_2$Boosting and two modifications: the \textquotedblleft classical\textquotedblright one which was introduced in nr:friedman:2001 and refined in nr:buhlmann.yu:2003 for regression analysis, an orthogonal variant and post-$L_2$Boosting. As far as we know, post-$L_2$Boosting has not yet been defined and analyzed in the literature. In signal processing and approximation theory, the first two methods are known as the pure greedy algorithm (PGA) and the orthogonal greedy algorithm (OGA) in the deterministic setting, i.e. in a setting without stochastic error terms.
For $L_2$Boosting with componentwise least squares, the algorithm is given below.
For simplicity, write $\gamma^m$ for the value of $\gamma^m_{j^m}$ at the $m^{th}$ step.
The act of stopping is crucial for boosting algorithms, as stopping too late or never stopping leads to overfitting and therefore some kind of penalization is required. A suitable solution is to stop early, i.e., before overfitting takes place. \textquotedblleft Early stopping\textquotedblright\ can be interpreted as a form of penalization. Similar to LASSO, early stopping might induce a bias through shrinkage. A potential way to decrease the bias is by \textquotedblleft post-Boosting\textquotedblright which is defined in the next section.
In general, during the run of the boosting algorithm, it is possible that the same variable is selected at different steps, which means the variable is revisited. This revisiting behavior is key to the analysis of the rate of convergence of $L_2$Boosting. In the next section we will analyze the revisting properties of boosting in more detail.
Post-$L_2$Boosting is a post-model selection estimator that applies ordinary least squares (OLS) to the model selected by the first-step, which is $L_2$Boosting. To define this estimator formally, we make the following definitions: $T:=supp(\beta)$ and $\hat{T}:=supp(\beta^{m^*})$, the support of the true model and the support of the model estimated by $L_2$Boosting as described above with stopping at $m^*$. A superscript $C$ denotes the complement of the set with regard to $\{1,\ldots,p\}$. In the context of LASSO, OLS after model selection was analyzed in belloni:2013. Given the above definitions, the post-model selection estimator or OLS post-$L_2$Boosting estimator will take the form
A variant of the Boosting Algorithm is orthogonal Boosting (oBA) or the Orthogonal Greedy Algorithm in its deterministic version. Only the updating step is changed: an orthogonal projection of the response variable is conducted on all the variables which have been selected up to this point. The advantage of this method is that any variable is selected at most once in this procedure, while in the previous version the same variable might be selected at different steps which makes the analysis far more complicated. More formally, the method can be described as follows by modifying Step (4):
Define $X_o^m$ as the matrix which consists only of the columns which correspond to the variables selected in the first $m$ steps, i.e. all $X_{j_k}$, $k=0,1,\ldots,m$. Then we have:
In approximation theory a key question is how fast functions can be approximated by greedy algorithms. Approximation theory is concerned with deterministic settings, i.e., the case without noise. Nevertheless, to derive rates for the $L_2$Boosting algorithm in a stochastic setting, the corresponding results for the deterministic part play a key role. For example, the results in nr:buhlmann:2006 are limited by the result used from approximation theory, namely the rate of convergence of weak relaxed greedy algorithms derived in Temlyakov2000. For the pure greedy algorithm DeVore1996 establish a rate of convergence of $m^{-1/6}$ in the $\ell_2-$norm, where $m$ denotes the number of steps iterated in the PGA. This rate was improved to $m^{-11/62}$ in Konyagin1999, but Livshitz2003 establish a lower bound of $m^{-0.27}$. The class of functions $\mathcal{F}$ which is considered in those papers is determined by general dictionaries $\mathcal{D}$ and given by \[ \mathcal{F} = \{ f \in \mathcal{H}: f = \sum_{k \in \Lambda} c_k w_k, w_k \in \mathcal{D}, |\Lambda| < \infty \quad \mbox{and} \quad \sum_{k \in \Lambda} |c_k| \leq M \}, \] where $M$ is some constant, $\mathcal{H}$ denotes a Hilbert space, and the sequence $(c_k)$ are the coefficients with regard to the dictionary $\mathcal{D}$.
In this section we discuss the approximation bound of the pure greedy algorithm where we impose an additional but widely used assumption on the Gram matrix $\mathbb{E}_n[x_i x_i']$ in high dimensional statistics to tighten the bounds. First, the assumptions and an initial result describing the revisiting behavior will be given, then a new approximation result based on the revisiting behavior will be presented which is the core of this section. The proofs for this section and a detailed analysis of the revisiting behavior of the algorithm are moved to Appendix A.
For the analysis of the pure greedy algorithm, the following two assumptions are made, which are standard for high-dimensional models.
For the second assumption, we make a restricted eigenvalue assumption which is also commonly used in the analysis of LASSO.
Define $\Sigma(s,M):=\{A|dim(A)\leq s\times s, A \textrm{ is any diagonal submatrices of }M\}$, for any square matrix $M$.
We need the following definition.
More restrictive requirements that $M_0$ should be large enough will be imposed in order to get good convergence rate for the PGA, i.e., $L_2$Boosting without a noise term.
Define $V^m=X\alpha^m$ as the residual for the PGA. $\alpha^m$ is defined as the difference between the true parameter vector $\beta$ and the approximation at the $m^{th}$ step, $\beta^m$, $\alpha^m= \beta - \beta^m$. We would like to explore how fast $V^m$ converges to $0$. In our notation, $||V^{m+1}||^2_{2,n}=||V^m||_{2,n}^2-(\gamma^m)^2$, therefore $||V^m||^2_{2,n}$ is non-increasing in $m$.
As described in Algorithm 1, the sequence of variables selected in the PGA is denoted by $j^0,j^1,\ldots$. Define $T^m:=T\cup \{j^0,j^1,\ldots,j^{m-1}\}$. Define $q(m):=|T^m|$ as the cardinality of $T^m$, $m=0,1,\ldots$. It is obvious that $q(m)\leq m+s$.
It is essential to understand how PGA revisits the set of already selected variables. To analyze the revisiting behavior of the PGA, some definitions are needed to fix ideas.
The lower bound stated in Lemma (ref) has room for improvement, e.g., when $c=0$, $|R(m)|/m=1$ as it is shown in Lemma (ref) in Appendix A, while we get $1/2$ in Lemma (ref) as lower bounds of $|R(m)/m|$ as $m$ becomes large enough. Deriving tight bounds is an interesting question for future research. More detailed properties of the revisiting behavior of $L_2$Boosting are provided in the Appendix A.
With an estimated bound for the proportion of $R$s in the sequence $\mathcal{A}$, we are now able to derive an upper bound for $||V^m||_{2,n}^2$. By Lemma (ref), define $n^*_k:=\frac{m+\mu_a(c)q(k)}{2-\mu_a(c)}$ which is an upper bound of $|q(m+k)-q(k)|$ up to constant converging to $1$ as $q(m)$ goes to infinity. Before we state the main result of this section we present an auxiliary lemma.
Based on Lemma (ref), we are able to develop our main results on approximation theory of pure greedy algorithm under $L_2$ loss and Assumptions (ref) and (ref).
In this section we discuss the main results regarding the $L_2$Boosting procedure (BA), post-$L_2$Boosting (post-BA) and the orthogonal procedure (oBA) in a high-dimensional setting.
We analyze the linear regression model introduced in a high-dimensional setting, which was introduced in Section 2.
First, we analyze the classical $L_2$Boosting algorithm with componentwise least squares. For this purpose, the approximation results which we derived in the previous section are key. While in the previous section the stochastic component was absent, in this section it is explicitly considered.
The following definitions will be helpful for the analysis: $U^{m}$ denotes the residuals at the $m^{th}$ iteration, $U^{m}=Y-X\beta^{m}$. $\beta^{m}$ is the estimator at the $m^{th}$ iteration. We define the difference between the true and the estimated vector as $\alpha^{m}:=\beta-\beta^m$. The prediction error is given by $V^m=X\alpha^m$.
For the Boosting algorithm in the high-dimensional setting it is essential to determine when to stop, i.e. the stopping criterion. In the low-dimensional case, stopping time is not important: the value of the objective function decreases and converges to the traditional OLS solution exponentially fast, as described in B\"uhlmann and Yu (2006). In the high-dimensional case, such fast convergence rates are usually not available: the residual $\varepsilon$ can be explained by $n$ linearly independent variables $x_j$. Thus selecting more terms only leads to overfitting. Early stopping is comparable to the penalization in LASSO, which prevents one from choosing too many variables and hence overfitting. Similarly to LASSO, a sparse structure will be needed for analysis.
At each step, we minimize $||U^m||_{2,n}^2$ along the \textquotedblleft most greedy\textquotedblright variable $X_{j^m}$. The next assumption is on the residual / stochastic error term $\varepsilon$ and encompasses many statistical models which are common in applied work.
Set $\sigma_n^2:=\mathbb{E}_n[\varepsilon^2]$. Recall that $||U^{m+1}||_{2,n}^2=||U^m||_{2,n}^2-(\gamma^m_j)^2$, where $|\gamma_j^m|=\max_{1\leq j\leq p}|<X_j,U^m>_n|=\max_{1\leq j\leq p}|<X_j,V^m>_n+<X_j,\varepsilon>_n|$. The lemma below establishes the main result of convergence rate of $L_2$Boosting.
The bound of the approximation error $||V^m||_{2,n}^2$ stated in inequality ((ref)) is obtained under an infeasible stopping criteria. Below we establish another result which employs the same convergence rate but with a feasible stopping criterion which can be implemented in empirical studies.
In this section we analyze orthogonal $L_2$Boosting. For the orthogonal case, we obtain a faster rate of convergence than with the variant analyzed in the section before. We make use of similar notation as in the previous subsection: $U^m_o$ denotes the residual and $V^m_o$ the prediction error, formally defined below. Again, define $\beta^m_o$ as the parameter estimate after the $m^{th}$ iteration.
The orthogonal Boosting Algorithm was introduced in the previous section. For completeness we give here the full version with some additional notation which will be required in a later analysis.
It is easy to see that:
The benefit of the oBA method, compared to $L_2$Boosting, is that once a variable $X_j$ is selected, the procedure will never select this variable again. This means that every variable is selected at most once.
For any square matrix $W$, we denote by $\phi_s(W)$ and $\phi_l(W)$ the smallest and largest eigenvalues of $W$.
Denote by $T^m$ the set of variables selected at the $m^{th}$ iteration. Write $S^m:=T-T^m$. We know that $|T^m|= m$ by construction. Set $S_{c}^m=T^m-S^m$.
The above lemma essentially says that if $S^m$ is non-empty, then there is still room for significant improvement in the value $||V^m||_{2,n}^2$. The next lemma is key and shows how rapidly the estimates decay. It is obvious that $||U^m_o||_{2,n}$ and $||V^m_o||_{2,n}$ are both decaying sequences. Before we state this lemma, we introduce an additional assumption.
Although in general $L_2$Boosting may have a slower convergence rate than LASSO, oBA reaches the rate of LASSO (under some additional conditions). The same technique used in Lemma 6 also holds for the post-$L_2$Boosting case. Basically, we can prove, using similar arguments, that $T^{Ks}\supset T$ when $K$ is a large enough constant. Thus, post-$L_2$Boosting enjoys the LASSO convergence rate under assumptions A.1--A.4. We state this in the next section formally.
In many cases, penalization estimators like LASSO introduce some bias by shrinkage. The idea of \textquotedblleft post-estimators\textquotedblright\ is to estimate the final model by ordinary least squares including all the variables which were selected in the first step. We introduced post-$L_2$Boosting in Section 2. Now we give the convergence rate for this procedure. Surprisingly, it improves upon the rate of convergence of $L_2$Boosting and reaches the rate of LASSO (under stronger assumptions). The proof of the result follows the idea of the proof for Lemma (ref).
In this section we present the results of our simulation study. The goal of this exercise is to illustrate the relevance of our theoretical results for providing insights into the functionality of boosting and the practical aspects of boosting. In particular, we demonstrate that the stopping rules for early stopping we propose work reasonably well in the simulations and give guidance for practical applications. Moreover, the comparison with LASSO might also be of interest. First, we start with an illustrative example, later we present further results, in particular for different designs and settings.
The goal of this section is to give an illustration of the different stopping criteria. We employ the following data generating process (dgp):\footnote{In order to allow comparability the dgp is adopted from nr:buhlmann:2006.}
with $\varepsilon \sim N(0,2^2)$, $X=(X_1,\ldots, X_{10}) \sim N_10(0, I_{10})$, $I_{10}$ denoting the identity matrix of size $10$. To evaluate the methods and in particular the stopping criteria we conduct an analysis of both in-sample and out-of-sample mean squared error (MSE). For the out-of-sample analysis we draw a new observation for evaluation and calculation of the MSE. For the in-sample analysis we also repeat the procedure and form the average over all repetitions. In both cases we employ $60$ repetitions. The sample size is $n=20$. Hence we have $20$ observations to estimate $10$ parameters.
The results are presented in Figures 5.1 and 5.2. Both show how MSE depends on the number of steps of the boosting algorithm. We see that MSE first decreases with more steps, reaches its minimum and then starts to increase again due to overfitting. In both graphs the solution of the $L_2$Boosting algorithm convergences to the OLS solution. We also indicate the MSE of LASSO estimators as horizontal lines (with cross-validated choice of the penalty parameter and data-driven choice of the penalization parameter.) In order to find a feasible stopping criterion we have to rely on the in-sample analysis. Figure (ref) reveals that the stopping criterion we introduced in the sections before performs very well and even better than stopping based on a corrected AIC values which has been proposed in the literature as stopping criterion for boosting. The average stopping steps of our criterion and the corrected AIC-based criterion (AICc) are presented by the vertical lines. On average our criterion stops earlier than the AICc based one. As our criterion performs better then the AICc we will not report AICc results in the following subsection. For the post-estimator similar patterns arise and are omitted.
In this section we present results for different designs and settings so give a more detailed comparison of the methods.
We consider the linear model
with $\varepsilon$ standard normal distributed and i.i.d. For the coefficient vector $\beta$ we consider two designs. First, we consider a sparse design, i.e., the first $s$ elements of $\beta$ are set equal to one, all other components to zero ($\beta=(1,\ldots,1,0,\ldots,0)$). Then we consider a polynomial design in which the $j$th coefficient given by $1/j$, i.e. $\beta=(1,1/2,1/3, \ldots, 1/p)$.
For the design matrix $X$ we consider two different settings: an \textquotedblleft orthogonal\textquotedblright\ setting and a \textquotedblleft correlated\textquotedblright\ setting. In the former setting the entries of $X$ are drawn as i.i.d. draws from a standard normal distribution. In the correlated design, the $x_i$ (rows of $X$) are distributed according to a multivariate normal distribution where the correlations are given by a Toeplitz matrix with factor $0.5$ and alternating signs.
We have the following settings:
We consider the following estimators: $L_2$Boosting with componentwise least squares, orthogonal $L_2$Boosting and LASSO. For Boosting and LASSO, we also consider the post-selection estimators (\textquotedblleft post\textquotedblright). For LASSO we consider a data-driven regressor-dependent choice for the penalization parameter (BCCH:2012) and cross validation. Although cross validation is very popular, it does not rely on established theoretical results and therefore we prefer a comparison with the formal penalty choice developed in BCCH:2012. For Boosting we consider three stopping rules: \textquotedblleft oracle\textquotedblright, \textquotedblleft Ks\textquotedblright, and a \textquotedblleft data-dependent\textquotedblright stopping criterion which stops if $\frac{||U^m||_{2,n}^2}{||U^{m-1}||_{2,n}^2} = \frac{\hat{\sigma}_{m,n}^2}{\hat{\sigma}_{m-1,n}^2} > (1-C\log(p)/n))$ for some constant $C$. This means stopping, if the ratio of the estimated variances does not improve upon a certain amount any more.
The $Ks$-rule stops after $K \times s$ variables have been selected where $K$ is a constant. As $s$ is unknown, the rule is not directly applicable. The oracle rule stops when the mean-squared-error (MSE), defined below, is minimized, which is also not feasible in practical applications.
The simulations were performed in R (R:2014). For LASSO estimation the packages hdm and glmnet:2010 (for cross validation) were used. The Boosting procedures were implemented by the authors and the code is available upon request.
To evaluate the performance of the estimators we use the MSE criterion. We estimate the models on the same data sets and use the estimators to predict $50$ observations out-of-sample. The (out-of-sample) MSE is defined as
where $m$ denotes the iteration at which we stop, depending on the employed stopping rule. The MSE is estimated by
for the out-of-sample predictions.
The results of the simulation study are shown in Tables 3 -- 10.
As expected, the oracle-based estimator dominates in all cases except in the correlated, sparse setting with more parameters than observations. Our stopping criterion gives very good results, on par with the infeasible $Ks$-rule. Not surprisingly, given our results, both post-Boosting and orthogonal Boosting outperform the standard $L_2$Boosting in most cases. A comparison of post- and orthogonal Boosting does not provide a clear answer with advantages on both sides. It is interesting to see that the post-LASSO increases upon LASSO, but there are some exceptions, probably driven by overfitting. Cross validation works very well in many constellations. An important point of the simulation study is to compare Boosting and LASSO. It seems that in the polynomial decaying setting, Boosting (orthogonal Boosting with our stopping rule) dominates post-LASSO. This also seems true in the iid, sparse setting. In the correlated, sparse setting they are on par. Summing up, it seems that Boosting is a serious contender for LASSO.
In this section we present applications from different fields to illustrate the boosting algorithms. We present applications to demonstrate how the methods work when applied to real data sets and, then compare these methods to related methods, i.e. LASSO. The focus is on making predictions which is an important task in many instances.
Thos application involves genetic data and analyzes the production of riboflavin. First, we describe the data set, then we present the results.
The data set has been provided by DSM (Kaiserburg, Switzerland) and was made publicly available for academic research in BKM:2014 (Supplemental Material).
The real-valued response / dependent variable is the logarithm of the riboflavin production rate. The (co-)variables measure the logarithm of the expression level of $4,088$ genes ($p=4,088$), which are normalized. This means that the covariables are standardized to have variance $1$, and the dependent variable and the resources are \textquotedblleft de-meaned\textquotedblright ,which is equivalent to including an unpenalized intercept. The data set consists of $n=71$ observations which were hybridized repeatedly during a fed-batch fermentation process in which different engineered strains and strains grown under different fermentation conditions were analyzed. For further details we refer to BKM:2014, their Supplemental Material, and the references therein.
We analyzed a data set about the production of riboflavin (vitamin $B_2$) with B. subtilis. We split the data set randomly into two samples: a training set and a testing set. We estimated models with different methods on the training set and then used the testing set to calculate out-of-sample mean squared errors (MSE) in order to evaluate the predictive accuracy. The size of the training set was $60$ and the remaining $11$ observations were used for forecasting. The table below shows the MSE errors for different methods discussed in the previous sections.
All calculations were peformed in R (R:2014) with the package hdm and our own code. Replication files are available upon request.
The results show that, again, post- and orthogonal $L_2$Boosting give comparable results. They both outperform LASSO and post-LASSO in this application.
Here the task is to predict the final score in the subjects Mathematics and Portugese in secondary education. This is relevant, e.g., to identify students which need additional support to master the material. The data contains both student grades and demographic, social and school related features and it was collected by using school reports and questionnaires. Two datasets are provided regarding the performance in two distinct subjects: Mathematics and Portuguese. The data set is made available at the UCI Machine Learning Repository and was contributed by Paulo Cortez. The main reference for the data set is corsil2008.
We employed five-fold CV to evaluate the predictive performance of the data set. The results remain stable when choosing a different number of folds. The data sets contain, for both test results, $33$ variables, which are used as predictors. The data set for the Mathematics test scores contains $395$ observations, the sample size for Portuguese is $649$. The results confirm our theoretical derivations that boosting is comparable to Lasso.
Although boosting algorithms are widely used in industry, the analysis of their properties in high-dimensional settings has been quite challenging. In this paper the rate of convergence for the $L_2$Boosting algorithm and variants are derived, which has been a long-standing open problem until now.