Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses

We show that discrete synaptic weights can be efficiently used for learning in large scale neural systems, and lead to unanticipated computational performance. We focus on the representative case of learning random patterns with binary synapses in single layer networks. The standard statistical analysis shows that this problem is exponentially dominated by isolated solutions that are extremely hard to find algorithmically. Here, we introduce a novel method that allows us to find analytical evidence for the existence of subdominant and extremely dense regions of solutions. Numerical experiments confirm these findings. We also show that the dense regions are surprisingly accessible by simple learning protocols, and that these synaptic configurations are robust to perturbations and generalize better than typical solutions. These outcomes extend to synapses with multiple states and to deeper neural architectures. The large deviation measure also suggests how to design novel algorithmic schemes for optimization based on local entropy maximization.

Figure 1

Numerical evidence of the existence of clusters of solutions. Entropy at a given distance from a reference solution $\tilde{W}$, in the classification case at $\alpha =0.4$. From bottom to top: (magenta) theoretical prediction for a typical $\tilde{W}$; (blue) numerical estimate based on a random walks on connected solutions starting from one provided by SBPI, with $N=1001$; (red) estimate from belief propagation using a solution from SBPI, with $N=10001$; (green) theoretical curve for the optimal $\tilde{W}$ as computed from Eq. (1); and (dotted black) upper bound ($\alpha =0$ case, all configurations are solutions). The random-walk points underestimate the number of solutions since they only consider single-flip-connected clusters; the BP curve is lower than the optimal curve because in the latter $\tilde{W}$ is optimized as a function of the distance, while in the former it is fixed. Inset: comparison between a typical solution and one found with SBPI, in the teacher-student case at $\alpha =0.5$ with $N=1001$. Larger potentials correspond to smaller distances. Top points (red): SBPI reference solution, with the entropy computed by BP; bottom curve (magenta): theoretical prediction for a typical solution; bottom points (purple): BP results using the teacher as reference.

Figure 2

Large deviation analysis. Local entropy curves at varying distance $d$ from the reference solution $\tilde{W}$ for various $\alpha$ (classification case). Black dotted curve, $\alpha =0$ case (upper bound). Red solid curves, RS results from Eq. (1) (optimal $\tilde{W}$). Up to $\alpha =0.77$, the curves are monotonic. At $\alpha =0.78$, a region incorrectly described within the RS ansatz appears (dotted; geometric bounds are violated at the boundaries of the part of the curve with negative derivative). At $\alpha =0.79$, the solution is discontinuous (a gap appears in the curve), and parts of the curve have negative entropy (dotted). Blue dashed curves, equilibrium analysis (typical $\tilde{W}$) [14] (dotted parts are unphysical): the curves are never positive in a neighborhood of $d=0$. Inset: enlargement of the region around $d=0$ (notice the solution for $\alpha =0.79$, followed by a gap).

Figure 3

Generalization error (teacher-student scenario). From top to bottom: (blue) typical solution, (red) optimal $\tilde{W}$ from Eq. (1) at small $d$ (we used $d=0.025$ for numerical reasons and since the curve is not sensitive to the precise value of $d$ in this regime; this solution disappears after $\alpha \simeq 1.2$), (black points) solutions from SBPI at $N=10001$, 100 samples per point, (magenta) optimal $\tilde{W}$ from Eq. (1) at the value of $d$ for which ${\mathcal{S}}_I$ is maximum (i.e., it equals the equilibrium entropy), and (green) Bayesian case: error from the average over all solutions. At ${\alpha }_{\mathrm{TS}}=1.245$ there is the first-order transition to perfect learning; between ${\alpha }_{\mathrm{TS}}$ and $\alpha =1.5$ there is a metastable regime; the dashed parts of the curves correspond to unphysical solutions of the RS equations with negative entropy.