Properties of the geometry of solutions and capacity of multi-layer neural networks with Rectified Linear Units activations

References

Appendix A Model

Our model is a tree-like committee machine with $N$ weights $W_{li}$ divided into $K$ groups of $\nicefrac{{N}}{{K}}$ entries. We use the index $l=1,\dots,K$ for the group and $i=1,\dots,\frac{N}{K}$ for the entry. We consider two cases, the binary case $W_{li}=\pm 1$for all $l,i$ and the continuous case with spherical constraints on each group, $\sum_{i=1}^{N/K}W_{li}^{2}=N/K$ for all $l$.

The training set consists of $p=\alpha N$ random binary i.i.d. patterns. The inputs are denoted by $\xi_{li}^{\mu}$ and the outputs by $\sigma^{\mu}$, where $\mu=1,\dots,p$ is the pattern index.

The connection weights between the first layer and the output are denoted by $c_{l}$ and considered binary and fixed; for the case of ReLU activations we set the first half $l=1,\dots,K/2$ to the value $+1$ and the rest to $-1$; for the case of the sign activations we can set them to all to $+1$ without loss of generality.

A configuration of the weights $W$ solves the training problem if it classifies correctly all the patterns; we denote this with the indicator function

where $\Theta\left(x\right)=1$ if $x>0$ and otherwise is the Heaviside step function.

The volume of the space of configurations that correctly classify the whole training set is then

As explained in the main text, in all cases the resulting expression takes the form

where the $\mathcal{G}_{S}$ part is only affected by the spherical or binary nature of the weights, whereas the $\mathcal{G}_{E}$ part is only affected by $K$ and by the activation function $g$. Determining their value requires to compute a saddle-point over some overlap parameters $q_{l}^{ab}$ with $a,b=1,\dots,n$ representing overlaps between replicas, and their conjugates $\hat{q}_{l}^{ab}$; in turn, this requires an ansatz about the structure of the saddle-point in order to perform the $n\to 0$ limit.

For the spherical weights, the $\mathcal{G}_{S}$ part (before the $n\to 0$ limit) reads

while for the binary case we have a very similar expression, except that the summations don’t have the $a=b$ case and the integral over $W^{a}$ becomes a summation:

In all cases, we study the problem in the large $K$ limit, which allows to invoke the central limit theorem and leads to a crucial simplification of the expressions.

Appendix B Critical capacity

In the replica-symmetric (RS) case we seek solutions of the form $q_{l}^{ab}=\delta_{ab}+\left(1-\delta_{ab}\right)q$ for all $l,a,b$, where $\delta_{ab}$ is the Kronecker delta symbol, and similarly for the conjugated parameters, $\hat{q}_{l}^{ab}=\delta_{ab}\hat{Q}+\left(1-\delta_{ab}\right)\hat{q}$ for all $l,a,b$. The resulting expressions, as reported in the main text, are:

The values of the overlaps and conjugated parameters are found by setting to the derivatives of the free entropy.

The critical capacity $\alpha_{c}$ is found in the binary case by seeking numerically the value of $\alpha$ for which the saddle point solutions returns a zero free entropy.For the spherical case, instead, $\alpha_{c}$ is determined by finding the value of $\alpha$ such that $q\to 1$, which can be obtained analytically by reparametrizing $q=1-\delta q$ and expanding around $\delta q\ll 1$. In this limit, we must also reparametrize $\Delta$ using $\Delta_{2}-\Delta=\delta\Delta\,\delta q^{x}$, where $x$ is an exponent that depends on the activation function: it is $x=\nicefrac{{1}}{{2}}$ for the sign and $x=1$ for the ReLU. Due to this difference in this exponent, $\alpha_{c}$ diverges in the sign activation case (as was shown in (barkai1992broken, ; engel1992storage, )), while for the ReLU activations it converges to $2\left(1-\frac{1}{\pi}\right)^{-1}$. However, the RS result for the spherical case is only an upper bound, and a more accurate result requires replica-symmetry breaking.

B.2 1RSB ansatz

In the one-step replica-symmetry-breaking ($1$-RSB) ansatz we seek solutions with 3 possible values of the overlaps $q_{l}^{ab}$ and their conjugates. We group the $n$ replicas in $\frac{n}{m}$ groups of $m$ replicas each, and denote with $q_{0}$ the overlaps among different groups and with $q_{1}$ the overlaps within the same group. As before, the self overlap is $q^{aa}=1$ and its conjugate $\hat{q}^{aa}=\hat{Q}$ (these are only relevant in the spherical case).

the expressions of $\Delta_{2}$ and $\Delta_{-1}$ are the same as in the RS case. The expressions of $\Delta_{0}$ and $\Delta_{1}$ take the same form as the RS expressions for $\Delta$, except that $q_{0}$ and $q_{1}$ must be used instead of $q$.

