1 Introduction↩︎

It is generally believed that the success of deep learning hinges on the ability of deep neural networks (DNNs) to learn features that are well suited to the task they are trained on. There is however little understanding of what these features are and how they are selected by the network.

On the other hand, recent results [1] have shown that it is possible to train DNNs without feature learning. This suggests the existence of two regimes of DNNs, a kernel regime (also called lazy or NTK regime) without feature learning and an active regime where features are learned. The presence or absence of feature learning can depend on multiple factors, such as the initialization/parametrization of DNNs [2]–[5], very large depths [6] or large learning rate [7], [8].

In this paper, we focus on the impact of \(L_{2}\) regularization on feature learning in DNNs. This analysis is further motivated by recent results [9]–[11] which show that the implicit bias of gradient descent on losses such as the cross entropy (which decay exponentially towards infinity) is essentially the same as the bias induced by \(L_2\) regularization in DNNs.

Generally, the bias induced by the addition of \(L_{2}\)-regularization on the parameters \(\theta\) of a model \(f_{\theta}\) can be described by the representation cost \(R(f)=\min_{\theta:f_{\theta}=f}\left\Vert \theta\right\Vert ^{2}\), since \(\min_{\theta}C(f_{\theta})+\lambda\left\Vert \theta\right\Vert ^{2}=\min_{f}C(f)+\lambda R(f)\).

In deep linear networks, the addition of \(L_{2}\) regularization on the parameters corresponds to the addition of an \(L_{p}\)-Schatten norm regularization to the represented matrix, with \(p=\frac{2}{L}\) where \(L\) is the depth of the network [10], [12]. This implies a sparsity effect that increases with depth \(L\).

In non-linear networks the sparsity effect of \(L_{2}\)-regularization has been described for shallow networks (\(L=2\)) in [13]–[15] or for shallow non-linear networks with added linear layers [16]. Though it seems natural that this effect should become stronger for deeper networks, to our knowledge little theoretical work has been done in this area.

1.1 Contributions↩︎

In this paper, we study the minima of the loss of \(L_{2}\) regularized fully-connected DNNs of depth \(L\). We propose two reformulations of the loss:

1. The first reformulation expresses the loss in terms of the representations \(Z_{1},\dots,Z_{L}\) (the layer pre-activations of every input in the training set) of every layer of the network. This reformulation has the advantage of being local - the optimal choice of a layer \(Z_{\ell}\) only depends on its neighboring layers \(Z_{\ell-1}\) and \(Z_{\ell+1}\). The optimal choice of representation \(Z_{\ell}\) is at the balance between an attractive force (determined by the previous layer) and a repulsive force (coming from the next layer). It illustrates how the representations \(Z_{1},\dots,Z_{L-1}\) interpolates between the input layer \(Z_{0}\) and output layer \(Z_{L}\).

2. The second reformulation expresses the loss in terms of the covariances of the representation before applying the non-linearity \(K_{\ell}=Z_{\ell}^{T}Z_{\ell}\) and after the non-linearity \(K_{\ell}^{\sigma}=\left(Z_{\ell}^{\sigma}\right)^{T}Z_{\ell}^{\sigma}\). For positively homogeneous non-linearities and when the number of neurons \(n_{\ell}\) in every hidden layer \(\ell\) is larger or equal to \(N(N+1)\) for \(N\) the number of datapoints, this reformulation is an optimization of a (partially convex) loss over the covariances \((K_{1},K_{1}^{\sigma}),\dots,(K_{L-1},K_{L-1}^{\sigma})\) and the outputs \(Z_{L}\), restricted to a (translated) convex cone. This reformulation does not depend on the number of neurons \(n_{\ell}\) in the hidden layers (as long as \(n_{\ell}\geq N(N+1)\)).

The second reformulation implies that for positively homogeneous non-linearities such as the ReLU, as the number of neurons in the hidden layers \(n_{\ell}\) increase, the global minimum of the \(L_{2}\)-regularized loss goes down until reaching a plateau (i.e. adding neurons does not lead to an improvement in the loss). This illustrates the sparsity effect of \(L_{2}\)-regularization, where the optimum reached on a very large network is equivalent to a much smaller network.

The start of the plateau hence gives a measure of sparsity of the global minimum. We show that the minimal number of neurons \(n_{\ell}\) to reach this plateau is determined by a notion of rank \(\mathrm{Rank}_{\sigma}\left(K_{\ell},K_{\ell}^{\sigma}\right)\) of the covariance pairs. We show that \(\mathrm{Rank}_{\sigma}\left(K_{\ell},K_{\ell}^{\sigma}\right)\leq N(N+1)\), i.e. the plateau must start before \(N(N+1)\) and that the scaling of this upper bound is tight by giving an example dataset such that at the optimum \(\mathrm{Rank}_{\sigma}\left(K_{\ell},K_{\ell}^{\sigma}\right)\geq N^{2}/4\). We also present other datasets where the start of the plateau is either constant or grows linearly with the number of datapoints. We also observe empirically that the plateau can start at much smaller widths for real data such as MNIST and the teacher/student setting.

2 Setup↩︎

