Typical and atypical solutions in non-convex neural networks with
  discrete and continuous weights
We study the binary and continuous negative-margin perceptrons as simple
non-convex neural network models learning random rules and associations. We
analyze the geometry of the landscape of solutions in both models and find
important similarities and differences. Both models exhibit subdominant
minimizers which are extremely flat and wide. These minimizers coexist with a
background of dominant solutions which are composed by an exponential number of
algorithmically inaccessible small clusters for the binary case (the frozen
1-RSB phase) or a hierarchical structure of clusters of different sizes for the
spherical case (the full RSB phase). In both cases, when a certain threshold in
constraint density is crossed, the local entropy of the wide flat minima
becomes non-monotonic, indicating a break-up of the space of robust solutions
into disconnected components. This has a strong impact on the behavior of
algorithms in binary models, which cannot access the remaining isolated
clusters. For the spherical case the behaviour is different, since even beyond
the disappearance of the wide flat minima the remaining solutions are shown to
always be surrounded by a large number of other solutions at any distance, up
to capacity. Indeed, we exhibit numerical evidence that algorithms seem to find
solutions up to the SAT/UNSAT transition, that we compute here using an 1RSB
approximation. For both models, the generalization performance as a learning
device is shown to be greatly improved by the existence of wide flat minimizers
even when trained in the highly underconstrained regime of very negative
margins.
Carlo Baldassi, Enrico M. Malatesta, Gabriele Perugini, Riccardo Zecchina
# Typical and atypical solutions in non-convex neural networks with discrete and continuous weights

###### Abstract

We study the binary and continuous negative-margin perceptrons as simple non-convex neural network models learning random rules and associations. We analyze the geometry of the landscape of solutions in both models and find important similarities and differences. Both models exhibit subdominant minimizers which are extremely flat and wide. These minimizers coexist with a background of dominant solutions which are composed by an exponential number of algorithmically inaccessible small clusters for the binary case (the frozen 1-RSB phase) or a hierarchical structure of clusters of different sizes for the spherical case (the full RSB phase).

In both cases, when a certain threshold in constraint density is crossed, the local entropy of the wide flat minima becomes non-monotonic, indicating a break-up of the space of robust solutions into disconnected components. This has a strong impact on the behavior of algorithms in binary models, which cannot access the remaining isolated clusters. For the spherical case the behaviour is different, since even beyond the disappearance of the wide flat minima the remaining solutions are shown to always be surrounded by a large number of other solutions at any distance, up to capacity. Indeed, we exhibit numerical evidence that algorithms seem to find solutions up to the SAT/UNSAT transition, that we compute here using an 1RSB approximation. For both models, the generalization performance as a learning device is shown to be greatly improved by the existence of wide flat minimizers even when trained in the highly underconstrained regime of very negative margins.

## I Introduction

One of the most important and open problems in machine learning is to characterize at the theoretical level the typical properties of the loss landscape of neural networks. Given the impressive results that machine learning has achieved, e.g. in computer vision, image and speech recognition and translation, it is of primary importance to understand what are the key ingredients in those high-dimensional loss landscapes that allow very simple algorithms to work so well.

In the field of the physics of disordered systems [1] there have been, in the last few decades, many efforts to develop analytical and numerical techniques suitable for the study of nonconvex high-dimensional landscapes. Despite the many differences in the types of landscapes studied [2; 3], the main questions addressed by physicists are very similar to those of interest to the machine learning community. For example: can we predict, given an initial condition, in which part of the landscape a given algorithm will converge? What is the role played by local minima and saddles?

In the last years several empirical results have emerged on the general structure of the landscape. First, it has been found that there exists a wide and flat region in the bottom of the landscape: empirical analysis of the Hessian of configurations obtained by using simple variants of gradient descent algorithms [4; 5] showed that such regions are very attractive for simple learning dynamics. In [6] it was also shown that the most common algorithm used in machine learning, Stochastic Gradient Descent (SGD), is intrinsically biased by its noisy component towards flatter solutions. Low dimensional representations of the landscape have also shown [7] that several heuristic techniques used in machine learning are effective because they tend to smooth the landscape, increasing therefore the convergence abilities of gradient descent algorithms. Other lines of research [8; 9; 10], studied the connectivity properties of solutions, showing that minimizers of the loss function obtained with different initializations actually lie in the same basin, i.e. can be connected by a zero training-error path. In [11] the authors tested a large number of complexity measures on several and diverse models concluding that the ones based on flatness are more predictive of generalization properties.

In the statistical mechanics literature the role of wide and flat minima in the neural network landscape has emerged recently from the study of simple one-layer [12; 13] and two-layer models [14; 15]. Those works, that we summarize for convenience in the next section, have been limited so far to non-convex neural networks with binary weights; the connections between the geometrical properties of the landscape and the behavior of algorithms has been investigated in several works. In this paper we bridge this gap, trying to shed new light on the geometrical organization of solutions in simple non convex continuous neural network models.

Our main findings show that both discrete and continuous models are characterized by the existence of wide-flat minima which undergo a shattering phase transition below (but close) to capacity. For the continuous model the disappearance of wide-flat minima does not imply the onset of algorithmic hardness, as it happens for the discrete case. We argue that this is due to the underlying full-RSB background of ground states which is different from the disconnected structure of ground states of the discrete case. We show numerically that the algorithms typically used for learning tend to end-up in the wide-flat regions when they exist and that these regions show remarkable generalization capabilities.

For more complex neural network architectures, such as deep multi layer networks, we expect that the differences be
tween discrete and continuous models to become less evident. However, more analytical studies will be needed to address this point.

