SciPost Physics

SciPost Phys. 2, 019 (2017) · published 2 June 2017

• doi: 10.21468/SciPostPhys.2.3.019
• pdf
• BiBTeX
• RIS
• Submissions/Reports
• 

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.

• Gerace et al., Gaussian universality of perceptrons with random labels
  Phys. Rev. E 109, 034305 (2024) [Crossref]
• Sclocchi et al., Proliferation of non-linear excitations in the piecewise-linear perceptron
  SciPost Phys. 10, 013 (2021) [Crossref]
• Biroli et al., Mean-Field Caging in a Random Lorentz Gas
  J. Phys. Chem. B 125, 6244 (2021) [Crossref]
• Ikeda, Universal non-mean-field scaling in the density of states of amorphous solids
  Phys. Rev. E 99, 050901 (2019) [Crossref]
• Franz et al., Critical Jammed Phase of the Linear Perceptron
  Phys. Rev. Lett. 123, 115702 (2019) [Crossref]
• Aguirre-López et al., Satisfiability transition in asymmetric neural networks
  J. Phys. A: Math. Theor. 55, 305001 (2022) [Crossref]
• Artiaco et al., Hard-sphere jamming through the lens of linear optimization
  Phys. Rev. E 106, 055310 (2022) [Crossref]
• Rocks et al., Limits of multifunctionality in tunable networks
  Proc. Natl. Acad. Sci. U.S.A. 116, 2506 (2019) [Crossref]
• Ikeda, Jamming and replica symmetry breaking of weakly disordered crystals
  Phys. Rev. Research 2, 033220 (2020) [Crossref]
• Mignacco et al., Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification*
  J. Stat. Mech. 2021, 124008 (2021) [Crossref]
• Mignacco et al., The effective noise of stochastic gradient descent
  J. Stat. Mech. 2022, 083405 (2022) [Crossref]
• Annesi et al., Star-Shaped Space of Solutions of the Spherical Negative Perceptron
  Phys. Rev. Lett. 131, 227301 (2023) [Crossref]
• Urbani, A continuous constraint satisfaction problem for the rigidity transition in confluent tissues
  J. Phys. A: Math. Theor. 56, 115003 (2023) [Crossref]
• Baldassi et al., Typical and atypical solutions in nonconvex neural networks with discrete and continuous weights
  Phys. Rev. E 108, 024310 (2023) [Crossref]
• Altieri et al., Mean-field stability map of hard-sphere glasses
  Phys. Rev. E 100, 032140 (2019) [Crossref]
• Ikeda et al., Mean field theory of jamming of nonspherical particles
  J. Phys. A: Math. Theor. 52, 344001 (2019) [Crossref]
• Folena et al., Marginal stability of soft anharmonic mean field spin glasses
  J. Stat. Mech. 2022, 053301 (2022) [Crossref]
• Boltz et al., Fluctuation distributions of energy minima in complex landscapes
  Phys. Rev. Research 3, 013061 (2021) [Crossref]
• Sclocchi et al., High-dimensional optimization under nonconvex excluded volume constraints
  Phys. Rev. E 105, 024134 (2022) [Crossref]
• Franz et al., Critical energy landscape of linear soft spheres
  SciPost Phys. 9, 012 (2020) [Crossref]
• El Alaoui et al., Algorithmic Pure States for the Negative Spherical Perceptron
  J Stat Phys 189, 27 (2022) [Crossref]
• Franz et al., Surfing on minima of isostatic landscapes: avalanches and unjamming transition
  J. Stat. Mech. 2021, 023208 (2021) [Crossref]
• Bonnet et al., Glasslike caging with random planes
  Phys. Rev. E 109, 024125 (2024) [Crossref]
• Folena et al., Introduction to the dynamics of disordered systems: Equilibrium and gradient descent
  Physica A: Statistical Mechanics and its Applications 631, 128152 128152 (2023) [Crossref]
• Bilitewski et al., Dynamics and energy landscape of the jammed spin liquid
  Phys. Rev. B 99, 054416 (2019) [Crossref]
• Kamali et al., Dynamical mean field theory for models of confluent tissues and beyond
  SciPost Phys. 15, 219 (2023) [Crossref]
• Artiaco et al., Exploratory study of the glassy landscape near jamming
  Phys. Rev. E 101, 052605 (2020) [Crossref]
• Geiger et al., Landscape and training regimes in deep learning
  Physics Reports 924, 1 (2021) [Crossref]
• Bilitewski et al., Jammed Spin Liquid in the Bond-Disordered Kagome Antiferromagnet
  Phys. Rev. Lett. 119, 247201 (2017) [Crossref]
• Altieri, Higher-order corrections to the effective potential close to the jamming transition in the perceptron model
  Phys. Rev. E 97, 012103 (2018) [Crossref]
• Franz et al., Jamming in Multilayer Supervised Learning Models
  Phys. Rev. Lett. 123, 160602 (2019) [Crossref]
• Biroli et al., Liu-Nagel phase diagrams in infinite dimension
  SciPost Phys. 4, 020 (2018) [Crossref]
