Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems

Abstract

Random constraint satisfaction problems (CSP) have been studied extensively using statistical physics techniques. They provide a benchmark to study average case scenarios instead of the worst case one. The interplay between statistical physics of disordered systems and computer science has brought new light into the realm of computational complexity theory, by introducing the notion of clustering of solutions, related to replica symmetry breaking. However, the class of problems in which clustering has been studied often involve discrete degrees of freedom: standard random CSPs are random K-SAT (aka disordered Ising models) or random coloring problems (aka disordered Potts models). In this work we consider instead problems that involve continuous degrees of freedom. The simplest prototype of these problems is the perceptron. Here we discuss in detail the full phase diagram of the model. In the regions of parameter space where the problem is non-convex, leading to multiple disconnected clusters of solutions, the solution is critical at the SAT/UNSAT threshold and lies in the same universality class of the jamming transition of soft spheres. We show how the critical behavior at the satisfiability threshold emerges, and we compute the critical exponents associated to the approach to the transition from both the SAT and UNSAT phase. We conjecture that there is a large universality class of non-convex continuous CSPs whose SAT-UNSAT threshold is described by the same scaling solution.

28 pages, 5 figures

References in corpus (10)

• Theoretical perspective on the glass transition and amorphous materials
• Jamming at Zero Temperature and Zero Applied Stress: the Epitome of Disorder
• Supercooled Liquids for Pedestrians
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Fractal free energy landscapes in structural glasses
• Universal microstructure and mechanical stability of jammed packings
• Jamming Criticality Revealed by Removing Localized Buckling Excitations
• Following the evolution of glassy states under external perturbations: compression and shear-strain
• Mean-field avalanches in jammed spheres
• The jamming transition in high dimension: an analytical study of the TAP equations and the effective thermodynamic potential

Cited by in corpus (68)

• Scaling description of generalization with number of parameters in deep learning
• The jamming transition as a paradigm to understand the loss landscape of deep neural networks
• Memorizing without overfitting: Bias, variance, and interpolation in over-parameterized models
• The limits of multifunctionality in tunable networks
• Universality of jamming of non-spherical particles
• Out-of-equilibrium dynamical mean-field equations for the perceptron model
• Jamming in multilayer supervised learning models
• Liu-Nagel phase diagrams in infinite dimension
• Storage capacity in symmetric binary perceptrons
• The effective noise of Stochastic Gradient Descent
• Marginally stable phases in mean-field structural glasses
• Critical jammed phase of the linear perceptron
• Marginal stability of soft anharmonic mean field spin glasses
• Vibrational density of states and specific heat in glasses from random matrix theory
• Universal non-mean-field scaling in the density of state of amorphous solids
• Jammed spin liquid in the bond-disordered kagome Heisenberg antiferromagnet
• Generating dense packings of hard spheres by soft interaction design
• Mean field stability map of hard-sphere glasses
• The nature of non-phononic excitations in disordered systems
• Marginally jammed states of hard disks in a one-dimensional channel
• Mean-field caging in a random Lorentz gas
• Disorder-free spin glass transitions and jamming in exactly solvable mean-field models
• Jamming with tunable roughness
• Finite size effects in the microscopic critical properties of jammed configurations: A comprehensive study of the effects of different types of disorder
• Gaussian Universality of Perceptrons with Random Labels
• An exploratory study of the glassy landscape near jamming
• Impact of jamming criticality on low-temperature anomalies in structural glasses
• Critical energy landscape of linear soft spheres
• Jamming below upper critical dimension
• Mean-Field Predictions of Scaling Prefactors Match Low-Dimensional Jammed Packings
• Quantum Jamming: Critical Properties of a Quantum Mechanical Perceptron
• A continuous constraint satisfaction problem for the rigidity transition in confluent tissues
• Introduction to the dynamics of disordered systems: equilibrium and gradient descent
• Mean field theory of jamming of nonspherical particles
• Jamming and replica symmetry breaking of weakly disordered crystals
• From complex to simple : hierarchical free-energy landscape renormalized in deep neural networks
• Higher order corrections to the effective potential close to the jamming transition in the perceptron model
• High dimensional optimization under non-convex excluded volume constraints
• Surfing on minima of isostatic landscapes: avalanches and unjamming transition
• Force balance controls the relaxation time of the gradient descent algorithm in the satisfiable phase
• Bose-Einstein-Like condensation of deformed random matrix: A replica approach
• Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks
• Good speciation and endogenous business cycles in a constraint satisfaction macroeconomic model
• Dynamics and energy landscape of the jammed spin-liquid
• Hard-Sphere Jamming through the Lens of Linear Optimization
• Dense Hopfield Networks in the Teacher-Student Setting
• Dynamical mean field theory for models of confluent tissues and beyond
• Tractability from overparametrization: The example of the negative perceptron
• Vibrational density of states of jammed packing: mean-field theory
• Pattern capacity of a single quantum perceptron
• Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification
• Critical fragility in socio-technical systems
• Gardner formula for Ising perceptron models at small densities
• Infinitesimal asphericity changes the universality of the jamming transition
• The Copycat Perceptron: Smashing Barriers Through Collective Learning
• Existence of Nonequilibrium Glasses in the Degenerate Stealthy Hyperuniform Ground-State Manifold
• Statistical mechanics of the maximum-average submatrix problem
• Proliferation of non-linear excitations in the piecewise-linear perceptron
• Two-level systems and harmonic excitations in a mean-field anharmonic quantum glass
• Perspective: A Phase Diagram for Deep Learning unifying Jamming, Feature Learning and Lazy Training
• On the topology of solutions to random continuous constraint satisfaction problems
• Comment on "Explicit Analytical Solution for Random Close Packing in $d=2$ and $d=3$"
• Glass-like Caging with Random Planes
• Fluctuation Distributions of Energy Minima in Complex Landscapes
• Satisfiability transition in asymmetric neural networks
• Critical properties of the SAT/UNSAT transitions in the classification problem of structured data
• Interaction-free ergodicity-breaking driven by temporally hyperuniform noise
• Gradient descent dynamics and the jamming transition in infinite dimensions