The paper is organized as follows: in Section II we summarize the main phenomenology that has emerged in the context of binary weights models; in Section III we introduce the non-convex models studied in this paper, namely the binary and spherical negative-margin perceptrons and we summarize their known properties. In Section IV we present the 1-step replica symmetry breaking (1RSB) computation of the SAT/UNSAT transition of the negative-margin perceptron. In Section V we employ the Franz-Parisi technique to study the local landscape of a configuration extracted with a given probability measure from the set of solutions. In particular we study the flatness of the typical minima of a generic loss function and we develop a method to extract configurations maximizing the flatness. We then explore how clusters of flat solutions evolve as a function of the training set size, revealing a phase transition in the geometrical organization of the solutions in the landscape. We call this _Local Entropy_ (LE) transition. In Section VI we present further numerical experiments: firstly we show numerical evidence suggesting that at the Local Entropy transition the manifold of atypical solutions undergoes a profound change in structure; secondly we show in a continuous-weights model how the generalization performance is greatly improved by the existence of wide and flat minimizers. Section VII contains our conclusions.

## II Overview of the phenomenology in binary models

In this section we summarize the main results on the connection between algorithmic behaviour and geometrical properties of the landscape of solutions in binary models of neural networks. We focus for simplicity on the paradigmatic example of the binary perceptron problem, defined as follows.

Given a training set composed by \(P=\alpha N\) binary random patterns \(\mathbf{\xi}^{\mu}\in\{-1,1\}^{N}\) and labels \(y^{\mu}\in\{-1,1\}\) with \(\mu=1,\ldots,P\), we aim to find a binary \(N\)-dimensional weight \(\mathbf{w}\in\{-1,1\}^{N}\) such that

\[y^{\mu}=\text{sign}\left(\mathbf{w}\cdot\mathbf{\xi}^{\mu}\right) \tag{1}\]

for all \(\mu\). The non-convexity of the problem is induced by the binary nature of the weights. Since the late 1980s this model has been studied using statistical physics techniques by Gardner and Derrida [16; 17] and by Krauth and Mezard [18] in the limit \(N\), \(P\to\infty\) with fixed \(\alpha\). They found that one can find solutions to the problem only up to a given critical value of \(\alpha\) that separates a SAT from an UNSAT phase: for \(\alpha<\alpha_{c}\) the problem admits an exponential number of solutions, whereas for \(\alpha>\alpha_{c}\) no solution to the problem can be found. Huang and Kabashima [19] computed the entropy of solutions at a given distance from a typical solution (the so-called _Franz-Parisi_ entropy), and showed that for \(\alpha<\alpha_{c}\) the space of solutions splits into well-separated clusters of vanishing entropy. More in detail, they found that picking a configuration \(\tilde{\mathbf{w}}\) at random from the set of all solutions, its closest other solution is found by flipping an extensive number of weights. This means that typical solutions are completely isolated. The geometrical organization of typical solutions was later confirmed rigorously in a related model, the symmetric binary perceptron [20; 21]. In several constraint satisfaction problems (CSPs), such point-like solutions are generally believed to be hard to find algorithmically. In particular in Boolean satisfiability problems like \(k\)-SAT [22] and in graph coloring [23] all the best known algorithms start to fail in finding solutions at the so-called _clustering_ transition, which occurs at the constraint density for which only such isolated isolated solutions remain.

The analytical picture of the landscape of the binary perceptron, and its relation with the behaviour of algorithms, however, was far from being completely understood. Indeed, if only those kind of point-like, sharp solutions exists, it should be really hard to find them. Nevertheless, not only there exist algorithms that solve efficiently the optimization problem [24; 25; 26], but the solutions they find also have substantially different properties from the typical, isolated ones that can be described analytically: we mention in particular the fact that one can numerically show that solutions found by algorithms usually lie in dense clusters of solutions [15] and observables like stability distribution [14] and generalization (in teacher-student models) [12] do not coincide with the theoretical calculations cited above.

This apparent paradox has been resolved in [12; 13], where it was shown analytically that there exists rare, subdominant (i.e. atypical) clusters of solutions in the landscape which are highly attractive for the learning algorithm dynamics. It was then shown [27; 28] that the typical (sharp) and atypical (clusterized) solutions coexist in the landscape until a certain critical value \(\alpha_{\text{LE}}\) is reached; this new transition has been named _Local Entropy_ (LE) transition: for \(\alpha<\alpha_{\text{LE}}\), both sharp and flat minima can be found whereas for \(\alpha>\alpha_{\text{LE}}\) only sharp minima exist. This has a drastic impact on learning: the most efficient algorithms are not able to overcome this threshold, since beyond it only isolated solutions exists. \(\alpha_{\text{LE}}\) can be therefore thought as a "clustering transition" as was studied earlier in various CSPs, but whose nature is different, being the result of disappearance of atypical, clustered, solutions. Moreover, this analytical picture was exploited to create new algorithms, that have been explicitly designed to target wide and flat minima: we mention in particular focusing Belief Propagation (fBP); for other types of "replicated algorithms" see [12]. Those algorithms in turn are the ones that succeed in getting closer to the local entropy transition. Other algorithms like Reinforced Belief Propagation (rBP) [24], reinforced maximum [26] and Stochastic BP-inspired (SBPI) [25] also induce a bias towards clustered solutions.

The phenomenology described above has been shown to hold qualitatively also on other binary models like, e.g. one-hidden layer tree committee machines and teacher student models. Those lines of research also showed that the heuristic techniques and architectural choices used in machine learn
ing, such as the use of the cross-entropy loss [15], or ReLU activation function [14], or regularization [29] tend to affect the learning landscape and to induce wider and flatter minima. In addition, a similar analysis of the role of overparameterization [28] suggests that it allows the emergence of atypical clusterized solutions at the local entropy transition. The appearance of those solutions makes the dynamics change from glassy to non-glassy [3].

## III The model

The scenario described in the previous section holds for binary weights neural network models. On the other hand, in continuous models less results are known so far. In [14; 15] the existence of wide and flat solutions was shown in one layer continuous weights models. However, there has been no detailed study of the change in the structure of these regions as a function of overparameterization, nor of their algorithmic implications as in the case of binary models. Here we study these questions in an even simpler model, the negative-margin perceptron. It is defined as follows.

