Storage capacity in symmetric binary perceptrons

Abstract

We study the problem of determining the capacity of the binary perceptron for two variants of the problem where the corresponding constraint is symmetric. We call these variants the rectangle-binary-perceptron (RPB) and the $u-$function-binary-perceptron (UBP). We show that, unlike for the usual step-function-binary-perceptron, the critical capacity in these symmetric cases is given by the annealed computation in a large region of parameter space (for all rectangular constraints and for narrow enough $u-$function constraints, $K<K^{\ast }$). We prove this fact (under two natural assumptions) using the first and second moment methods. We further use the second moment method to conjecture that solutions of the symmetric binary perceptrons are organized in a so-called frozen-1RSB structure, without using the replica method. We then use the replica method to estimate the capacity threshold for the UBP case when the $u-$function is wide $K>K^{\ast }$. We conclude that full-step-replica-symmetry breaking would have to be evaluated in order to obtain the exact capacity in this case.

18 + 7 pages

References in corpus (14)

• The structural glass transition and the entropy of the metastable states
• Learning by message-passing in networks of discrete synapses
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• The simplest model of jamming
• Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems
• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• Information-theoretic thresholds from the cavity method
• The Parisi formula for mixed $p$-spin models
• Origin of the computational hardness for learning with binary synapses
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Statistical mechanics of lossy data compression using a non-monotonic perceptron
• Quiet Planting in the Locked Constraint Satisfaction Problems
• A frozen glass phase in the multi-index matching problem

Cited by in corpus (10)

• Disordered Systems Insights on Computational Hardness
• Gaussian Universality of Perceptrons with Random Labels
• Clustering of solutions in the symmetric binary perceptron
• Teacher-student learning for a binary perceptron with quantum fluctuations
• (Dis)assortative Partitions on Random Regular Graphs
• On the Atypical Solutions of the Symmetric Binary Perceptron
• Tractability from overparametrization: The example of the negative perceptron
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties