A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning

Introduction

Deep learning techniques have revolutionized the way many engineering and scientific problems are addressed, establishing the data-driven approach as a leading choice for practical success. Contemporary deep learning methods are extreme, extensively developed versions of classical machine learning (ML) settings that were previously restricted by limited computational resources and insufficient availability of training data. Established practice today is to learn a highly complex deep neural network (DNN) from a set of training examples that, while itself large, is quite small relative to the number of parameters in the DNN. While such overparameterized DNNs comprise the state-of-the-art in ML practice, the fundamental reasons for this practical success remain unclear. Particularly mysterious are two empirical observations: i) the explicit benefit (in generalization) of adding more parameters into the model, and ii) the ability of these models to generalize well despite perfectly fitting even noisy training data. These observations endure across diverse architectures in modern ML — while they were first made for complex, state-of-the-art DNNs (Neyshabur et al., 2014; Zhang et al., 2017), they have since been unearthed in far simpler model families including wide neural networks, kernel methods, and even linear models (Belkin et al., 2018b; Spigler et al., 2019; Geiger et al., 2020; Belkin et al., 2019a).

In this paper, we survey the recently developed theory of overparameterized machine learning (henceforth abbreviated as TOPML) that establishes foundational mathematical principles underlying phenomena related to interpolation (i.e., perfect fitting) of training data. We will shortly provide a formal definition of overparameterized ML, but describe here some salient properties that a model must satisfy to qualify as overparameterized. First, such a model must be highly complex in the sense that its number of independently tunable parametersThe number of parameters is an accepted measure of learned model complexity for simple cases such as ordinary least squares regression in the underparameterized regime and underlies classical complexity measures like Akaike’s information criterion (Akaike, 1998). For overparameterized models, the correct definition of learned model complexity is an open question at the heart of TOPML research. See Section 7.3 for a detailed exposition. is significantly higher than the number of examples in the training dataset. Second, such a model must not be explicitly regularized in any way. DNNs are popular instances of overparameterized models that are usually trained without explicit regularization (see, e.g., Neyshabur et al., 2014; Zhang et al., 2017). This combination of overparameterization and lack of explicit regularization yields a learned model that interpolates the training examples and therefore achieves zero training error on any training dataset. The training data is usually considered to be noisy realizations from an underlying data class (i.e., noisy data model). Hence, interpolating models perfectly fit both the underlying data and the noise in their training examples. Conventional statistical learning has always associated such perfect fitting of noise with poor generalization performance (e.g., Friedman et al., 2001, p. 194); hence, it is remarkable that these interpolating solutions often generalize well to new test data beyond the training dataset.

The observation that overparameterized models interpolate noise and yet generalize well was first elucidated in pioneering experiments by Neyshabur et al. (2014); Zhang et al. (2017). These findings sparked widespread conversation across deep learning practitioners and theorists, and inspired several new research directions in deep learning theory. However, meaningful progress in understanding the inner workings of overparameterized DNNs has remained elusiveFor example, the original paper (Zhang et al., 2017) now appears in a 2021 version of Communications of the ACM (Zhang et al., 2021). The latter survey highlights that almost all of the questions posed in the original paper remain open. owing to their multiple challenging aspects. Indeed, the way for recent TOPML research was largely paved by the discovery of similar empirical behavior in far simpler parametric model families (Belkin et al., 2019a; Geiger et al., 2020; Spigler et al., 2019; Advani et al., 2020).

In particular, Belkin et al. (2019a); Spigler et al. (2019) explicitly evaluated the test error of these model families as a function of the number of tunable parameters and showed that it exhibits a remarkable double descent behavior (pictured in Figure 1). The first descent occurs in the underparameterized regime and is a consequence of the classical bias–variance tradeoff; indeed, the test error peaks when the learned model first becomes sufficiently complex to interpolate the training data. More unusual is the behavior in the overparameterized regime: there, the test error is observed to decrease monotonically with the number of parameters, forming the second descent in the double descent curve. The double descent phenomenon suggests that the classical bias–variance tradeoff, a cornerstone of conventional ML, is predictive only in the underparameterized regime where the learned model is not sufficiently complex to interpolate the training data. A fascinating implication of the double descent phenomenon is that the global minimum of the generalization error can be achieved by a highly overparameterized model even without explicit regularization, and despite perfect fitting of noisy training data.

In this paper, we survey the emerging field of TOPML research with a principal focus on foundational principles developed in the past few years. Compared to other recent surveys (Bartlett et al., 2021; Belkin, 2021), we take a more elementary signal processing perspective to elucidate these principles. Formally, we define the TOPML research area as the sub-field of ML theory where

there is clear consideration of exact or near interpolation of training data

the learned model complexity is high with respect to the training dataset size. Note that the complexity of the learned model is typically affected by (implicit or explicit) regularization aspects as a consequence of the learning process.

Importantly, this definition highlights that while TOPML was inspired by observations in deep learning, several aspects of deep learning theory do not involve overparameterization. More strikingly, TOPML is relevant to diverse model families other than DNNs.

The first studies of TOPML were conducted for the linear regression task; accordingly, much of our treatment centers around a comprehensive survey of overparameterized linear regression. However, TOPML goes well beyond the linear regression task. Overparameterization naturally arises in diverse ML tasks, such as classification (e.g., Muthukumar et al., 2020a), subspace learning for dimensionality reduction (Dar et al., 2020), data generation (Luzi et al., 2021), and dictionary learning for sparse representations (Sulam et al., 2020). In addition, overparameterization arises in various learning settings that are more complex than elementary fully supervised learning: unsupervised and semi-supervised learning (Dar et al., 2020), transfer learning (Dar and Baraniuk, 2020), pruning of learned models (Chang et al., 2021), and others. We also survey recent work in these topics.

This paper is organized as follows. In Section 2 we introduce the basics of interpolating solutions in overparameterized learning, as a machine learning domain that is outside the scope of the classical bias–variance tradeoff. In Section 3 we overview recent results on overparameterized regression. Here, we provide intuitive explanations of the fundamentals of overparameterized learning by taking a signal processing perspective. In Section 4 we review the state-of-the-art findings on overparameterized classification. In Section 5 we overview recent work on overparameterized subspace learning. In Section 6 we examine recent research on overparameterized learning problems beyond regression and classification. In Section 7 we discuss the main open questions in the theory of overparameterized ML.

Beyond the classical bias–variance tradeoff: The realm of interpolating solutions

where ${\epsilon\sim P_{\epsilon}}$ is a scalar-valued noise term that has zero mean and variance $\sigma_{\epsilon}^{2}$. Moreover, the noise $\epsilon$ is also independent of the input $\mathbf{x}\sim P_{\mathbf{x}}$.

The input vector can be perceived as a random vector $\mathbf{x}\sim P_{\mathbf{x}}$ that, together with the unknown mapping $f_{\sf true}$ and the relevant noise model, induces a probability distribution $P_{\mathbf{x},y}$ over ${\mathcal{X}\times\mathcal{Y}}$ for the input-output pair $(\mathbf{x},y)$. Moreover, the $n$ training examples $\{(\mathbf{x}_{i},y_{i})\}_{i=1}^{n}$ in ${\mathcal{D}}$ are usually considered to be i.i.d. random draws from $P_{\mathbf{x},y}$.

where $\widehat{f}$ denotes the mapping with minimal training error among the constrained set of mappings $\mathcal{F}$. The generalization performance of a mapping $f$ is evaluated using the test error

where $(\mathbf{x},y)\sim P_{\mathbf{x},y}$ are random test data. The best generalization performance corresponds to the lowest test error, which is achieved by the optimal mapping

Note that the optimal mapping as defined above does not posit any restrictions on the function class. If the solution space $\mathcal{F}$ of the constrained optimization problem in (4) includes the optimal mapping $f_{\sf opt}$, the learning architecture is considered as well specified. Otherwise, the training procedure cannot possibly induce the optimal mapping $f_{\sf opt}$, and the learning architecture is said to be misspecified.

Above, the squared bias term is defined as