Appendix C Franz-Parisi potential

The Franz-Parisi entropy (franz1995recipes, ; huang2014origin, ) is defined as (cf. eq. (7) of the main text):

The calculation proceeds by taking the RS ansatz with the same structure as that of sec. B.1 and the limit $n\to 0$, $r\to 0$. We obtain, in the large $K$ limit:

where we introduced the auxiliary quantities $\Sigma_{0}$, $\Sigma_{1}$, $\Gamma$, $D_{0}$, $D_{1}$ and $\Delta_{3}$ which depend on the choice of the activation function (like the $\Delta_{-1/0/1/2}$ of the previous section). For the sign activations we get:

In order to find the order parameters for any given $\alpha$ and $S$, we need to set to the derivatives of the free entropy w.r.t. the order parameters $q$, $p$, $t$ and the conjugates $\hat{Q}$, $\hat{q}$, $\hat{P}$, $\hat{p}$, $\hat{t}$, $\hat{S}$, thus obtaining a system of 9 equations (7 for the binary case) to be solved numerically. The equations actually reduce to 6 (5 in the binary case) since $q$, $\hat{Q}$ and $\hat{q}$ are the same ones derived from the typical case (sec. B.1).

Appendix D Large deviation analysis

Following (baldassi2019shaping, ), the large deviation analysis for the description of the high-local-entropy landscape uses the same equations as the standard $1$RSB expressions eqs. (20), (21) and (22). In this case, however, the overlap $q_{1}$ is not determined by a saddle point equation, but rather it is treated as an external parameter that controls the mutual overlap between the $y$ replicas of the system. Also, the parameter $m$ is not optimized and it is not restricted to the range $\left[0,1\right]$; instead, it plays the role of the number of replicas $y$ and it is generally taken to be large (we normally use either a large integer number to compare the results with numerical simulations, or we take the limit $m\to\infty$). For these reason, there are two saddle point equations less compared to the standard $1$RSB calculation.

The resulting expression for the free entropy $\mathcal{F}_{\text{LD}}\left(q_{1}\right)$ represents, in the spherical case, the log-volume of valid configurations (solutions at the correct overlap) of the system of $y$ replicas. These configurations are thus embedded in $\mathcal{S}^{Ky}$ where $\mathcal{S}$ is the $\nicefrac{{N}}{{K}}$-dimensional sphere of radius $\sqrt{\nicefrac{{N}}{{K}}}$. In order to quantify the solution density, we must normalize $\mathcal{F}_{\text{LD}}\left(q_{1}\right)$, subtracting the log-volume of all the admissible configurations at a given $q_{1}$ without the solution constraint (which is obtained by the analogous computation with $\alpha=0$). The resulting quantity is thus upper-bounded by (cf. Fig. (2) of the main text). For the binary case, $\mathcal{F}_{\text{LD}}\left(q_{1}\right)$ is the log of the number of admissible solutions, and the same normalization procedure can be applied.

In the $m\to\infty$ case the order parameters $q_{0}$ and $\hat{q}_{0}$ need to be rescaled with $m$ and reparametrized with two new quantities $\delta q_{0}$ and $\delta\hat{q}_{0}$, as follows:

As a consequence, we also reparametrize $\Delta_{0}$ with a new parameter $\delta\Delta_{0}$ defined as:

The expressions eqs. (20), (21) and (22) become:

Appendix E Distribution of stabilities

The stability for a given pattern/label pair $\xi^{*},\sigma^{*}$ is defined as:

The distribution over the training set for a typical solutions can thus be computed as

where we arbitrarily chose the first pattern/label pair $\xi^{1}$, $\sigma^{1}$ without loss of generality. The expression can be computed by the replica method as usual, and the order parameters are simply obtained from the solutions of the saddle point equations for the free entropy. The resulting expression at the RS level is:

where $G\left(x\right)=\frac{1}{\sqrt{2\pi}}e^{-x^{2}/2}$ is a standard Gaussian. The difference between the models (spherical/binary and sign/ReLU) is encoded in the different values for the overlaps and in the different expressions for the parameters $\Delta$, $\Delta_{-1}$, $\Delta_{2}$.

In the large deviation case, we simply compute the expression with a $1$RSB ansatz and fix $q_{1}$ and $m$ as described in the previous section. The resulting expression is

where the effective parameters $\Delta_{-1}$ , $\Delta_{0}$, $\Delta_{1}$ and $\Delta_{2}$ are the same defined in section B.2. In the $m\to\infty$ limit the previous expression reduces to

where $\delta\Delta_{0}$ is defined in equation (50).