Self-planting: digging holes in rough landscapes

DOI10.1088/1742-5468/AB4800MaRDI QIDQ5854083zbMATH OpenOpenAlexFDO

Authors Dhruv Sharma, Jean-Philippe Bouchaud, Francesco Zamponi, M. Tarzia

Publication date 16 March 2021

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.01490

Mathematics Subject Classification ID

Applications to the sciences (65Z05)

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.

Recommendations

• Quiet planting in the locked constraint satisfaction problems
• Optimal testing for planted satisfiability problems
• Reweighted belief propagation and quiet planting for random K-SAT
• scientific article; zbMATH DE number 1329955
• On the complexity of random satisfiability problems with planted solutions

Cites work

• Cleaning large correlation matrices: tools from random matrix theory
• Emergent \(\mathrm{SO}(3)\) symmetry of the frictionless shear jamming transition
• scientific article; zbMATH DE number 4092811 (Why is no real title available?)
• Information capacity of a perceptron
• Neural networks and physical systems with emergent collective computational abilities
• Reweighted belief propagation and quiet planting for random K-SAT
• Statistical mechanics of learning
• The elements of statistical learning. Data mining, inference, and prediction
• The simplest model of jamming
• The space of interactions in neural network models

Cited in

(2)

• Good speciation and endogenous business cycles in a constraint satisfaction macroeconomic model
• Digging for roots using the Pascal spade

This page was built for publication: Self-planting: digging holes in rough landscapes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5854083)