which is the expected squared difference between the estimates produced by the learned and the optimal mappings (where the learned estimate is under expectation with respect to the training dataset). For several popular estimators used in practice such as the least squares estimator (which is, in fact, the maximum likelihood estimator under Gaussian noise), the expectation of the estimator is equal to the best fit of the data within the class of mappings $\mathcal{F}$; therefore, the bias can be thought of in these simple cases as the approximation-theoretic gap between the performance achieved by this best-in-class model and the optimal model given by $f_{\sf opt}(\cdot)$. The variance term is defined as

which reflects how much the estimate can fluctuate due to the dataset used for training. The irreducible error term is defined as

which quantifies the portion of the test error that does not depend on the learned mapping (or the training dataset). The model in (2) implies that $f_{\sf opt}=f_{\sf true}$ and ${\mathcal{E}_{\sf irred}}=\sigma_{\epsilon}^{2}$.

The test error decomposition in (7) demonstrates a prominent concept in conventional statistical learning: the bias-variance tradeoff as a function of the “complexity” of the function class (or set of mappings) $\mathcal{F}$. The idea is that increased model complexity will decrease the bias, as better approximations of $f_{\sf opt}(\cdot)$ can be obtained; but will increase the variance, as the magnitude of fluctuations around the best-in-class model increase. Accordingly, the function class $\mathcal{F}$ is chosen to minimize the sum of the bias (squared) and its variance; in other words, to optimize the bias-variance tradeoff. Traditionally, this measure of complexity is given by the number of free parameters in the modelThe number of free parameters is an intuitive measure of the worst-case capacity of a model class, and has seen fundamental relationships with model complexity in learning theory (Vapnik, 2013) and classical statistics (Akaike, 1998) alike. In the absence of additional structural assumptions on the model or data distribution, this capacity measure is tight and can be matched by fundamental limits on performance. There are several situations in which the number of free parameters is not reflective of the true model complexity that involve additional structure posited both on the true function (Candès et al., 2006; Bickel et al., 2009) and the data distribution (Bartlett et al., 2005). As we will see through this paper, these situations are intricately tied to the double descent phenomenon.. In the underparameterized regime, where the learned model complexity is insufficient to interpolate the training data, this bias-variance tradeoff is ubiquitous in examples across model families and tasks. However, as we will see, the picture is significantly different in the overparameterized regime where the learned model complexity is sufficiently high to allow interpolation of training data.

On the other hand, as we will now see, the examples differ in their composition of feature map as well as the relationship between the input dimension $d$ and the feature dimension $p$.

Here, $\mathbf{\Phi}$ is the $n\times p$ matrix whose $(i,j)$ entry is given by $\mathbf{u}_{j}^{T}\mathbf{x}_{i}$, and the training data output is given by the $n$-dimensional vector ${\mathbf{y}\triangleq[y_{1},\dots,y_{n}]^{T}}$.

Here, ${\mathbf{\Phi}}$ is the $n\times p$ matrix whose $(i,j)$ entry is given by $\varphi_{j}(\mathbf{x}_{i})$, and the training data output is given by the $n$-dimensional vector ${\mathbf{y}\triangleq[y_{1},\dots,y_{n}]^{T}}$.

2 The double descent phenomenon

Figure 2 studies the relationship between model complexity (in number of parameters) and test error induced by linear regression with a linear feature map (in line with Example 2.1). For both experiments, we set $d=128$ and $n=32$, and vary the number of parameters $p$ to be between $1$ and $d$. We also consider $\boldsymbol{\beta}$ to be an approximately $20$-sparse parameter vector such that the majority of its energy is contained in the first $20$ discrete cosine transform (DCT) features (see Figure 2 for an illustration). The input data covariance matrix $\mathbf{\Sigma}_{\mathbf{x}}$ is also considered to be anisotropic, as pictured in the heatmap of its values in Figure 2.

The second choice of the Hadamard basis also gives rise to a double descent behavior, but is quite different both qualitatively and quantitatively. The feature space utilized for learning (the Hadamard basis) is fundamentally mismatched to the feature space in which the original parameter vector $\boldsymbol{\beta}$ is sparse (the DCT basis). Consequently, as seen in Figure 2, the energy of the true parameter vector $\boldsymbol{\beta}$ is spread over the $d$ Hadamard features in an unorganized manner. Moreover, the covariance matrix of Hadamard features, depicted as a heat-map in Figure 2, is significantly more correlated and dispersed in its structure. Figure 2 displays a stronger benefit of overparameterization in this model owing to the increased model misspecification arising from the choice of Hadamard feature map. Unlike in the well-specified case of DCT features, the overparameterized regime significantly dominates the underparameterized regime in terms of test performance.

Finally, the results in Fig. 3 correspond to $\boldsymbol{\beta}$ that its components are shown in Fig. 3 and its DCT-domain representation is presented in Fig. 3. The majority of $\boldsymbol{\beta}$’s energy is in a mid-range “feature band” that includes the 18 DCT features at coordinates $j=21,\dots,38$; in addition, there are two more high-energy features in coordinates $j=1,2$, and the remaining coordinates are of low energy (see Fig. 3). The input covariance matrix $\mathbf{\Sigma}_{\mathbf{x}}$, presented in Fig. 3, is the same as before (i.e., the majority of input feature variances is located at the first 20 DCT features). Therefore, when using a function class $\mathcal{F}_{p}^{\sf lin}$ with DCT features (see results in the second row of subfigures of Fig. 3), there is a mismatch between the “feature bands” that contain the majority of $\boldsymbol{\beta}$’s energy and the majority of input variances. This situation leads to the error curves presented in Fig. 3, where double descent of test errors occurs, but the global minimum of test error is not achieved by an interpolating solution. This will be explained in more detail below.

3 Why is double descent a surprise?

As a consequence of the classical bias-variance tradeoff, the test error as a function of the number of parameters forms a U-shaped curve in the underparameterized regime. For example, Fig. 2 depicts this U-shaped curve in the underparameterized range of solutions $p<n$, i.e., to the left of the interpolation threshold (vertical dotted line at $p=n=32$). This classical bias-variance tradeoff is usually induced by two fundamental behaviors of non-interpolating solutions:

The bias term usually decreases because the optimal mapping $f_{\sf opt}$ can be better approximated by classes of mappings $\mathcal{F}$ that are more complex. In other words, models with more parameters or less regularization typically result in a lower (squared) bias component in the test error decomposition (7). As an example, see the red dashed curve to the left of the interpolation threshold in Fig. 2.

The variance term usually increases because classes of mapping $\mathcal{F}$ that are of higher complexity result in higher sensitivity to (or variation with respect to) the noise in the specific training dataset $\mathcal{D}$. Note that such noise can arise due to stochastic measurement errors and/or model misspecification (see, e.g., Rao, 1971). In other words, models with more parameters or less regularization typically result in a higher variance component in the test error decomposition (7). As an example, see the magenta dashed curve to the left of the interpolation threshold in Fig. 2.

4 The role of model misspecification in beneficial interpolation

where the second equality is due to the orthogonality of the basis vectors $\{\mathbf{u}_{j}\}_{j=1}^{d}$. We can notice the difference between the optimal solution $f_{{\sf opt},\mathcal{F}_{p}^{\sf lin}}$ in ${\mathcal{F}_{p}^{\sf lin}(\{\mathbf{u}_{j}\}_{j=1}^{d})}$ and the unconstrained optimal solution $f_{\sf opt}$ as follows. Note that $\mathbf{U}_{p}\mathbf{U}_{p}^{T}$ in (17) is the projection matrix onto the $p$-dimensional feature space that is utilized for learning and spanned by the $p$ orthonormal vectors $\{\mathbf{u}_{j}\}_{j=1}^{p}$. Hence, unless both $\boldsymbol{\beta}$ and the entire distribution of $\mathbf{x}$ are contained in the $p$-dimensional feature space, there is misspecification that excludes the optimal solution $f_{\sf opt}$ from the function class ${\mathcal{F}_{p}^{\sf lin}(\{\mathbf{u}_{j}\}_{j=1}^{d})}$.

