Origin of the computational hardness for learning with binary synapses

Abstract

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.

9 pages, 1 figure

References in corpus (6)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Theory of spike timing based neural classifiers
• Learning by random walks in the weight space of the Ising perceptron

Cited by in corpus (7)

• Unsupervised feature learning from finite data by message passing: discontinuous versus continuous phase transition
• Wide flat minima and optimal generalization in classifying high-dimensional Gaussian mixtures
• Interpolating between boolean and extremely high noisy patterns through Minimal Dense Associative Memories
• Maximally flexible solutions of a random $K$-satisfiability formula
• Code optimization, frozen glassy phase and improved decoding algorithms for low-density parity-check codes
• Active online learning in the binary perceptron problem
• Frozen $1$-RSB structure of the symmetric Ising perceptron