Given a set of \(P=\alpha N\) normally distributed random patterns \(\xi^{\mu}\), \(\mu=1,\ldots,P\) we want to find a vector of \(N\) continuous weights \(\mathbf{w}\) normalized on \(\mathcal{S}_{N}\), the sphere of radius \(\sqrt{N}\)

\[\mathbf{w}\cdot\mathbf{w}=\sum_{i=1}^{N}w_{i}^{2}=N \tag{2}\]

that satisfy the set of \(P\) constraints

\[\Delta^{\mu}(\mathbf{w};\kappa)=\frac{1}{\sqrt{N}}\mathbf{w}\cdot\mathbf{\xi}^{\mu}-\kappa \geq 0\,,\quad\forall\mu=1,\ldots,P\,. \tag{3}\]

\(\kappa\) is fixed and it is called _margin_. We will call a configuration \(\tilde{w}\) satisfying (2) and (3) simply as a _solution_ to the problem. For \(\kappa\geq 0\) the problem is convex and the space of solutions is always connected. For \(\kappa<0\) the problem becomes non-convex and it has been named the negative spherical perceptron problem [33].

In the following we will be also interested in the binary analog of the problem (\(w_{i}=\pm 1\)), that we will call the "negative binary perceptron problem".

### Related work

The negative spherical perceptron has been studied in the statistical mechanics community since the 1980s in the seminal work of Gardner and Derrida [30]. In particular they studied, for a fixed value of \(\kappa\), the so called SAT/UNSAT transition \(\alpha_{c}\): this is the maximum value of patterns per number of parameters that can be perfectly classified by the network, in the limit of large \(N\). They computed it by using the replica method in the Replica-Symmetric (RS) approximation. They also computed the De Almeida-Thouless (dAT) line that marks the onset of the instability of the RS ansatz, showing that the SAT/UNSAT transition is correctly computed in the RS approximation only for \(\kappa\geq 0\). We plot \(\alpha_{c}(\kappa)\) in the RS approximation and \(\alpha_{\text{dAT}}(\kappa)\) for \(\kappa<0\) in Fig. 1.

More recently, the negative spherical perceptron has been studied as the "simplest model of jamming" [34]: the patterns \(\mathbf{\xi}^{\mu}\) can be interpreted as point obstacles in fixed random positions on \(\mathcal{S}_{N}\) and the constraints (3) correspond to imposing that a particle at position \(\mathbf{w}\) on \(\mathcal{S}_{N}\) is at a Euclidean distance larger than \(\sigma=\sqrt{2N+2\kappa}\) from the point obstacles1. The jamming point corresponds, for a fixed \(\alpha\), to the maximization of the margin \(\kappa\) (that we will denote from now on as \(\kappa_{\text{max}}(\alpha)\)2), i.e. to the maximization of the distance from the point obstacles. Because of isomorphism with the problem of packing of spheres, the negative perceptron problem has been studied using the replica method in [31], where the whole phase diagram of typical solutions has been derived. In particular they showed that for low enough margin the model exhibits the classical Random First Order Transition (RFOT) phenomenology: increasing \(\alpha\) for a fixed \(\kappa\) one first finds a _clustering_ transition, then a _Kautzmann_ transition and finally a _Gardner_ transition. For clarity, we have plotted those lines in Fig. 1; we refer to the caption of the figure and the paper [31] for their precise definitions. In the same paper, the critical exponents were calculated on the jamming line and they appeared to be equal to the ones found in the jamming of hard spheres in infinite dimension [35].

Footnote 1: For this reason the variable \(\Delta^{\mu}\) has been named _gap variable_. In the statistical mechanics literature it has been also called _stability_ of pattern \(\mu\).

Footnote 2: \(\kappa_{\text{max}}\) (\(\alpha\)) is simply the inverse function of the SAT/UNSAT transition \(\alpha_{c}\) (\(\kappa\)) mentioned before.

In another work [33], Montanari and coworkers studied the performance of several algorithms by characterizing their algorithmic threshold and compared it with rigorous upper and lower bounds to the critical capacity \(\alpha_{c}\). In particular they showed that there exists a gap between the interpolation threshold of Linear Programming (LP) algorithm and the lower bound to \(\alpha_{c}\). However, other algorithms, such as Gradient Descent (GD) and Stochastic GD (SGD) on the cross-entropy loss function, behave much better since they have a much higher algorithmic threshold with respect to the one of LP. They were not able to conclude if in this problem there exists a computational barrier that cannot be overcome by any algorithm (as common in binary CSP) or if one can design better optimization algorithms able to reach \(\alpha_{c}\).

## IV 1RSB critical capacity in the negative spherical perceptron

Following the seminal work of Gardner [16; 17; 30] the partition function of the negative perceptron models is

\[Z=\int d\mu(\mathbf{w})\,\mathbb{X}_{\xi}(\mathbf{w};\kappa) \tag{4}\]
where, denoting by \(\Theta(\cdot)\) the Heaviside theta function, we have denoted with

\[\mathbb{X}_{\xi}(\mathbf{w};\kappa)\equiv\prod_{\mu=1}^{\alpha N}\Theta\left(\Delta^{ \mu}(\mathbf{w};\kappa)\right) \tag{5}\]

the indicator that selects the solutions to the optimization problem (3). \(d\mu(\mathbf{w})\) is a measure over the weights that we have introduced to treat both the spherical and binary cases:

\[d\mu_{\text{sph}}(\mathbf{w}) =\delta\left(N-\sum_{i}w_{i}^{2}\right)\prod_{i=1}^{N}dw_{i} \tag{6a}\] \[d\mu_{\text{bin}}(\mathbf{w}) =\prod_{i=1}^{N}dw_{i}\,\left[\frac{1}{2}\delta\left(w_{i}-1 \right)+\frac{1}{2}\delta\left(w_{i}+1\right)\right] \tag{6b}\]