Consider cases where the features are statistically independent (e.g., the above example with DCT features and Gaussian input with covariance matrix that is diagonalized by the DCT matrix). These cases let us to further emphasize the effect of misspecification on the bias and variance of the learned solution from ${\mathcal{F}_{p}^{\sf lin}(\{\mathbf{u}_{j}\}_{j=1}^{d})}$. The important observation here is that the data model ${y=\mathbf{x}^{T}\boldsymbol{\beta}+\epsilon}$ can be written as

where $\boldsymbol{\phi}=\mathbf{U}_{p}^{T}\mathbf{x}$ is the $p$-dimensional feature vector of the input, and ${\xi\triangleq\sum_{j=p+1}^{d}{\left(\mathbf{u}_{j}^{T}\mathbf{x}\right)\left(\mathbf{u}_{j}^{T}\boldsymbol{\beta}\right)}}$ is a random variable which is statistically independent of the feature vector $\boldsymbol{\phi}$. We consider zero-mean Gaussian input $\mathbf{x}$, here, with covariance matrix ${\mathbf{\Sigma}_{\mathbf{x}}=\mathbf{U}\mathbf{\Lambda}_{\mathbf{x}}\mathbf{U}^{T}}$. Hence, the misspecification variable $\xi$ is also zero-mean Gaussian but with variance

which sums over the $d-p$ feature directions that are not utilized in the $p$-dimensional feature space of ${\mathcal{F}_{p}^{\sf lin}(\{\mathbf{u}_{j}\}_{j=1}^{d})}$.

We define the misspecification bias (squared) as

namely, the expected squared difference between the optimal solution in the function class ${\mathcal{F}_{p}^{\sf lin}(\{\mathbf{u}_{j}\}_{j=1}^{d})}$ and the optimal unconstrained solution. We also define the in-class bias (squared) as

which is the expected squared difference between the learned solution (expected over the training dataset) and the optimal solution in the function class ${\mathcal{F}_{p}^{\sf lin}(\{\mathbf{u}_{j}\}_{j=1}^{d})}$ that was utilized for learning. Now, based on the orthogonality of the feature maps that form ${\mathcal{F}_{p}^{\sf lin}(\{\mathbf{u}_{j}\}_{j=1}^{d})}$ and considering cases where the features are statistically independent, we can decompose the squared bias from (8) as

which can be further set in the test error decomposition in (7). More specifically, the definition of ${\mathcal{F}_{p}^{\sf lin}(\{\mathbf{u}_{j}\}_{j=1}^{d})}$ in Example 2.1 implies that

which is the variance (19) of the misspecification variable $\xi$.

Still considering statistically independent features, we can also decompose the variance term (9) to express its portion due to misspecification in ${\mathcal{F}_{p}^{\sf lin}(\{\mathbf{u}_{j}\}_{j=1}^{d})}$. We can write the variance decomposition as

Here, the variance component due to misspecification is

where $\mathbf{\Phi}=\mathbf{X}\mathbf{U}_{p}$ is the $n\times p$ matrix of training input features, and $\mathbf{\Lambda}_{\mathbf{x},p\times p}$ is the $p\times p$ diagonal matrix with input covariance eigenvalues $\lambda_{1},\dots,\lambda_{p}$. The in-class variance component ${\sf var}_{\sf inclass}(\widehat{f})$ has a bit more intricate formulation that we exclude from this discussion. Hastie et al. (2019) further assume that the input and the true parameter vector are both isotropic random vectors and, accordingly, provide a simple formulation for the in-class variance term in their setting.

Let us return to the example given in Fig. 2 for regression with DCT features that are statistically independent due to the covariance form of the Gaussian input. This setting allows us to demonstrate the misspecification components of the bias and variance from (23) and (25). Figure 4 extends Fig. 2 by illustrating the misspecification and in-sample components of the bias and variance versus the number of parameters $p$ in the function class. Indeed, the misspecification bias decreases as the function class is more parameterized. In contrast, the in-class bias is zero in the underparameterized regime, and increases with $p$ in the overparameterized regime. Yet, the reduction in the misspecification bias due to overparameterization is more significant than the corresponding increase in the in-sample bias; and this is in accordance with having the global minimum of test error in the overparameterized range. We can observe that both the in-class and misspecification variance terms peak around the interpolation threshold (i.e., $p=n$) due to the poor conditioning of the input feature matrix. Based on the structure of the true parameter vector (see Fig. 2), the significant misspecification occurs for $p<20$ and this is apparent for the misspecification components of both the bias and variance.

More generally than the case of statistically independent features, the examples in Figures 2-3 include misspecification for any $p<d$. This is because, for both DCT and Hadamard features, the representation of the true parameter vector $\boldsymbol{\beta}$ requires all the $d$ features (see Figures 2,2,3). Learning using DCT features benefits from the fact that $\boldsymbol{\beta}$ has energy compaction in the DCT domain, which in turn significantly reduces the misspecification bias for $p$ that is large enough to include the majority of $\boldsymbol{\beta}$’s energy. In contrast, in the case of learning using the Hadamard features, the representation of $\boldsymbol{\beta}$ in the feature space has its energy spread randomly all over the features, without energy compaction, and therefore the effect of misspecification is further amplified in this case. The amplified misspecification due to a poor selection of feature space actually promotes increased benefits from overparameterization (compared to underparameterized solutions, which are extremely misspecified) as can be observed in Fig. 2.

The in-depth experiments and explanation above illustrate the rich variety of generalization behaviors even in elementary settings. Understanding these behaviors requires mathematical study beyond the fundamental discussion in this section. In the next section, we review recently conducted mathematical studies on this topic, and illuminate the core phenomena that explain generalization behavior in this interpolating regime.

Overparameterized regression

A signal-dependent term, which expresses how much error is incurred by a solution that interpolates the noiseless version of our (noisy) training data.

A noise-dependent term, which expresses how much error is incurred by a solution that interpolates only the noise in our training data.

Situations that adequately tradeoff these terms give rise to the double descent behavior, and can be described succinctly for several families of linear models. We will now describe these results in more detail.

We can state the diversity of results by Belkin et al. (2020); Bartlett et al. (2020); Hastie et al. (2019); Kobak et al. (2020); Muthukumar et al. (2020b); Mitra (2019) in a common framework by decomposing the test error incurred by the MNI, denoted by $\widehat{\boldsymbol{\alpha}}$, into the respective test errors that would be induced by two related solutions. To see this, consider the noisy data model (2) with scalar output, and note that the MNI from (16) satisfies $\widehat{\boldsymbol{\alpha}}=\widehat{\boldsymbol{\alpha}}_{\sf{sig}}+\widehat{\boldsymbol{\alpha}}_{\sf{noise}}$ where

Then, a typical decomposition of an upper bound on the test error is given by

where ${\mathcal{E}_{\sf test,sig}}$ is a signal specific component that is determined by the noiseless data interpolator $\widehat{\boldsymbol{\alpha}}_{\sf{sig}}$; and ${\mathcal{E}_{\sf test,noise}}$ is a noise specific component that is determined by the pure noise interpolator $\widehat{\boldsymbol{\alpha}}_{\sf{noise}}$. Moreover, we can typically lower bound the test error as ${\mathcal{E}_{\sf test}}\geq\max\{{\mathcal{E}_{\sf test,sig}},{\mathcal{E}_{\sf test,noise}}\}$; therefore, this decomposition is sharp in a certain sense.

For simplicity, we summarize recent results from the literature in the non-asymptotic setting, i.e., error bounds that hold for finite values of $n$,$p$ and $d$ (in addition to their infinite counterparts). Accordingly, we characterize the behavior of the test error (and various factors influencing it) as a function of the parameters $n,p,d$ using two types of notation. First, considering an arbitrary function $h(\cdot,\cdot,\cdot)$, we will use ${{\mathcal{E}_{\sf test}}=\mathcal{O}(h(n,p,d))}$ to mean that there exists a universal constant $C>0$ such that ${\mathcal{E}_{\sf test}}\leq Ch(n,p,d)$ for all $n,p,d$. Second, we will use ${\mathcal{E}_{\sf test}}=\Theta(h(n,p,d))$ to mean that there exist universal constants ${c,C>0}$ such that ${ch(n,p,d)\leq{\mathcal{E}_{\sf test}}\leq Ch(n,p,d)}$ for all $n,p,d$. Moreover, the bounds that we state typically hold with high probability over the training data, in the sense that the probability that the upper bound holds goes to $1$ as $n\to\infty$ (and $p,d\to\infty$ with the desired proportions with respect to $n$ in order to maintain overparameterization).

