On the Implicit Bias in Deep-Learning Algorithms

Introduction

Deep learning has been highly successful in recent years and has led to dramatic improvements in multiple domains. Deep-learning algorithms often generalize quite well in practice, namely, given access to labeled training data, they return neural networks that correctly label unobserved test data. However, despite much research our theoretical understanding of generalization in deep learning is still limited.

Neural networks used in practice often have far more learnable parameters than training examples. In such overparameterized settings, one might expect overfitting to occur, that is, the learned network might perform well on the training dataset and perform poorly on test data. Indeed, in overparameterized settings, there are many solutions that perform well on the training data, but most of them do not generalize well. Surprisingly, it seems that gradient-based deep-learning algorithmsNeural networks are trained using gradient-based algorithms, where the network’s parameters are randomly initialized, and then adjusted in many stages in order to fit the training dataset by using information based on the gradient of a loss function w.r.t. the network parameters. prefer the solutions that generalize well .

Decades of research in learning theory suggest that in order to avoid overfitting one should use a model which is “not more expressive than necessary”. Namely, the model should be able to perform well on the training data, but should be as “simple” as possible. This idea goes back to the Occam’s Razor philosophical principle, which argues that we should prefer simple explanations over complicated ones. For example, in Figure 1 the data points are labeled according to a degree-$3$ polynomial plus a small random noise, and we fit it with a degree-$3$ polynomial (green) and with a degree-$8$ polynomial (red). The degree-$8$ polynomial achieves better accuracy on the training data, but it overfits and will not generalize well.

Simplicity in neural networks may stem from having a small number of parameters (which is often not the case in modern deep learning), but may also be achieved by adding a regularization term during the training, which encourages networks that minimize a certain measure of complexity. For example, we may add a regularizer that penalizes models where the Euclidean norm of the parameters (viewed as a vector) is large. However, in practice neural networks seem to generalize well even when trained without such an explicit regularization , and hence the success of deep learning cannot be attributed to explicit regularization. Therefore, it is believed that gradient-based algorithms induce an implicit bias (or implicit regularization) which prefers solutions that generalize well, and characterizing this bias has been a subject of extensive research.

In this review article, we discuss the implicit bias in training neural networks using gradient-based methods. The literature on this subject has rapidly expanded in recent years, and we aim to provide a high-level overview of some fundamental results. This article is not a comprehensive survey, and there are certainly important results which are not discussed here.

The double-descent phenomenon

An important implication of the implicit bias in deep learning is the double-descent phenomenon, observed by Belkin et al. . As we already discussed, conventional wisdom in machine learning suggests that the number of parameters in the neural network should not be too large in order to avoid overfitting (when training without explicit regularization). Also, it should not be too small, in which case the model is not expressive enough and hence it performs poorly even on the training data, a situation called underfitting. This classical thinking can be captured by the U-shaped risk (i.e., error or loss) curve from Figure 2(A). Thus, as we increase the number of parameters, the training risk decreases, and the test risk initially decreases and then increases. Hence, there is a “sweet spot” where the test risk is minimized. This classical U-shaped curve suggests that we should not use a model that perfectly fits the training data.

However, it turns out that the U-shaped curve only provides a partial picture. If we continue to increase the number of parameters in the model after the training set is already perfectly labeled, then there might be a second descent in the test risk (hence the name “double descent”). As can be seen in Figure 2(B), by increasing the number of parameters beyond what is required to perfectly fit the training set, the generalization improves. Hence, in contrast to the classical approach which seeks a sweet spot, we may achieve generalization by using overparameterized neural networks. Modern deep learning indeed relies on using highly overparameterized networks.

The double-descent phenomenon is believed to be a consequence of the implicit bias in deep-learning algorithms. When using overparameterized models, gradient methods converge to networks that generalize well by implicitly minimizing a certain measure of the network’s complexity. As we will see next, characterizing this complexity measure in different settings is a challenging puzzle.