One then is interested in computing the free entropy of the system in the thermodynamic limit

\[\phi\equiv\lim_{N\to\infty}\frac{1}{N}\left\langle\ln Z\right\rangle_{\xi}\, \tag{7}\]

where \(\left\langle\cdot\right\rangle_{\xi}\) is the average over all the random patterns \(\{\xi^{\mu}\}_{\mu=1}^{\alpha N}\). The free entropy can be computed by using the replica trick [1]

\[\left\langle\ln Z\right\rangle_{\xi}=\lim_{n\to 0}\frac{1}{n}\ln\left\langle Z ^{n}\right\rangle_{\xi} \tag{8}\]

The entropy can be fully characterized by a \(n\times n\) order parameter matrix \(q^{ab}\) which physically represents the typical overlap between two replicas extracted from the Gibbs measure (5), i.e.

\[q^{ab}=\frac{1}{N}\sum_{i=1}^{N}\left\langle w_{i}^{\alpha}w_{i}^{b}\right\rangle. \tag{9}\]

where we have indicated by \(\left\langle\cdot\right\rangle\) the average over the Gibbs measure in (5). We review in appendix B the analytical calculations of the entropy in the case in which the structure of the overlap matrix \(q^{ab}\) is Replica-Symmetric (RS)

\[q_{ab}=\delta_{ab}+(1-\delta_{ab})q \tag{10}\]

Figure 1: Phase diagram of the negative spherical perceptron. The light blue line represents the SAT/UNSAT transition computed in the Replica-Symmetric approximation as presented originally in Gardner-Derrida’s work [30]. This line is correct only in the region \(\kappa\geq 0\), where the model is convex. A better approximation to the SAT/UNSAT transition is the orange line, which is computed here using the 1RSB approximation. The other lines were computed in [30] and [31]. The green line represents the De Almeida-Thouless instability of the RS ansatz: when one crosses \(\alpha_{\text{dAT}}\) for \(\kappa>\kappa_{\text{1RSB}}\) one goes from an RS to a fRSB phase; when \(\kappa_{\text{RFOT}}<\kappa<\kappa_{\text{1RSB}}\) one instead goes from RS to a 1RSB stable phase. For a value of \(\kappa<\kappa_{\text{RFOT}}\) one encounters several transitions when \(\alpha\) is increased: the _dynamical_ or _clustering_ transition \(\alpha_{\text{dyn}}\) (blue line), the _Kauzmann transition_ (green line) and the _Gardner transition_ (in red). For \(\alpha<\alpha_{\text{dyn}}\) the system is RS. For \(\alpha_{\text{dyn}}<\alpha<\alpha_{\text{K}}\) the system is in a dynamical 1RSB phase, where \(q_{1}>q_{0}\) and the Parisi block parameter \(m=1\). For \(\alpha_{\text{K}}<\alpha<\alpha_{\text{G}}\) the Gibbs measure is dominated by a 1RSB solution having \(m<1\). Above the Gardner transition \(\alpha>\alpha_{\text{G}}\) the system is fRSB. Note that the dynamical transition presented in [31] is slightly below the one presented here [32].
or broken at 1-step Replica Symmetry Breaking level (1RSB)

\[q_{ab}=q_{0}+(q_{1}-q_{0})I_{ab}^{m}+(1-q_{1})\delta_{ab} \tag{11}\]

where \(I_{ab}^{m}\) is the \(n\times n\) matrix having elements equal to 1 inside the blocks of size \(m\) located around the diagonal and 0 otherwise.

In both spherical and binary negative perceptron problems the free entropy is a decreasing function of \(\alpha\), meaning that the solution space shrinks when constraints are added. Increasing \(\alpha\) one then crosses a critical value \(\alpha_{c}\) (the SAT/UNSAT transition) such that for larger constraint densities there is no solution to the problem. In binary models \(\alpha_{c}\) can be computed easily by evaluating the value of \(\alpha\) for which the Replica-Symmetric (RS) free entropy goes to 0 [18; 36]. In this model the typical overlap between solutions does not go to 1 at the SAT/UNSAT transition.

In continuous models the estimation of \(\alpha_{c}\) is instead much harder and requires the use of the full Replica Symmetry Breaking Ansatz (fRSB) [37]. We present in appendix B the computation of \(\alpha_{c}\) (or, equivalently of the _maximum margin_\(\kappa_{\text{max}}\) at a fixed value of \(\alpha\)) in the spherical negative perceptron in the RS and 1RSB approximations. In the RS case, this requires to study the limit \(q\to 1\). In the 1RSB case, we must consider instead the limit \(q_{1}\to 1\) with \(m\to 0\) and \(\vec{m}\equiv m/(1-q_{1})\) finite [38]. We plot those two approximations in Fig. 1; the 1RSB ansatz shows a substantial change on the estimation of the critical capacity. It can be regarded as a good upper bound to the true SAT/UNSAT transition. For another upper bound (which is slightly less stringent than the one presented here) and a lower bound to the true value of \(\alpha_{c}\) see [33].

## V Probing the local entropy landscape using the Franz-Parisi method

In this section we discuss how the landscape of solutions of the negative perceptron problem is composed by solutions that can be completely different in nature. In particular, among the various observables that we can compute analytically, we are interested in the so called "_local entropy_" of a given solution. Given a configuration \(\mathbf{w}\), normalized as in eq. (2) and that solves the set of constraints (3), we define its local entropy \(\mathcal{S}_{\xi}(\mathbf{\tilde{w}},S;\mathbf{\kappa})\) as the log of the volume (or number in the binary case) of solutions at a given (normalized) distance \(d\) from \(\tilde{w}\); namely

