Geometry of Optimization and 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 networkThe 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 and 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. 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?

In section 2, 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.

Focusing on networks with RELU activations in this section, we observe that scaling down the incoming edges to a hidden unit and scaling up the outgoing edges by the same factor yields an equivalent network computing the same function. Since predictions are invariant to such rescalings, it is natural to seek a geometry, and corresponding optimization method, that is similarly invariant.

We therefore suggest a novel optimization method, Path-SGD, that is an approximate steepest descent method with respect to path regularization. Path-SGD is rescaling-invariant and we demonstrate that Path-SGD outperforms gradient descent and AdaGrad for classifications tasks on several benchmark datasets. This again demonstrates the importance of implicit regularization that is introduced by optimization.

This summary paper combines material previously presented by the authors at the \nth3 International Conference on Learning Representations (ICLR), the \nth28 Conference on Learning Theory (COLT) and Advances in Neural Information Processing Systems (NIPS) 28, as well as Intel Collaborative Research Institutes retreats (Neyshabur et al., 2015a, b, c).

Implicit Regularization

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.

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.

We have argued that the implicit regularization is due to the optimization. It is therefore expected that different optimization methods introduce different implicit regularizations which leads to different generalization properties. In an attempt to find an optimization method with better generalization properties, we recall that the optimization is also tied to a choice of geometry/distance measure in the parameter space. We look into the desirable properties of a geometry for neural networks and suggest an optimization algorithm that is tied to that geometry.

The Geometry of Optimization: Rescaling and Unbalanceness

Given a training set $\mathcal{S}=\{(x_{1},y_{n}),\dots,(x_{n},y_{n})\}$, our goal is to minimize the following objective function:

Let $w^{(t)}$ be the weights at step $t$ of the optimization. We consider update step of the following form $w^{(t+1)}=w^{(t)}+\Delta w^{(t+1)}$. For example, for gradient descent, we have $\Delta w^{(t+1)}=-\eta\nabla L(w^{(t)})$, where $\eta$ is the step-size. In the stochastic setting, such as SGD or mini-batch gradient descent, we calculate the gradient on a small subset of the training set.

Unfortunately, gradient descent is not rescaling invariant. The main problem with the gradient updates is that scaling down the weights of an edge will also scale up the gradient which, as we see later, is exactly the opposite of what is expected from a rescaling invariant update.

In an unbalanced network, gradient descent updates could blow up the smaller weights, while keeping the larger weights almost unchanged. This is illustrated in Figure LABEL:sub@fig:compare-b. If this were the only issue, one could scale down all the weights after each update. However, in an unbalanced network, the relative changes in the weights are also very different compared to a balanced network. For example, Figure LABEL:sub@fig:compare-c shows how two rescaling equivalent networks could end up computing a very different function after only a single update.

Magnitude/Scale measures for deep networks

Following Neyshabur et al. (2015b), we consider the grouping of weights going into each node of the network. This forms the following generic group-norm type regularizer, parametrized by $1\leq p,q\leq\infty$:

Path-SGD: An Approximate Path-Regularized Steepest Descent

Motivated by empirical performance of max-norm regularization and the fact that path-regularizer is invariant to rescaling, we are interested in deriving the steepest descent direction with respect to the path regularizer $\phi_{p}(w)$:

The steepest descent step (6) is hard to calculate exactly. Instead, we will update each coordinate $w_{e}$ independently (and synchronously) based on (6). That is:

Taking the partial derivative with respect to $w_{e}$ and setting it to zero we obtain:

where $v_{\text{in}}[i]\dots\stackrel{{\scriptstyle e}}{{\rightarrow}}\dots v_{\text{out}}[j]$ denotes the paths from any input unit $i$ to any output unit $j$ that includes $e$. Solving for $w_{e}$ gives us the following update rule:

We call the optimization using the update rule (8) path-normalized gradient descent. When used in stochastic settings, we refer to it as Path-SGD.