Implicit bias in classification

The above characterization of the implicit bias in logistic regression can be used to explain generalization. Consider the case where $d>n$, thus, the input dimension is larger than the size of the dataset, and hence there are infinitely many vectors $\mathbf{w}$ with $\left\|\mathbf{w}\right\|_{2}=1$ such that for all $i\in\{1,\ldots,n\}$ we have $y_{i}\cdot\mathbf{w}^{\top}\mathbf{x}_{i}>0$, i.e., there are infinitely many directions that correctly label the training data. Some of the directions which fit the training data generalize well, and others do not. The above result guarantees that gradient flow converges to the maximum-margin direction. Consequently, we can explain generalization by using standard margin-based generalization bounds (cf. ), which imply that predictors achieving large margin generalize well.

2 Linear networks

We turn to deep neural networks where the activation is the identity function. Such neural networks are called linear networks. These networks compute linear functions, but the network architectures induce significantly different dynamics of gradient flow compared to the case of linear predictors $\mathbf{x}\mapsto\mathbf{w}^{\top}\mathbf{x}$ that we already discussed. Hence, the implicit bias in linear networks has been extensively studied, as a first step towards understanding implicit bias in deep nonlinear networks. It turns out that understanding implicit bias in linear networks is highly non-trivial, and its study reveals valuable insights.

3 Homogeneous neural networks

Neural networks of practical interest have nonlinear activations and compute nonlinear predictors. The notion of margin maximization in nonlinear predictors is generally not well-defined. Nevertheless, it has been established that for certain neural networks gradient flow maximizes the margin in parameter space. Thus, while in linear networks we considered margin maximization in predictor space (a.k.a. function space), here we consider margin maximization w.r.t. the network’s parameters.

A KKT point satisfies several conditions (called KKT conditions), and it was proved in that in the case of homogeneous neural networks these conditions are necessary for optimality. However, they are not sufficient even for local optimality (cf. ). Thus, a KKT point may not be an actual optimum of the maximum-margin problem. It is analogous to showing that some unconstrained optimization problem converges to a point where the gradient is zero, without proving that it is a global/local minimum. Intuitively, convergence to a KKT point of the maximum-margin problem implies a certain bias towards margin maximization in parameter space, although it does not guarantee convergence to a maximum-margin solution.

As we already discussed, in linear classifiers and linear neural networks, margin maximization (in predictor space) can explain generalization using well-known margin-based generalization bounds. Can margin maximization in parameter space explain generalization in nonlinear neural networks? In recent years several works showed margin-based generalization bounds for neural networks (e.g., ). Hence, generalization in neural networks might be established by combining these results with results on the implicit bias towards margin maximization in parameter space. On the flip side, we note that it is still unclear how tight the known margin-based generalization bounds for neural networks are, and whether the sample complexity implied by such results (i.e., the required size of the training dataset) may be small enough to capture the situation in practice.

Several results on implicit bias were shown for some specific cases of nonlinear homogeneous networks. For example: showed bias towards margin maximization w.r.t. a certain function norm (known as the variation norm) in infinite-width two-layer homogeneous networks; proved margin maximization in two-layer Leaky-ReLU networks trained on linearly separable and symmetric data, and proved convergence to a linear classifier in two-layer Leaky-ReLU networks under different assumptions; showed bias towards minimizing the number of linear regions in univariate two-layer ReLU networks (see also ).

Finally, the implicit bias in non-homogeneous neural networks (such as ResNets) is currently not well-understood.We remark that a result by suggests that for a sum of homogeneous networks of different orders (such a sum is non-homogeneous), the implicit bias may encourage solutions that discard the networks with the smallest order. Improving our knowledge of non-homogeneous networks is an important challenge in the path towards understanding implicit bias in deep learning.

4 Extensions

For simplicity, we considered so far only gradient flow in binary classification. We note that many of the above results can also be extended to other gradient methods (such as gradient descent, steepest descent and SGD), and to multiclass classification with the cross-entropy loss (see, e.g., ).