\[\mathcal{S}_{\xi}(\mathbf{\tilde{w}},d;\mathbf{\kappa}) =\frac{1}{N}\ln\mathcal{N}_{\xi}(\mathbf{\tilde{w}},d;\mathbf{\kappa}) \tag{12}\] \[\equiv\frac{1}{N}\ln\!\int\!d\mu(\mathbf{w})\,\mathbb{Z}_{\xi}\left( \mathbf{w};\mathbf{\kappa}\right)\delta(N(1-2d)-\mathbf{w}\cdot\tilde{\mathbf{w}})\]

For any distance \(d\) the local entropy is bounded from above by the value it attains for \(\alpha=0\), which we call \(\mathcal{S}_{\text{max}}\). In this case the previous equation simply measures the log of the _total_ volume (or the total number in the binary case) of configurations that are at a certain distance by \(d\) from \(\mathbf{\tilde{w}}\). Because of the homogeneity of space, \(\mathcal{S}_{\text{max}}\) cannot depend on \(\mathbf{\tilde{w}}\). In the spherical case one gets (see appendix C.1)

\[\begin{split}\mathcal{S}_{\text{max}}^{\text{spin}}(d)& \equiv\frac{1}{N}\ln\int\,d\mu_{\text{spin}}(\mathbf{w})\,\delta \left(N(1-2d)-\sum_{i}w_{i}\right)\\ &\overset{N\to\infty}{=}\frac{1}{2}\left[1+\ln(2\pi)+\ln\left(1- (1-2d)^{2}\right)\right]\.\end{split} \tag{13}\]

Figure 2: Left panel: average local entropy of typical minimizers of the cross-entropy loss function defined in (17). The light blue dots are obtained by optimizing the same loss using SGD (\(N=1000\)). Here we have chosen \(\alpha=3.0\), \(\kappa=-0.5\) and \(\gamma=5\). Right panel: comparison of the average local entropy of typical and atypical solutions in the spherical negative perceptron. Franz-Parisi entropy for \(\kappa=-0.5\) and \(\alpha=1\) for a typical reference extracted from the flat measure over solutions having margin \(\tilde{\kappa}\) as in (19). The blue line corresponds to the case \(\tilde{\kappa}=\kappa\); the red curve is instead the curve for the maximum margin \(\tilde{\kappa}=\kappa_{\text{max}}\). Since \(\alpha<2\) in this case the RS estimation of \(\kappa_{\text{max}}\) is correct. The dashed line corresponds to the bound in (13). The points correspond to the average local entropy estimated using BP on solutions found by SA on the number of error loss (light blue point) and fBP (orange ones). The agreement between theory and simulations is remarkable.
whereas in the binary case we have

\[\begin{split}\mathcal{S}_{\max}^{\text{bin}}(d)&\equiv \frac{1}{N}\ln\int d\mu_{\text{bin}}(\mathbf{w})\,\delta\left(N(1-2d)-\sum_{l}w_{ i}\right)\\ &\overset{N\to\infty}{=}-d\ln(d)-(1-d)\ln(1-d)\.\end{split} \tag{14}\]

Given a probability distribution \(P_{\xi}(\tilde{\mathbf{w}})\) over the set of configurations satisfying the constraints (3), we are interested in computing the local entropy of a typical \(\tilde{\mathbf{w}}\) sampled from \(P_{\xi}(\tilde{\mathbf{w}})\) and averaged over all the possible realizations of the \(\alpha N\) patterns:

\[\phi_{\text{FP}}(d;\kappa)=\left(\int d\mu(\tilde{\mathbf{w}})P_{\xi}(\tilde{\mathbf{ w}})\mathcal{S}_{\xi}(\tilde{\mathbf{w}},d;\kappa)\right)_{\xi}. \tag{15}\]

This "averaged local entropy" was introduced in the context of mean field spin glasses by Franz and Parisi [40] and for this reason we will call it _Franz-Parisi entropy_. Intuitively, sampling from a distribution \(P_{\xi}^{1}(\tilde{\mathbf{w}})\) that has a larger Franz-Parisi entropy with respect to another one \(P_{\xi}^{2}(\tilde{\mathbf{w}})\) for all distances within some radius will result in solutions that lie in wider and flatter minima.

It is interesting therefore to study how extracting the reference configuration \(\tilde{\mathbf{w}}\) by using a different class of probability distributions \(P_{\xi}(\tilde{\mathbf{w}})\) one obtains different types of local entropy curves. Those analytical results on the flatness of a particular class of solutions can then be compared with the ones actually found by several algorithms.

In the next two subsections we explore two different ways of choosing \(P_{\xi}(\tilde{\mathbf{w}})\).

### Extracting the reference from the typical minima of a loss function

What one usually does to find a solution to (3) is to introduce a loss function \(\mathcal{L}\)

\[\mathcal{L}(\tilde{\mathbf{w}})=\sum_{\mu=1}^{\alpha N}\ell(\Delta^{\mu}(\tilde{ \mathbf{w}};\kappa)) \tag{16}\]

where \(\ell(\cdot)\) is a loss per pattern. In first-order algorithms such as gradient descent (GD) and Stochastic GD (SGD) the loss \(\mathcal{L}\) needs to be differentiable. A very common loss that is used extensively in machine learning practice is the cross-entropy, which for a binary classification problem has the form3

Footnote 3: In standard deep learning practice the “pseudo-inverse-temperature” parameter \(\mathbf{\gamma}\) is not normally used since in the exponent it is redundant with the norm of the last layer; in our models the norm is fixed so we add it explicitly (and keep it fixed). The renormalization by \(\mathbf{\gamma}^{-1}\) keeps under control the limits of small or large \(\mathbf{\gamma}\), which could be also achieved by re-parameterizing the SGD learning rate.

\[\ell(x)=\frac{1}{2\gamma}\log\left(1+e^{-2\gamma x}\right) \tag{17}\]

In order to study the local entropy landscape around the minimizer found by such algorithms we use as reference configurations \(\tilde{\mathbf{w}}\) the ones extracted from the Gibbs measure