We consider fully-connected deep neural networks with \(L+1\) layers, numbered from \(0\) (the input layer) to \(L\) (the output layer), with nonlinear activation function \(\sigma:\mathbb{R}\to\mathbb{R}\) (e.g. the ReLU \(\sigma(x)=\max\{0,x\}\))). Each layer \(\ell\) contains \(n_{\ell}\) neurons and we denote \(\mathbf{n}=\left(n_{1},\dots,n_{L}\right)\) the widths of the network. Given an input dataset \(\{x_{1},\ldots,x_{N}\}\subset\mathbb{R}^{n_{0}}\) of size \(N\), we consider the data matrix \(X=(x_{0},\ldots,x_{n})\in\mathbb{R}^{n_{0}\times N}\), and encode the activations and preactivations of the whole data set by considering the pre-activations \(Z_{\ell}(X;\mathbf{W})\in\mathbb{R}^{n_{\ell}\times N}\) and activations \(Z_{\ell}^{\sigma}(X;\mathbf{W})\in\mathbb{R}^{(n_{\ell}+1)\times N}\) given by: \[\begin{align} Z_{0}^{\sigma}(X;\mathbf{W}) & =\left(\begin{array}{c} X\\ \beta\mathbf{1}_{N}^{T} \end{array}\right)\\ Z_{\ell}(X;\mathbf{W}) & =W_{\ell}Z_{\ell-1}^{\sigma}(X;\mathbf{W})\\ Z_{\ell}^{\sigma}(X;\mathbf{W}) & =\left(\begin{array}{c} \sigma\left(Z_{\ell}\right)\\ \beta\mathbf{1}_{N}^{T} \end{array}\right), \end{align}\] where \(\mathbf{W}=\left(W_{\ell}\right)_{\ell=1,\dots,L}\) is the collection of \(n_{\ell}\times (n_{\ell-1}+1)\)-dim weight matrices \(W_{\ell}\), \(\sigma\left(Z_{\ell}\right)\) is obtained by applying elementwise the nonlinearity \(\sigma\) to the matrix \(Z_{\ell}\), and the scalar \(\beta\in\mathbb{R}\) represents the amount of bias (i.e. when \(\beta=0\) there is no bias, when \(\beta=1\) this definition is equivalent to the traditional definition of bias). The output of the network is the pre-activation of the \(L\)-th layer \(Z_{L}\).

We often drop the dependence on the weights \(\mathbf{W}\) and on the dataset \(X\) and simply write \(Z_{\ell}\) and \(Z_{\ell}^{\sigma}\).

We denote \(f_{\mathbf{W}}:\mathbb{R}^{n_{0}}\to\mathbb{R}^{n_{L}}\) the network function, which maps an input \(x\) to the pre-activation at the last layer.

2.1 \(L_{2}\)-Regularized Loss and Representation Cost↩︎

Given a general cost functional \(C:\mathbb{R}^{n_{L}\times N}\to\mathbb{R}\), the \(L_{2}\)-regularized loss of DNNs of widths \(\mathbf{n}\) is \[\mathcal{L}_{\lambda,\mathbf{n}}(\mathbf{W})=C(Z_{L}(X;\mathbf{W}))+\lambda\left\Vert \mathbf{W}\right\Vert ^{2},\] where \(\left\Vert \mathbf{W}\right\Vert\) is the \(L_{2}\)-norm of \(\mathbf{W}\) understood as a vector. Note that \(\left\Vert \mathbf{W}\right\Vert ^{2}=\sum_{\ell=1}^{L}\left\Vert W_{\ell}\right\Vert _{F}^{2}\) where \(\left\Vert \cdot\right\Vert _{F}\) denotes the Frobenius norm. From now on, we often omit to specify the widths \(\mathbf{n}\) and simply write \(\mathcal{L}_{\lambda}\).

The additional regularization cost should bias the network toward low norm solutions. This bias on the parameters leads to a bias in function space, which is described by the so-called representation cost \(\mathcal{R}_{\mathbf{n}}(f)\) defined on functions \(f:\mathbb{R}^{n_{0}}\to\mathbb{R}^{n_{L}}\): \[\mathcal{R}_{\mathbf{n}}(f)=\min_{\mathbf{W}:f_{\mathbf{W}}=f}\left\Vert \mathbf{W}\right\Vert ^{2},\] where the minimum is taken over all choices of parameters \(\mathbf{W}\) of a width \(\mathbf{n}\) network, with fixed \(\beta\) bias amount, such that the network function \(f_{\mathbf{W}}\) equals \(f\). By convention, if no such parameters exist then \(\mathcal{R}_{\mathbf{n}}(f)=+\infty\).

Similarly, given an input-output pair \(X\in\mathbb{R}^{n_{0}\times N}\), \(Y\in\mathbb{R}^{n_{L}\times N}\), the representation cost \(R_{\mathbf{n}}(X,Y)\) is: \[R_{\mathbf{n}}(X,Y)=\min_{\mathbf{W}:Z_{L}(X,\mathbf{W})=Y}\left\Vert \mathbf{W}\right\Vert ^{2},\] with again the convention that if there exists no weight \(\mathbf{W}\) such that \(Z_{L}(X,\mathbf{W})=Y\), then \(R_{\mathbf{n}}(X,Y)=+\infty\). The representation cost \(R_{\mathbf{n}}\) naturally describes the bias induced by the \(L_{2}\)-regularized loss of DNNs since: \[\min_{\mathbf{W}}C(Z_{L}(X;\mathbf{W}))+\lambda\left\Vert \mathbf{W}\right\Vert ^{2}=\min_{Y}C(Y)+\lambda R_{\mathbf{n}}(Y,X).\]

3 Two Reformulations of the Regularized Loss: Hidden Representation and Covariance Optimization↩︎