The margin-maximization guarantees that we discussed for gradient flow hold in an asymptotic sense, and an important question is how fast the convergence is. It turns out that the convergence rate might be extremely slow . For example, when learning a linear predictor on linearly-separable training dataset using gradient descent (with a sufficiently small step size), after $T$ iterations the distance between the normalized predictor $\bar{\mathbf{w}}_{T}$ and the maximum margin predictor $\mathbf{w}^{*}$ generally satisfies $\left\|\bar{\mathbf{w}}_{T}-\mathbf{w}^{*}\right\|_{2}={\cal O}\left(1/\log(T)\right)$,See for a more precise statement. and hence to reach $\left\|\bar{\mathbf{w}}_{T}-\mathbf{w}^{*}\right\|_{2}\leq\gamma$ for some $\gamma>0$, the number of iterations must be exponential in $1/\gamma$. We remark that Shamir showed that the slow convergence rate to the maximum-margin predictor does not imply that $T$ must be extremely large in order to avoid overfitting. Namely, he proved that also for much smaller values of $T$, the predictor $\bar{\mathbf{w}}_{T}$ achieves a sufficiently large margin on a sufficiently large portion of the dataset, which implies good generalization properties.

Moreover, so far we considered only training with the logistic loss, which is a common loss function for binary classification. The results can generally be extended to loss functions that have an exponential tail, but the implicit bias is different when using other loss functions (e.g., losses with a polynomial tail) .

Additional aspects of the implicit bias, which apply both to classification and regression, are discussed in Sections 5 and 6.

Implicit bias in regression

We note that the results on linear regression can be extended to optimization methods other than gradient flow, such as gradient descent, SGD, and mirror descent .For mirror descent with a potential function $\psi(\mathbf{w})$, the implicit bias is given by ${\cal R}(\mathbf{w})=D_{\psi}\left(\mathbf{w},\mathbf{w}(0)\right)$, where $D_{\psi}$ is the Bregman divergence w.r.t. $\psi$. In particular, if we start at $\mathbf{w}(0)=\operatorname*{argmin}_{\mathbf{w}}\psi(\mathbf{w})$ then we have ${\cal R}(\mathbf{w})=\psi(w)$.

2 Linear networks

Exact expressions for ${\cal R}(\mathbf{w})$ have been obtained for linear diagonal networks and linear fully-connected networks . The expressions for ${\cal R}(\mathbf{w})$ are rather complicated, and depend on the initialization scale, i.e., the norm of $\mathbf{w}(0)$, and the initialization “shape”, namely, the relative magnitudes of different weights and layers in the network. Below we discuss a few special cases.

Some additional aspects of the implicit bias in linear networks are discussed in Sections 5 and 6.

3 Matrix factorization as a test-bed for neural networks

The matrix factorization problem is analogous to training a two-layer linear network. Furthermore, we may consider deep matrix factorization where we have $W=W_{k}W_{k-1}\ldots W_{1}$, which is analogous to training a deep linear network. Therefore, this problem is considered a natural test-bed to investigate implicit bias in neural networks, and has been studied extensively in recent years (e.g., ).

Gunasekar et al. conjectured that in matrix factorization, the implicit bias of gradient flow starting from small initialization is given by the nuclear norm of $W$ (a.k.a. the trace norm). That is, ${\cal R}(W)=\left\|W\right\|_{*}$. They also proved this conjecture in the restricted case where the matrices $\{X_{i}\}_{i=1}^{n}$ commute. The conjecture was further studied in a line of works (e.g., ) providing positive and negative evidence, and was formally refuted by . In the authors showed that gradient flow in matrix completion might approach a global minimum at infinity rather than converging to a global minimum with a finite norm. This result suggests that the implicit bias in matrix factorization may not be expressible by any norm or quasi-norm. They conjectured that the implicit bias can be explained by rank minimization rather than norm minimization. In , the authors provided theoretical and empirical evidence that gradient flow with infinitesimally small initialization in the matrix-factorization problem is mathematically equivalent to a simple heuristic rank-minimization algorithm called Greedy Low-Rank Learning (see also ). This result was generalized to tensor factorization in .