\[P_{\xi}(\tilde{\mathbf{w}})=\frac{e^{-\beta\sum_{\mu=1}^{\alpha N}\ell(\Delta^{ \mu}(\tilde{\mathbf{w}};\kappa))}}{\int d\mu(\tilde{\mathbf{w}}^{\prime})\,e^{-\beta \sum_{\mu=1}^{\alpha N}\ell(\Delta^{\mu}(\tilde{\mathbf{w}}^{\prime};\kappa))}} \tag{18}\]

In order to focus on the minima of the loss function \(\mathcal{L}\) we take the large \(\beta\) limit. We report in Appendix C the result of the computation of the Franz-Parisi entropy in the RS ansatz.

Figure 3: Average local entropy \(\phi_{\text{FP}}\) of typical and atypical solutions in the binary (left panel, with \(\alpha=1\), \(\kappa=-0.5\)) and continuous weight models (right panel, with \(\alpha=2\), \(\kappa=-0.5\)) as a function of the distance. In both cases \(\phi_{\text{FP}}\) is computed within the RS ansatz and for several values of the margin \(\tilde{\kappa}\) of the reference solution. The dashed grey line correspond to the upper bound to the entropy as in equation (14) and (13) respectively for the binary and spherical cases. The distance at which the curves attain the maximum correspond to the typical distance between solution having margin \(\tilde{\kappa}\) and \(\kappa\)[39].
We plot in the left panel of Fig. 2 the RS Franz-Parisi entropy of the typical minima of the cross entropy loss function. We show in the same plot that the theoretical computation is in striking agreement with numerical simulations done by optimizing the same loss with the SGD algorithm. The local entropy of a configuration of weights has been computed using Belief Propagation (BP), see [13] for the details of the implementation.

### Flat measure over solutions having margin \(\tilde{\kappa}\)

Secondly, we studied the average local entropy of solutions sampled using a flat measure over all configurations having margin \(\tilde{\kappa}\geq\kappa\), that is

\[P_{\xi}(\tilde{\mathbf{w}})=\frac{\mathbb{X}_{\xi}(\tilde{\mathbf{w}};\tilde{\mathbf{\kappa }})}{\int d\mu(\tilde{\mathbf{w}}^{\prime})\,\mathbb{X}_{\xi}(\tilde{\mathbf{w}}^{ \prime};\tilde{\kappa})} \tag{19}\]

In the case \(\tilde{\kappa}=\kappa\) we are sampling typical solutions to the problem. We studied how the Franz-Parisi curve changes as we vary the margin \(\tilde{\kappa}\) in the RS ansatz (see SM); since a solution having a margin \(\tilde{\kappa}>\kappa\) solves a more constrained problem than (3), we intuitively expect that its Franz-Parisi entropy will be higher than that for \(\tilde{\kappa}=\kappa\).

This approach has been explored so far in models with binary weights and \(\kappa\geq 0\). We summarize here the main findings for the case of the negative binary perceptron, see the left panel of Fig. 3. First, if one samples a typical solution to the problem one will find that there exists, for any (arbitrarily small) value of \(\alpha\), a neighborhood of \(d=0\) where the Franz-Parisi entropy is negative [27]. This implies that, within a certain distance from the reference, only a sub-extensive number of solutions can be found. One therefore says that typical solutions are _isolated_[19; 20; 41]. Secondly, if one samples solutions having larger margin with respect to the one of the problem \(\tilde{\kappa}>\kappa\) one finds that there always exists a neighborhood around \(d=0\) having positive average local entropy. Therefore solutions having larger margin are always surrounded by an exponential number of other solutions within a small but extensive distance. Moreover as one decreases the distance from the reference further, the local entropy curve becomes nearly indistinguishable from the total number of configurations at that distance, implying that the cluster where the reference is located is very dense. If \(\alpha\) is sufficiently small, the local entropy becomes monotonic as the margin \(\tilde{\kappa}\) is increased.

Differently from the binary weights case, in the spherical case we found that no typical solution is actually isolated, there is always a non-vanishing volume of solutions at a given distance from a typical solution, see Fig. 3, right panel. Moreover if \(\alpha\) is low enough even a typical solution has a monotonic local entropy. Apart for those two differences, the general picture is similar: as the margin \(\tilde{\kappa}\) is increased, the local entropy gets larger in a given range of distances from the reference, meaning that those (atypical) solutions are located inside a denser cluster. As in the binary case, the solution having the largest local entropy at small distances is the one sampled with the maximum margin \(\tilde{\kappa}=\kappa_{\text{max}}\). We refer to appendix C.5 for a discussion of the RSB effects that play an important role in the large \(\alpha\) regime.

In the right panel of Fig. 2, we also show the comparison between the average local entropy of typical and atypical solutions in the negative spherical perceptron and the agreement with the one found by two algorithms: Simulated Annealing on the number-of-errors loss and fBP. The latter algorithm was explicitly designed to target flatter solutions, see [12] for the details of its implementation; we found that fBP finds solutions whose local entropy is comparable to (even slightly larger than) the theoretical one found imposing the maximum possible margin for the reference, as was previously observed in binary models [27]. In Appendix E we show that even for

Figure 4: Derivative of the Franz-Parisi entropy \(\partial\phi_{\text{FP}}/\partial d\) for the maximum margin solutions as a function of \(d\) for several values of \(\alpha\). The left panel is for the binary case (\(\kappa=-1\)), whereas the right panel is for the spherical case (\(\kappa=-0.5\)). Qualitatively the two plots are similar: for small values of \(\alpha\) the \(\phi_{\text{FP}}\) is monotonic (the derivative is always positive). At \(\alpha_{\text{LE}}\), \(\partial\phi_{\text{FP}}/\partial d\) develops a zero at small distances. For \(\alpha>\alpha_{\text{LE}}\) the Franz-Parisi entropy is not monotonic.
larger value of \(\alpha\), where the RS ansatz on the order parameters for the reference configuration is wrong (i.e. \(\alpha>\alpha_{\text{LAT}}(\bar{\kappa})\)) the agreement with numerical simulations is still rather good.