We now provide two reformulations of the \(L_{2}\)-regularized loss \(\mathcal{L}_{\lambda}(\mathbf{W})\) and representation cost \(R_{\mathbf{n}}(X,Y)\), which both put emphasis on the hidden representations \(Z_{\ell}\) and how they are progressively modified throughout the neural network. The first reformulation holds for general non-linearities while the second only applies to networks with homogeneous nonlinearities.

3.1 Feature optimization : attraction/repulsion↩︎

The key observation is that the weights \(W_{\ell}\) can be decomposed as follows: \[W_{\ell}=Z_{\ell}\left(Z_{\ell-1}^{\sigma}\right)^{+}+\tilde{W}_{\ell},\] where the residual matrix \(\tilde{W}_{\ell}\) is orthogonal to \(Z_{\ell-1}^{\sigma}\), i.e. \(\tilde{W}_{\ell}Z_{\ell-1}^{\sigma}=0\), and \((\cdot)^{+}\) is the Moore-Penrose pseudo-inverse. This stems from the fact that \(W_{\ell}=W_{\ell}\mathrm{P}_{\mathrm{Im}Z_{\ell-1}^{\sigma}}+\tilde{W}_{\ell}\) where \(\tilde{W}_{\ell}:=W_{\ell}\mathrm{P}_{(\mathrm{Im}Z_{\ell-1}^{\sigma})^{\perp}}\), and \(\mathrm{P}_{\mathrm{Im}Z_{\ell-1}^{\sigma}}\), resp. \(\mathrm{P}_{(\mathrm{Im}Z_{\ell-1}^{\sigma})^{\perp}}\), is the orthogonal projection on \(\mathrm{Im}Z_{\ell-1}^{\sigma}\), resp. on the orthogonal complement of \(\mathrm{Im}Z_{\ell-1}^{\sigma}\); one concludes using the facts that \(\mathrm{P}_{\mathrm{Im}Z_{\ell-1}^{\sigma}}=Z_{\ell-1}^{\sigma}\left(Z_{\ell-1}^{\sigma}\right)^{+}\) and \(Z_{\ell}=W_{\ell}Z_{\ell-1}^{\sigma}\) .

Note that the matrix \(\tilde{W}_{\ell}\) does not affect either the hidden representations \(Z_{\ell}\) nor the output \(Z_{L}\). Besides, the Frobenius norm of \(W_{\ell}\) can be rewritten as \(\vert\!\vert W_{\ell}\vert\!\vert_{F}^{2}=\vert\!\vert Z_{\ell}\left(Z_{\ell-1}^{\sigma}\right)^{+}\vert\!\vert_{F}^{2}+\vert\!\vert\tilde{W}_{\ell}\vert\!\vert_{F}^{2}\). When minimizing the \(L_{2}\)-regularized cost, it is therefore always optimal to consider null residual matrices \(\tilde{W}_{\ell}=0\), resulting in a reformulation of the cost which only depends on the pre-activations \(Z_{\ell}\):

Note that one can also reformulate the representation cost: \[R_{\mathbf{n}}(X,Y)=\min_{\mathbf{Z}\in\mathcal{Z},Z_{L}=Y}\sum_{\ell=1}^{L}\left\Vert Z_{\ell}\left(Z_{\ell-1}^{\sigma}\right)^{+}\right\Vert _{F}^{2}.\] The representation in terms of the output and hidden representations have several interesting properties, especially when it comes to minimization:

1. The optimization becomes local in the sense that all terms and constraints depend either only on the output cost \(C(Z_{L})\) or on two neighboring terms (e.g. \(\left\Vert Z_{\ell}\left(Z_{\ell-1}^{\sigma}\right)^{+}\right\Vert _{F}^{2}\)). As a result, the (projected) gradient of the loss \(\mathcal{L}_{\lambda}^r(Z_{1},...,Z_{L})\) w.r.t. to \(Z_{\ell}\) only depends on \(Z_{\ell-1},Z_{\ell}\) and \(Z_{\ell+1}\). This is in contrast to the optimization of \(\mathcal{L}_{\lambda}(\mathbf{W})\), where the gradient of \(C(Z_{L})\) with respect to \(W_{\ell}\) depends on all parameters \(W_{1},\ldots,W_{L}\).

2. The value \(\left\Vert Z_{\ell}\left(Z_{\ell-1}^{\sigma}\right)^{+}\right\Vert _{F}^{2}\) represents a ‘multiplicative distance’ between \(Z_{\ell}\) and \(Z_{\ell-1}^{\sigma}\) (in contrast to the ‘additive distance’ \(\left\Vert Z_{\ell}-Z_{\ell-1}^{\sigma}\right\Vert _{F}^{2}\)); the representation \(Z_{\ell}\) therefore interpolates multiplicatively between \(Z_{\ell-1}\) and \(Z_{\ell+1}\). This is most obvious for linear networks (i.e. \(\sigma=\mathrm{id}\) and \(\beta=0\)): in this case, one can check that at any global minimizer, the covariances of the hidden layers equal \(Z_{\ell}^{T}Z_{\ell}=X^{T}(X^{-T}Z_{L}^{T}Z_{L}X^{-1})^{\frac{\ell}{L}}X\), interpolating between the input covariance \(X^{T}X\) and output covariance \(Z_{L}^{T}Z_{L}\).