Overall, although an explicit expression for a function ${\cal R}$ is not known in the case of matrix factorization, we can view the implicit bias as a heuristic for rank minimization. It is still unclear what the implications of these results are for more practical nonlinear neural networks.

4 Nonlinear networks

The results on implicit bias in matrix factorization might suggest that there is a certain tendency towards rank minimization in deep learning with the square loss. However, the authors in showed that gradient flow is not biased towards rank minimization of the weight matrices in ReLU networks, at least in the simple case of two-layer networks and small datasets.We remark that showed a certain tendency towards rank minimization in deep networks trained with the square loss using weight decay, or with the logistic loss.

Overall, our understanding of implicit bias in nonlinear networks with regression losses is very limited. While in classification we have a useful characterization of the implicit bias in nonlinear homogeneous models, here we do not understand even extremely simple models. Improving our understanding of this question is a major challenge for the upcoming years.

In what follows, we will discuss some additional aspects of the implicit bias, which apply both to regression and classification.

Dynamical stability

In the previous sections, we mostly focused on implicit bias in gradient flow, and also discussed cases where the results on gradient flow can be extended to other gradient methods. However, when considering gradient descent or SGD with a finite step size (rather than infinitesimal), the discrete nature of the algorithms and the stochasticity induce additional implicit biases that do not exist in gradient flow. These biases are crucial for understanding the behavior of gradient methods in practice, as empirical results suggest that increasing the step size and decreasing the batch size may improve generalization (cf. ).

It is well known that gradient descent and SGD cannot stably converge to minima that are too sharp relative to the step size (see, e.g., ). Namely, in a stable minimum, the maximal eigenvalue of the Hessian is at most $2/\eta$, where $\eta$ is the step size. As a result, when using an appropriate step size we can rule out stable convergence to certain (sharp) minima, and thus encourage convergence to flat minima, which are believed to generalize better . Similarly, small batch sizes in SGD also encourage flat minima .

We note that a function might be represented with many different networks, i.e., there are many sets of parameters that correspond to the same function. However, it is possible that some of these representations are sharp (in parameter space) and others are flat (cf. ). As a result, understanding the implications in function space of the bias towards flat minima (in parameter space) is often a challenging question.

An intriguing related phenomenon, observed by Cohen et al. , is the tendency of gradient descent to operate in a regime called the Edge of Stability (EoS). They showed empirically for several architectures and tasks, and for both the cross-entropy and the square loss, that the behavior of gradient descent with step size $\eta$ consists of two stages. First, the loss curvature grows until the sharpness touches the bound of $2/\eta$. Then, gradient decent enters the EoS regime, where curvature hovers around this bound, and the train loss behaves non-monotonically, yet consistently decreases over long timescales. This phenomenon is not well understood, as traditional convergence analyses of gradient descent do not apply when the sharpness is above $2/\eta$. The study of the EoS regime may contribute to our understanding of the dynamics and implicit bias in gradient descent and SGD. It was investigated in several recent theoretical works . For example, showed that training with modified gradient descent or modified loss (for a large family of losses) provably enters the EoS regime, and that the loss decreases in a non-monotone manner, and studied EoS in training a two-layer single-neuron ReLU network with the square loss.

Additional implicit biases

Additional aspects of the implicit bias have also been studied in the literature. Below we briefly discuss some of them.

Another direction for understanding implicit bias in gradient descent and SGD, is to transform it into gradient flow on a modified loss. In , the authors show that the discrete iterates of gradient descent and SGD with small step size lie close to the path of gradient flow on certain modified losses, obtained by adding explicit regularizers (see also ).