We begin by focusing on the contribution to the upper bound on the test error that arises from a fit of pure noise, i.e., ${\mathcal{E}_{\sf test,noise}}$, and identifying necessary and sufficient conditions under which this error is sufficiently small. We will see that these conditions, in all cases, reduce to a form of high “effective overparameterization” in the data relative to the number of training examples (in a sense that we will define shortly). In particular, these results can be described under the following two particular models for the feature covariance matrix $\mathbf{\Sigma}_{\boldsymbol{\phi}}$:

The simplest result to obtain is in the case of isotropic covariance, for which $\mathbf{\Sigma}_{\boldsymbol{\phi}}=\mathbf{I}_{p}$. For instance, this case occurs when the feature maps in Example 2.1 are applied on input data $\mathbf{x}$ with isotropic covariance matrix $\mathbf{\Sigma}_{\mathbf{x}}=\mathbf{I}_{d}$. If the features are also statistically independent (e.g., consider Example 2.1 with isotropic Gaussian input data), the results by Bartlett et al. (2020); Hastie et al. (2019); Muthukumar et al. (2020b) imply that the noise error term scales as

where $\sigma_{\epsilon}^{2}$ denotes the noise variance. The result in (27) displays an explicit benefit of overparameterization in fitting noise in a harmless manner. In more detail, this result is (i) a special case of the more general (non-asymptotic) results for arbitrary covariance by Bartlett et al. (2020), (ii) one of the closed-form precise asymptotic results presented as $n,p\to\infty$ by Hastie et al. (2019), and (iii) a consequence of the more general characterization of the minimum-risk interpolating solution, or “ideal interpolator”, derived by Muthukumar et al. (2020b).

On the other hand, the signal error term can be bounded as

displaying an explicit harm in overparameterization from the point of view of signal recovery. In more detail, this result is (i) a non-asymptotic upper bound provided by Bartlett et al. (2020) (and subsequent work by Tsigler and Bartlett (2020) shows that this term is matched by a sharp lower bound), (ii) precise asymptotics provided by Hastie et al. (2019).

As discussed later in Section 3.1.2, the behavior of ${\mathcal{E}_{\sf test,sig}}$ has negative implications for consistency in a certain high-dimensional sense. Nevertheless, the non-asymptotic example in Figure 5 shows that one can construct signal models with isotropic covariance that can benefit from overparameterization. Such benefits are partly due to the harmless interpolation of noise, and partly due to a decrease in the misspecification error arising from increased overparameterization.

The general case of anisotropic covariance and features that are independent in their principal component basis is significantly more complicated. Nevertheless, it turns out that a high amount of “effective overparameterization” can be defined, formalized, and shown to be sufficient and necessary for interpolating noise in a harmless manner. This formalization was pioneeredAsymptotic (not closed-form) results are also provided by the concurrent work of Hastie et al. (2019). These asymptotics match the non-asymptotic scalings provided by Bartlett et al. (2020) for the case of the spiked covariance model and Gaussian features in the regime where $p/n=\gamma>1$. These results can also be used to recover in part the benign overfitting results as shown by Bartlett et al. (2021). Muthukumar et al. (2020b) recover these scalings in a toy Fourier feature model through elementary calculations that will be reviewed in Section 3.2 using cosine features. by Bartlett et al. (2020), who provide a definition of effective overparameterization solely as a function of $n$, $p$ and the spectrum of the covariance matrix $\mathbf{\Sigma}_{\boldsymbol{\phi}}$, denoted by the eigenvalues ${\lambda_{1}\geq\ldots\geq\lambda_{p}}$. We refer the reader to Bartlett et al. (2021) for a detailed exposition of these results and their consequences. Here, we present the essence of these results in a popular model used in high-dimensional statistics, the spiked covariance model. Under this model (recall that $p>n$), we have a feature covariance matrix $\mathbf{\Sigma}_{\boldsymbol{\phi}}$ with ${s<p-n}$ high-energy eigenvalues and ${p-s}$ low-energy (but non-zero) eigenvalues. In other words, ${\lambda_{1}\geq\ldots\geq\lambda_{s}=\lambda_{H}}$ and ${\lambda_{s+1}=\ldots=\lambda_{p}=\lambda_{L}}$ for some ${\lambda_{H}\gg\lambda_{L}}$ (for example, notice that Figure 2 is an instance of this model). In this special case, the results of Bartlett et al. (2020) can be simplified to show that the test error arising from overfitting noise is given by

Equation (29) demonstrates a remarkably simple set of sufficient and necessary conditions for harmless interpolation of noise in this anisotropic ensemble:

The number of high-energy directions, given by $s$, must be significantly smaller than the number of samples $n$.

The number of low-energy directions, given by $p-s$, must be significantly larger than the number of samples $n$. This represents a requirement for sufficiently high “effective overparameterization” to be able to absorb the noise in the data, and fit it in a relatively harmless manner.

Interestingly, the work of Kobak et al. (2020) considered the above anisotropic model for the special case of a single spike (i.e., for $s=1$, which usually implies that the first condition is trivially met) and showed that the error incurred by interpolation is comparable to the error incurred by ridge regression. These results are related in spirit to the above framework, and so we can view the conditions derived by Bartlett et al. (2020) as sufficient and necessary for ensuring that interpolation of (noisy) training data does not lead to sizably worse performance than ridge regression. Of course, good generalization of ridge regression itself is not always a given (in particular, it generalizes poorly for isotropic models). In this vein, the central utility of studying this anisotropic case is that it is now possible to also identify situations under which the test error arising from fitting pure signal, i.e., ${\mathcal{E}_{\sf test,sig}}$, is sufficiently small. We elaborate on this point next.

These negative results make clear that anisotropy of features is required for the signal-specific error term ${\mathcal{E}_{\sf test,sig}}$ to be sufficiently small; in fact, this is the main reason for the requirement that $\lambda_{H}\gg\lambda_{L}$ in the spiked covariance model to ensure good generalization in regression tasks. In addition to this effective low dimensionality in data, we also require a low-dimensional assumption on the signal model. In particular, the signal energy must be almost entirely aligned with the directions (i.e., eigenvectors) of the top $s\ll n$ eigenvalues of the feature covariance matrix (representing high-energy directions in the data). Finally, we note as a matter of detail that the original work by Bartlett et al. (2020) precisely characterizes the contribution from ${\mathcal{E}_{\sf test,noise}}$ upto constants independent of $p$ and $n$; however, they only provide upper bounds on the bias term. In follow-up work, Tsigler and Bartlett (2020) provide more precise expressions for the bias that show that the bias is non-vanishing in “tail” signal components outside the first $s$ “preferred” directions. Their upper and lower bounds match up to a certain condition number. The follow-up studies by Mei and Montanari (2019); Liao et al. (2020); Derezinski et al. (2020); Mei et al. (2021) also provide precise asymptotics for the bias and variance terms in very general random feature models, which can be shown to fall under the category of anisotropic covariance models.

1.3 When does double descent occur?

low-dimensional signal structure, with the non-zero components of the signal aligned with the $s$ eigenvectors corresponding to the highest-value eigenvalues (i.e., high-energy directions in the data)

an overparameterized number of low-value (but non-zero) directions.

Given these pieces, the ingredients for double descent become clear. In addition to the aforementioned signal and noise-oriented error terms in (26), we will in general have a misspecification error term, denoted by ${\mathcal{E}_{\sf test,missp}}$, which will always decrease with overparameterization and therefore further contributes to the double descent phenomenon. For example, recall Section 2.4 and the example in Fig. 4 where the misspecification bias and variance terms decrease with $p$ in the overparameterized range. Optimization aspects can also affect the double descent behavior, for example, D’Ascoli et al. (2020) study the contribution of optimization initialization to double descent phenomena in a lazy training setting (i.e., where the learned parameters are close to their initializations (Chizat et al., 2019)).