3. A lot of work has been done to propose biologically plausible training methods for DNNs [18], [19], in contrast to backpropagation which is not local. A line of work [20]–[22], propose a biologically plausible optimization technique which minimizes a cost which closely resembles our first reformulation, with the multiplicative distances \(\left\Vert Z_{\ell}\left(Z_{\ell-1}^{\sigma}\right)^{+}\right\Vert _{F}^{2}\) replaced by additive ones \(\left\Vert Z_{\ell}-Z_{\ell-1}^{\sigma}\right\Vert _{F}^{2}\). Due to this change, there is no direct correspondence between the networks trained with this biologically plausible technique and those trained with backpropagation. If one could extend this training technique to work with multiplicative distances one could guarantee such a direct correspondence.

4. The optimization leads to an attraction-repulsion algorithm. If we optimize only on the term \(Z_{\ell}\) and fix all other representations, the only two terms that depend on \(Z_{\ell}\) are \(\left\Vert Z_{\ell}\left(Z_{\ell-1}^{\sigma}\right)^{+}\right\Vert _{F}^{2}\) and \(\left\Vert Z_{\ell+1}\left(Z_{\ell}^{\sigma}\right)^{+}\right\Vert _{F}^{2}\). The former term is attractive as it pushes the representations \(Z_{\ell}\) towards the origin (and hence pushes the representations at depth \(\ell\) of every input towards each other), especially along directions where \(Z_{\ell-1}^{\sigma}\) is small. The latter term is repulsive as it pushes the representations \(Z_{\ell}^{\sigma}\) away from the origin, especially along directions where \(Z_{\ell+1}\) is large.

5. This attraction-repulsion process is similar to the Information Bottleneck theory [23]: the repulsive term ensure that \(Z_{\ell}\) keeps enough information about the inputs to reconstruct \(Z_{\ell+1}\), while the attractive term pushes \(Z_{\ell}\) to keep as little information as possible.

The attraction and repulsion forces of of the \(\ell\)-th layer are the derivative \(\partial_{Z_{\ell}}\left\Vert Z_{\ell}\left(Z_{\ell-1}^{\sigma}\right)^{+}\right\Vert _{F}^{2}\) and \(\partial_{Z_{\ell}}\left\Vert Z_{\ell+1}\left(Z_{\ell}^{\sigma}\right)^{+}\right\Vert _{F}^{2}\) which are both \(n_{\ell}\times N\) matrices. One can visualize these forces either column by column (each column corresponding to a datapoint \(i=1,\dots,N\)) or line by line (each line corresponding to a neuron \(k=1,\dots,n_{\ell}\)). These two visualizations of the forces are presented in Figure 1 for the two hidden layers of a depth \(L=3\) network, projected to the 2 largest principal components of the columns resp. lines of \(Z_{\ell}\). Figures 1 (a) and 1 (c) illustrate how the inputs corresponding to different classes are pushed away from each other, leading to a clustering effect. Figures 1 (b) and 1 (d) show that the neurons naturally align along rays starting from the origin. This happens for homogeneous non-linearities, such as the ReLU in this example, because if two neurons \(k,k'\) have proportional activations, i.e. \(Z_{\ell,k}=\alpha Z_{\ell,k}\) for some \(\alpha\in\mathbb{R}\), then their attractive and repulsive forces will also be proportional with the same scaling \(\alpha\). As a result, the neuron \(k\) is stable, i.e. the attraction and repulsion cancel each other, if and only if the neuron \(k'\) is stable.

This phenomenon can be interpreted as a form of sparsity: a group of aligned neurons can be replaced by a single neuron without changing the resulting function \(Z_{L}\). Can we guarantee a degree of sparsity in the hidden representations? Can we bound the number of aligned groups in a neuron? In the next section, we introduce a further reformulation of the loss which allows us to partially answer these questions.

3.2 Covariance learning : partial convex optimization for positively homogeneous nonlinearities↩︎

The loss of the first reformulation \(\mathcal{L}_{\lambda}^{r}\) depends on the hidden representations \(Z_{\ell}\) and \(Z_{\ell}^{\sigma}\) only through the covariances \(K_{\ell}=Z_{\ell}^{T}Z_{\ell}\) and \(K_{\ell}^{\sigma}=\left(Z_{\ell}^{\sigma}\right)^{T}Z_{\ell}^{\sigma}\), since \(\left\Vert Z_{\ell}\left(Z_{\ell-1}^{\sigma}\right)^{+}\right\Vert _{F}^{2}=\mathrm{Tr}\left[K_{\ell}\left(K_{\ell-1}^{\sigma}\right)^{+}\right]\). Hence, we provide a second reformulation expressed in terms of the tuple of covariance pairs \(\mathbf{K}=((K_{1},K_{1}^{\sigma}),\dots,(K_{L-1},K_{L-1}^{\sigma}))\) and the outputs \(Z_{L}\). Using the notations \(K_{0}^{\sigma}=X^{T}X+\beta^{2}\mathbf{1}_{N\times N}\) and \(K_{L}=Z_{L}^{T}Z_{L}\), we define: \[\mathcal{L}_{\lambda}^{\mathrm{k}}(\mathbf{K},Z_{L})=C(Z_{L})+\lambda\sum_{\ell=1}^{L}\mathrm{Tr}\left[K_{\ell}\left(K_{\ell-1}^{\sigma}\right)^{+}\right].\] It remains to identify the set \(\mathcal{K}_{\mathbf{n}}(X)\) of covariances \(\mathbf{K}\) and outputs \(Z_{L}\) which can be represented by a width \(\mathbf{n}\) network with inputs \(X\). For positively homogeneous nonlinearities of degree 1 such as the ReLU (i.e. when \(\sigma(\lambda x)=\lambda\sigma(x)\) for any positive \(\lambda\)), the set \(\mathcal{K}_{\mathbf{n}}(X)\) can be expressed using the notion of conical hulls.

