Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold

Abstract

Random constraint satisfaction problems can display a very rich structure in the space of solutions, with often an ergodicity breaking -- also known as clustering or dynamical -- transition preceding the satisfiability threshold when the constraint-to-variables ratio $\alpha$ is increased. However, smart algorithms start to fail finding solutions in polynomial time at some threshold ${\alpha }_{\mathrm{alg}}$ which is algorithmic dependent and generally bigger than the dynamical one ${\alpha }_d$. The reason for this discrepancy is due to the fact that ${\alpha }_d$ is traditionally computed according to the uniform measure over all the solutions. Thus, while bounding the region where a uniform sampling of the solutions is easy, it cannot predict the performance of off-equilibrium processes, that are still able of finding atypical solutions even beyond ${\alpha }_d$. Here we show that a reconciliation between algorithmic behaviour and thermodynamic prediction is nonetheless possible at least up to some threshold ${\alpha }_d^{\mathrm{opt}}\ge {\alpha }_d$, which is defined as the maximum value of the dynamical threshold computed on all possible probability measures over the solutions. We consider a simple Monte Carlo-based optimization algorithm, which is restricted to the solution space, and we demonstrate that sampling the equilibrium distribution of a biased measure improving on ${\alpha }_d$ is still possible even beyond the ergodicity breaking point for the uniform measure, where other algorithms hopelessly enter the out-of-equilibrium regime. The conjecture we put forward is that many smart algorithms sample the solution space according to a biased measure: once this measure is identified, the algorithmic threshold is given by the corresponding ergodicity-breaking transition.

References in corpus (34)

• Analytical Solution of the Off-Equilibrium Dynamics of a Long Range Spin-Glass Model
• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• On the Out of Equilibrium Relaxation of the Sherrington - Kirkpatrick model
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Higher order glass-transition singularities in colloidal systems with attractive interactions
• Jamming versus Glass Transitions
• A Landscape Analysis of Constraint Satisfaction Problems
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Learning by message-passing in networks of discrete synapses
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• Focused Local Search for Random 3-Satisfiability
• Dynamical transition of glasses: from exact to approximate
• Circumspect descent prevails in solving random constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Unveiling the structure of wide flat minima in neural networks
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Generating dense packings of hard spheres by soft interaction design
• Biased landscapes for random Constraint Satisfaction Problems
• A Cavity Master Equation for the continuous time dynamics of discrete spins models
• The large deviations of the whitening process in random constraint satisfaction problems
• Disorder-free spin glass transitions and jamming in exactly solvable mean-field models
• On the solution of a `solvable' model of an ideal glass of hard spheres displaying a jamming transition
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
• A theory of non-equilibrium local search on random satisfaction problems
• Maximally flexible solutions of a random $K$-satisfiability formula
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Optimization of the dynamic transition in the continuous coloring problem
• Neural networks: from the perceptron to deep nets

Cited by in corpus (1)

• Algorithmic thresholds in combinatorial optimization depend on the time scaling