Examples of the approximation-theoretic benefits of overparameterization are also provided by Hastie et al. (2019), but these do not go far enough to recover the double descent behavior, as they are still restricted to the isotropic setting in which signal recovery becomes more harmful as the number of parameters increases. Belkin et al. (2020) provided one of the first explicit characterizations of double descent under two models of randomly selected “weak features”. In their model, the $p$ features are selected uniformly at random from an ensemble of $d$ features (which are themselves isotropic in distribution and follow either a Gaussian or Fourier model). This idea of “weak features” is spiritually connected to the classically observed benefits of overparameterization in ensemble models like random forests and boosting, which were recently discussed in an insightful unified manner (Wyner et al., 2017). This connection was first mentioned in Belkin et al. (2019a).

Subsequent to the first theoretical works on this topic, Mei and Montanari (2019) also showed precise asymptotic characterizations of the double descent behavior in a random features model.

2 A signal processing perspective on harmless interpolation

In this section, we present an elementary explanation for harmless interpolation using the concepts of aliasing and Parseval’s theorem for a “toy” case of overparameterized linear regression with cosine features on regularly spaced, one-dimensional input data. This elementary explanation was first introduced by Muthukumar et al. (2020b), and inspired subsequent work for the case of classification (Muthukumar et al., 2020a). While this calculation illuminates the impact of interpolation in both isotropic and anisotropic settings, we focus here on the isotropic case for simplicity.

This toy setting can be perceived as a special case of Example 2.2 with one-dimensional input and cosine feature maps. Note that our example for real-valued cosine feature maps differs in some low-level mathematical details compared to the analysis originally given by Muthukumar et al. (2020b) for Fourier features.

Throughout this example, we will consider $p$ to be an integer multiple of $n$. We also consider one-dimensional data $x\in$ and a family of cosine feature maps ${\varphi_{j}(x)=\kappa_{j}\cos((j-1)\pi x),~{}j=1,\dots,\infty}$, where the normalization constant $\kappa_{j}$ equals $1$ for $j=1$ and $\sqrt{2}$ for $j\geq 2$. Then, the $p$-dimensional cosine feature vector is given by

This is clearly an orthonormal, i.e., isotropic feature family in the sense that

where $\delta_{jk}$ denotes the Kronecker delta. Furthermore, in this “toy” model we assume $n$-regularly spaced training data points, i.e., ${x_{i}=\frac{i-\frac{1}{2}}{n}}\text{ for }i=1,\ldots,n$. While the more standard model in the ML setup would be to consider $\{x_{i}\}_{i=1}^{n}$ to be i.i.d. draws from the input distribution (which is uniform over $$in this example), the toy model with deterministic, regularly-spaced$\{x_{i}\}_{i=1}^{n}$ will yield a particularly elementary and insightful analysis owing to the presence of exact aliases.

In the regime of overparameterized learning, we have $p>n$. The case of regularly-spaced training inputs allows us to see overparameterized learning as reconstructing an undersampled signal: the number of samples (given by $n$) is much less than the number of features (given by $p$). Thus, the undersampling perspective implies that aliasing, in some approximateThe reason that this statement is in an approximate sense in practice is because the training data is typically random, and we can have a wide variety of feature families. sense, is a core issue that underlies model behavior in overparameterized learning . We illustrate this through Example 3.1, which is an idealized toy model and a special case of Example 2.2.

In the discussion below, we will consider (30) in both noisy and noiseless settings (where $\epsilon_{i}=0$ in the latter case). To demonstrate clearly the concept of aliasing, suppose the true signal is

i.e., a single cosine function whose frequency is determined by an integer ${k\in\{1,\dots,n-1\}}$. We start by considering the noiseless version of (30), which we illustrate in Figure 7. (Note that in this figure the true signal and the training data points are presented as blue curve and black circle markers, respectively.) Then, a trivial estimate that interpolates all the training data points is the unnormalized $(k+1)^{\rm th}$ cosine function: ${f_{{\sf alias},0}(x)=\frac{1}{\sqrt{2}}\varphi_{k+1}(x)=\cos(k\pi x)}$. Yet, $f_{{\sf alias},0}(x)$ is not the only interpolating estimate that relies on a single cosine function. Recall that in Example 3.1 we assume $p/n$ to be an integer. Then, using periodicity and other basic properties of cosine functions, one can prove that there is a total of $N_{\sf alias}\triangleq\frac{p}{n}$ estimates (each in a form of a single cosine function from $\varphi_{j}(x)$, $j=1,\dots,p$) that interpolate the training data over the grid $x_{i}=\frac{i-\frac{1}{2}}{n}$, $i=1,\dots,n$. Specifically, one subset of single-cosine interpolating estimates is given by

and the second subset of single-cosine interpolating estimates is given by

Then, using Parseval’s theorem on the learned function form from (11) we get

the observation of double descent with this solution in particular, and

its connection to minimum Hilbert-norm interpolation via kernel machines (Schölkopf et al., 2002).

Overparameterized classification

The basic regression task highlighted two central questions regarding the success of overparameterized models in practice: a) when and why there is a benefit to adding more parameters? and b) why interpolating noise need not cause harmful overfitting? However, most of the empirical success of neural networks are documented for classification tasks, which pose their own intricacies and challenges. Accordingly, in this section we review answers to these questions in the context of classification problems.

A benefit of overparameterization in classification problems was observed well before the recently discovered double descent phenomenon. In fact, this was observed classically in the case of boosting: adding more weak learners led to better generalization empirically (Drucker and Cortes, 1996; Breiman, 1996). An insightful piece of work by Schapire et al. (1998) provided a candidate explanation for this behavior: they showed that the training data margin, roughly the minimum distance to the decision boundary of any training data point, increases as more parameters are added into the model. Intuitively, an increased training data margin means that points are classified with higher confidence, and should lead to better generalization guarantees. More formally, generalization bounds that scale inversely with the margin (which is a training-data dependent quantity) and directly proportional to the Rademacher complexity (which is a parameter-dependent quantity, and is typically small for low norm solutions) can explain good generalization for classification in some cases of overparameterization, where the “effective dimension” (as we discussed for the anisotropic case in Section 3.1.1) is sufficiently small with respect to $n$ and there is no label noise in the data. In fact, these techniques can be used to explain the good generalization behavior of deep neural networks possessing a low spectral norm (Bartlett, 1998; Bartlett et al., 2017).

These types of generalization bounds, coupled with the by now well-known implicit bias of first-order methods such as gradient descent towards the max-margin SVM (Soudry et al., 2018; Ji and Telgarsky, 2019), are often touted as an explanation for the benefit of overparameterization and harmlessness of “interpolation” in the sense that these solutions obtain zero training error on the logistic/cross-entropy loss. However, these data-dependent bounds are far from universally accepted to fully explain the good generalization behavior of overparameterized neural networks; several recent works (Dziugaite and Roy, 2017; Nagarajan and Kolter, 2019) show that they fall short empirically of explaining good generalization behavior. In fact, predicting good generalization behavior in practice was listed as a NeurIPS 2020 challenge (Jiang et al., 2020). Theoretically as well, there are several missing gaps that these techniques do not fill. For example, while the margin can trivially be shown to increase as a function of overparameterization, quantitative rates on this increase do not exist and in general are difficult to show. Even in the classic case of boosting, the worst-case training data margin could be a too pessimistic measure: perhaps average-case margins do a better job in explaining good generalization behavior (Gao and Zhou, 2013; Banburski et al., 2021).

In the simplest cases of linear and kernel methods, the margin-based bounds can be shown to fall short from explaining this good generalization behavior in a number of ways. a) they cannot explain good generalization behavior of the SVM in the presence of non-zero label noise (as noted by Belkin et al. (2018b)), and b) they are tautological when the number of independent degrees of freedom in the data (or the “effective dimension”) exceeds the number of samples. While this case may appear prohibitive for generalization, the concurrent work of Muthukumar et al. (2020a); Chatterji and Long (2021) showed that there are indeed intermediate ultra high-dimensional regimes in which classification can generalize well (but in fact regression does not work). See Bartlett and Long (2020) for a formal description of these shortcomings not only of margin-based bounds, but all possible bounds that are functionals of the training dataset.