Note that one can also reformulate the representation cost: \[R_{\mathbf{n}}(X,Y)=\min_{\mathbf{K}:(\mathbf{K},Y)\in\mathcal{K}_{\mathbf{n}}(X)}\sum_{\ell=1}^{L}\mathrm{Tr}\left[K_{\ell}\left(K_{\ell-1}^{\sigma}\right)^{+}\right].\]

Since the dimension of the space of pairs of symmetric \(N\times N\) matrices is \(N(N+1)\), if \(n_{\ell}\geq N(N+1)\) then, by the Caratheodory’s theorem for conical hulls, \[S_{n_{\ell}}=S:=\mathrm{cone}\left( \left\{ \left(xx^{T},\sigma(x)\sigma(x)^{T}\right):x\in\mathbb{S}^{N-1}\right\} \right) +(0,\beta^{2}\mathbf{1}_{N\times N}).\] Hence, as soon as \(n_{\ell}\geq N(N+1)\) for all hidden layers, the set \(\mathcal{K}_{\mathbf{n}}(X)\) does not depend on the list of widths \(\mathbf{n}\). We denote \[\mathcal{K}(X)=\left\{ (\mathbf{K},Z_{L})\mid\forall\ell=1,\ldots,L-1,(K_{\ell},K_{\ell}^{\sigma})\in S,\mathrm{Im}K_{\ell}\subset\mathrm{Im}K_{\ell-1}^{\sigma},\mathrm{Im}Z_{L}\subset\mathrm{Im}K_{L-1}^{\sigma}\right\}\] this width-independent set. The following proposition shows that for sufficiently wide networks with a positively homogeneous nonlinearity, training a deep DNN with \(L_{2}\) regularization is equivalent to a partially convex optimization over a translated convex cone.

3.3 Direct optimization of the reformulations↩︎

It is natural at this point to wonder whether one could optimize directly over the representations \(\mathbf{Z}\) (using the first reformulation) or over the covariances \(\mathbf{K}\) and output \(Z_{L}\) (using the second reformulation), and whether this would have an advantage over the traditional optimization of the weights.

For the first reformulation, one can simply use the projected gradient descent with updates given by \[\mathbf{Z}_{t+1}=P_{\mathcal{Z}}\left(\mathbf{Z}_{t}-\eta\nabla\mathcal{L}_{\lambda}^{r}(\mathbf{Z})\right)\] for any projection \(P_{\mathcal{Z}}\) to the constraint space \(\mathcal{Z}\). For example, a projection is obtained by mapping \(Z_{\ell}\) to \(Z_{\ell}P_{\mathrm{Im}Z_{\ell-1}^{\sigma}}\) sequentially from \(\ell=1\) to \(\ell=L\). Note however that the loss explodes as the constraints become unsatisfied so that for gradient flow, there is no need for the projections. This suggests that these projections might also be unnecessary as long as the learning rate is small enough. For more details, see Appendix 6.1. For the second reformulation, there is no obvious way to compute a projection to the constraint space \(\mathcal{K}\): the cone \(S\) is spanned by an infinite amount of points and we do not have an explicit formula for the dual cone \(S^{*}\). Frank-Wolfe optimization can be used to overcome the need for computing the projections.

However, these direct optimizations of the reformulations lead to issues of computational complexity and stability. First, the computation of the gradients \(\nabla\mathcal{L}_{\lambda}^{r}(\mathbf{Z})\) and \(\nabla\mathcal{L}_{\lambda}^{\mathrm{k}}(\mathbf{K},Z_{L})\) requires solving a linear equation of dimension \(N\), which is very costly, in contrast to the traditional optimization of the weights \(\mathbf{W}\) for which the gradient can be computed very efficiently. Second, if \(Z_{\ell}^{\sigma}\) is not full-rank, the computation of its pseudo-inverse \(\left(Z_{\ell}^{\sigma}\right)^{+}\) and the projection \(P_{\mathrm{Im}Z_{\ell}^{\sigma}}\) are very unstable. Therefore, if we only have finite-precision knowledge of \(Z_{\ell}\), we cannot reliably compute \(\left(Z_{\ell}^{\sigma}\right)^{+}\) nor \(P_{\mathrm{Im}Z_{\ell}^{\sigma}}\).

Although it could be possible to solve these problems (e.g. using the Tikhonov regularization for the unstability problem) and to develop efficient algorithms to optimize both reformulations efficiently, we decided in this paper to focus on the theoretical implications of these reformulations.

4 Sparsity of the Regularized Optimum for Homogeneous DNNs↩︎

In this section, we assume that the non-linearity is positively homogenous. Under this assumption, the second reformulation of the loss (and of the representation cost) holds and implies the existence of a sparsity phenomenon.

First observe that as the widths \(\mathbf{n}\) increase, both the global minimizer of the loss \(\min_{\mathbf{W}}\mathcal{L}_{\lambda}(\mathbf{W})\) and the representation cost \(R_{\mathbf{n}}(X,Y)\) diminish. We denote by \(\mathcal{L}_{\lambda,\mathbf{n}}\) the \(L_{2}\)-regularized loss of DNNs with widths \(\mathrm{n}\). Recall that the depth \(L\) is fixed.

