Perceptron free energies and microscopic jamming exponents

The explanation

Take two switches, each set to +1 or −1. Draw a random pattern, say (0.5, −1.2). For each setting, multiply and add, then divide by √2. Setting (1, 1) scores about −0.495. Setting (1, −1) scores about 1.202. Setting (−1, 1) scores about −1.202, and (−1, −1) about 0.495. If the rule is score at least zero, two of the four settings pass. Add more random patterns, and fewer settings pass all of them. That is a perceptron: a vector of variables facing random linear constraints.

With N switches and about αN patterns, the question is how big the passing set is, on a log scale per switch. Gardner and Derrida set up this storage problem with replica calculations in 1988Source 1. At positive temperature, each constraint becomes soft. A log-potential f rewards or penalises each pattern's score, and the pressure is the log of the average total weight, divided by NSource 2.

Rigorous results needed small density. Talagrand and later Bolthausen, Nakajima, Sun and Xu handled only small αSource 3. The obstacle is that a sum of nonlinear terms of Gaussian patterns is not itself Gaussian. So the Parisi formula for standard spin glasses does not apply directlySource 4.

The first paper claims an exact formula for the Ising perceptron at every positive density. Ising means each variable is ±1. It allows any bounded log-potential and imposes no symmetry, concavity or smallness conditionSource 5. The fourth paper does the same for the spherical perceptron. There the variables form a vector of fixed length, and the potential must be bounded and continuousSource 6. The third paper replaces the Gaussian patterns by a rotation-invariant matrix. Its singular values may follow any compact limiting law, provided none stray far from the restSource 7.

The second paper studies jamming. Jamming is where a system of random constraints just stops having solutions, like grains locking into a pile. Franz and Parisi tied the negative-margin spherical perceptron to the jamming class of high-dimensional spheresSource 8. Margin −1 means each score must be at least −1. Near jamming, many constraints are almost tight. Gaps are how far a score sits above its limit. Forces are how hard a tight constraint pushes back.

The paper claims a sharp threshold, with power laws for small gaps and weak forcesSource 9. The fraction of gaps below u grows like u to the power 1 − γ. The force law has exponent 1 + θ, with γ = 1/(2 + θ). It places γ between 0.4126930 and 0.4126934, and θ between 0.4231063 and 0.4231088, with a numerical certificateSource 10. Take u = 0.01. Then 0.01 to the power 1 − γ is about 0.067, nearly seven times larger than 0.01. So tiny gaps are far more common than a straight-line law suggests. Earlier rigorous bounds did not give a sharp threshold at margin −1 or these lawsSource 11.

How sure is this? A computer proof checker called Lean has checked the spherical perceptron's variational formula, for bounded continuous potentials. For the Ising perceptron, Lean has checked only that the formula's value is a finite number. The Ising convergence, the rotation-invariant extension and the jamming laws are not formalized. No specialist review has been published.

What it doesn't show. This does not cover hard yes-or-no constraints in the Ising papers, or the jamming laws in any other order of limits.