In summary, we see that despite the elegance and attractive generality of these classic data-dependent bounds, they fail to explain at least two types of good generalization behavior in overparameterized regimes with noisy training data. An alternative avenue of analysis involves leveraging the recently developed techniques for the case of regression to bring to bear on the technically more complex classification task. As we will recap below, this avenue has yielded sizable dividends in resolving the above questions for linear and kernel methods.

2 Double descent and harmless interpolation

3 Beyond regression

Recall that we needed two ingredients for benign overfitting in linear regression: a) sufficiently low bias (which required low effective dimension in data), and b) sufficiently low interpolation error (which required infinitely many low-energy directions in data compared to the number of samples). The above analyses essentially show that benign overfitting will also occur for a classification task under these assumptions. However, we can go significantly further and identify a strictly broader class of regimes under which classification will generalize even when regression may not in overparameterized regimes. This insight started with the concurrent works of Muthukumar et al. (2020a); Chatterji and Long (2021) and has been expanded and improved upon in subsequent work (Wang and Thrampoulidis, 2021; Wang et al., 2021; Cao et al., 2021).

Subspace learning for dimensionality reduction

Initial research on interpolating solutions focused on the supervised learning paradigm of regression and classification tasks. In this section, we overview recent results on interpolation phenomena in unsupervised and semi-supervised settings for subspace learning tasks.

The study by Dar et al. (2020) on overparameterized subspace learning was one of the first to explore interpolation phenomena beyond the realm of regression and classification. Dar et al. (2020) start from considering an overparameterized version of a linear subspace fitting problem, which is commonly addressed via principal component analysis (PCA) of the training data. Recall that PCA is an unsupervised task, in contrast to the supervised nature of regression and classification. Let us examine the following non-asymptotic setting in which the learned subspace can interpolate the training data.

The input is a $d$-dimensional random vector $\mathbf{x}$ that satisfies the following model

where $\mathbf{B}_{m}$ is a $d\times m$ real matrix with orthonormal columns, $\mathbf{z}\sim\mathcal{N}(\mathbf{0},\mathbf{I}_{m})$ is a random latent vector of dimension $m$, and $\boldsymbol{\epsilon}\sim\mathcal{N}(\mathbf{0},\sigma_{\epsilon}^{2}\mathbf{I}_{d})$ is a $d$-dimensional noise vector independent of $\mathbf{z}$. The training dataset $\mathcal{D}=\{\mathbf{x}_{i}\}_{i=1}^{n}$ includes $n$ i.i.d. draws of $\mathbf{x}$ after centering with respect to their sample mean. The training examples from $\mathcal{D}$ are also organized as the rows of the $n\times d$ matrix $\mathbf{X}$.

We denote the $p$-dimensional feature vector of $\mathbf{x}$ as $\boldsymbol{\phi}\triangleq\mathbf{U}_{p}^{T}\mathbf{x}$ and the training feature matrix as $\mathbf{\Phi}\triangleq\mathbf{X}\mathbf{U}_{p}$. Then, the training optimization procedure

(which aims to minimize the reconstruction error) can be also formulated as the least-squares problem given below as

Note that the formulation in (42) shows that the learning problem can be addressed via PCA of ${\widehat{\mathbf{\Sigma}}_{\boldsymbol{\phi}}\triangleq\frac{1}{n}\mathbf{\Phi}^{T}\mathbf{\Phi}}$, which is the sample covariance matrix of the training features. We denote ${\rho\triangleq{\rm rank}\left\{\widehat{\mathbf{\Sigma}}_{\boldsymbol{\phi}}\right\}\leq n-1}$. If $k\leq\rho$, then $\mathbf{A}_{k}$ is formed by the $k$ principal eigenvectors of $\widehat{\mathbf{\Sigma}}_{\boldsymbol{\phi}}$; otherwise, $\mathbf{A}_{k}$ is formed by the $\rho$ principal eigenvectors of $\widehat{\mathbf{\Sigma}}_{\boldsymbol{\phi}}$ and $k-\rho$ orthonormal vectors that span a $(k-\rho)$-dimensional subspace of the nullspace of $\widehat{\mathbf{\Sigma}}_{\boldsymbol{\phi}}$.

Dar et al. (2020) define two types of overparameterization for PCA-based subspace learning as in Example 5.1, which we demonstrate for DCT features in Figure 8:

A learned linear subspace is overparameterized if $p>n$, i.e., the number of features is larger than the number of training examples. This means that the sample covariance matrix of the (centered) training features is rank deficient, but the learned subspace is not necessarily interpolating in the feature space. In Fig. 8, the domain of overparameterized solutions is located above the black dashed line.

A learned linear subspace is rank overparameterized if it is overparameterized (i.e., ${p>n}$) and its dimension is at least the number of centered training examples (i.e., ${k\geq n}$). This implies that the sample covariance matrix of the training features is rank deficient in a way that introduces degrees of freedom to the construction of the learned subspace. Specifically, the learned subspace interpolates the training data in the $p$-dimensional feature domainA recent study by Zhuo et al. (2021) defines rank overparameterization in matrix sensing problems. However, the rank overparameterization of Zhuo et al. (2021) is not related to interpolation nor the number of training examples, but only means that the solution matrix has a higher rank than the true matrix in the data model. This is in contrast to the rank overparameterization defined by Dar et al. (2020) for studying overparameterization in the sense of interpolating solutions for subspace learning problems.. In Fig. 8, the domain of rank overparameterized solutions is located to the right of the red dashed line.

Interpolating linear subspaces, which are constructed based on PCA, do not exhibit double descent phenomena in their test errors. This is also aligned with earlier analytical results by Paul (2007); Johnstone and Lu (2009); Shen et al. (2016) from the related works in the area of high-dimensional statistics.

2 The effects of orthonormality constraints and supervision levels on double descent phenomena

Motivated by the lack of double descent phenomena in PCA-based subspace learning, Dar et al. (2020) define a new family of subspace learning problems in order to study their generalization behavior in overparameterized settings. This new family of learning problems connects the PCA-based subspace fitting approach (which is unsupervised and has strict orthonormality constraints on the learned matrix columns) and a regression-based approach (which is fully supervised and does not have orthonormality constraints on the learned matrix). Specifically, Dar et al. (2020) define a supervision-orthonormality plane where each coordinate induces a different subspace learning problem with a unique pair of supervision level and orthonormality constraints on the columns of the learned matrix. The supervision levels range from unsupervised to fully supervised through a gradual range of semi-supervised settings with a varying proportion between the input-only and input-output examples in the training dataset. The orthonormality constraints range from strict to unconstrained through a gradual range of soft orthonormality constraints. The softened orthonormality constraint is implemented by extending the function class (38) into the form of

where $\gamma\geq 0$ determines the softness of the orthonormality constraint, and $\sigma_{j}\{\mathbf{A}_{m}\}$ is the $j^{\sf th}$ singular value of $\mathbf{A}_{m}$. Note that the latent dimension $m$ is known due to the availability of true latent vectors $\mathbf{z}$ in the supervised training data. The orthonormality constraints in Equation (5.2) are defined by the size of the interval around 1 that the singular values of the learned matrix are allowed to reside in. The problem is more orthonormally constrained as the singular values are limited to a smaller interval around 1. Specifically, constraining all singular values to 1 provides a solution with orthonormal columns as in Equation (38).

Using this supervision-orthonormality plane, Dar et al. (2020) show that double descent phenomena become more evident as the subspace learning problem is more supervised and less orthonormally constrained. The majority of the problems on the supervision-orthonormality plane do not have closed-form solutions and, therefore, are empirically evaluated using an optimization framework based on projected gradient descent. These results also emphasize the influence of supervision level on generalization behavior under overparameterization, even beyond the scope of subspace learning.

Additional overparameterized learning problems

