In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning

Introduction

Central to any form of learning is an inductive bias that induces some sort of capacity control (i.e. restricts or encourages predictors to be “simple” in some way), which in turn allows for generalization. The success of learning then depends on how well the inductive bias captures reality (i.e. how expressive is the hypothesis class of “simple” predictors) relative to the capacity induced, as well as on the computational complexity of fitting a “simple” predictor to the training data.

Let us consider learning with feed-forward networks from this perspective. If we search for the weights minimizing the training error, we are essentially considering the hypothesis class of predictors representable with different weight vectors, typically for some fixed architecture. Capacity is then controlled by the size (number of weights) of the network The exact correspondence depends on the activation function—for hard thresholding activation the pseudo-dimension, and hence sample complexity, scales as $O(S\log S)$, where $S$ is the number of weights in the network. With sigmoidal activation it is between $\Omega(S^{2})$ and $O(S^{4})$ (Anthony & Bartlett 1999).. Our justification for using such networks is then that many interesting and realistic functions can be represented by not-too-large (and hence bounded capacity) feed-forward networks. Indeed, in many cases we can show how specific architectures can capture desired behaviors. More broadly, any $O(T)$ time computable function can be captured by an $O(T^{2})$ sized network, and so the expressive power of such networks is indeed great (Sipser 2006, Theorem 9.25).

At the same time, we also know that learning even moderately sized networks is computationally intractable—not only is it NP-hard to minimize the empirical error, even with only three hidden units, but it is hard to learn small feed-forward networks using any learning method (subject to cryptographic assumptions). That is, even for binary classification using a network with a single hidden layer and a logarithmic (in the input size) number of hidden units, and even if we know the true targets are exactly captured by such a small network, there is likely no efficient algorithm that can ensure error better than 1/2 (Sherstov 2006; Daniely et al. 2014)—not if the algorithm tries to fit such a network, not even if it tries to fit a much larger network, and in fact no matter how the algorithm represents predictors (see the Appendix). And so, merely knowing that some not-too-large architecture is excellent in expressing reality does not explain why we are able to learn using it, nor using an even larger network. Why is it then that we succeed in learning using multilayer feed-forward networks? Can we identify a property that makes them possible to learn? An alternative inductive bias?

Here, we make our first steps at shedding light on this question by going back to our understanding of network size as the capacity control at play.

Our main observation, based on empirical experimentation with single-hidden-layer networks of increasing size (increasing number of hidden units), is that size does not behave as a capacity control parameter, and in fact there must be some other, implicit, capacity control at play. We suggest that this hidden capacity control might be the real inductive bias when learning with deep networks.

Network Size and Generalization

Consider training a feed-forward network by finding the weights minimizing the training error. Specifically, we will consider a network with $d$ real-valued inputs $\boldsymbol{x}=(x,\ldots,x[d])$, a single hidden layer with $H$ rectified linear units, and $k$ outputs $y,\ldots,y[k]$,

What happens to the training and test errors when we increase the network size $H$? The training error will necessarily decrease. The test error might initially decrease as the approximation error is reduced and the network is better able to capture the targets. However, as the size increases further, we loose our capacity control and generalization ability, and should start overfitting. This is the classic approximation-estimation tradeoff behavior.

Consider, however, the results shown in Figure 1, where we trained networks of increasing size on the MNIST and CIFAR-10 datasets. Training was done using stochastic gradient descent with momentum and diminishing step sizes, on the training error and without any explicit regularization. As expected, both training and test error initially decrease. More surprising is that if we increase the size of the network past the size required to achieve zero training error, the test error continues decreasing! This behavior is not at all predicted by, and even contrary to, viewing learning as fitting a hypothesis class controlled by network size. For example for MNIST, 32 units are enough to attain zero training error. When we allow more units, the network is not fitting the training data any better, but the estimation error, and hence the generalization error, should increase with the increase in capacity. However, the test error goes down. In fact, as we add more and more parameters, even beyond the number of training examples, the generalization error does not go up.

We also further tested this phenomena under some artificial mutilations to the data set. First, we wanted to artificially ensure that the approximation error was indeed zero and does not decrease as we add more units. To this end, we first trained a network with a small number $H_{0}$ of hidden units ($H_{0}=4$ on MNIST and $H_{0}=16$ on CIFAR) on the entire dataset (train+test+validation). This network did have some disagreements with the correct labels, but we then switched all labels to agree with the network creating a “censored” data set. We can think of this censored data as representing an artificial source distribution which can be exactly captured by a network with $H_{0}$ hidden units. That is, the approximation error is zero for networks with at least $H_{0}$ hidden units, and so does not decrease further. Still, as can be seen in the middle row of Figure 2, the test error continues decreasing even after reaching zero training error.

Next, we tried to force overfitting by adding random label noise to the data. We wanted to see whether now the network will use its higher capacity to try to fit the noise, thus hurting generalization. However, as can be seen in the bottom row of Figure 2, even with five percent random labels, there is no significant overfitting and test error continues decreasing as network size increases past the size required for achieving zero training error.