For DNNs with positively homogeneous nonlinearities, a direct consequence of our reformulation through the hidden covariances is that both the global minimum of the loss \(\mathcal{L}_{\lambda}\) and the representation cost \(R_{\mathbf{n}}(X,Y)\) plateau for any widths \(\mathbf{n}\) such that \(n_{\ell}\geq N(N+1)\).

We can therefore define a width-independent representation cost \(R(X,Y)\) (which still depends on the fixed depth \(L\)) equal to the representation cost \(R_{\mathbf{n}}(X,Y)\) of any sufficiently wide network.

4.1 Rank of the Hidden Representations↩︎

Now that we have revealed the plateau phenomenon, a natural question that we investigate in this section is when does this plateau begin. In order to do so, we introduce the notion of rank \(\mathrm{Rank}_{\sigma}(K,K^{\sigma})\) of a pair of Gram matrices \((K,K^{\sigma})\in S\) which is the minimal number \(k\) such that \[K=\sum_{i=1}^{k}z_{i}z_{i}^{T}\text{ and }K^{\sigma}=\sum_{i=1}^{k}\sigma\left(z_{i}\right)\sigma\left(z_{i}\right)^{T}+\beta^{2}\mathbf{1}_{N\times N}\label{eq:Rank-Signa}\tag{1}\] for some \(z_{1},\dots,z_{k}\in\mathbb{R}^{N}\). This notion of rank describes exactly the minimal number of neurons required to recover a set of covariances \(\mathbf{K}\):

We can now describe the plateau \(R=\left\{ \mathbf{n}:\min_{\mathbf{W}\in\mathbb{R}^{P_{\mathbf{n}}}}\mathcal{L}_{\lambda,\mathbf{n}}(\mathbf{W})=\min_{\mathbf{m}}\min_{\mathbf{W}\in\mathbb{R}^{P_{\mathbf{m}}}}\mathcal{L}_{\lambda,\mathbf{m}}(\mathbf{W})\right\}\), i.e. the set of widths \(\mathbf{n}\) such that the minimum \(\min_{\mathbf{W}\in\mathbb{R}^{P_{\mathbf{n}}}}\mathcal{L}_{\lambda,\mathbf{n}}(\mathbf{W})\) is optimal over all possible widths:

Hence, the investigation of \(\mathrm{Rank}_{\sigma}(\cdot,\cdot)\) is crucial to understand where the plateau begins; unfortunately, it can be difficult to compute. However, from its definition and the Caratheodory’s theorem for conical hulls (see our discussion after Remark 4), we have the following natural bounds:

We show in the next section that the order of magnitude of the upper bound is tight. More specifically, we construct a dataset for which any global optimum satisfies \(\mathrm{Rank}_{\sigma}(K_{1},K_{1}^{\sigma})\geq\frac{N^{2}}{4}\). This implies that, in this example, the plateau transition occurs when the number of hidden neurons is of order \(O(N^{2})\). Note however that, in our numerical experiments (see Figure 2), the rank of the global optimum can be much smaller for more traditional dataset such as MNIST.

4.2 Tightness of the Upper-Bound↩︎

In this section, we construct a pair of input and output datasets \(X\) and \(Y\), both in \(\mathbb{R}^{N\times N}\), such that for any optimal parameters \(\mathbf{W}\) of a ReLU network of depth \(L=2\) with no bias (\(\beta=0\)), the rank of the hidden representation \(\mathrm{Rank}_{\sigma}\left(K_{1},K_{1}^{\sigma}\right)\) is greater than \(\frac{N^{2}}{4}\).

Note that one can write the decomposition (1 ) as \(K=C^{T}C\) and \(K_{\sigma}=B^{T}B\) where \(C=(z_{1},\ldots,z_{k})\) and \(B=\mathrm{ReLU}(C)\) is obtained by applying elementwise the ReLU to \(C\). Key to our construction is the fact that \(B\) is then a matrix with non-negative entries: the matrix \(K_{\sigma}\) is completely positive and \(\mathrm{Rank}_{\sigma}\left(K,K^{\sigma}\right)\) can be studied using the CP-rank of \(K\):

When \(\sigma\) is the ReLU, the kernel \(K_{\ell}^{\sigma}\) is completely positive for all hidden layers \(\ell\), and thus \[\max\left(\mathrm{Rank}\left(K_{\ell}\right),\mathrm{Rank}_{cp}\left(K_{\ell}^{\sigma}\right)\right)\leq\mathrm{Rank}_{\sigma}(K,K^{\sigma}).\] In order to obtain the tightness of the upper bound, we proceed in two steps: first, we construct a completely positive matrix \(A\) with high CP-rank, and then construct inputs \(X\) and outputs \(Y\) such that the optimal hidden covariance \(K_{1}=K_{1}^{\sigma}\) for a depth \(L=2\) network equals the matrix \(A\).

As shown in [24], bi-partite graphs can be used to construct matrices with high CP-rank. We refine this by showing that graphs on \(N\) vertices without cliques of \(3\) or more vertices lead to \(N \times N\) matrices with CP-rank equal to the number of edges, and as a corollary, we construct a completely positive matrix with CP-rank equal to \(\frac{N^{2}}{4}\).