### Phase transition in the geometrical organization of solutions: local entropy transition

Next, we investigate what happens to the widest and flattest minima as we increase the constraint density \(\alpha\). We therefore study the local entropy profile of the maximum-margin solutions for several increasing values of \(\alpha\), for a fixed value of \(\kappa\).

In Fig. 4 we plot \(\frac{\partial\phi_{\text{LP}}}{\partial d}\) as a function of the distance \(d\). The phenomenology is quite similar in both the binary and the spherical cases. If \(\alpha\) is lower than a critical threshold \(\alpha_{\text{LE}}(\kappa)\), the local entropy profile exhibits only one maximum (not shown in the figure), located at the typical distance \(d_{\text{typ}}(\alpha)\) between solutions with margin \(\bar{\kappa}=\kappa_{\text{max}}\) and \(\kappa\); for \(d<d_{\text{typ}}\) the local entropy is monotonic with positive derivative. This means that the reference is located in a wide and flat region that extends to very large scales [12; 27]. For \(\alpha=\alpha_{\text{LE}}\), there appears at small distances another point where the derivative \(\frac{\partial\phi_{\text{LP}}}{\partial d}\) vanishes. For \(\alpha>\alpha_{\text{LE}}\) the local entropy is non-monotonic and it has a local maximum at a distance \(d_{\star}<d_{\text{typ}}(\alpha)\): this suggests that the most robust solutions are no longer located in regions that extend to arbitrary large distances, but that have a typical size \(d_{\star}\) instead. This _Local Entropy transition_[12; 27] occurring at \(\alpha_{\text{LE}}(\kappa)\) can therefore be interpreted as the point at which the cluster of atypical robust solutions fractures in many pieces.

In [27] the local entropy transition has been computed for the binary perceptron model for \(\kappa=0\) and it has been shown that it gives similar results to the more precise method of finding the reference that maximizes the local entropy at every distance [12]. In the same works, moreover, it has been shown that this change in the geometry of atypical solutions strongly affects the behaviour of algorithms: no known algorithm is able to find solutions for \(\alpha>\alpha_{\text{LE}}\). We plot in Fig. 5 the local entropy transition as a function of \(\kappa\) for the binary (left panel) and for the spherical case (right panel). In the same plots we show the algorithmic threshold of several algorithms. In the same plots we show the SAT/UNSAT transition, which was computed by using the zero entropy criterium in the binary case [18] and by using the RS and 1RSB approximations in the spherical case. In the left panel of Fig. 5 we can see that in the binary case no algorithm is able to cross the local entropy transition; in addition fBP which is an algorithm designed to target maximally entropic regions appears to stop working _exactly_ at the local entropy transition. In the spherical case, this is not the case: even if the atypical states fracture in many pieces, algorithms are still able to overcome the threshold and find solutions. Indeed the typical landscape of solutions is very different in the two models: in the spherical case even typical solutions are surrounded by an exponential number of solutions up to capacity. The algorithmic thresholds plotted in the right panel of Fig. 5 seem to suggest that algorithms are able to reach the SAT/UNSAT transition of the model, especially knowing that taking into account higher order RSB corrections can considerably lower the estimate of \(\alpha_{c}\). Binary and spherical models are thus significantly different from the optimization point of view.

Notice that the computation of \(\alpha_{\text{LE}}\) could still be very imprecise in the spherical case because of the presence of large RSB effects. However, when \(\kappa\) is near zero, we expect the RSB corrections to play a minor role and our computation to be reliable; indeed the RS estimate of the maximum margin configuration is expected to approximate quite well the true value. On the other hand, when the margin is very negative, the RS estimate of \(\kappa_{\text{max}}\) is very imprecise (cf. Fig. 1); therefore we expect our estimate of \(\alpha_{\text{LE}}\) to be imprecise as well. In the appendix we describe a method to estimate the local entropy transition that does not rely on the ability to sample a replica in deep RSB phase; the method is therefore expected to give much more precise estimates when \(\kappa\) is large in modulus.

## VI Numerical experiments

### Numerical justification of the local entropy transition

While we expect to observe a clear difference in algorithmic behaviour between the discrete and continuous versions of the model at the local entropy transition, we still expect to observe in both cases a structural geometrical change. Beyond the local entropy transition the discrete model displays a disconnected 1-RSB structure of solutions also at the out-of-equilibrium level. On the contrary, the continuous version displays a full RSB structure which is expected to be accessible (though not particularly flat). For the discrete case several works have already clarified the phenomenon both analytically and numerically. Here we focus on the continuous case.

We measure numerically the error of a weight vector \(\mathbf{w}_{\mathbf{\gamma}}\) obtained as a convex combination of \(y\) solutions \(\mathbf{w}^{a}\) with \(a=1,\ldots,y\) and normalized on the sphere in \(N\) dimension of radius \(\sqrt{N}\), namely

\[\mathbf{w}_{\mathbf{\gamma}}\equiv\frac{\sqrt{N}\sum_{a=1}^{y}\gamma_{a}\mathbf{w}^{a}}{ \|\sum_{a=1}^{y}\gamma_{a}\mathbf{w}^{a}\|}\,,\qquad\sum_{a=1}^{y}\gamma_{a}=1\,, \quad\forall a:\;\gamma_{a}\geq 0 \tag{20}\]