What is happening here? A possible explanation is that the optimization is introducing some implicit regularization. That is, we are implicitly trying to find a solution with small “complexity”, for some notion of complexity, perhaps norm. This can explain why we do not overfit even when the number of parameters is huge. Furthermore, increasing the number of units might allow for solutions that actually have lower “complexity”, and thus generalization better. Perhaps an ideal then would be an infinite network controlled only through this hidden complexity.

We want to emphasize that we are not including any explicit regularization, neither as an explicit penalty term nor by modifying optimization through, e.g., drop-outs, weight decay, or with one-pass stochastic methods. We are using a stochastic method, but we are running it to convergence—we achieve zero surrogate loss and zero training error. In fact, we also tried training using batch conjugate gradient descent and observed almost identical behavior. But it seems that even still, we are not getting to some random global minimum—indeed for large networks the vast majority of the many global minima of the training error would horribly overfit. Instead, the optimization is directing us toward a “low complexity” global minimum.

Although we do not know what this hidden notion of complexity is, as a final experiment we tried to see the effect of adding explicit regularization in the form of weight decay. The results are shown in the top row of figure 2. There is a slight improvement in generalization but we still see that increasing the network size helps generalization.

A Matrix Factorization Analogy

To gain some understanding at what might be going on, let us consider a slightly simpler model which we do understand much better. Instead of rectified linear activations, consider a feed-forward network with a single hidden layer, and linear activations, i.e.:

This is of course simply a matrix-factorization model, where $\boldsymbol{y}=\boldsymbol{W}\boldsymbol{x}$ and $\boldsymbol{W}=\boldsymbol{V}\boldsymbol{U}^{\top}$. Controlling capacity by limiting the number of hidden units exactly corresponds to constraining the rank of $\boldsymbol{W}$, i.e. biasing toward low dimensional factorizations. Such a low-rank inductive bias is indeed sensible, though computationally intractable to handle with most loss functions.

However, in the last decade we have seen much success for learning with low norm factorizations. In such models, we do not constrain the inner dimensionality $H$ of $\boldsymbol{U},\boldsymbol{V}$, and instead only constrain, or regularize, their norm. For example, constraining the Frobenius norm of $\boldsymbol{U}$ and $\boldsymbol{V}$ corresponds to using the trace-norm as an inductive bias (Srebro et al. 2004):

Other norms of the factorization lead to different regularizers.

Unlike the rank, the trace-norm (as well as other factorization norms) is convex, and leads to tractable learning problems (Fazel et al. 2001; Srebro et al. 2004). In fact, even if learning is done by a local search over the factor matrices $\boldsymbol{U}$ and $\boldsymbol{V}$ (i.e. by a local search over the weights of the network), if the dimensionality is high enough and the norm is regularized, we can ensure convergence to a global minima (Burer & Choi 2006). This is in stark contrast to the dimensionality-constrained low-rank situation, where the limiting factor is the number of hidden units, and local minima are abundant (Srebro & Jaakkola 2003).

Furthermore, the trace-norm and other factorization norms are well-justified as sensible inductive biases. We can ensure generalization based on having low trace-norm, and a low-trace norm model corresponds to a realistic factor model with many factors of limited overall influence. In fact, empirical evidence suggests that in many cases low-norm factorization are a more appropriate inductive bias compared to low-rank models.

We see, then, that in the case of linear activations (i.e. matrix factorization), the norm of the factorization is in a sense a better inductive bias than the number of weights: it ensures generalization, it is grounded in reality, and it explain why the models can be learned tractably.

Let us interpret the experimental results of Section 2 in this light. Perhaps learning is succeeding not because there is a good representation of the targets with a small number of units, but rather because there is a good representation with small overall norm, and the optimization is implicitly biasing us toward low-norm models. Such an inductive bias might potentially explain both the generalization ability and the computational tractability of learning, even using local search.

Under this interpretation, we really should be using infinite-sized networks, with an infinite number of hidden units. Fitting a finite network (with implicit regularization) can be viewed as an approximation to fitting the “true” infinite network. This situation is also common in matrix factorization: e.g., a very successful approach for training low trace-norm models, and other infinite-dimensional bounded-norm factorization models, is to approximate them using a finite dimensional representation Rennie & Srebro 2005; Srebro & Salakhutdinov 2010. The finite dimensionality is then not used at all for capacity (statistical complexity) control, but purely for computational reasons. Indeed, increasing the allowed dimensionality generally improves generalization performance, as it allows us to better approximate the true infinite model.

Infinite Size, Bounded Norm Networks

Let $L$ be a loss function and $D=(\boldsymbol{x}_{t},y_{t})_{t=1}^{n}$ be training examples.

By the inequality between the arithmetic and geometric means, we have

with $v(\boldsymbol{u}):=\mu_{+}(\boldsymbol{u})-\mu_{-}(\boldsymbol{u})$ and regularizer $\left\lVert{v}\right\rVert_{1}=\sum_{\boldsymbol{u}\in\mathcal{U}}|v(\boldsymbol{u})|$. Training a convex NN is then given by:

Moreover, even if $\mathcal{U}$ is infinite and even continuous, there will always be an optimum of (8) which is a discrete measure with support at most $n+1$ (Rosset et al. 2007). That is, (8) can be equivalently written as:

