Origin of the computational hardness for learning with binary synapses
This addresses a fundamental issue in machine learning theory for researchers studying computational complexity and optimization in neural networks, but it is incremental as it builds on prior observations of glassy behavior.
The paper tackled the problem of understanding why learning with binary synapses is computationally hard by analyzing the weight space structure of a binary perceptron. The result revealed that the weight space consists of isolated solutions, explaining the glassy behavior of local search algorithms.
Supervised learning in a binary perceptron 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 preceptron 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\textemdash the weight space is composed of isolated solutions, rather than clusters of exponentially many close-by solutions. The point-like clusters far apart from each other in the weight space explain the previously observed glassy behavior of stochastic local search heuristics.