The study of the training error around geodesic paths connecting the same or different classes of solutions is actually an interesting problem in its own right [43]. Here we provide some preliminary numerical results on the simple cases \(y=2\) or \(3\) in which the solutions \(\mathbf{w}^{a}\) are obtained with SGD with the hinge loss \(\ell\left(x\right)=\max\left(0,-x\right)\) (the margin is included in \(x\), see eq. (16)). In particular, the case \(y=2\) amounts at computing the barrier along a "linear" (geodesic) path connecting two given solutions. This topic has been widely studied in deep learning literature [8; 9; 10] as it is believed to be a good proxy to probe the error landscape around solutions. Based on the phenomenology exhibited by deep networks, we expect
two robust solutions to be connected by an almost zero error path [10]. This is in fact what we observe in the overparameterized regime (low \(\alpha\)), see Fig. 6. However, as the constraint density is increased, a barrier in the linear path connecting solutions appears, in a region close to the RS estimate of the local entropy transition. Moreover, if we study the error landscape on the "plane" (\(2D\) manifold) spanned by \(y=3\) solutions, we see that, for \(\alpha>\alpha_{\text{LE}}\), a high error region appears in the barycenter, signaling that right above the local entropy transition SGD starts to find solutions that are likely to be located in different basins.

### Connections with generalization

In order to probe numerically the computational advantages of wide flat minima and to create a natural link to future studies on multilayered models, we have analyzed the generalization properties in a teacher-student setting. Specifically we generate data with a random teacher perceptron (\(\kappa=0\)) and train a student perceptron with negative \(\kappa\). Once learning has completed, we test the generalization performance of the student with zero margin. Remarkably, we find that - provided we converge into wide flat minima - even learning with very negative values of \(\kappa\) (a very under-constrained learning problem, with very little signal coming for the training set) leads to good generalization performance, see Fig. 7 for the continuous case. Learning with fBP leads to minimizers which are well inside the flat region and as such are effectively robust, even though the robustness condition coming from the learning constraint is very weak (the negative \(\kappa\)). Other algorithms display different degree of robustness depending on the details, such as the effective temperature \(\gamma\) of the cross-entropy loss minimized by SGD, or the cooling schedule for Simulated Annealing. Similar behaviours are found in the binary case, which we refer to the appendix.

Figure 5: SAT/UNSAT and local entropy transitions as a function of \(\kappa\) for the binary (left) and spherical (right) cases. The points represent the highest value of \(\alpha\) that we were able to reach at \(N=1000\) with several algorithms: fBP, SBPI [25] and Binary NET (BNET) [42] in the binary case; fBP and SGD for the continuous case. In the spherical case we plot the critical capacity both in the RS and 1RSB approximations. Notice also that in this case the local entropy transition coincides with the SAT/UNSAT transition for \(\kappa\geq 0\), since the solution space is connected and convex.

Figure 6: Average maximum error fraction along the geodesic path connecting two solutions (red points) and on the \(2D\) manifold (“plane”) spanned by three solutions on the \(N\)-dimensional hypersphere surface (blue points). A high error barrier between solutions appears before the algorithmic threshold \(\alpha_{\text{c}}\), and its on-set is compatible with the local entropy transition (in this case \(\alpha_{\text{LE}}(\kappa=-0.5)\simeq 4.2\)). The two inset plots show the error on the plane spanned by three solutions (represented by red dots at the vertices of the triangle): for \(\alpha<\alpha_{\text{LE}}\), the error along the linear paths (edges of the triangles) is tiny, and it is even smaller at the barycenter of the plane; for \(\alpha>\alpha_{\text{LE}}\) a high error peak appears in the barycenter. Configurations were obtained by optimizing the hinge loss with margin \(\kappa=-0.5\) using SGD. Points are averages over 20 realizations of the patterns and 5 different runs for each dataset. The value of \(N\) is 2000.
## VII Conclusions

In this paper we have studied the binary and spherical negative-margin perceptrons, i.e. two simple non-convex neural networks learning a random rule with binary and spherical weights. We have analyzed in both models the geometry of the landscape of solutions, showing important similarities but also differences. First, we have pointed out how the typical solutions of the models are substantially different: in the binary case for any \(\alpha>0\) the landscape is composed by an extensive number of clusters with vanishing entropy; in the spherical case, instead, typical solutions are always surrounded by an exponential number of other solutions. Second, we have studied highly robust (i.e. high-margin) but exponentially rare solutions of both problems, and showed that in both cases those configurations have a larger local entropy compared to typical solutions. In binary models the configurations having the largest local entropy corresponds to the one having the largest margin; in continuous weights models the same is true, modulo RSB effects (see Appendix).

Finally, we analyzed the solutions with the largest local entropy as a function of the constraint density \(\alpha\): we showed that in both models when a certain threshold \(\alpha_{\text{LE}}\) is crossed the local entropy becomes non-monotonic. This seems to signal a break-up of the space of robust solutions into disconnected components. Indeed, we have verified numerically in the spherical case, that for \(\alpha<\alpha_{\text{LE}}\) algorithms find solutions lying in the same basin, whereas for \(\alpha>\alpha_{\text{LE}}\) we observe a sudden rise of energy barriers along the geodesic path between pairs of solutions and in between triplets of solutions. Even if we cannot rule out at this time the existence of non-geodesic zero-energy paths connecting these solutions, this is already an indication of a profound change in the structure of the manifold of solutions.

In binary models we have verified that the transition has a very strong impact on the behavior of algorithms. In spherical models, even if we have a strong indication that the geometry of the space of solutions is undergoing a radical change in structure near the transition, it does not appear to have an impact on algorithmic hardness. As we have shown, efficient algorithms are probably able to reach the SAT/UNSAT transition, which we have computed here in the 1RSB ansatz.

We have verified that similar analytical findings are found also in models, the so called _tree-committee_ machine [14], where the non-convexity in the problem is not induced by the negative margin but by the presence of an additional layer and a generic non-linearity. Interesting future research directions involve the extension of those results to models presenting the notion of generalization and finally the analytical investigation of the connectivity properties of solutions in neural network models [43].

## Acknowledgements

E.M.M. wishes to thank R. Diaz Hernandez Rojas, S. Franz, P. Urbani and F. Zamponi for several interesting discussions.