Hence, to obtain a completely positive matrix of high CP-rank, it remains to find a graph with no cliques and as many edges as possible. For even \(N\), we consider the complete bipartite graph, i.e. the graph with two groups of size \(N/2\) and with edges between any two vertices iff they belong to different groups. For this graph, the matrix \(B_N=E^{T}E\) takes the form of a block matrix: \[B_{N}=\left(\begin{array}{cc} \frac{N}{2}I_{\frac{N}{2}} & \mathbf{1}_{\frac{N}{2}\times\frac{N}{2}}\\ \mathbf{1}_{\frac{N}{2}\times\frac{N}{2}} & \frac{N}{2}I_{\frac{N}{2}} \end{array}\right)\] where \(\mathbf{1}_{\frac{N}{2}}\) is the \(N/2\times N/2\) matrix with all ones entries. Since this bipartite graph has no cliques and \(\frac{N^{2}}{4}\) edges, from the previous proposition, we obtain \(\mathrm{Rank_{cp}}\left(B_{N}\right)=\frac{N^{2}}{4}\).

The following proposition shows how for any completely positive matrix (with CP-rank \(k\)) there is a dataset such that a shallow ReLU network will have a hidden representation pair \((K_1,K_1^\sigma)\)of rank \(k\):

By Proposition 14, with the outputs \(Y_N=B_N\), the rank of the hidden representations (and the start the plateau) is larger or equal to \(\frac{N^2}{4}\). This shows that the order \(N^2\) of the bound of Lemma 10 is tight when it comes to data-agnostic bounds. However under certain assumptions on the data one can guarantee a much earlier plateau.

For example, if we instead apply Proposition 14 to a task closer to classification, where the columns of the outputs \(Y_N \in \mathbb{R}^{n_L \times N}\) are one-hot vectors, then \((Y_N^T Y_N)^{\frac{1}{2}}\) is (up to permutations of the columns/lines) a block diagonal matrix with \(n_L\) constant positive blocks, which is completely positive with CP-rank equal to the number of classes \(n_L\). This is in line with our empirical experiments in Figure 2 where we observe in MNIST a plateau starting roughly at a width of 10, which is the number of classes.

Another example where the structure of the data leads to an earlier plateau is when the input and output dimensions are both 1, in which case we can guarantee that the start of the plateau grows at most linearly with the number of datapoints \(N\):

More generally, we propose to view the start of the plateau as an indicator of how well a certain task is adapted to a DNN architecture. An early plateau suggests that the network is able to solve the task optimally with very few neurons, in contrast to a late plateau. The fact that the optimal network requires few neurons (and hence few parameters) can be used to guarantee good generalization.

4.3 Conclusion↩︎

We have given two reformulations of the loss of \(L_{2}\)-regularized DNNs. The first works for a general non-linearity and shows how the hidden representations of the inputs \(Z_{1},\dots,Z_{L-1}\) are learned to interpolate between the input and output representations, as a balance between attraction and repulsion forces for every layer. The second reformulation for homogeneous non-linearities allows us to analyze a sparsity effect of \(L_{2}\)-regularized DNNs, where the learned networks are equivalent to another network with much fewer neurons. This effect can be visualized by the appearance of a plateau in the minimal loss as the number of neurons grows, the earlier the plateau, the sparser the solution, since an early plateau means that very few neurons were required to obtain the same loss as a network with an infinite number of neurons. We show that this plateau cannot start later than \(N(N+1)\), and then show that the order of this bound is tight by constructing a toy dataset for which the plateau starts at \(\frac{N^{2}}{4}\), however, we observe that on more traditional datasets, the start of the plateau can be much earlier.

Acknowledgements↩︎

C. Hongler acknowledges support from the Blavatnik Family Foundation, the Latsis Foundation, and the NCCR Swissmap.

Checklist↩︎

1. For all authors...

   1. Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?

   2. Did you describe the limitations of your work?

   3. Did you discuss any potential negative societal impacts of your work?

   4. Have you read the ethics review guidelines and ensured that your paper conforms to them?

2. If you are including theoretical results...

   1. Did you state the full set of assumptions of all theoretical results?

   2. Did you include complete proofs of all theoretical results?

3. If you ran experiments...

   1. Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)?

   2. Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)?

   3. Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)?

   4. Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)?

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...

   1. If your work uses existing assets, did you cite the creators?

   2. Did you mention the license of the assets?

   3. Did you include any new assets either in the supplemental material or as a URL?

   4. Did you discuss whether and how consent was obtained from people whose data you’re using/curating?

   5. Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content?

5. If you used crowdsourcing or conducted research with human subjects...

   1. Did you include the full text of instructions given to participants and screenshots, if applicable?

   2. Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable?

   3. Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation?

The appendix is structured as follows:

1. In Section 5, we describe the Experimental setup.

2. In Section 6, we prove Proposition 1 of the main underlying the first reformulation.

3. In Section 7, we prove Proposition 3 for the second reformulation. We also give an example of a local minimum of the original loss which is not a local minimum in the second reformulation.

4. In Section 8, we prove Proposition 8, 13, 14 and 15 of the main.

5 Experimental Setup↩︎

The experiments were done on fully-connected DNNs of depth \(L=3\) with varying widths.

We used the MNIST dataset [17] under the ‘Creative Commons Attribution-Share Alike 3.0’ license. For the MNIST examples we trained the networks on the multiclass cross-entropy loss with \(L_{2}\)-regularization.

We also used synthetic data sampled from a teacher network. The network has depth \(L=3\), widths \(\mathbf{n}=(50,10,10,10)\) with random Gaussian weights. The cost used was the Mean Squared Error (MSE).

For the experiments of Figure 1 of the main, the DNN was trained with full batch GD. For the experiments of Figure 2 we first trained with Adam [25] and finished with full batch GD (GD seems to be better suited to consistently reach the bottom of the local minima, though Adam trains faster overall). For the right plot of Figure 2, three independent networks were trained for every width and the one with the smallest loss at the end of training was chosen (the plotted test error is that of the chosen network).

