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 (19)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Recipes for metastable states in Spin Glasses
• Phase diagram of glassy systems in an external field
• Learning by message-passing in networks of discrete synapses
• Effective potential in glassy systems: theory and simulations
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Statistical mechanics of lossy data compression using a non-monotonic perceptron
• Theory of spike timing based neural classifiers
• Universality Classes of Critical Points in Constrained Glasses
• Entropy landscape of solutions in the binary perceptron problem
• Perceptron capacity revisited: classification ability for correlated patterns
• Weight space structure and analysis using a finite replica number in the Ising perceptron
• Statistical mechanics of sparse generalization and model selection
• Learning by random walks in the weight space of the Ising perceptron
• Combined local search strategy for learning in networks of binary synapses
• Theory and learning protocols for the material tempotron model
• Replication-based Inference Algorithms for Hard Computational Problems

Cited by in corpus (41)

• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• Shaping the learning landscape in neural networks around wide flat minima
• Efficiency of quantum versus classical annealing in non-convex learning problems
• Properties of the geometry of solutions and capacity of multi-layer neural networks with Rectified Linear Units activations
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• Storage capacity in symmetric binary perceptrons
• Mean-field inference methods for neural networks
• Unveiling the structure of wide flat minima in neural networks
• Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
• Learning through atypical "phase transitions" in overparameterized neural networks
• Learning may need only a few bits of synaptic precision
• On the role of synaptic stochasticity in training low-precision neural networks
• Unsupervised feature learning from finite data by message passing: discontinuous versus continuous phase transition
• A Max-Sum algorithm for training discrete neural networks
• Clustering of solutions in the symmetric binary perceptron
• Teacher-student learning for a binary perceptron with quantum fluctuations
• Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks
• Eight challenges in developing theory of intelligence
• Wide flat minima and optimal generalization in classifying high-dimensional Gaussian mixtures
• Generalization from correlated sets of patterns in the perceptron
• Statistical mechanics of continual learning: variational principle and mean-field potential
• On the Atypical Solutions of the Symmetric Binary Perceptron
• Nonequilbrium physics of generative diffusion models
• An optimization-based equilibrium measure describes non-equilibrium steady state dynamics: application to edge of chaos
• The Copycat Perceptron: Smashing Barriers Through Collective Learning
• Interpolating between boolean and extremely high noisy patterns through Minimal Dense Associative Memories
• Maximally flexible solutions of a random $K$-satisfiability formula
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness
• Code optimization, frozen glassy phase and improved decoding algorithms for low-density parity-check codes
• Data-driven effective model shows a liquid-like deep learning
• Equivalence between algorithmic instability and transition to replica symmetry breaking in perceptron learning systems
• Reinforced stochastic gradient descent for deep neural network learning
• Active online learning in the binary perceptron problem
• The discrete random energy model and one step replica symmetry breaking
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Frozen $1$-RSB structure of the symmetric Ising perceptron
• Gradient dynamics in reinforcement learning
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties