--- abstract: | We study model evaluation and model selection from the perspective of generalization ability (GA): the ability of a model to predict outcomes in new samples from the same population. We believe that GA is one way formally to address concerns about the external validity of a model. The GA of a model estimated on a sample can be measured by its empirical out-of-sample errors, called the generalization errors (GE). We derive upper bounds for the GE, which depend on sample sizes, model complexity and the distribution of the loss function. The upper bounds can be used to evaluate the GA of a model, ex ante. We propose using generalization error minimization (GEM) as a framework for model selection. Using GEM, we are able to unify a big class of penalized regression estimators, including lasso, ridge and bridge, under the same set of assumptions. We establish finite-sample and asymptotic properties (including $\mathcal{L}_2$-consistency) of the GEM estimator for both the $n \geqslant p$ and the $n < p$ cases. We also derive the $\mathcal{L}_2$-distance between the penalized and corresponding unpenalized regression estimates. In practice, GEM can be implemented by validation or cross-validation. We show that the GE bounds can be used for selecting the optimal number of folds in $K$-fold cross-validation. We propose a variant of $R^2$, the $GR^2$, as a measure of GA, which considers both both in-sample and out-of-sample goodness of fit. Simulations are used to demonstrate our key results. **Keywords**: generalization ability, generalization error upper bound, GEM estimator, penalized regression, model selection, cross-validation, bias-variance trade-off, $\mathcal{L}_2$-consistency of penalized regression, lasso, external validity, high-dimensional data. author: - | Ning Xu\ School of Economics, University of Sydney\ mariamendoza@example.org - | Jian Hong\ School of Economics, University of Sydney\ mariamendoza@example.org - | Timothy C.G. Fisher\ School of Economics, University of Sydney\ mariamendoza@example.org bibliography: - 'LASSOrefs2.bib' title: 'Generalization error minimization: a new approach to model evaluation and selection with an application to penalized regression[^1]' --- Introduction ============ Traditionally in econometrics, a statistical inference about a population is formed using a model imposed and estimated on a sample. Put another way, the goal of inference is to see whether a model estimated on a sample may be generalized to the population. Deciding whether the estimated model is valid for generalization is referred to as the process of model evaluation. The performance of a model is usually evaluated using the sample data at hand, referred to as the 'internal validity' of the model. However, internal validity may not be a useful indicator of model performance in many different scenarios. A perspective of increasing interest in applied econometrics considers the performance of a model on out-of-sample data. In this paper, we focus on the ability of a model estimated from a given sample to fit new samples, referred to as the **generalization ability** (GA) of the model. Generalization ability is one aspect of **external validity**, the extent to which the results from a study generalize to other settings. Researchers evaluating pilot programs and randomized trials in a variety of settings from labour economics to development economics are increasingly focused on the external validity of their findings.[^2] For instance, @heckman2007econometric, @ludwig2011mechanism and @allcott2012external discuss the importance of externally valid results in policy and program evaluation. In a similar vein, @guala2005experiments and @list2011economists emphasize the importance of external validity in determining whether experiments can offer a robust explanation of causes and effects in the field. While external validity encompasses many issues from experimental design, sample selection, and economic theory, it clearly also raises econometric issues around model estimation and evaluation. In order to explore the properties of estimators from the perspective of GA, three questions need to be addressed. How do we measure GA? Given a useful measure, what are its properties? Given its properties, how can GA be exploited for estimation? These questions have received only tangential interest in the literature. @roe2009internal discuss the trade-off between internal and external validity in empirical data, pointing out that while internal validity (or in-sample fit) is well studied, there is much less research on how to control external validity (out-of-sample fit). Some work on external validity has focussed on the properties of specific estimation methods. @angrist2010extrapolate, for example, studies the external validity of instrument variable estimation in a labor market setting. In this paper, we answer these questions, starting by proposing a measure of GA that is straightforward to implement empirically. With a new sample at hand, GA is easily measured by using validation or cross-validation to quantify the goodness-of-fit of the estimated model on new (out-of-sample) data. Without a new sample, however, it can be difficult to measure GA *ex ante*. In this paper, when only a single sample is available, we quantify the GA of the in-sample estimates by deriving upper bounds on the empirical out-of-sample errors, which we call the **empirical generalization errors** (eGE). The upper bounds reveal the properties of the eGE as well as insight into other important statistical properties, such as the trade-off between in-sample and out-of-sample fit in estimation. Furthermore, the upper bounds can be extended to analyze the performance of validation, $K$-fold cross-validation and specific estimators such as penalized regression. Thus, the GA approach yields insight into the finite-sample and asymptotic properties of model estimation and evaluation from several different perspectives. Essentially, GA measures the performance of a model from an external point-of-view: the greater the GA of an estimator, the better its predictions on out-of-sample data. Furthermore, we show that GA also serves as a natural criterion for model selection, throwing new light on the model selection process. We propose the criterion of minimizing eGE (maximizing GA), or **generalization error minimization** (**GEM**), as a framework for model selection. Using penalized regression as an example of a specific model selection scenario, we show how the traditional bias-variance trade-off is connected to GEM and to the trade-off between in-sample and out-of-sample fit. Moreover, the GEM framework allows us to establish additional properties for penalized regression implicit in the bias-variance trade-off. Approaches to model selection ----------------------------- Given the increasing prevalence of high-dimensional data in economics, model selection is coming to the forefront in empirical work. Researchers often desire a smaller set of predictors in order to gain insight into the most relevant relationships between outcomes and covariates. Without explicitly introducing the concept of GA, the classical approach to model selection focusses on the bias-variance trade-off, yielding methods such as the information criteria (IC), cross-validation, and penalized regression. Consider the standard linear regression model $$Y = X \beta + u$$ where $Y\in\mathbb{R}^{n}$ is a vector of outcome variables, $X\in\mathbb{R}^{n\times p}$ is a matrix of covariates and $u\in\mathbb{R}^{n}$ is a vector of i.i.d. random errors. The parameter vector $\beta\in\mathbb{R}^{p}$ may be sparse in the sense that many of its elements are zero. Model selection typically involves using a score or penalty function that depends on the data [@heckerman95], such as the Akaike information criterion [@akaike73], Bayesian information criterion [@schwarz78], cross-validation errors [@stone74; @stone77] or the mutual information score among variables [@friedman97; @friedman00]. An alternative approach to model selection is penalized regression, implemented through the objective function: $$\underset{b_{\lambda}}{\min}~~ \frac{1}{n} \left(\left\Vert Y - Xb_{\lambda}\right\Vert _{2}\right)^{2} + \lambda\Vert b_{\lambda}\Vert_{\gamma} \label{penreg}$$ where $\Vert\cdot\Vert_{\gamma}$ is the $\mathcal{L}_{\gamma}$-norm and $\lambda\geqslant0$ is a penalty parameter. Note in eq. (\[penreg\]) that if $\lambda=0$, the OLS estimator is obtained. The IC can be viewed as special cases with $\lambda=1$ and $\gamma=0$. The lasso [@tibshirani96] corresponds to the case with $\gamma=1$ (an $\mathcal{L}_{1}$ penalty). When $\gamma=2$ (an $\mathcal{L}_{2}$ penalty), we have the ridge estimator [@hoerlkennard70]. For any $\gamma>1$, we have the bridge estimator [@frankfriedman93], proposed as a generalization of the ridge. One way to derive the penalized regression estimates $b_{\lambda}$ is using the **cross-validation** approach, summarized in Algorithm 1. As shown in Algorithm 1, cross-validation solves the constrained minimization problem in eq. (\[penreg\]) for each value of the penalty parameter $\lambda$ to derive a $b_{\lambda}$. When the feasible range of $\lambda$ is exhausted, the estimate that produces the smallest out-of-sample error among all the estimated $\{b_{\lambda}\}$ is chosen to be the penalized regression estimate, $b^*$. ---- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. Set the penalty parameter $\lambda = 0$. 2. Partition the sample into a training set $T$ and a test set $S$. Standardize all variables (to ensure the penalized regression residual $e$ satisfies $\mathbb{E}(e)=0$ in $T$ and $S$). 3. Compute the penalized regression estimate $b_{\lambda}$ on $T$. Use $b_{\lambda}$ to calculate the prediction error on $S$. 4. Increase the penalty parameter $\lambda$ by a preset step size. Repeat 2 and 3 until $b_{\lambda} = \mathbf{0}$. 5. Select $b^*$ to be the $b_{\lambda}$ that minimizes the prediction error on $S$. ---- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ : Algorithm 1: Penalized regression estimation under cross-validation A range of consistency properties have been established for the IC and penalized regression. @shao97 proves that various IC and cross-validation are consistent in model selection. @breiman95 [@chickering04] show that the IC have drawbacks: they tend to select more variables than necessary and are sensitive to small changes in the data. @zhanghuang08 [@knightfu00; @meinshausenbuhlmann06; @zhaoyu06] show that $\mathcal{L}_1$-penalized regression is consistent in different settings. @huangall08 [@hoerlkennard70] show the consistency of penalized regression with $\gamma > 1$. @zou06 [@caner09; @friedman10] propose variants of penalized regression in different scenarios and @fu98 compares different penalized regressions using a simulation study. Alternative approaches to model selection, such as combinatorial search algorithms may be computationally challenging to implement, especially with high-dimensional data.[^3] Major results and contribution ------------------------------ A central idea in this paper is that model evaluation and model selection may be re-framed from the perspective of GA. If the objective is to improve the GA of a model, model selection is necessary. Conversely, GA provides a new and elegant angle to understand model selection. By introducing generalization errors as the measure of GA, we connect GEM to the traditional bias-variance trade-off, the trade-off between in-sample and out-of-sample fit and the properties of validation and cross-validation. By the same token, the concept of GA may be used to derive additional theoretical properties of model selection. Specifically for the case of regression analysis, we use GEM to unify the properties for the class of penalized regressions with $\gamma \geqslant 0$, and show that the finite-sample and asymptotic properties of penalized regression are closely related to GA. The **first contribution** of this paper is to quantify the GA of a model, *ex ante*, by deriving an upper bound for the GE. The upper bounds depend on the sample size, an index of the complexity of models, a loss function, and the distribution of the underlying population. The upper bound also characterizes the trade-off between in-sample fit and out-of-sample fit. As shown in @vc71 [@vc71b; @shalizi2011; @smale2009; @hu2009], the inequalities underlying conventional analysis of GA focus on the relation between the population error and the empirical in-sample error. Conventional methods to improve GA involve computing discrete measures of model complexity, such as the VC dimension, Radamacher dimension or Gaussian complexity, which typically are hard to compute. In contrast, for any out-of-sample data, we quantify bounds for the prediction error of the extremum estimate learned from in-sample data. Furthermore, we show that empirical GA analysis is straightforward to implement via validation or cross-validation and possesses desirable finite-sample and asymptotic properties for model selection. A **second contribution** of the paper is to propose GEM as a general framework for model selection and estimation. By re-framing the bias-variance trade-off from the perspective of in-sample and out-of-sample fit, GA is connected to the traditional bias-variance trade-off and model selection. To be specific: model selection is necessary to improve the GA of an estimated model while GA naturally serves as an elegant way to understand the properties of model selection. Thus, a model estimated by GEM will not only achieve the highest GA—and thus some degree of external validity—but also possess a number of nice theoretical properties. GEM is also naturally connected to the properties of cross-validation. As argued by @varian14, cross-validation could be adopted more often in empirical analysis in economics, especially as big data sets are becoming increasingly available in many fields. A **third contribution** of the paper is to use GA analysis to unify a class of penalized regression estimators and derive their finite-sample and asymptotic properties (including $\mathcal{L}_{2}$-consistency) under the same set of assumptions. Various properties of penalized regression estimators have previously been established, such as probabilistic consistency or the oracle property [@knightfu00; @zhaoyu06; @candestao07; @meinshausenyu09; @bickeletal09]. GA analysis reveals that similar properties can be established more generally and for a wider class of penalized regression estimators. We also show that the $\mathcal{L}_{2}$-difference between the OLS estimate and any penalized regression estimate depends on their respective GAs. Lastly, a **fourth contribution** of the paper is to show that GA analysis may be used to tune the hyper-parameter for validation (i.e., the ratio of training sample size to test sample size) or cross-validation (i.e., the number of folds $K$). Existing research has studied cross-validation for the estimation of specific parametric and nonparametric models [@hall1991; @hall2011; @stone74; @stone77]. In contrast, by adapting the classical error bound inequalities that follow from our analysis of GA, we derive the optimal tuning parameters for validation and cross-validation in a model-free setting. We also show how $K$ affects the bias-variance trade-off for cross-validation: a higher $K$ increases the variance and lowers the bias. The paper is organized as follows. In Section 2, we propose empirical generalization errors as the measure of GA and the criterion to evaluate the external performance of the estimated model. Also, by deriving the upper bounds for the empirical generalization errors in different scenarios, we reveal important features of the extremum estimator such as the trade-off between in-sample and out-of-sample fit. Our approach also offers a framework to study the properties of validation and cross-validation. In Section 3, we apply the GEM framework as a model selection criterion for penalized regression. We also demonstrate a number of new properties for penalized regression that flow from the GEM framework. We prove the $\mathcal{L}_{2}$-consistency of penalized regression estimators for both $p\leqslant n$ and $p>n$ cases. Further, we establish the finite-sample upper bound for the $\mathcal{L}_{2}$-difference between penalized and unpenalized estimators based on their respective GAs. In Section 4, we use simulations to demonstrate the ability of penalized regression to control for overfitting. We also propose a measure of overfitting based on the empirical generalization errors, called the generalized $R^2$ or $GR^{2}$. Section 5 concludes with a brief discussion of our results. Proofs (showing detailed steps) are contained in Appendix A and summary plots of the simulations are in Appendix B. Generalization ability and the upper bound for the finite-sample generalization error ===================================================================================== In this section, we propose the eGE, the measurement of GA for a model, as a new angle to evaluate the 'goodness' of a model. By deriving the upper bounds of eGE of the extremum estimator, we show that the upper bounds of eGE directly quantifies how much the model overfits or underfits the finite samples, also the upper bounds of eGE may be used to study the properties of eGE for a model. Furthermore, these upper bounds can be used to study the properties of cross validation and validation on finite samples. All those result implies that eGE is a convenient and useful criterion for model evaluation. Generalization ability, generalization error and overfitting ------------------------------------------------------------ In econometrics, choosing the best approximation to data often involves measuring a loss function, $Q(b\vert y_i,\mathbf{x}_i)$, defined as a functional that depends on some estimate $b$ and the sample points $(y_i,\mathbf{x}_i)$. The population error (or risk) functional is defined as $$\mathcal{R}(b\vert Y,X)=\int Q(b\vert y,\mathbf{x})\mathrm{d}F(y,\mathbf{x})$$ where $F(y,\mathbf{x})$ is the joint distribution of $y$ and $\mathbf{x}$. Without knowing the distribution $F(y,\mathbf{x})$ a priori, given a random sample $(Y,X)$, we define the empirical error functional as follows $$\mathcal{R}_{n}(b\vert Y,X) = \frac{1}{n}\;\sum_{i=1}^n\;Q(b\vert y_i,\mathbf{x}_i).$$ For example, in the regression case, $b$ is the estimated parameter vector and $\mathcal{R}_{n}(b\vert Y,X)=\frac{1}{n}\sum_{i=1}^n(y_i - \mathbf{x}_i^T b)^{2}$. When estimation involves minimizing the in-sample empirical error, we have the extremum estimator [@amemiya1985advanced]. In many settings, however, minimizing the in-sample empirical error does not guarantee a reliable model. In regression, for example, often the $R^2$ is used to measure goodness-of-fit for the in-sample data. However, an estimate with a high in-sample $R^{2}$ may fit out-of-sample data poorly, a feature commonly referred to as **overfitting**: the in-sample estimate is too tailored for the sample data, compromising its out-of-sample performance.[^4] As a result, in-sample fit (internal validity) of the model may not be a reliable indicator of the general applicability (external validity) of the model. Thus, @vc71 refer to the **generalization ability** (GA) of a model: a measure of how an extremum estimator performs on out-of-sample data. GA can be measured several different ways. In the case where $Y$ and $X$ are directly observed, GA is a function of the difference between the actual and predicted $Y$ for out-of-sample data. In this paper, GA is measured by the out-of-sample empirical error functional. \[Training set, test set, empirical training error and empirical generalization error\] \[defn2.1\] 1. Let $(y_i, \mathbf{x}_i)$ denote a sample point from $F(y, \mathbf{x})$, the joint distribution of $(y,\mathbf{x})$. Let $\Lambda$ denote the space of all models. The **loss function** for $b\in\Lambda$ is $Q(b\vert y_i,\mathbf{x}_i),\,i=1,\ldots,n$. The **population error functional** for $b\in\Lambda$ is $\mathcal{R}(b\vert Y,X)=\int Q(b\vert y,\mathbf{x})\mathrm{d}F(y,\mathbf{x})$. The **empirical error functional** is $\mathcal{R}_{n}(b\vert Y,X) =\frac{1}{n}\;\sum_{i=1}^n\;Q(b\vert y_i,\mathbf{x}_i)$. 2. Given a sample $(Y,X)$, the **training set** $(Y_{t},\,X_{t})\in\mathbb{R}^{n_t \times p}$ refers to data used to estimate $b$ (i.e., the in-sample data) and the **test set** $(Y_{s},\,X_{s})\in\mathbb{R}^{n_s \times p}$ refers to data *not* used to estimate $b$ (i.e., the out-of-sample data). Let $\widetilde{n}=\min\{n_s,n_t\}$. The **effective sample size** for the training set, test set and the total sample, respectively, is $n_t/p$, $n_s/p$ and $n/p$. 3. Let $b_{train}\in\Lambda$ denote an extremum estimator, where $b_{train}$ minimizes $\mathcal{R}_{n_t}(b|Y_{t},X_{t})$. Under **validation**, the **empirical training error (eTE)** for $b_{train}$ is $\mathcal{R}_{n_t}(b_{train}|Y_{t},X_{t})$, the **empirical generalization error (eGE)** is $\mathcal{R}_{n_s}(b_{train}|Y_{s},X_{s})$ and the **population error** is $\mathcal{R}(b_{train}|Y,X)$. 4. For $K$**-fold cross-validation**, denote the training set and test set in the $q$th round, respectively, as $(Y_{t}^q,X_{t}^q)$ and $(Y_s^q,X_s^q)$. In each round, the sample size for the training set is $n_t = n(K-1)/K$ and the sample size for the test set is $n_s = n/K$. Thus, $\mathcal{R}_{n_s}(b_{train}|Y_{s}^q,X_{s}^q)$ is the eGE and $\mathcal{R}_{n_t}(b_{train}|Y_{t}^q,X_{t}^q)$ is the eTE, respectively, in the $q$th round of cross-validation. Two methods are typically used to compute the eGE of an estimate: validation and cross-validation. Under the validation approach, the sample is randomly divided into a training set and a test set. Following estimation on the training set, the fitted model is applied to the test set to compute the validated eGE. $K$-fold cross-validation may be thought of as 'multiple-round validation'. Under the cross-validation approach, the sample is randomly divided into $K$ subsamples or folds.[^5] One fold is chosen to be the test set and the remaining $K-1$ folds comprise the training set. Following estimation on the training set, the fitted model is applied to the test set to compute the eGE. The process is repeated $K$ times, with each of the $K$ folds in turn taking the role of the test set while the remaining $K-1$ folds are used as the training set. In this way, $K$ different estimates of the eGE for the fitted model are obtained. The average of the $K$ eGEs yields the cross-validated eGE. Cross-validation uses each data point in both the training and test sets. The method also reduces resampling error by running the validation $K$ times over different training and test sets. Intuitively this suggests that cross-validation is more robust to resampling error and on average will perform at least as well as validation. In Section 3, we study the generalization ability of penalized extremum estimators in both the validation and cross-validation cases. To study the properties of eGE for a model, three assumptions are required for the analysis in this section of the paper, stated as follows. **Assumptions** 1. In the probability space $(\Omega,\mathcal{F},P)$, we assume $\mathcal{F}$-measurability of the loss function $Q(b\vert y, \mathbf{x})$, the population error $\mathcal{R}(b|Y,X)$ and the empirical error $\mathcal{R}_{n}(b\vert Y,X)$, for any $b\in\Lambda$ and any sample point $(y_i, \mathbf{x}_i)$. Distributions of loss functions have closed-form, first-order moments. 2. The sample $\{(y_i, \mathbf{x}_i)\}_{i=1}^n$ is randomly drawn from the population. In cases with multiple random samples, both the training set and the test set are randomly sampled from the population. In cases with a single random sample, both the training set and the test set are randomly partitioned from the sample. 3. For any sample, the extremum estimator $b_{train}\in\Lambda$ exists. The in-sample error for $b_{train}$ converges in probability to the minimal population error as $n\rightarrow\infty$. A few comments are in order for assumptions A1–A3. The loss distribution assumption A1 is made to simplify the analysis. The existence and convergence assumption A3 is standard (see, for example, @neweymcfadden94). The independence assumption A2 is not essential; GA analysis is valid for both i.i.d. and non-i.i.d. data. While the original research on GA in @vc74 [@vc74b] imposes the i.i.d. restriction, subsequent work has generalized their results to cases where the data are dependent or not identically distributed.[^6] Others have shown that if heterogeneity is due to an observed random variable,[^7] the variable may be added to the model to control for the heterogeneity, while if the heterogeneity is related to a latent variable, various approaches—such as the hidden Markov model, mixture modelling or factor modelling—are available for heterogeneity control. In this paper, due to the different measure-theory setting for dependent data, we focus on the independent case as a first step. Given A1–A3, both the eTE and eGE converge to the population error: $$\mathrm{lim}_{\widetilde{n}\rightarrow\infty}\mathcal{R}_{n_t}(b_{train}|Y_{t},X_{t}) = \mathrm{lim}_{\widetilde{n}\rightarrow\infty}\mathcal{R}_{n_s}(b_{train}|Y_{s},X_{s}) = \mathcal{R}(b_{train}|Y,X).$$ The upper bound of the empirical generalization error ----------------------------------------------------- The problem of GA and overfitting is discovered many years ago. Originally, to improve the generalization ability of a model, @vc71 [@vc71b] propose minimizing the upper bound of the population error of the estimator $\mathcal{R}(b|Y,X)$ as opposed to minimizing the eTE. The balance between in-sample fit and out-of-sample fit is formulated by @vc74b using the Glivenko-Cantelli theorem and Donsker's theorem for empirical processes. Specifically, the so-called **VC inequality** [@vc74b] summarizes the relationship between $\mathcal{R}(b|Y,X)$ and $\mathcal{R}_{n_t}(b|Y,X)$. \[VC inequality: the upper bound for the population error\] Under A1–A3, the following inequality holds with probability at least $1-\eta$, $\forall b_{train} \in\Lambda$, and $\forall n\in\mathbb{N}^{+}$, $$\mathcal{R}(b_{train}|Y,X) \leqslant\mathcal{R}_{n_t}(b_{train}|Y_{t},X_{t}) +\frac{\sqrt{\epsilon}}{1-\sqrt{\epsilon}}\;\mathcal{R}_{n_t}(b_{train}|Y_{t},X_{t}) \label{eq:lem2.1}$$ where $\mathcal{R}(b_{train}|Y,X)$ is the population error, $\mathcal{R}_{n_t}(b_{train}|Y_t,X_t)$ is the empirical training error, $\epsilon=(1/n_t)[h\ln(n_t/h)+h-\ln\left(\eta\right)]$, and $h$ is the **VC dimension**. \[lem2.1\] The VC dimension $h$ is a more general measure of the geometric complexity of a model than the number of parameters, $p$, which does not readily extend as a measure of complexity in nonlinear or non-nested models. While $h$ reduces to $p$ directly for generalized linear models, $h$ can also be used to order the complexity of nonlinear or non-nested models.[^8] Thus, eq. (\[eq:lem2.1\]) can be used as a tool for linear, nonlinear and non-nested model selection. While Lemma \[lem2.1\] is established under A2, eq. (\[eq:lem2.1\]) can be generalized to non-i.i.d. cases. @shalizi2011 generalizes the VC inequality for $\alpha$- and $\beta$-mixing stationery time series while @smale2009 generalizes the VC inequality for panel data. Moreover, a number of papers [@yashin1986; @skrondal2004generalized; @wang2005learning; @yu2009learning; @pearl2015detecting] show that heterogeneity can be controlled in the context of the VC inequality by implementing the latent variable model or by adding the variable causing heterogeneity into the model. The VC inequality provides an upper bound for the population error based on the eTE and the VC dimension of the model. As shown in Figure \[fig:VCineq\], when the VC dimension is low (i.e., the model is simple), the effective sample size ($n_t/h$) of the training set is large, $\epsilon$ is small, the second term on the RHS of (\[eq:lem2.1\]) is small, and the eTE is close to the population error. In this case the extremum estimator has a good GA. However, when the VC dimension is high (i.e., the model is very complicated), the effective sample size $n_t/h$ is small, the second term on the RHS of (\[eq:lem2.1\]) becomes larger. In such situations, a small eTE does not guarantee a good GA, and overfitting is more likely. @vc71 show that minimizing the RHS of eq. (\[eq:lem2.1\]) reduces overfitting and improves the GA of the extremum estimator. However, this can be hard to implement because the VC dimension is hard to calculate for anything other than linear models.[^9] Also, VC inequality is for population. But in practice population is often not accessible and the data we collect is always finite, moreover we are often interesting in how a estimated model would perform on finite out-of-sample data, such as "how well the effect of a policy, estimated from a sample from suburb A, would explain the variation in suburb B, given relevant heterogeneity controlled. " Hence, as a handy and intuitive measurement for GA or overfitting in empirical study, eGE has been proposed and widely used in applications. As a reasonable criterion for model evaluation, we would expect that eGE should demonstrate a number of nice properties that characterize its pattern or regularity as an empirical process. For example, intuitively if we get an estimated model from the training set and apply it to many test sets with same size, we would expect that value of different eGEs could be as stable as possible despite of the sampling error; also, if we calculate the eGE of a model on test sets with different sizes, we would expect that value of eGEs should be influenced by the size of training set, the size of test set and the tail behavior of the error distribution. However, due to the procedure of sampling from population and subsampling by validation/cross validation, the randomness of eGE as a empirical process increase the difficulty to derive those properties. To reduce and absorb the influence of sampling and subsampling, one approach is to derive an upper bound for eGE,[^10] which is somehow similar to what eq. (\[eq:lem2.1\]) does to population error, Thus, we now describe the finite-sample relation between the eGE and the eTE in validation, by adapting eq. (\[eq:lem2.1\]). \[The upper bound for the eGE of the extremum estimator under validation\] Under A1–A3 and given an extremum estimator $b_{train} \in \Lambda$, the following upper bound for the eGE holds with probability at least $\varpi(1-1/n_t)$, $\forall\varpi\in\left(0,1\right)$. $$\mathcal{R}_{n_s}(b_{train}|Y_{s},X_{s}) \leqslant \frac{\mathcal{R}_{n_t}(b_{train}|Y_{t},X_{t})}{(1-\sqrt{\epsilon})} + \varsigma, \label{eq:thm2.1}$$ where $\mathcal{R}_{n_s}(b_{train}|Y_{s},X_{s})$ is the eGE and $\mathcal{R}_{n_t}(b_{train}|Y_t,X_t)$ the eTE, $\epsilon$ is defined in Lemma \[lem2.1\], $\varsigma = B\:\ln\sqrt{2/(1-\varpi)}/n_s$ if $Q(\cdot) \in(0,B]$ and $B$ is bounded, and otherwise $$\varsigma = \left\{ \begin{array}{ll} \mathrm{var}[Q(b_{train}\vert y, \mathbf{x})] / (n_s (1 - \varpi)) & \mbox{if } \nu\in(2,\infty) \\[12pt] \sqrt[\nu]{2} \tau \left(\mathbb{E}\left[Q(b_{train}|Y_{s},X_{s})\right]\right)/ (n_s^{1-1/{\nu}}\sqrt[\nu]{1-\varpi}) & \mbox{if } \nu\in(1,2] \end{array} \right.$$ where $$\tau \geqslant \sup \frac{[\int\left(Q(b|y,\mathbf{x})\right)^{\nu} \mathrm{d}F(y,\mathbf{x})]^{1/{\nu}}} {\int Q(b|y,\mathbf{x}) \mathrm{d}F(y,\mathbf{x})}.$$ \[thm2.1\] Eq. (\[eq:thm2.1\]) provides an upper bound for the eGE of the test set as it depends on the eTE of the model with a given $h$ estimated on the training set. Thus, eq. (\[eq:thm2.1\]) shows how the eTE from extremum estimation on the training set may be used to compute the eGE of the model on the test set. In other words, eq. (\[eq:thm2.1\]) measures the GA of a model of a given complexity under the validation approach. Theorem \[thm2.1\] has several important implications. 1. *Upper bound of the eGE.* Eq. (\[eq:thm2.1\]) establishes the upper bound of the eGE for any out-of-sample data of size $n_s$ based on the eTE from any in-sample data of size $n_t$. Thus, eq. (\[eq:thm2.1\]) quantifies the upper bound of the eGE, as opposed to Lemma \[lem2.1\], which quantifies the upper bound of the population error. Previously, measuring the eGE of a model with new data required the use of validation or cross-validation. Given Theorem \[thm2.1\], the eGE may be quantified directly using the RHS of eq. (\[eq:thm2.1\]), avoiding the need for validation. 2. *The trade-off between accuracy and looseness of the upper bound.* Theorem (\[thm2.1\]) also shows that $\varpi \in \left[ 0,1 \right]$ influences the trade-off between the accuracy and efficiency of the upper bound. The higher $\varpi$, the more likely the upper bound holds and the larger $\varsigma$. Thus, while the probability the bound holds increases, it comes at the cost of a looser upper bound. In contrast, a lower $\varpi$ reduces the upper bound, offering a empirically efficient upper bound at the cost of reducing the probability that it holds. 3. *The eGE-eTE trade-off in model selection.* Eq. (\[eq:thm2.1\]) also characterizes the trade-off between eGE and eTE for model selection in both the finite-sample and asymptotic cases. The population GE and the population TE converge to the population error. Hence, minimizing eTE can lead directly to the true DGP in the population. By contrast, for the finite-sample case illustrated in Figure \[fig:TEGE\], while an overcomplicated model (a low $n_t/h$) will have a small eTE, eq. (\[eq:thm2.1\]) shows it may result in a large eGE on new data. Thus, an overcomplicated model will tend to *overfit* the in-sample data and have poor GA. On the other hand, an oversimplified model (a high $n_t/h$) will be unlikely to recover the true DGP leading to a large upper bound for the eGE. Thus, an oversimplified model will tend to *underfit*, fitting both the in-sample and out-of-sample data poorly. Thus, the complexity of a model is related to a trade-off between the eTE and eGE. 4. *GA and tails of the loss function distribution.* Eq. (\[eq:thm2.1\]) also shows how the tail of the loss function distribution affects the upper bound of the eGE through $\varsigma$, the second term on the RHS of eq. (\[eq:thm2.1\]). If $Q(\cdot)$ is bounded or light-tailed, $\varsigma$ is mathematically simple and converges to zero at the rate $1/n_s$. If the loss function is heavy-tailed and $\mathcal{F}$-measurable, $\nu$, the highest order of the population moment that is closed-form for the loss distribution,[^11] can be used to measure the heaviness of the loss distribution tail, a smaller $\nu$ implying a heavier tail. In the case of a heavy tail, $\varsigma$ is mathematically complicated and its convergence rate decreases to $1/n_{s}^{1-1/\nu}$. Hence, the heavier the tail of the loss distribution, the higher the upper bound of the eGE and the harder it is to control GA in finite samples. In the extreme case with $\nu = 1$, there is no way to adapt eq. (\[eq:thm2.1\]). Our next step is to establish a similar bound to eq. (\[eq:thm2.1\]) for $K$-fold cross-validation. Given that $K$-fold cross-validation is simply the multiple-round validation, a similar bound to eq. (\[eq:thm2.1\]) can be established for cross-validation by convolution. For convenience, define the empirical process $$T_q = \mathcal{R}_{n_s}(b_{train}|Y_{s}^q,X_{s}^q) - \frac{\mathcal{R}_{n_t}(b_{train}|Y_{t}^q,X_{t}^q)} {1-\sqrt{\epsilon}},\quad \forall q \in \left[1,K\right]$$ as the **eGE gap** in the $q$th round of cross-validation. \[The upper bound for the eGE of the extremum estimator for cross-validation\] Under A1–A3, given an extremum estimator $b_{train} \in \Lambda$ and given $T_q$, then (i) : if $\: \mathbb{E}(\vert T_q \vert^m) \leqslant m!B^{m-2}\mathrm{var}(T_q)/2,\;\forall m \geqslant 2$, the following upper bound for the eGE gap holds with probability at least $\alpha$ $$\begin{aligned} \frac{1}{K}\sum_{q=1}^{K} \mathcal{R}_{n_s}(b_{train}|Y_{s}^q,X_{s}^q) \leqslant \frac{\frac{1}{K}\sum_{q=1}^{K}\mathcal{R}_{n_t}(b_{train}|Y_{t}^q,X_{t}^q)} {1-\sqrt{\epsilon}} + \varsigma, \label{eq1:thm2.2} \end{aligned}$$ where $$\begin{aligned} \alpha & = & 1 - 2\exp\left\{-\frac{1}{2} \frac{(\varsigma - \mathbb{E}[T_q])^2} {\mathrm{var}(T_q)/K + B(\varsigma - \mathbb{E}[T_q])/(3K)}\right\}, \notag \\ \varsigma & = & \frac{\mathrm{var}[Q(b_{train}\vert y,\mathbf{x})]} {(1-\varpi)n/K}, \notag \end{aligned}$$ (ii) : if $T_q$ is heavy-tailed and sub-exponential, the following upper bound for the eGE holds with probability at least $\alpha$ $$\begin{aligned} \frac{1}{K}\sum_{q=1}^{K} \mathcal{R}_{n_s}(b_{train}|Y_{s}^q,X_{s}^q) \leqslant \frac{\frac{1}{K}\sum_{q=1}^{K}\mathcal{R}_{n_t}(b_{train}|Y_{t}^q,X_{t}^q)} {1-\sqrt{\epsilon}} + \varsigma, \label{eq2:thm2.2} \end{aligned}$$ where $$\begin{aligned} \varsigma & = & \sqrt[\nu]{2} \tau \frac{\mathbb{E}\left[Q(b_{train}|Y_{s},X_{s})\right]} {\sqrt[\nu]{1-\varpi}\; (n/K)^{1-1/{\nu}}}, \notag \\ \alpha & = & \left(1 - 2\tau^\nu\cdot \frac{\left(\mathbb{E}\left[Q(b_{train}\vert y,\mathbf{x})\right]\right)^\nu} {\varsigma^\nu\cdot n^{\nu}}-K/n_t \right)^+, \notag \end{aligned}$$ $\mathcal{R}_{n_s}(b_{train}|Y_{s}^q,X_{s}^q)$ is the eGE and $\mathcal{R}_{n_t}(b_{train}|Y_{t}^q,X_{t}^q)$ is the eTE, respectively, in the qth round of cross-validation. \[thm2.2\] Theorem \[thm2.2\] provides an upper bound for the average eGE from $K$ rounds of cross-validation. Generally speaking, the errors generated from cross-validation are affected both by sampling randomness (from the population) and by sub-sampling randomness that arises from partitioning the sample into folds. Thus, the errors from cross-validation are potentially more volatile than the usual errors from estimation. Eqs. (\[eq1:thm2.2\]) and (\[eq2:thm2.2\]) offers a way to characterize the property of eGE despite of the effect of sub-sampling randomness. The implications of eqs. (\[eq1:thm2.2\]) and (\[eq2:thm2.2\]) are as follows. 1. *Upper bound of the eGE.* Similar to eq. (\[eq:thm2.1\]), eq. (\[eq1:thm2.2\]) and (\[eq2:thm2.2\]) serve as the upper bound of the cross-validated eGE. Both equations reveal the trade-off between eTE and eGE and the influence of the tails of the loss distribution. In convolution, the tails dramatically affect the upper bound of the eGE. If $T_q$ is light-tailed, $\alpha$ converges to $1$ exponentially when $n \rightarrow \infty$. When $T_q$ is sub-exponential, the convolution is more complicated and it is hard to approximate the probability. However, with sufficiently large $n$, Theorem \[thm2.2\] shows that we can approximate the convoluted probability. 2. *The trade-off between accuracy and looseness of the upper bound.* Similar to eq. (\[eq:thm2.1\]), in both eq. (\[eq1:thm2.2\]) and (\[eq2:thm2.2\]) we need to consider the trade-off between between $\alpha$ and $\varsigma$ (or $\varpi$ as in Theorem \[thm2.1\]), i.e., the trade-off between efficiency and accuracy. Similar to Theorem \[thm2.1\], ceteris paribus, a larger $\varsigma$ in each round of cross-validation increases $\varpi$ and $\alpha$. Thus, in each round, the upper bound moves upwards and the probability the upper bound holds increases, implying that both increase overall under cross-validation. While the probability the bound holds increases, it comes at the cost of a looser bound. 3. *Cross-validation hyperparameter $K$.* Eqs. (\[eq1:thm2.2\]) and (\[eq2:thm2.2\]) characterize how $K$ affects the average eGE from cross-validation (also called the cross-validation error in the literature). With a given sample and fixed $K$, sub-sampling randomness will produce a different average eGE each time cross-validation is performed. From Definition \[defn2.1\], $n_t = n(K-1)/K$ and $n_s = n/K$, so the sizes of the training and test sets change with $K$. As $K$ increases the *test sets* become smaller, increasing the influence of sub-sampling randomness on the eGE. On the other hand, as $K$ decreases the *training sets* become smaller, increasing the influence of sub-sampling randomness on eTE. The two effects complicate analysis of the effect of $K$ on trade-off between eTE and eGE under cross-validation. Thus, to characterize the influence of sub-sampling randomness, we establish the trade-off for cross-validation by a bound, after running cross-validation many times.[^12] Figure \[fig:Ktradeoff\] illustrates the effect of $K$. - *Small $K$.* For low values of $K$, $n_t$ is low in each round of in-sample estimation and the eTE in each round $q$, $\mathcal{R}_{n_t}(b_{train}|Y_{t}^q,X_{t}^q)/(1-\sqrt{\epsilon})$, is more biased away from the population error, as shown in Figure \[fig:Ktradeoff1\]. Also for small $K$, the $K$-round average eTE (the first term on the RHS of eqs. (\[eq1:thm2.2\]) and (\[eq2:thm2.2\])), is more biased away from the true population error, as shown in Figure \[fig:Ktradeoff2\]. As a result, the RHS of eqs. (\[eq1:thm2.2\]) and (\[eq2:thm2.2\]) suffer more from finite-sample bias for low values of $K$. However, since a small $K$ implies $n_s$ is relatively large, more data is used for eGE calculation in each round, in each round the eGE on the test set should be less volatile. Thus, the $K$-round averaged eGE for cross-validation is relatively less volatile, reflecting the fact that $\varsigma$ is not very large in eqs. (\[eq1:thm2.2\]) and (\[eq2:thm2.2\]). - *Large $K$.* For high values of $K$, $n_s$ is low. Given a small test set size, the eGE in each round may be hard to bound from above, the averaged eGE from $K$ rounds will be more volatile and $\varsigma$ will increase. However, with a high $K$, the first term on the RHS of eqs. (\[eq1:thm2.2\]) and (\[eq2:thm2.2\]) tends to be closer to the true population error and the averaged eGE suffers less from bias. In summary, Figure \[fig:Ktradeoff2\] shows that as the value of $K$ increases, the averaged eGE from cross-validation follows a typical bias-variance trade-off. For low values of $K$, the average eGE is less volatile but more biased away from the population error. As $K$ increases, the averaged eGE becomes more volatile but less biased away from the population error. Theorem \[thm2.2\] confirms the exhaustive simulation study results from @kohavi1995study. As a side benefit, Theorem \[thm2.2\] also suggests that an optimal number of folds $K$ may exist for each sample when the cross-validation approach is used with extremum estimation, as in the $K^*$ shown in Figure \[fig:Ktradeoff2\]. More specifically, the $K$ that minimizes the upper bound (\[eq1:thm2.2\]) and (\[eq2:thm2.2\]) also maximizes the GA from cross-validation. We leave to the next section discussion on the optimal $K$ for regression. Theorems \[thm2.1\] and \[thm2.2\] establish upper bounds for the eGE of the extremum estimator given any size random sample, which reveals a method to analyze the prorperty of eGE for the extremum estimators. Potentially, if we take eGE as the criterion for model selection, Theorems \[thm2.1\] and \[thm2.2\] may be used to evaluate the performance of model selection under validation and cross-validation. Hence it would be natural to select the model with minimal eGE in the space of alternative models Generalization error minimization --------------------------------- By establishing upper bounds for eGE under validation or cross-validation in section 2.1, we show that, as a criterion for model evaluation, a number of properties for eGE could be shown in finite samples and the asymptotic case, which suggest that it may serve as a good angle to understand model selection. Hence, by considering eGE as a criterion for model selection, we propose selecting the model based on minimizing the eGE, which we refer to as **generalization error minimization** or **GEM**. Generally speaking, GEM can be implemented alongside with many conventional techniques of model selection, such as penalized regressions, the information criteria and maximum a posteriori (MAP). However, in next section, we show that GEM works especially well for penalized regression. As shown in Algorithm 1, penalized regression estimation returns a $b_{\lambda}$ for each $\lambda$. Each value of $\lambda$ generates a different model and a different eGE. As a result, Theorems \[thm2.1\] and \[thm2.2\] guarantee that the model with the minimum eGE among $\left\{ b_{\lambda}\right\}$ has the best empirical generalization ability. By applying GEM in conjunction with validation/cross-validation and various penalty methods, the theoretical properties of the penalized regressions, such as its robustness, mode of consistency and convergence rate could be analyzed by directly applying the upper bounds we derive previously. Finite-sample and asymptotic properties for penalized regression under GEM ========================================================================== In Section 2, to analyze eGE from the perceptive of model-free, we establish a class of upper bounds for eGE of the extremum estimators, which is potentially connected to the eTE-eGE trade-off, bias-variance trade-off and cross validation; we also propose the GEM as the general framework of model selection. In this section, we implement the GEM onto regression analysis. As shown in the following section, we apply eGE to regression analysis and show that GEM serves as a new and clear angle to understand the procedure of penalized regression. By applying the eGE as the criterion of model selection, model selection directly serves as an effective method to improve GA; the other way around, the properties of model selection can directly be explained and re-framed by the eGE of the model. Moreover, other than the properties in section 2, additional properties can be established for penalized regression under GEM framework. Specifically, we establish: (1) specific error bounds for any penalized regression, (2) $\mathcal{L}_2$-consistency for all penalized regression estimators, (3) that the upper bound for the $\mathcal{L}_2$-difference between the penalized regression estimator and the OLS estimator is a function of the eGE, the tail behavior of distribution for the loss function and the exogeneity of the sample. Penalized regression -------------------- Firstly, we formally define penalized regression and its two most popular variants: lasso ($\mathcal{L}_1$-penalized regression) and ridge ($\mathcal{L}_2$-penalized regression). It is important to stress that each variable in $(Y,X)$ must be standardized before implementing penalized regression. As shown by @tibshirani96, without standardization the penalized regression estimates may be influenced by the magnitude (units) of the variables. After standardization, of course, $X$ and $Y$ are unit- and scale-free. \[Penalized regression, ridge regression, lasso regression, $\mathcal{L}_2$-eGE and $\mathcal{L}_2$-eTE\] 1. The general form of the objective function for penalized regression is $$\min_{b_\lambda} \frac{1}{n}\left(\left\Vert Y-Xb_{\lambda}\right\Vert_{2}\right)^{2} +\lambda\;\mathrm{Penalty}(\Vert b_{\lambda}\Vert_{\gamma}^\gamma). \label{lasso-type}$$ where the penalty term $\mathrm{Penalty}(\Vert\cdot\Vert_{\gamma})$ is a function of the $\mathcal{L}_{\gamma}$-norm of $b_{\lambda}$. 2. Let $b_{\lambda}$ denote the solution to the constrained minimization eq. (\[lasso-type\]) for a given value of the penalty parameter $\lambda$. Let $b^*$ denote the estimator with the minimum eGE among all the alternative $\{b_{\lambda}\}$ (as in Algorithm 1 in Section 1). Let $b_{OLS}$ denote the OLS estimator on the training set. 3. The objective function for the lasso ($\mathcal{L}_1$-norm penalty) is $$\min_{b_\lambda} \frac{1}{n} \left(\left\Vert Y-Xb_{\lambda}\right\Vert _{2}\right)^{2} +\lambda\Vert b_{\lambda}\Vert_{1}, \label{lasso-reg}$$ and the objective function for ridge regression ($\mathcal{L}_2$-norm penalty) is $$\min_{b_\lambda} \frac{1}{n} \left(\left\Vert Y-Xb_{\lambda}\right\Vert _{2}\right)^{2} +\lambda\Vert b_{\lambda}\Vert_{2}^2. \label{ridge-reg}$$ 4. The $\mathcal{L}_2$-norm eTE and eGE for any $b$ are defined, respectively, $$\begin{aligned} \mathcal{R}_{n_t}(b|Y_{t},X_{t}) & =\frac{1}{n_t}\,(\Vert Y_{t}-X_{t}b\Vert_{2})^{2} \\ \mathcal{R}_{n_s}(b|Y_{s},X_{s}) & =\frac{1}{n_s}\,(\Vert Y_{s}-X_{s}b\Vert_{2})^{2} \end{aligned}$$ The idea behind penalized regression is illustrated in Figure \[figpenreg\]. As shown in Figure \[figpenreg:fig3\], different $\mathcal{L}_{\gamma}$ penalties correspond to different boundaries for the estimation feasible set. For the $\mathcal{L}_1$ penalized regression (lasso), the feasible set is a diamond. The feasible set expands to a circle under an $\mathcal{L}_{2}$ penalty. As illustrated in Figures \[figpenreg:fig1\] and \[figpenreg:fig2\], for given $\lambda$, the smaller $\gamma$, the more likely $b_{\lambda}$ is a corner solution. It follows that under the $\mathcal{L}_{1}$ penalty, variables are more likely to be dropped compared with the $\mathcal{L}_{2}$ penalty.[^13] In the special case when $\gamma=0$ and $\lambda=2$ ($\lambda=\ln n_t$), the $\mathcal{L}_0$ penalized regression is identical to the Akaike (Bayesian) information criterion. Penalized regression primarily focuses on overfitting. By contrast, OLS minimizes the eTE without any penalty, often resulting in a large eGE (e.g., the 'overfitting' in Figure \[fig:VCineq\]). It is also possible that OLS fits the training data poorly, causing both the eTE and eGE to be large (e.g., the 'underfitting' in Figure \[fig:VCineq\]). Generally speaking, it is easier to deal with overfitting than underfitting.[^14] Overfitting in OLS is usually caused by including too many variables, which can be resolved by reducing $p$. Underfitting, however, is likely due to a lack of data (variables) and the only remedy is to collect more data. GEM for penalized regression ---------------------------- The conventional route to establish finite-sample and asymptotic properties for regression is by analyzing the properties of the estimator in the space of the eTE. By contrast, to study how penalized regression improves GA, we reformulate the analysis in the space of the eGE. Figure \[fig:outline\] outlines our proof strategy. We show that a number of finite-sample properties for penalized regression can be established under the GEM framework. ![\[fig:outline\]Outline of proof strategy](OutlineTIM.pdf){width="0.5\paperwidth"} In asymptotic analysis, consistency is typically considered to be one of the most fundamental properties. To demonstrate that GEM is a viable estimation framework, we prove that the penalized regression model selected by eGE minimization converges to the true DGP as $n\rightarrow\infty$. Essentially, we show that penalized regression bijectively maps $b^*$ to the minimal eGE among $\{b_{\lambda}\}$ on the test set. To link the finite-sample and asymptotic results we need to show that, if the true DGP $\beta$ is bijectively assigned to the global minimum eGE in the population, and if $$\min_{b\in b_{\lambda}}\; \frac{1}{n_s}\sum_{i=1}^{n_s}\Vert Y_{s}-X_{s}b\Vert_{2}^{2} \quad\longrightarrow\quad \min_b \int\Vert y-\mathbf{x}^{T}b\Vert_{2}^{2}~\mathrm{d}F(y, \mathbf{x}),$$ then $b^*$ is consistent in probability or $\mathcal{L}_2$, or $$b^* = \operatorname*{argmin}_{b_{\lambda}}\{\mbox{eGEs}\} \quad\xrightarrow{\mathbf{P}~\mathrm{or}~\mathcal{L}_2}\quad \operatorname*{argmin}_b\int\Vert y_{s}-\mathbf{x}_{s}^{T}b\Vert_{2}^{2} \mathrm{d}F(y,\mathbf{x}) = \beta.$$ To establish consistency for penalized regression, we make the following three additional assumptions. **Further assumptions** 1. The true DGP is $Y = X\beta + u$. 2. $\mathbb{E} \left( u^T X \right) = \mathbf{0}$. 3. No perfect collinearity in $X$. Assumptions A4–A6 restrict the true DGP indexed by $\beta$ to be identifiable. Otherwise, there may exist an alternative that is not statistically different from the true DGP. The assumptions are standard for linear regression. Under assumptions A1–A6, we first show that the true DGP has the lowest generalization error. \[Identification of $\beta$ in the space of eGE\] Under A1–A6, the true DGP, $Y = X\beta + u$, is the one and only one offering the minimal eGE as $\widetilde{n} \rightarrow \infty$. \[prop3.1\] Proposition \[prop3.1\] states that there is a bijective mapping between $\beta$ and the global minimum eGE in the population. If A5 or A6 were violated, variables may exist in the sample that render the true DGP not to have the minimum eGE in the population. As shown in Algorithm 1, penalized regression chooses $b^*$ to be the model with the minimum eGE in $\{b_\lambda\}$. Thus, we need to establish that when the sample size is large enough, the true DGP is included among $\{b_{\lambda}\}$, the list of models selected by validation or cross-validation. \[Existence of $\mathcal{L}_2$-consistency\] Under A1–A6 and Proposition \[prop3.1\], there exists at least one $\widetilde{\lambda}$ such that $\lim_{\widetilde{n} \rightarrow \infty} \Vert b_{\widetilde{\lambda}} - \beta \Vert_2 = 0$. \[prop3.2\] Using lasso as the example of penalized regression, Figure \[figlassotypeshrink:fig\] illustrates Propositions \[prop3.1\] and \[prop3.2\]. In Figure \[figlassotypeshrink:fig\], $\beta$ refers to the true DGP, $b_{\lambda}$ refers to the solution of eq. (\[lasso-reg\]), and the diamond-shaped feasible sets are due to the $\mathcal{L}_1$ penalty. Different values of $\lambda$ imply different areas for the feasible sets, which get smaller as the value of $\lambda$ increases. There are three possible cases: (i) under-shrinkage—for a low value of $\lambda$ (Figure \[figlassoshrink:fig1\]), $\beta$ lies within the feasible set and has the minimum eTE in the population; (ii) perfect-shrinkage—for the oracle $\lambda$ (Figure \[figlassoshrink:fig2\]), $\beta$ is located precisely on the boundary of the feasible set and still has the minimum eTE in the population; (iii) over-shrinkage—for a high value of $\lambda$ (Figure \[figlassoshrink:fig3\]), $\beta$ lies outside the feasible set. In cases (i) and (ii), the constraints become inactive as $\widetilde{n}\rightarrow\infty$, so $\lim_{\widetilde{n}\rightarrow\infty}b_{\lambda} = \lim_{\widetilde{n}\rightarrow\infty}b_{OLS} = \beta$. However, in case (iii), $\lim_{\widetilde{n}\rightarrow\infty}b_{\lambda}\neq\beta$. An important implication is that tuning the penalty parameter $\lambda$ is critical for the theoretical properties of the penalized regression estimators. Main results for penalized regression under GEM ----------------------------------------------- Intuitively, the penalized regression estimator will be consistent in some norm or measure as long as, for a specific $\lambda$, $\beta$ lies in the feasible set and offers the minimum eTE. In practice, however, we may not know a priori whether $\lambda$ causes over-shrinking or not, especially when the number of variables, $p$, is not fixed. As a result, we need to use an approach like validation or cross-validation to tune the value of $\lambda$. Applying the results in Section 2, we show that GEM guarantees that the model selected by penalized regression with the appropriate $\lambda$, $b^*$, asymptotically converges in $\mathcal{L}_{2}$ to the true DGP. In this section we analyze the finite-sample and asymptotic properties of the GEM estimator in two settings: $n\geqslant p$ and $n < p$. In the case where $n\geqslant p$, OLS is feasible, and is the unpenalized regression estimator. In the case where $n < p$, OLS is not feasible, and forward stagewise regression (FSR) is the unpenalized regression estimator. ### GEM for penalized regression with $n\geqslant p$ Firstly, by adapting eq. (\[eq:thm2.1\]) and (\[eq1:thm2.2\]) and (\[eq2:thm2.2\]) for regression, we establish the upper bound of the eGE. \[Upper bound for the eGE of the OLS estimator\] Under A1–A6, if we assume $u \sim N(0,\sigma^2)$, 1. **Validation case.** The following bound for the eGE for $b_{OLS}$ holds with probability at least $\varpi(1-1/n_t)$, $\forall\varpi\in\left(0,1\right)$. $$\frac{1}{n_s}(\Vert e_s \Vert_2)^2 \leqslant \frac{(\Vert e_t \Vert_2)^2}{n_t(1-\sqrt{\epsilon})} + \frac{2 \sigma^4}{n_s\sqrt{1-\varpi}}, \label{eq1:lem3.1}$$ where $(\Vert e_s \Vert_2)^2$ is the eGE and $(\Vert e_t \Vert_2)^2$ is the eTE of the OLS estimator, and $\epsilon$ is defined in Lemma \[lem2.1\]. 2. **$K$-fold cross-validation case.** The following bound for the eGE for $b_{OLS}$ holds with probability at least $\varpi(1-1/n_t)$, $\forall\varpi\in\left(0,1\right)$. $$\frac{1}{K}\sum^{K}_{q=1}\frac{(\Vert e_s^q \Vert_2)^2}{n/K} \leqslant \frac{\sum_{q=1}^K (\Vert e_t^q \Vert_2)^2} {n(K-1)(1-\sqrt{\epsilon})} + \frac{2\sigma^4}{(n/K)\sqrt{1-\varpi}}, \label{eq2:lem3.1}$$ where $(\Vert e_s^q \Vert_2)^2$ is the eGE and $(\Vert e_t^q \Vert_2)^2$ is the eTE of the OLS estimator in the $q$th round of cross-validation, and $\epsilon$ is defined in Lemma \[lem2.1\]. \[lem3.1\] In a similar fashion to eqs. (\[eq:thm2.1\]) and (\[eq1:thm2.2\]) and (\[eq2:thm2.2\]), eqs. (\[eq1:lem3.1\]) and (\[eq2:lem3.1\]) measure the upper bound of the eGE for the OLS estimator under validation and cross-validation, respectively. In standard practice, of course, neither validation nor cross-validation are implemented as part of OLS estimation and the eGE of the OLS estimator is not computed. Nevertheless, eqs. (\[eq1:lem3.1\]) and (\[eq2:lem3.1\]) show that it is possible to compute the eGE of the OLS estimator without having to carry out validation or cross-validation. Eqs. (\[eq1:lem3.1\]) and (\[eq2:lem3.1\]) also show that the higher the variance of $u$ in the true DGP, the higher the upper bound of the eGE under validation and cross-validation. As a bonus of the GEM approach, eq. (\[eq2:lem3.1\]) also shows that we can find the $K$ that maximizes the GA from cross-validation by tuning $K$ to the lowest upper bound of the cross-validated eGE, determined by minimizing the expectation of the RHS of eq. (\[eq2:lem3.1\]). \[The optimal $K$ for penalized regression\] Under A1–A6, and based on eq. (\[eq2:lem3.1\]) from Lemma \[lem3.1\], if we also assume the error term $u \sim N(0, \sigma^2)$, the optimal $K$ for cross-validation in penalized regression (the minimum expected upper bound of eGE) is defined: $$K^* = \operatorname*{argmin}_{K} \frac{\sigma^2}{1 - \sqrt{\epsilon}} + \frac{2\sigma^4}{(n/K)\sqrt{1 - \varpi}}$$ \[cor3.1\] The penalty parameter $\lambda$ can be tuned by validation or $K$-fold cross-validation. For $K\geqslant 2$, we have $K$ different test sets for tuning $\lambda$ and $K$ different
{'source': 'arXiv_out/1610'}