{'fraction_non_alphanumeric': 0.044537159526474676, 'fraction_numerical': 0.014348224280044775, 'mean_word_length': 4.100692041522492, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Implicit Regularization of Ordinary Least Squares Ensembles

Ensemble methods that average over a collection of independent predictors that are each limited to a subsampling of both the examples and features of the training data command a significant presence in machine learning, such as the ever-popular random forest, yet the nature of the subsampling effect, particularly of the features, is not well understood. We study the case of an ensemble of linear predictors, where each individual predictor is fit using ordinary least squares on a random submatrix of the data matrix. We show that, under standard Gaussianity assumptions, when the number of features selected for each predictor is optimally tuned, the asymptotic risk of a large ensemble is equal to the asymptotic ridge regression risk, which is known to be optimal among linear predictors in this setting. In addition to eliciting this implicit regularization that results from subsampling, we also connect this ensemble to the dropout technique used in training deep (neural) networks, another strategy that has been shown to have a ridge-like regularizing effect.


INTRODUCTION
Ensemble methods (Breiman, 1996;Amit and Geman, 1997;Josse and Wager, 2016) are an oft-used strategy used successfully in a broad range of problems in machine learning and statistics, in which one combines a number of weak predictors together to obtain one powerful predictor. This is accomplished by giving each weak learner a different view of the training data. Various strategies for changing this training data view exist, among which many are simple sampling-based techniques in which each predictor is (independently) given access to a subsampling the rows (examples) and columns (features) of the training data matrix, such as bagging (Breiman, 1996;Bühlmann and Yu, 2002). Another noteworthy technique is boosting (Freund and Schapire, 1997;Breiman, 1998), in which the training data examples are reweighted adaptively according to how badly they have been misclassified while buliding the ensemble. In this work, we consider the former class of techniques-those that train each weak predictor using an independent subsampling of the training data.
Ensemble methods based on independent example and feature subsampling are attractive for two reasons. First, they are computationally appealing in that they are massively parallelizable, and since each member of the ensemble uses only part of the data, they are able to overcome memory limitations faced by other methods (Louppe and Geurts, 2012). Second, ensemble methods are known to achieve lower risk due to the fact that combining several different predictors reduces variance (Bühlmann and Yu, 2002;Wager et al., 2014;Scornet et al., 2015), and empirically they have been found to perform very well. Random forests (Breiman, 2001;Athey et al., 2019;Friedberg et al., 2018), for example, ensemble methods that combine example and feature subsampling with shallow decision tress, remain among the best-performing off-the-shelf machine learning methods available (Cutler and Zhao, 2001;Fernández-Delgado et al., 2014;Wyner et al., 2017).
Let X ∈ R n×p be the training data matrix consisting of n examples of data points each having p features. While there exist theoretical results on the benefits of example (row) subsampling (Bühlmann and Yu, 2002), the exact nature of the effect of feature (column) subsampling on ensemble performance remains poorly understood. In this paper, we study the prototypical form of this problem in the context of linear regression. That is, given the data matrix X and target variables y ∈ R n , we study the ensemble β ens = 1  Figure 1: Example (rows) and feature (columns) subsampling of the training data used in the ordinary least squares fit for one member of the ensemble. The i-th member of the ensemble is only allowed to predict using its subset of the features (green). It must learn its parameters β (i) by performing ordinary least squares using the subsampled examples of y (red) and the subsampled examples (rows) and features (columns) of the data matrix X (blue, crosshatched).
where each β (i) is learned using ordinary least squares on an independent random subsampling of both the examples and features of the training data. This subsampling is illustrated in Figure 1. We show that under such a scheme, the resulting predictor of this ensemble performs as well as the ridge regression (Hoerl and Kennard, 1970;Friedman et al., 2001) predictor fit using the entire training data, which is known to be the optimal linear predictor under the data assumptions that we consider. Further, the asymptotic risk of the ensemble depends only on the amount of feature subsampling and not on the amount of example subsampling, provided each individual ordinary least squares problem is underdetermined. Our main result in Theorem 3.6, made possible using the recent result on asymptotic risk for ridge regression by Dobriban and Wager (2018), can be summarized as follows: Theorem 3.6 (informal statement). When the features and underlying model weights both follow i.i.d. Gaussian distributions, the optimal asymptotic risk for an ensemble of ordinary least squares predictors is equal to the optimal asymptotic ridge regression risk.
We can interpret this result as an example of implicit regularization (Neyshabur et al., 2014;Gunasekar et al., 2017;Arora et al., 2019). That is, while the individual ordinary least squares subproblems are completely unregularized, the ensemble behaves as if it had been regularized using a ridge regression penalty. Recently, there has been much interest in investigating the implicit regularization effects of commonly used heuristic methods, particularly in cases where they enable the training of highly overparameterized models that generalize well to test data despite having the capacity to overfit the training data (Zhang et al., 2017;Belkin et al., 2018). Examples of heuristic techniques that have been shown to have implicit regularization effects include stochastic gradient descent (Hardt et al., 2016) and dropout (Srivastava et al., 2014). Incidentally, we show below a strong connection between the ensemble of ordinary least squares predictors and dropout, which is known to have a ridge-like regularizing effect (Wager et al., 2013), and this link is made via stochastic gradient descent.
Contributions We summarize our contributions as follows: [C1] We prove that when the amount of feature subsampling is optimized to minimize risk, an ensemble of ordinary least squares predictors achieves the same risk as the optimal ridge regression predictor asymptotically as n, p → ∞ (see Section 3).
[C2] We demonstrate the converge of the ensemble risk to the optimal ridge regression risk via simulation (see Section 4.1).
[C3] We reveal a connection between the ordinary least squares ensemble and the popular dropout technique used in deep (neural) network training (see Section 4.3) and from the insight gained from this connection develop a recipe for mitigating excess risk under suboptimal feature subsampling via simple output scaling (see Section 4.4).

ENSEMBLES OF ORDINARY LEAST SQUARES PREDIC-TORS
We consider the familiar setting of linear regression, where there exists a linear relationship between the target variable y ∈ R and the feature variables x ∈ R p -i.e., y = x, β , where β ∈ R p is the model parameter vector. The goal of a machine learning algorithm is to estimate these parameters given n i.i.d. noisy samples x (i) , y (i) n i=1 . The noise relationship is given by where zero-mean random variables with unit variance independent of X. We assume a Gaussian N (0, Σ) distribution on x.
Our ensemble consists of k linear predictors each fit using ordinary least squares on a submatrix of X, and the resulting prediction is the average of the outputs. Equivalently, our ensemble is defined by its estimate of the parameters where β (i) is the parameter estimate of the i-th member of the ensemble. To characterize the estimates β (i) , we first introduce some notation. Let the selection matrix S corresponding to a subset of indices S ⊆ [p] denote the the p × |S| matrix obtained by selecting from I p the columns corresponding to the indices in S, where I p denotes the p × p identity matrix. This definition of selection matrices also analogously applies to subsets of [n]. Returning to the ensemble, let S (S i ) k i=1 and T (T i ) k i=1 denote the collection of feature subsets and example subsets, respectively, where each S i ⊆ [p] and each T i ⊆ [n]. Then, assuming |S i | < |T i |, for each member of the ensemble we let where S c i = [p] \ S i denotes the complement of the set S i . This can alternatively be written in closed form as where (·) † denotes the Moore-Penrose pseudoinverse. Thus, the closed-form expression for the ensemble parameter estimate is given by

ENSEMBLE RISK
We define the risk of a linear predictor as the expected squared error of a prediction of the target variable on an independent data point x: For any predictor of the form β = f (X)y, for some f : R n×p → R p×n , we can rewrite parameter estimation error as Then by the independence of X and z and some algebra, we can decompose the risk into the so-called "bias" and "variance" components For the ensemble, we obtain for the bias where Similarly, for the variance we have where Thus, evaluating the risk of the ensemble is a matter of evaluating these pairwise interaction terms.
To begin evaluating the above terms, we need to introduce additional assumptions. Specifically, we assume that the subsets are independent and that all indices are equally likely to be included in each subset.
Assumption 3.1 (finite subsampling). The subsets in the collections S and T are selected at random such that |S i | < |T i | − 1 and that the following hold: • The subsets S 1 , S 2 , . . . , S k , T 1 , T 2 , . . . , T k are conditionally independent given the example subset sizes (|T i |) k i=1 . A simple sampling strategy that satisfies these assumptions is to fix |S i | and |T i | such that |S i | < |T i | − 1 and select subsets uniformly at random of the given sizes. Another strategy is to construct the subsets by flipping a coin for each index, rejecting any resulting subsets that fail to satisfy |S i | < |T i | − 1.
With Assumption 3.1, we are now equipped to evaluate the pairwise interaction terms. For simplicity, we will also assume identity covariance on the data. The following two lemmas enable us to characterize the bias and variance components of the risk in the finite-dimensional setting. The proofs of these lemmas are exercises in linear algebra and conditional expectations and can be found in the Appendix.
With some slight abuse of notation, we allow E S,T to denote the expectation taken with respect to the choice of indices in the subsets, but not their sizes. In other words, E S,T indicates the conditional expectation over S and T , conditioned on the subset sizes indicated by the context.
Lemma 3.2 (bias). Assume that Σ = I p and that Assumption 3.1 holds. Then for i = j, Lemma 3.3 (variance). Assume that Σ = I p and that Assumption 3.1 holds. Then One observation that we can make already from these results is that the example subsampling only affects the terms where i = j. Assuming that the subsampling procedure is the same for each i, so that for large k the i = j terms are sure to dominate the sum, this means that in the limit as k → ∞, the effects of example subsampling are non-existent. We note that this is a result of the assumption that |S i | < |T i |, and that if we were to have |S i | > |T i |, then we would observe effects of example subsampling when i = j, which we discuss further in Section 5.2.
We now turn our attention to the setting where n, p → ∞ in order to better reason about the results contained in these lemmas. We introduce the following additional assumption.
Assumption 3.4 (asymptotic subsampling). For some α, η ∈ [0, 1], the subsets in the collections S and T are selected randomly such This assumption is easily satisfied. For example, in the sampling strategy where we fix |S i | and |T i |, we can choose |S i | = αp and |T i | = ηn . For the coin-flipping strategy, we can select feature subsets with a coin of probability α and example subsets with a coin of probability η.
Under this assumption, and additionally assuming without loss of generality that β 2 = 1, if n, p → ∞ such that p/n → γ and η > αγ, the quantities in (14) and (15) converge almost surely as follows: and We are now equipped to state our asymptotic risk result for the ensemble of ordinary least squares predictors. Denote for an ensemble satisfying Assumptions 3.1 and 3.4 with parameters α, η, and k the limiting risk From (10) and (12), we know that both the bias and variance components of the limiting risk are the averages of k 2 terms, and from (16) and (17), we know that the k(k − 1) terms where i = j will take one value and the remaining k terms where i = j will take another. Thus we have the limiting bias lim n,p→∞ and limiting variance lim n,p→∞ Upon careful examination of these quantities, we observe that in fact both the limiting bias and the limiting variance are decreasing in k, and thus the ensemble serves not only as a means to reduce variance (as is well understood), but also to reduce bias. We defer further discussion to Section 4.2. Adding the limiting bias and variance yields the following result.
Theorem 3.5 (limiting risk). Assume that Σ = I p and β 2 = 1 and that Assumptions 3.1 and 3.4 hold. Then in the limit as n, p → ∞ with p/n → γ, for η > αγ, we have almost surely that Here we see again more explicitly that for large k, the effect of example subsampling vanishes. This leaves us with the large-ensemble risk We note that while the large-ensemble risk depends only upon α, we cannot realize this risk with an ensemble if η ≤ αγ. Our remaining results concern the large-ensemble risk and therefore assume that η = 1 for simplicity, but we caution the reader that some of these results may not be valid for some smaller values of η, depending on σ and γ.
Because α is an algorithmic hyperparameter, it can be tuned to minimize the risk. If we do so, then what we obtain is the perhaps surprising result that the optimal large-ensemble risk of the ordinary least squares predictor is equal to the limiting risk of the ridge regression predictor under our assumptions. The ridge regression predictor with parameter λ is defined as We formally state this result in the following theorem. This result leverages the recent analysis of the limiting risk of ridge regression by Dobriban and Wager (2018). The proof is found in the Appendix.
Theorem 3.6. Assume that Σ = I p and β ∼ N (0, p −1 I p ) and that Assumptions 3.1 and 3.4 hold with η = 1. Then in the limit as n, p → ∞ with p/n → γ, we have almost surely that A curious result obtained during the proof of this theorem is the following corollary relating the optimal large ensemble risk to the optimal choice of the hyperparameter α.
The implication of Theorem 3.6 is quite strong. Under the assumption of the theorem that true parameters β have a Gaussian distribution with covariance p −1 I p , the ridge regression predictor is the predictor with the lowest expected risk of all predictors of the form β = f (X)y. To see this, note that if we take the expectation of (9) with respect to β, we find that the optimal f (X) must satisfy the first order optimality condition which for invertible Σ yields the optimally tuned ridge regression predictor. Thus, in the Σ = I p setting, the optimally tuned ensemble achieves the optimal risk for any linear predictor. However, as the choice of η approaches αγ, this rate becomes slower. In Figure 2, we plot the convergence in k of the limiting risk to the large-ensemble risk for η = 1 (using all examples) and for η = 1.1 × (αγ) (near to as small as possible while still having |S i | < |T i |). We plot these curves for σ = 1 and for three different values of γ, using n = 200, which is sufficient to realize the convergence in n and p. We choose α = α * , the minimizer of the large-ensemble risk. What we observe is that, indeed, for both choices of η, the risks converge to the optimal ridge risk. As expected, however, with the smaller choice of η the risk converges nearly an order of magnitude more slowly. While the choice of α = α * will result in optimal risk for large enough ensembles, for finite k this choice can in some cases be undesirable. For instance, consider the setting where η = 1 and γ > 1. Then as σ → 0, α * → γ −1 . This obviously yields the optimal large-ensemble risk, by definition, but for any finite k, the limiting risk tends to infinity for this choice of α. However, if we know what the size of our ensemble will be, we can tune α to the limiting risk for finite k instead of the large ensemble risk. In general, this means choosing an α smaller than α * . In Figure 3, we demonstrate the convergence in k to the large-ensemble risk as a function of σ for α = α * and for α = arg min α R ens α ,η,k . We plot these curves for γ = 2 and σ ∈ [0.1, 10], using n = 200. While for both choices of α we see convergence in k for each σ, as σ → 0, the risk is very large for α = α * . For α adapted to the choice of k, however, this effect is mitigated.

Bias and Variance Decrease with Ensemble Size
We return here to the observation made in Section 3 that the limiting bias and variance are both decreasing in k. This can be seen by comparing the i = j and i = j terms in each case. In the case of bias, for the bias to be decreasing, it must be that Since α 2 γ < 1 and η > αγ, after some algebra, this reduces to Because α ≤ 1, the left-hand side is non-positive, and since α < γ −1 , the right-hand side is strictly positive. Thus this inequality always holds, and the bias is decreasing.
In the case of variance, for the variance to be decreasing, we must have Again since α 2 γ < 1 and η > αγ, this reduces to αη < 1.
So, unless both α = 1 and η = 1, in which case every member of the ensemble is the ordinary least squares predictor fit using the entire training data, the variance is decreasing.

Dropout and Ridge Regression
There is an interesting connection between the ordinary least squares ensemble with η = 1 and the popular dropout technique (Srivastava et al., 2014) used in deep (neural) network training, which consists of randomly masking the features at each iteration of (stochastic) gradient descent. To draw this connection, define Then our ensemble member parameter estimates are minimizers of this loss function.
For each i, the i-th member of the ensemble is able to solve its subproblem independently of the other members. As a result, we can consider the ensemble to be a model with k i=1 |S i | parameters that are eventually averaged to reduce them down to p parameters. If we were to instead constrain ourselves so that For both the setting where we use fewer features than optimal with α = α * /2 (blue) and the fixed α = 1/2 setting (red), we see significantly improved risk by scaling.
we were allowed to use only p parameters, such that we could not optimize each member of the ensemble independently, we might try to optimize them jointly by minimizing the average loss. That is, If we go a step further and let k → ∞ and optimize this loss using stochastic gradient descent where at each iteration we use the gradient of an individual i selected at random, then our ensemble becomes equivalent to the predictor learned using dropout. It is well-known that dropout with linear regression has a very strong connection to ridge regression (Srivastava et al., 2014); specifically, we find that In the case of Σ = I p , diag(X X) will converge to I p as n, p → ∞, in which case dropout and ridge regression are equivalent up to a rescaling. We discuss the case where Σ = I p in Section 5.1.

Scaled Ensembles
Our ensemble combines the individual predictors by simple averaging. However, in light of the fact that dropout is only equivalent to ridge regression up to a rescaling of the output, it is worth considering the effect of using an equally-weighted linear combination but using different weights from 1/k in constructing the ensemble predictor. That is, we consider the risk of the µ-scaled predictor β ens µ = (µ/k) k i=1 β (i) . A simple calculation, proved in the Appendix, shows that under the assumptions of Theorem 3.5 the large-ensemble risk of the µ-scaled predictor is given by Hence, it is possible to minimize the risk of β ens µ over the choice of parameter µ. This results in as the optimal choice for µ and R ens α,µ * = 1 − as the achieved risk for the optimally-scaled ensemble. Note that as a result of Corollary 3.7, R ens α * = 1 − α * . Therefore, for ensembles with optimally-tuned α = α * we have µ * = 1, and any scaling in constructing the ensemble predictor will not further improve the achieved risk. However, it is easy to see that when α > α * (the ensemble members select more features than is optimal), µ * < 1, and the risk is improved by adding extra shrinkage to the ensemble predictor. Similarly, if α < α * , (the ensemble members select less features than is optimal), µ * > 1, and the risk is improved by inflating the ensemble predictor. We illustrate the improvement in risk to be had in Figure 4, where we plot the risk with (µ = µ * ) and without (µ = 1) optimal scaling for two choices of α-one where we always select half as many features as optimal (α = α * /2), and one where we always use half of the available features (α = 1/2).

Non-Identity Covariance
Of course, it is important to understand the behavior of the ordinary least squares ensemble in the case where Σ = I p when considering applications of the method to real data. As discussed in Section 3, provided Σ is invertible, ridge regression remains the optimal linear predictor, and whether the ensemble (or extensions thereto) still achieves the optimal risk in this setting remains an open question.
By inspection of the closed-form solution of dropout in (34), we see that it is no longer equivalent (as n, p → ∞) to ridge regression and is therefore no longer optimal. We believe that this is likely the case for the ensemble as well. However, if we extend the coin-flipping strategy for feature subset selection to one where we have a collection of coin with probabilities α ∈ [0, 1] p , one for each feature, we can extend the result in (34) to obtain the closed-form dropout solution where A = diag(α). We prove this result in the Appendix. Thus, if α is chosen such that then the corrected dropout estimator is equivalent to ridge regression with parameter λ as n, p → ∞. This leads us to believe that the optimal ensemble in the Σ = I p setting should also use non-uniform feature sampling, and extending our analysis to this case is an interesting area for future work.

Beyond Ordinary Least Squares: Ensembles of Interpolators
Throughout this work we have assumed that the members of the ensemble solve their subproblems using ordinary least squares, which yields the unique solution that minimizes the squared error given |T i | observations of |S i | variables, and this uniqueness requires that |T i | be no less than |S i |. In the case where |T i | < |S i |, there are infinitely many solutions that minimize the squared error. However, we could in this case opt to regularize the solution to solve this problem. While analysis of the effect of regularizing the solution of the subproblems in the ensemble is beyond the scope of this work, we comment briefly on what would happen if we were to simply use the same solution presented in (5)-i.e., use the pseudoinverse solution, which has the smallest 2 norm of all solutions to the least squares problem. In this case, when η = 1, the learned predictor would be an interpolator (Belkin et al., 2018;Hastie et al., 2019) of the training data, and such methods have recently become increasingly of interest given the ability of deep (neural) network methods to have extremely good test performance while having (nearly) zero training error (Zhang et al., 2017;Belkin et al., 2019). Specifically, it becomes immediately clear that in this setting, the effect of the choice of η does not vanish as k → ∞. Lemma 3.3 can easily be extended to this setting, since the roles of S i and T i in (13) can simply be reversed to yield As n, p → ∞, this converges almost surely to Thus, the variance component of the large-ensemble risk in this setting is equal to σ 2 η 2 /(γ −η 2 ) and does not depend upon α. In future work, we plan to extend our analysis for the bias component of the large-ensemble risk to this setting, and we expect that in this case the bias will depend on both α and η.

Optimal Ensemble Mixing
In the ordinary least squares ensemble, we have used equal weighting when taking the average of our predictors. Instead, we could extend the idea presented in Section 4.4 to consider unequal weighting parameterized by µ ∈ R k , giving us the ensemble parameter estimate β ens µ = k i=1 µ i β (i) . While equal weighting gives us optimal risk in the setting where β ∼ N (0, p −2 I p ), where ridge regression is optimal, under other distributional assumptions on β, such as sparsity, where ridge regression is not optimal, unequal weighting has the potential to yield better ensembles.
Using the sparsity example, consider β such that β 0 = s p, and suppose that for some i, S i = S β , where S β = {j : β j = 0}. For simplicity, assume that η = 1, so that T i = [n] for all i. In this case, any predictor that uses the remaining p − s features injects noise into its predictions, so the best predictor uses only the s features in S β . Under the i.i.d. Gaussian noise assumption, the predictor with lowest risk is in fact where i is such that S i = S β . Thus an optimal weighting µ is given by where C = | {i : S i = S β } |. This optimal weighting is decidedly non-uniform, and this raises the question of what schemes could be employed, either adaptively or non-adaptively, to minimize risk, and how they would fit into this analysis framework.
M. Belkin, D. J. Hsu, and P. Mitra. Overfitting or perfect fitting? Risk bounds for classification and regression

C PROOF OF LEMMA 3.3 (VARIANCE)
To compute the variance, we need to evaluate the terms of the form Let S be the selection matrix corresponding to the set S i ∩ S j . Then The equality (72) is the result of two applications of Lemma A.1.
In the case that i = j, an application of Lemma A.2 simplifies the above to The equality comes from S X XS −1 having an inverse Wishart distribution with scale matrix I |Si∩Sj | and n degrees of freedom. When i = j, we obtain a similar result directly without needing Lemma A.2. The above simplifies to D PROOF OF THEOREM 3.6 We first introduce the result due to Dobriban and Wager (2018).
Proposition D.1 (from Dobriban and Wager, 2018, Theorem 2.1). Assume that Σ = I p and β ∼ N (0, p −1 I p ). Then in the limit as n, p → ∞ with p/n → γ, we have almost surely that We note that this expression is equal to σ 2 (R * (1/σ 2 , γ) − 1) in the notation of Dobriban and Wager (2018), where this transformation is necessary because we assume β 2 = 1 rather than σ = 1 and because we evaluate the noise-free risk.
The minimizer of the large ensemble risk should satisfy the first-order optimality condition, so we begin by taking its derivative.
From here, it is simply a matter of cumbersome algebra to show that the choice α * = γ(σ 2 + 1) + 1 − (γ(σ 2 + 1) + 1) 2 − 4γ 2γ (79) is the valid root of this quadratic expression and is such that R ens α * = inf λ R( β ridge λ ). We here show a slightly more interesting approach, leading to Corollary 3.7. First, we start from (78) and add a root of α * = 0, and then we proceed to manipulate the resulting equation.
Now, we observe for the larger root (which we denote as α * ) that α * = γ(σ 2 + 1) + 1 + (γ(σ 2 − 1) + 1) 2 + 4σ 2 γ 2 2γ (92) Thus the only case where α * is a valid hyperparameter choice (that is, α * ≤ min 1, γ −1 ) is when σ 2 = 0 and γ = 1, in which case α * = 1 is a double root of (78). So it suffices to evaluate the smaller root even in that case. Now that we know that α * is not conatined in [0, min 1, γ −1 ] (except in the aforementioned special case) and that by inspection of R ens α the asymptote at α = γ −1/2 is not contained in this interval, if we can show that the smaller root (which we denote simply as α * ) of (78) is contained in this interval, then we know that it is the minimizer of R ens α .
For the smaller root, it is clear from (79) that α * ≥ 0. We show by a series of equivalences that α * ≤ 1/γ: ⇐⇒ σ 2 + 1 − 1 γ 2 ≤ σ 2 − 1 + 1 γ 2 + 4σ 2 (97) The last inequality is always true. Further, we note that every equivalence here still holds under strict inequalities, so for σ > 0, we have that α * < γ −1 . By a similar argument, we can show that α * ≤ 1 and that α * < 1 if and only if σ > 0. By the form of the derivative in (77), we know that α * , as the smaller root, is a local minimum, and therefore it must be the minimum of R ens α on [0, min 1, γ −1 ]. Evaluating the risk at α * , we have Examining the inner product, we find that E X,z,S,T β, β − β ens = β, E X,z,S,T β − β ens = β, E X,S, where the equation (110) holds because E[z] = 0. Because the subsamplings are identically distributed, we have