An additional interesting aspect of the implicit bias in certain neural networks is a tendency towards balanced layers. In , the authors proved that when training fully-connected neural networks with homogeneous activation functions using gradient flow with any differentiable loss function, we have $\frac{d}{dt}\left(\left\|W_{j}\right\|_{F}^{2}-\left\|W_{j+1}\right\|_{F}^{2}\right)=0$ for all $j$, where $W_{j}$ and $W_{j+1}$ are the weight matrices in layers $j$ and $j+1$. Thus, the difference between the squared Frobenius norms of the layers remain invariant throughout training. Moreover, they showed that a similar result holds also for networks with sparse connections and shared weights, such as convolutional neural networks. Note that when starting gradient flow from a small initialization, it implies that the Frobenius norms of the layers remain roughly balanced throughout training. For linear neural networks an even stronger notion of balancedness holds: proved that $\frac{d}{dt}\left(W_{j}W_{j}^{\top}-W_{j+1}^{\top}W_{j+1}\right)=0$ for all $j$. Furthermore, as we already mentioned, showed that in linear neural networks and matrix factorization, when training using gradient descent with large step size, the implicit bias towards flat solutions implies bias towards balanced layers.

Many of the existing results on the implicit bias characterize properties of the parameters of the learned neural networks, namely, they consider the implicit bias in parameter space. However, since a function typically has many different representations, then understanding the implications of these results on function space is a non-trivial question. Several works studied the implications of norm minimization in parameter space on function space for different architectures of neural networks: studied univariate two-layer neural networks and extended the analysis to the multivariate case, studied fully-connected, diagonal and convolutional linear networks, and studied larger families of convolutional linear networks.

Finally, we note that in this article we mostly considered implicit bias in the rich regime, rather than in the NTK regime (a.k.a. kernel regime). The NTK regime does not capture feature learning, which seems to be a crucial element in the success of deep learning. The implicit bias in the NTK regime has been studied in several works (see, e.g., ), but we leave the discussion on these results outside the scope of this review.

Implications beyond generalization

While the primary motivation for studying implicit bias is to better understand generalization in deep learning, it may also have other significant implications. Indeed, various phenomena may stem from the tendency of gradient-based algorithms to prefer specific solutions over others. We believe that exploring such implications is an exciting research direction, and demonstrate it below with two examples.

First, neural networks are known to be extremely vulnerable to adversarial examples , namely, small perturbations to the inputs might change the network’s predictions. This phenomenon has been widely studied, but it is still not well-understood. Specifically, it is unclear why gradient methods tend to learn non-robust networks, namely, networks that are susceptible to adversarial examples, even in cases where robust networks exist. The tendency of gradient methods to learn non-robust networks can be viewed as an implication of the implicit bias. See for some results in this direction.

Second, the implicit bias might shed light on the hidden representations learned by neural networks, and on the extent to which neural networks are susceptible to privacy attacks. In , the authors used the characterization of the implicit bias in homogeneous networks due to , and showed that training data can be reconstructed from trained networks. Thus, neural networks “memorize” training data, and by using known properties of the implicit bias the data may be reconstructed, which might have negative implications on privacy.

Conclusion

Deep-learning algorithms exhibit remarkable performance, but it is not well-understood why they are able to generalize despite having much more parameters than training examples. Exploring generalization in deep learning is an intriguing puzzle with both theoretical and practical implications. It is believed that implicit bias is a main ingredient in the ability of deep-learning algorithms to generalize, and hence it has been widely studied. Moreover, investigating the implicit bias might have important implications beyond generalization.

Our understanding of implicit bias improved dramatically in recent years, but is still far from satisfactory. We believe that further progress in the study of implicit bias will eventually shed light on the mystery of generalization in deep learning.

I thank Nadav Cohen, Noam Razin, Ohad Shamir and Daniel Soudry for valuable comments and discussions.

References