The goal of Figure 2 is to identify the start of the plateau, note however that we cannot guarantee that our training procedures actually approaches a global minimum. Interestingly it was easier to observe a plateau on MNIST rather than on the teacher network data, which is why we had to take the minimum over 3 trials in the teacher setting. This could be due to the change of loss (from cross entropy to the MSE) or due to the change of the data. Note that in Figure 2 (right), it is unclear whether the ‘failed’ trials , i.e. the small blue dots with a loss above the plateau even for large widths, are stuck at local minima of the loss or if they could have reached the plateau if we had trained them longer.

The experiments each took between 1 and 4 hour on a single NVIDIA GeForce GTX 1080.

6 Equivalence for the first reformulation↩︎

6.1 Optimization↩︎

It is possible to optimize the first reformulation directly, using projected gradient descent to guarantee that the constraints \(\mathrm{Im}Z_{\ell+1}^{T}\subseteq\mathrm{Im}\left(Z_{\ell}^{\sigma}\right)^{T}\) remain satisfied. As we show now, this projection is unnecessary in the continuous case, which suggests that it might also be unnecessary in gradient descent with a small enough learning rate.

Assume there is a \(\ell\) s.t. \(\mathrm{Im}Z_{\ell+1}^{T}\nsubseteq\mathrm{Im}\left(Z_{\ell}^{\sigma}\right)^{T}\), i.e. there is a vector \(v\in\mathbb{R}^{N}\) (with \(\left\Vert v\right\Vert =1\)) such that \(v\in\ker Z_{\ell}^{\sigma}\) but \(\left\Vert Z_{\ell+1}v\right\Vert >0\). Consider any \(\tilde{\mathcal{Z}}\) such that \(\left\Vert \tilde{\mathcal{Z}}-\mathcal{Z}\right\Vert \leq\epsilon\), then \[\left\Vert \tilde{Z}_{\ell+1}\left(\tilde{Z}_{\ell}^{\sigma}\right)^{+}\right\Vert _{F}^{2}\geq\left\Vert \tilde{Z}_{\ell+1}vv^{T}\left(\tilde{Z}_{\ell}^{\sigma}\right)^{+}\right\Vert _{F}^{2}=\left\Vert \tilde{Z}_{\ell+1}v\right\Vert ^{2}\left\Vert v^{T}\left(\tilde{Z}_{\ell}^{\sigma}\right)^{+}\right\Vert ^{2}\geq\frac{\left\Vert Z_{\ell+1}v\right\Vert ^{2}-\epsilon}{\epsilon}.\] This implies that the loss explodes in the vicinity of any point where the constraints are not satisfied. As a result, gradient flow on the cost \(\mathcal{L}_{\lambda}^{r}\) starting from a value with a non-zero loss will never approach a non-acceptable point (where \(\mathrm{Im}Z_{\ell+1}^{T}\nsubseteq\mathrm{Im}\left(Z_{\ell}^{\sigma}\right)^{T}\)) since the loss is decreasing during gradient flow.

7 Equivalence for the second reformulation↩︎

7.1 Non-correspondence of the local minima↩︎

Let us consider the map \(\Gamma:\mathbf{Z}\mapsto(\mathbf{K},Z_{L})\) which maps each hidden representation \(Z_{\ell}\) to the kernel pair \((Z_{\ell}^{T}Z_{\ell},\left(Z_{\ell}^{\sigma}\right)^{T}Z_{\ell}^{\sigma})\). The continuity of \(\Gamma\) implies that if \(\Gamma(\mathbf{Z})\) is a local minimum then so is \(\mathbf{Z}\). The converse is not true, instead we have:

Let us now give an example of a set of weights \(\mathbf{W}\) of a depth \(L=2\) network which is a local minimum of \(\mathcal{L}_{\lambda}\) but such that the corresponding covariances \((\mathbf{K},Z_{L})\) are not a local minimum of \(\mathcal{L}_{\lambda}^{k}\):

8 Description of the Plateau↩︎

8.1 Tightness of the upper bound↩︎

Let us first prove the Proposition on the CP-rank of matrices resulting from graphs without cliques:

We may now prove the tightness of the upper bound on the \(\sigma\)-rank of the hidden representation in shallow ReLU networks without bias:

To show the tightness (up to constant factor) of the upper bound, one can simply apply this proposition to the special case \(Y_N=E^T E\), where \(E\) is the edge-vertex incidence matrix of the complete bipartite graph, in which case \(k=\frac{N^2}{4}\).

We could also consider an output dataset \(Y_N\in \mathbb{R}^{n_L \times} N\) whose lines are one-hot vectors, corresponding to a classification task. If we reorder the training set by class, the covariance \(Y_N^T Y_N\) is a block diagonal matrix, with all ones blocks corresponding to each class. The square root \(\left( Y_N^T Y_N \right)^{\frac{1}{2}}\) is also block-diagonal but the block of a class \(i\) has value \(\frac{1}{m_i}\) where \(m_i\) is the number of datapoints in the class \(i\). The matrix \(\left( Y_N^T Y_N \right)^{\frac{1}{2}}\) is completely positive and has rank \(k\) equal to the number of classes. This implies a much earlier plateau, which could explain why in real-world classification tasks, we observe a very early plateau.

8.2 One Dimensional Shallow Network↩︎

We now prove an upper bound on the start of the plateau for shallow networks with one-dimensional inputs and outputs:

References↩︎