In this section, we survey recent research on interpolating models in various other modern ML tasks, including data generation, transfer learning, pruning of learned models, and dictionary learning.

Data generation applications aim to produce new instances from a data class that its accurate description is unknown and only a set of its examples are given. Data generation is ubiquitous in deep learning practice, mainly in various architectures that follow the generative adversarial network (GAN) concept (Goodfellow et al., 2014). The idea of a GAN is to jointly train a generator network that produces synthetic instances from the desired class, and a discriminator network that evaluates the generator performance by identifying its synthetic outputs versus true samples from the data class. State-of-the-art practical GANs include highly complex generator and discriminator networks — consequently, understanding overparameterized GANs is a fundamental and important question.

Luzi et al. (2021) provide the first and, to the best of our knowledge, the only explicit study on interpolation phenomena (including double descent) in overparameterized GANs. The study by Luzi et al. (2021) is focused mainly on linear GANs that are overparameterized in the sense that their learned latent dimension is large with respect to the number of examples. This perspective on overparameterized GANs reveals a new behavior of test errors when examined with respect to the learned latent dimension: all interpolating solutions have the same generalization ability, which is often much worse than the best generalization in the non-interpolating (i.e., underparameterized) range of solutions. This theoretical result applies to generative models beyond linear GANs: interpolating solutions generalize equivalently in any generative model that is trained through minimization of a distribution metric or $f$-divergence.

Regardless of interpolation and overparameterization aspects, one can compute the PCA of the given data distribution for training a linear generator with respect to squared error loss, quadratic discriminator and Gaussian data (Feizi et al., 2020). Moreover, extending the unsupervised nature of PCA to include supervised training examples yields double descent phenomena when overparameterization is considered (Dar et al., 2020). Accordingly, Luzi et al. (2021) were motivated to include supervised examples in the training of linear GANs. Truly supervised examples are not realistic due to the need of the true latent representations of the data of interest. Therefore, Luzi et al. (2021) empirically establish the concept of pseudo-supervised training of GANs, which is done by associating the data examples with random latent representations drawn from an isotropic Gaussian distribution. This approach induces test error curves that have double descent and, sometimes, triple descent shapes. More importantly, this pseudo-supervised approach to GAN training was shown to improve generalization performance and to reduce training time, both for linear models with synthetic Gaussian data and for multi-layer nonlinear models with MNIST digit images.

2 Transfer learning

Transfer learning is a popular approach for training a DNN to solve a desired target problem, based on another DNN that was already learned for a related source problem. In practice, one or more layers of the source DNN are transferred to the target DNN and set fixed, finely tuned, or used to initialize a full training process. Provided that the source DNN is adequately trained using a large dataset, such transfer learning helps to address the challenges in training a highly overparameterized target DNN using a relatively smaller amount of data, and possibly faster.

A solid base for a fundamental understanding of transfer learning was recently laid by recent analytical results for transfer learning under linear models (Lampinen and Ganguli, 2019; Dar and Baraniuk, 2020; Obst et al., 2021; Dar and Baraniuk, 2021). The first study on double descent phenomena in transfer learning was provided by Dar and Baraniuk (2020) for a setting of two linear regression problems, where a subset of the target parameters is fixed to values transferred from an already computed least squares solution of the related source task. Dar and Baraniuk (2020) analytically characterized a two-dimensional double descent phenomena of the test error of the target task when evaluated with respect to the number of free parameters in the target and source solutions. They defined a noisy linear model to relate the true parameters of the target and source tasks and showed how the generalization error of the target task is affected by the interplay among the structure of the task relation, layout of the true parameters, and the subset of transferred parameters. Their results describe when parameter transfer is useful, and emphasize a fundamental tradeoff between overparameterized learning and transfer learning. In particular, when the source task solution plays a more significant role in the target task solution it also limits the actual overparameterization level. Thus, the best combination of transfer learning and overparameterization depends on the specific problem setting.

Another analytical study by Dhifallah and Lu (2021) considers transfer learning between two, possibly nonlinear, single-layer models. They examine general convex loss functions that makes their insights relevant to both regression and classification problems. Their transfer learning formulations include ridge regularization and a regularizer on the distance between the target and source task solutions (the second regularizer can be reduced into the particular case where the transferred parameters are set fixed in the target solution). Recall that Dar and Baraniuk (2020) examined transfer learning from a source task that can interpolate its training data, and therefore emphasize how the double descent phenomenon in the source task affect the generalization performance of the target task. In contrast, the focus in Dhifallah and Lu (2021) is on problems that are more regularized, including ridge regularization in the source task solution that prevents it from interpolating its data. The works by Dar and Baraniuk (2020) and Dhifallah and Lu (2021) both consider Gaussian settings and analytically characterize the conditions on the relation between the target and source tasks that yield beneficial transfer learning.

In a more recent study, Gerace et al. (2021) examine the fundamentals of transfer learning between two-layer networks (including ReLU nonlinearities) for binary classification problems. Specifically, they develop asymptotic characterization of the test errors based on a correlated hidden manifold model, which relies on Gaussian distributions, for the relation between the two tasks (the definition and other utilizations of the hidden manifold model are provided by Goldt et al. (2020); Gerace et al. (2020)). Compared to previous studies (that were focused on single-layer models), the transfer learning in two-layer models allows Gerace et al. (2021) to better emphasize the aspect of feature reuse. Their transfer learning includes regularization on both the source and target tasks and, accordingly, the double descent phenomena are somewhat attenuated — although still noticeable. In their main analytical setting, the first layer in source network is transferred and set fixed in the target network; therefore, this construction can be perceived as the transfer learning counterpart of the well-known random feature model (Rahimi and Recht, 2007), which is also evaluated as an alternative to transfer learning. They also empirically demonstrate (for both synthetic and real data) the beneficial settings for the examined transfer learning when compared to fine tuning and learning the two-layer network from scratch.

3 Pruning of learned models

While DNNs are highly parameterized models, it is also common to prune them into less complex forms that better trade off between generalization performance and computational/memory requirements. This is especially useful for applications with limitations on storage space for the learned model, as well as constraints on computation time and energy consumption for processing new inputs.

In general, model pruning is at the expense of higher overparameterization, and therefore the study of their interplay is of great interest. Chang et al. (2021) provided the first theoretical study on pruning of interpolating models and their double descent phenomena. Their main focus is on a pruning approach where a dense model is trained, pruned and then retrained over the support of coordinates that were not pruned. Hence, their pruning is a sparsifying method that defines a support of nonzero values within the entire model. Chang et al. (2021) consider three types of pruning rules: based on magnitude of values, based on the Hessian, and based on oracle knowledge of the best support that minimizes the test error for a desired model sparsity.

4 Dictionary learning for sparse representations

Dictionary learning is an unsupervised task of establishing an overcomplete dictionary for sparse representation of a given set of data examples. Sulam et al. (2020) consider learned dictionaries that include more atoms (columns in the dictionary matrix) than the true dictionary that generated the training data. They refer to such learned dictionaries as over-realized. Over-realized dictionaries can be learned to achieve zero training error, i.e., to provide perfect sparse representations of the training data. Hence, over-realized dictionaries constitute a particular type of overparameterized model. Sulam et al. (2020) show that over-realized dictionaries can generalize better than those of the ground-truth size in sparse representations of new test data from the same model. Regarding estimation of the true dictionary, they show that learning a dictionary of the true size can be outperformed by first learning an over-realized dictionary and then distilling it into a dictionary of the true size.

The results by Sulam et al. (2020) show that increasing the dictionary size is useful, but only up to a certain point, after which the performance continuously degrades with the increase in model size. Specifically, their results suggest that the best performance can be obtained by the smallest dictionary that interpolates the training data. Due to the underlying non-convex optimization problem in training, such an interpolating solution is achieved by an over-realized dictionary that is larger than the true dictionary.