Now that we know Path-SGD is an approximate steepest descent with respect to the path-regularizer, we can ask whether or not this makes Path-SGD a rescaling invariant optimization method. The next theorem proves that Path-SGD is indeed rescaling invariant.

A similar argument proves the invariance of Path-SGD update rule for outgoing edges of $v$. Therefore, Path-SGD is rescaling invariant.

The Path-SGD update rule (8), in the way it is written, needs to consider all the paths, which is exponential in the depth of the network. However, it can be calculated in a time that is no more than a forward-backward step on a single data point. That is, in a mini-batch setting with batch size $B$, if the backpropagation on the mini-batch can be done in time $BT$, the running time of the Path-SGD on the mini-batch will be roughly $(B+1)T$ – a very moderate runtime increase with typical mini-batch sizes of hundreds or thousands of points. Algorithm 1 shows an efficient implementation of the Path-SGD update rule.

We next compare Path-SGD to other optimization methods in both balanced and unbalanced settings.

Experiments on Path-SGD

In all of our experiments, we trained feed-forward networks with two hidden layers, each containing 4000 hidden units. We used mini-batches of size 100 and the step-size of $10^{-\alpha}$, where $\alpha$ is an integer between 0 and 10. To choose $\alpha$, for each dataset, we considered the validation errors over the validation set (10000 randomly chosen points that are kept out during the initial training) and picked the one that reaches the minimum error faster. We then trained the network over the entire training set. All the networks were trained both with and without dropout. When training with dropout, at each update step, we retained each unit with probability 0.5.

The optimization results are shown in Figure 3. For each of the four datasets, the plots for objective function (cross-entropy), the training error and the test error are shown from left to right where in each plot the values are reported on different epochs during the optimization. The dropout is used for the experiments on CIFAR-100 and SVHN. Please see Neyshabur et al. (2015a) for a more complete set of experimental results.

We can see in Figure 3 that not only does Path-SGD often get to the same value of objective function, training and test error faster, but also the plots for test errors demonstrate that implicit regularization due to steepest descent with respect to path-regularizer leads to a solution that generalizes better. This provides further evidence on the role of implicit regularization in deep learning.

The results suggest that Path-SGD outperforms SGD and AdaGrad in two different ways. First, it can achieve the same accuracy much faster and second, the implicit regularization by Path-SGD leads to a local minima that can generalize better even when the training error is zero. This can be better analyzed by looking at the plots for more number of epochs which we have provided in Neyshabur et al. (2015a). We should also point that Path-SGD can be easily combined with AdaGrad or Adam to take advantage of the adaptive stepsize or used together with a momentum term. This could potentially perform even better compare to Path-SGD.

Discussion

We demonstrated the implicit regularization in deep learning through experiments and discussed the importance of geometry of optimization in finding a “low complexity” solution. Based on that, we revisited the choice of the Euclidean geometry on the weights of RELU networks, suggested an alternative optimization method approximately corresponding to a different geometry, and showed that using such an alternative geometry can be beneficial. In this work we show proof-of-concept success, and we expect Path-SGD to be beneficial also in large-scale training for very deep convolutional networks. Combining Path-SGD with AdaGrad, with momentum or with other optimization heuristics might further enhance results.

Although we do believe Path-SGD is a very good optimization method, and is an easy plug-in for SGD, we hope this work will also inspire others to consider other geometries, other regularizers and perhaps better, update rules. A particular property of Path-SGD is its rescaling invariance, which we argue is appropriate for RELU networks. But Path-SGD is certainly not the only rescaling invariant update possible, and other invariant geometries might be even better.

Finally, we choose to use steepest descent because of its simplicity of implementation. A better choice might be mirror descent with respect to an appropriate potential function, but such a construction seems particularly challenging considering the non-convexity of neural networks.

Research was partially funded by NSF award IIS-1302662 and Intel ICRI-CI.

References