Self-planting: digging holes in rough landscapes

Abstract

Motivated by a potential application in economics, we investigate a simple dynamical scheme to produce planted solutions in optimization problems with continuous variables. We consider the perceptron model as a prototypical model. Starting from random input patterns and perceptron weights, we find a locally optimal assignment of weights by gradient descent; we then remove misclassified patterns (if any), and replace them by new, randomly extracted patterns. This "remove and replace" procedure is iterated until perfect classification is achieved. We call this procedure "self-planting" because the "planted" state is not pre-assigned but results from a co-evolution of weights and patterns. We find an algorithmic phase transition separating a region in which self-planting is efficiently achieved from a region in which it takes exponential time in the system size. We conjecture that this transition might exist in a broad class of similar problems.

arXiv comment12 pages, 6 figures; introduction and discussion of model made clearer

References in corpus (9)

• Statistical physics of inference: Thresholds and algorithms
• Glass and Jamming Transitions: From Exact Results to Finite-Dimensional Descriptions
• Cleaning large correlation matrices: tools from random matrix theory
• Universal Spectrum of Normal Modes in Low-Temperature Glasses: an Exact Solution
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• The simplest model of jamming
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Emergent SO(3) Symmetry of the Frictionless Shear Jamming Transition

Cited by in corpus (2)

• Good speciation and endogenous business cycles in a constraint satisfaction macroeconomic model
• Annealed averages in spin and matrix models