High dimensional optimization under non-convex excluded volume constraints

Abstract

We consider high dimensional random optimization problems where the dynamical variables are subjected to non-convex excluded volume constraints. We focus on the case in which the cost function is a simple quadratic cost and the excluded volume constraints are modeled by a perceptron constraint satisfaction problem. We show that depending on the density of constraints, one can have different situations. If the number of constraints is small, one typically has a phase where the ground state of the cost function is unique and sits on the boundary of the island of configurations allowed by the constraints. In this case, there is a hypostatic number of marginally satisfied constraints. If the number of constraints is increased one enters a glassy phase where the cost function has many local minima sitting again on the boundary of the regions of allowed configurations. At the phase transition point, the total number of marginally satisfied constraints becomes equal to the number of degrees of freedom in the problem and therefore we say that these minima are isostatic. We conjecture that by increasing further the constraints the system stays isostatic up to the point where the volume of available phase space shrinks to zero. We derive our results using the replica method and we also analyze a dynamical algorithm, the Karush-Kuhn-Tucker algorithm, through dynamical mean-field theory and we show how to recover the results of the replica approach in the replica symmetric phase.

arXiv comment7 pages, 3 figures

References in corpus (12)

• Spin-Glass Theory for Pedestrians
• Universal Spectrum of Normal Modes in Low-Temperature Glasses: an Exact Solution
• The simplest model of jamming
• Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems
• Universality of jamming of non-spherical particles
• Jamming in multilayer supervised learning models
• Critical jammed phase of the linear perceptron
• Disorder-free spin glass transitions and jamming in exactly solvable mean-field models
• Critical energy landscape of linear soft spheres
• Jamming and replica symmetry breaking of weakly disordered crystals
• Mean field theory of jamming of nonspherical particles
• Proliferation of non-linear excitations in the piecewise-linear perceptron

Cited by in corpus (9)

• On weak ergodicity breaking in mean-field spin glasses
• A continuous constraint satisfaction problem for the rigidity transition in confluent tissues
• Introduction to the dynamics of disordered systems: equilibrium and gradient descent
• Rigorous dynamical mean field theory for stochastic gradient descent methods
• Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks
• Tractability from overparametrization: The example of the negative perceptron
• Dynamical mean field theory for models of confluent tissues and beyond
• Gradient descent dynamics and the jamming transition in infinite dimensions
• The closest vector problem and the zero-temperature p-spin landscape for lossy compression