The learned dictionary can be perceived as a mapping from sparse code vectors to their corresponding data vectors of interest (although the sparse codes are not given in the training data and, thus, the learning is unsupervised). Hence, it is interesting to note that the error curves of learned over-realized dictionary do not exhibit double descent phenomena like in interpolating solutions to linear regression. A likely reason for the lack of double descent in over-realized dictionaries is that their construction via well-established methods (such as K-SVD (Aharon et al., 2006) or the online dictionary learning (Mairal et al., 2010)) is numerically stable and structurally constrained (e.g., dictionary columns are normalized). Thus, despite the ability of the over-realized dictionaries by Sulam et al. (2020) to interpolate their training data, they are not necessarily minimum-norm solutions. An interesting research direction for future work would be to define and study over-realized dictionaries with minimum-norm properties.

Open questions

The TOPML research area has received considerable attention in the last few years. While impressive progress has been made, that significantly improves our understanding of overparameterized learning, several important scientific challenges remain to be resolved. In this section we briefly discuss some of the major open questions in the TOPML field.

These results suggest that optimally tuned regularization will always dominate interpolation. From this perspective, the recent flurry of results show that interpolation is relatively harmless, rather than being relatively beneficial. However, to obtain the full extent of benefit of regularization over interpolation, we need to optimally tune the regularization parameter. This is usually unknown and needs to be estimated from data. While this can be done via estimating the noise variance, or more generally cross-validation (as formally shown in (Hastie et al., 2019)), such techniques usually require a strong i.i.d. assumption on the noise in the data and will not easily work for less friendly noise models, such as adversarial, correlated, or heteroskedastic noise. In such situations, an overly conservative choice of regularizer might preclude the benefits afforded by interpolation in settings with minimal noise. From a practitioner’s point of view, running iterative algorithms to completion (thus interpolating the data) may be more convenient than formulating a complex early stopping rule that will admit only minimally beneficial performance in practice (Neyshabur et al., 2014). In summary, the decision of whether to interpolate or regularize contains several theoretical and practical nuances and often depends on the context surrounding model deployment. We expect this debate to continue for the foreseeable future.

2 Are there applications other than ML where interpolating solutions are useful?

Theoretical research on interpolating solutions mainly attempts to explain the corresponding deep learning practice, which is far ahead of existing theories. Ideally, we can expect that new fundamental insights will induce novel extensions to contemporary practice. Another important question is whether recent theoretical findings on overparameterized interpolating solutions can lead to significant breakthroughs in domains other than ML. As an example consider signal estimation tasks, such as signal deconvolution and inverse problems, that receive degraded measurements of a specific signal without any particular examples of other signals. Another application area to explore is distributed optimization.

In general, the relevance of interpolating solutions in various problems is not a simple wish. As a fundamental example, we note that ML research on interpolating solutions in supervised learning is focused on random design settings where both the inputs and outputs are randomly drawn from an unknown but identical distribution. In particular, the training data is in general different from the test data. Therefore, in this random design setting, interpolating the input-output mappings of the training data does not prevent good performance on new inputs at test time. Supervised learning in random design settings is in accordance with contemporary ML frameworks where, indeed, interpolating solutions can provide remarkable performance. In contrast, classical statistics usually considers a fixed design setting in which the inputs are fixed (possibly set by the experiment designer) and the outputs are random. Specifically, training and test data include the same inputs but matched to different random outputs. Hence, in fixed design settings, a mapping that interpolates the input-output training examples is likely to seriously fail when applied on test inputs.

Let us consider the signal denoising problem to demonstrate the difference between random and fixed designs:

The denoising problem in the random design can take the following form. The given training dataset includes $n$ examples of noisy signals and their corresponding underlying, noiseless signals. Each of the $n$ examples corresponds to a different signal from the same class. The noiseless and the noisy signals are both $p$-dimensional vectors. In this random design, the goal is to learn a denoising mapping that takes a $p$-dimensional noisy signal and outputs a $p$-dimensional estimate for the corresponding noiseless signal. It is of interest that this mapping will operate well on new noisy signals from the considered class, but that were not included in the training dataset. Following the main principles that we overviewed in this paper, in this case of random-design signal denoising, a learned mapping that interpolates the $n$ training examples does not necessarily imply poor performance on new data.

The denoising problem in the fixed design can be defined as follows. The given data includes $n$ noisy measurements of the same signal, each measurement is a $p$-dimensional vector of noisy values of the signal over a uniformly-spaced grid of coordinates (i.e., we consider a discrete version of a continuous-domain signal). Examples for noiseless or noisy versions of other signals are not given. In this fixed design, the goal is to estimate the true, noiseless signal values (only) in the $p$ coordinates of the uniformly-spaced grid. The inputs are considered to be the $p$ coordinates of the uniformly-spaced grid. The estimate and the $n$ noisy measurements have the same discrete grid of $p$ coordinates; hence, not only that interpolation is impossible when $n>1$, it would be an incredibly poor estimate when $n=1$.

The above example simply demonstrates why interpolating solutions are irrelevant in many applications and, accordingly, that it is not trivial to find applications other than ML where interpolating solutions are beneficial. Yet, the success of interpolation in modern ML suggests to explore its relevance to other areas.

3 How should we define learned model complexity?

The correct definition of learned model complexity is an essential component of TOPML research. Recall that we defined a scenario to be overparameterized when the learned model complexity is high compared to the number of training examples. Thus, the definition of learned model complexity is clearly crucial for understanding whether a specific learning setting is in fact overparameterized. While this basic decision problem (i.e. whether a setting is overparameterized or not) can be solved by identifying whether the learned model interpolates or achieves zero training error, quantifying the actual extent of overparameterization is more challenging as well as more valuable as it allows us to distinguish various interpolating models. The summary of results in Section 3 of this paper showed a diversity of possible generalization behaviors for interpolating models. Whether we can interpret these results through a new overarching notion of learned model complexity remains a largely open question.

In linear models such as in LS regression, model complexity is often measured by the number of learned parameters in the solution. However, the double descent behavior clearly shows that the number of parameters is a misleading measure of learned model complexity; regularization in the learning process, as well as structural redundancies in the architecture may reduce the effective complexity of the learned model. Moreover, the definition of complexity of nonlinear and multi-layer models, including the extreme case of deep neural networks, becomes highly intricate. Model complexity measures that depend on the training data (e.g., Rademacher complexity (Bartlett and Mendelson, 2002)) are useful to understand classical ML via uniform convergence analyses. In contrast, such complexity measures fail to explain the good generalization ability in contemporary settings where the learned models interpolate their training data (Belkin et al., 2018b; Nagarajan and Kolter, 2019; Bartlett and Long, 2020). Researchers have also recently attempted, with relatively more success, to relate other classical notions of learned model complexity to the overparameterized regime. Recently, Dwivedi et al. (2020) adapted Rissanen’s classical notion of minimum description length (MDL) (Rissanen, 1978, 1983) to the overparameterized regime: their data-driven notion of MDL explains some of the behaviors observed in Section 3. Algorithm-dependent notions of model complexity, such as algorithmic stability (Bousquet and Elisseeff, 2002), are also interesting to consider; indeed, Rangamani et al. (2020) recently showed that in some cases, the minimum Hilbert-norm interpolation for kernel regression is also the most algorithmically stable. Much work remains to be done to systematically study these complexity measures in the overparameterized regime and understand whether they are always predictive of generalization behavior. Accordingly, the definition of an appropriate complexity measure continues to pose a fundamental challenge that is at the heart of the TOPML research area.

We thank all the organizers and participants of the inaugural TOPML workshop for extensive discussions and contributions that enriched the content in this survey. Special thanks to Ryan Tibshirani for fruitful discussions on the definition of TOPML and the open questions of the field.

VM thanks her co-authors for several insightful discussions that inspired the treatment of TOPML in this survey; special thanks goes to Anant Sahai for influencing the signal processing-oriented treatment of minimum-norm interpolation provided in Section 3.2 of this paper.

YD and RGB acknowledge support from NSF grants CCF-1911094, IIS-1838177, and IIS-1730574; ONR grants N00014-18-12571, N00014-20-1-2534, and MURI N00014-20-1-2787; AFOSR grant FA9550-18-1-0478; and a Vannevar Bush Faculty Fellowship, ONR grant N00014-18-1-2047.

References