Origin of the computational hardness for learning with binary synapses

Through supervised learning in a binary perceptron one is able to classify an extensive number of random patterns by a proper assignment of binary synaptic weights. However, to find such assignments in practice is quite a nontrivial task. The relation between the weight space structure and the algorithmic hardness has not yet been fully understood. To this end, we analytically derive the Franz-Parisi potential for the binary perceptron problem by starting from an equilibrium solution of weights and exploring the weight space structure around it. Our result reveals the geometrical organization of the weight space; the weight space is composed of isolated solutions, rather than clusters of exponentially many close-by solutions. The pointlike clusters far apart from each other in the weight space explain the previously observed glassy behavior of stochastic local search heuristics.

Figure 1

Entropy landscape of solutions in the binary perceptron problem. Iterations of the saddle-point equations are always converged to produce the data points. The error bars give statistical errors and are smaller than or equal to the symbol size. (a) Franz-Parisi potential as a function of the normalized Hamming distance. The behavior of the coupling field with the distance is shown in the inset for $\alpha =0.7$, for which an observed maximum implies the change of the concavity of the entropy curve (this also holds for other finite values of $\alpha$). (b) Minimal distance versus the constraint density. Within the minimal distance, there are no solutions satisfying the distance constraint from the reference equilibrium solution. (c) Schematic illustration of the weight space based on results of (a) and (b). The points indicate the equilibrium solutions of weights. ${\alpha }_s\simeq 0.833$ is the storage capacity after which the solution space is typically empty. $d_{\min }$ is the actual Hamming distance without normalization.