References

Appendix

For the convenience of the reader, we formalize here the hardness of learning feed-forward neural network mentioned in the Introduction. The results are presented in a way that is appropriate for feed-forward networks with RELU activations, but they are really a direct implication of recent results about learning intersections of halfspaces. For historical completeness we note that hardness of learning logarithmic depth networks was already established by Kearns & Valiant 1994, and that the more recent results we discuss here (Sherstov 2006; Daniely et al. 2014) establish also hardness of learning depth two networks, subject to perhaps simpler cryptographic assumptions. The presentation and construction here is similar to that of Livni et al. 2014.

Is there a sample complexity function $m(D,H)$ and an algorithm $\mathcal{A}$ that takes as input $\left\{(x_{i},y_{i})\right\}_{i=1,\dots,M},x_{i}\in\{\pm 1\}^{D},y\in\pm 1$ and returns a description of a function $f:\{\pm 1\}^{D}\rightarrow\pm 1$ such that the following is true:

For any $D$, any $H$ and any distribution $\mathcal{D}(x,y)$ over $x\in\{\pm 1\}^{D},y\in\pm 1$, if:

The input to $\mathcal{A}$ is drawn i.i.d. from $\mathcal{D}$.

$M\geq m(D,H)$ (i.e. $\mathcal{A}$ is provided with enough training data).

$m(D,H)\leq\text{poly}(D,H)$ for some $\text{poly}(D,H)$ (i.e. the sample complexity required by the algorithm is polynomial in the network size—if we needed a super-polynomial number of samples, we would have no hope of learning in polynomial time).

The function $f$ that corresponds to the description returned by $\mathcal{A}$ can be computed in time $\text{poly}(D,H)$ from its description (i.e. the representation used by the learner can be a feed-forward network of any size polynomial in $H$ and $D$, or of any other representation that can be efficiently computed).

$\mathcal{A}$ runs in time $\text{poly}(D,H,M)$

Subject for the cryptographic assumptions in Daniely et al. 2014, there is no algorithm that satisfies the conditions in the above question.

In fact, there is no algorithm satisfying the conditions even if we require that the labels can be perfectly predicted by a network with a single hidden layer with any super-constant, e.g. $\log(D)$, number of hidden units.

We show that every intersection of $k=\omega(1)$ homogeneous halfspaces over $\{\pm 1\}^{n}$ with normals in $\{\pm 1\}$ can be realized with unit margin by a feed-fowrad neural networks with $H=2k$ hidden units in a single hidden layer. For each hyperplane $\left\langle w_{i},x\right\rangle>0$, where $w_{i}\in\{\pm 1\}^{D}$, we include two units in the hidden layer: $g^{+}_{i}(x)=[\left\langle w_{i},x\right\rangle]_{+}$ and $g^{-}_{i}(x)=[\left\langle w_{i},x\right\rangle-1]_{+}$. We set all incoming weights of the output node to be $1$. Therefore, this network is realizing the following function:

Since all inputs and all weights are integer, the outputs of the first layer will be integer, $\left([\left\langle w_{i},x\right\rangle]_{+}-[\left\langle w_{i},x\right\rangle-1]_{+}\right)$ will be zero or one, and $f$ realizes the intersection of the $k$ halfspaces with unit margin. Hence, the hypothesis class of neural intersection of $k/2$ halfspaces is a subset of hypothesis class of feed-forward neural networks with $k$ hidden units in a single hidden layer. We complete the proof by applying Theorem 5.4 in Daniely et al. 2014 which states that for any $k=\omega(1)$, subject for the cryptographic assumptions in Daniely et al. 2014, the hypothesis class of intersection of homogeneous halfspaces over $\{\pm 1\}^{n}$ with normals in $\{\pm 1\}$ is not efficiently PAC learnable (even improperly) Their Theorem 5.4 talks about unrestricted halfspaces, but the construction in Section 7.2 uses only data in $\{\pm 1\}^{D}$ and halfspaces specified by $\langle w,x\rangle>0$ with $w\in\{\pm 1\}^{D}$. ∎

We proved here that even for $H=\omega(1)$ no algorithm can satisfy the condition in the question. A similar result can be shown for $H=\text{poly}(D)$ subject to weaker cryptographic assumptions in Sherstov 2006.

The Theorem tells us not only that we cannot expect to fit a small network to data even if the data is generated by the network (since doing so would give us an efficient learning algorithm, which contradicts the Theorem), but that we also can’t expect to learn by using a much larger network. That is, even if we know that labels can be perfectly predicted by a small network, we cannot expect to have a learning algorithm that learns a much larger (but poly sized) network that will have non-trivial error. In fact, being representable by a small network is not enough to ensure tractable learning no matter what representation the learning algorithm uses (e.g. a much larger network, a mixture of networks, a tree over networks, etc). This is a much stronger statement than just saying that fitting a network to data is $NP$-hard. Also, precluding the possibility of tractable learning if the labels are exactly explained by some small unknown network of course also precludes the possibility of achieving low error when the labels are only approximately explained by some small unknown network (i.e. of noisy or “agnostic” learning).