• Ikeda et al., Vibrational density of states of jammed packing at high dimensions: Mean-field theory
  Phys. Rev. E 106, 024904 (2022) [Crossref]
• Yoshino, Disorder-free spin glass transitions and jamming in exactly solvable mean-field models
  SciPost Phys. 4, 040 (2018) [Crossref]
• Parisi et al.,
  , (2020) [Crossref]
• Ikeda et al., Infinitesimal asphericity changes the universality of the jamming transition
  J. Stat. Mech. 2020, 033302 (2020) [Crossref]
• Sharma et al., A Constraint-Satisfaction Agent-Based Model for the Macro-economy
  SSRN Journal, (2020) [Crossref]
• Sartor et al., Mean-Field Predictions of Scaling Prefactors Match Low-Dimensional Jammed Packings
  Phys. Rev. Lett. 126, 048001 (2021) [Crossref]
• Hwang et al., Force balance controls the relaxation time of the gradient descent algorithm in the satisfiable phase
  Phys. Rev. E 101, 052308 (2020) [Crossref]
• Scalliet et al., Marginally stable phases in mean-field structural glasses
  Phys. Rev. E 99, 012107 (2019) [Crossref]
• Montanari et al., Tractability from overparametrization: the example of the negative perceptron
  Probab. Theory Relat. Fields 188, 805 (2024) [Crossref]
• Ding et al.,
  , 816 (2019) [Crossref]
• Altieri,
  , 65 (2019) [Crossref]
• Ikeda, Jamming Below Upper Critical Dimension
  Phys. Rev. Lett. 125, 038001 (2020) [Crossref]
• Baggioli et al., Vibrational density of states and specific heat in glasses from random matrix theory
  Phys. Rev. E 100, 062131 (2019) [Crossref]
• Geiger et al., Scaling description of generalization with number of parameters in deep learning
  J. Stat. Mech. 2020, 023401 (2020) [Crossref]
• Yoshino, From complex to simple : hierarchical free-energy landscape renormalized in deep neural networks
  SciPost Phys. Core 2, 005 (2020) [Crossref]
• Erba et al., Statistical mechanics of the maximum-average submatrix problem
  J. Stat. Mech. 2024, 013403 (2024) [Crossref]
• Zhang et al., Marginally jammed states of hard disks in a one-dimensional channel
  Phys. Rev. E 102, 042614 (2020) [Crossref]
• Aubin et al., Storage capacity in symmetric binary perceptrons
  J. Phys. A: Math. Theor. 52, 294003 (2019) [Crossref]
• Maimbourg et al., Generating dense packings of hard spheres by soft interaction design
  SciPost Phys. 4, 039 (2018) [Crossref]
• Brito et al., Universality of jamming of nonspherical particles
  Proc. Natl. Acad. Sci. U.S.A. 115, 11736 (2018) [Crossref]
• Arceri et al.,
  , 1 (2021) [Crossref]
• Franz et al., Impact of jamming criticality on low-temperature anomalies in structural glasses
  Proc. Natl. Acad. Sci. U.S.A. 116, 13768 (2019) [Crossref]
• Ikeda et al., Jamming with Tunable Roughness
  Phys. Rev. Lett. 124, 208001 (2020) [Crossref]
• Artiaco et al., Quantum jamming: Critical properties of a quantum mechanical perceptron
  Phys. Rev. A 103, L040203 (2021) [Crossref]
• Benatti et al., Pattern capacity of a single quantum perceptron
  J. Phys. A: Math. Theor. 55, 155301 (2022) [Crossref]
• Schirmacher et al., The nature of non-phononic excitations in disordered systems
  Nat Commun 15, 3107 (2024) [Crossref]
• Agoritsas et al., Out-of-equilibrium dynamical mean-field equations for the perceptron model
  J. Phys. A: Math. Theor. 51, 085002 (2018) [Crossref]
• Sharma et al., Good speciation and endogenous business cycles in a constraint satisfaction macroeconomic model
  J. Stat. Mech. 2021, 063403 (2021) [Crossref]
• Manacorda et al., Gradient descent dynamics and the jamming transition in infinite dimensions
  J. Phys. A: Math. Theor. 55, 334001 (2022) [Crossref]
• Geiger et al., Jamming transition as a paradigm to understand the loss landscape of deep neural networks
  Phys. Rev. E 100, 012115 (2019) [Crossref]
• Arceri et al.,
  , 229 (2022) [Crossref]
• Ikeda, Bose–Einstein-like condensation of deformed random matrix: a replica approach
  J. Stat. Mech. 2023, 023302 (2023) [Crossref]
• Rocks et al., Memorizing without overfitting: Bias, variance, and interpolation in overparameterized models
  Phys. Rev. Research 4, 013201 (2022) [Crossref]
• Charbonneau et al., Finite-size effects in the microscopic critical properties of jammed configurations: A comprehensive study of the effects of different types of disorder
  Phys. Rev. E 104, 014102 (2021) [Crossref]
• Pastore, Critical properties of the SAT/UNSAT transitions in the classification problem of structured data
  J. Stat. Mech. 2021, 113301 (2021) [Crossref]