The algorithmic hardness threshold for continuous random energy models

DOI10.4171/MSL/12MaRDI QIDQ2176074zbMATH OpenOpenAlexFDO

Authors Louigi Addario-Berry, P. Maillard

Publication date 4 May 2020

Published in Mathematical Statistics and Learning (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic hardnessalgorithmic lower boundcombinatorial optimizationGaussian processrandom energy modelspin glass

Mathematics Subject Classification ID

Gaussian processes (60G15) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Combinatorial optimization (90C27)

Abstract: We prove an algorithmic hardness result for finding low-energy states in the so-called emph{continuous random energy model (CREM)}, introduced by Bovier and Kurkova in 2004 as an extension of Derrida's emph{generalized random energy model}. The CREM is a model of a random energy landscape $(X_v{)}_{vin{0,1}^N}$ on the discrete hypercube with built-in hierarchical structure, and can be regarded as a toy model for strongly correlated random energy landscapes such as the family of $p$-spin models including the Sherrington--Kirkpatrick model. The CREM is parameterized by an increasing function $A:[0,1]o[0,1]$, which encodes the correlations between states. We exhibit an emph{algorithmic hardness threshold} $x_{\ast }$, which is explicit in terms of $A$. More precisely, we obtain two results: First, we show that a renormalization procedure combined with a greedy search yields for any $varepsilon>0$ a linear-time algorithm which finds states $vin{0,1}^N$ with $X_{v}ge(x_{\ast }-varepsilon)N$. Second, we show that the value $x_{\ast }$ is essentially best-possible: for any $varepsilon>0$, any algorithm which finds states $v$ with $X_{v}ge(x_{\ast }+varepsilon)N$ requires exponentially many queries in expectation and with high probability. We further discuss what insights this study yields for understanding algorithmic hardness thresholds for random instances of combinatorial optimization problems.

Review text

Summary: We prove an algorithmic hardness result for finding low-energy states in the so-called \textit{continuous random energy model (CREM)}, introduced by \textit{A. Bovier} and \textit{I. Kurkova} in [Ann. Inst. Henri Poincaré, Probab. Stat. 40, No. 4, 439--480 (2004; Zbl 1121.82020); ibid. 40, No. 4, 481--495 (2004; Zbl 1121.82021)] as an extension of Derrida's \textit{generalized random energy model}. The CREM is a model of a random energy landscape \((X_v)_{v \in \{0,1\}^N}\) on the discrete hypercube with built-in hierarchical structure, and can be regarded as a toy model for strongly correlated random energy landscapes such as the family of \(p\)-spin models including the Sherrington-Kirkpatrick model. The CREM is parameterized by an increasing function \(A \colon [0, 1]\to[0, 1]\), which encodes the correlations between states. We exhibit an \textit{algorithmic hardness threshold} \(x_\ast\), which is explicit in terms of \(A\). More precisely, we obtain two results: First, we show that a renormalization procedure combined with a greedy search yields for any \(\varepsilon > 0\) a linear-time algorithm which finds states \(v \in \{0,1\}^N\) with \(X_v \ge (x_\ast-\varepsilon) N\). Second, we show that the value \(x_\ast\) is essentially best-possible: for any \(\varepsilon > 0\), any algorithm which finds states \(v\) with \(X_v \ge (x_\ast+\varepsilon)N\) requires exponentially many queries in expectation and with high probability. We further discuss what insights this study yields for understanding algorithmic hardness thresholds for random instances of combinatorial optimization problems.

Recommendations

• Efficient approximation of branching random walk Gibbs measures
• Phase transitions in parameter rich optimization problems
• Random subcubes as a toy model for constraint satisfaction problems
• Gaussian mean field lattice gas
• Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses

Cites work

• Approximate ultrametricity for random measures and applications to spin glasses
• Belief propagation guided decimation fails on random formulas
• Brownian motion. With an appendix by Oded Schramm and Wendelin Werner
• Derrida's generalized random energy models. II: Models with continuous hierarchies
• Gibbs states and the set of solutions of random constraint satisfaction problems
• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• Maximal displacement of a branching random walk in time-inhomogeneous environment
• Mean Field Models for Spin Glasses
• Mean field models for spin glasses. Volume I: Basic examples.
• On belief propagation guided decimation for random k-SAT
• On the solution-space geometry of random constraint satisfaction problems
• Postulates for subadditive processes
• Random matrices and complexity of spin glasses
• Random-energy model: an exactly solvable model of disordered systems
• Search cost for a nearly optimal path in a binary tree
• Spin glasses and complexity
• Suboptimality of local algorithms for a class of max-cut problems
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• The first birth problem for an age-dependent branching process
• The first- and last-birth problems for a multitype age-dependent branching process
• The Sherrington-Kirkpatrick model

Cited in

(15)

• The overlap gap property in principal submatrix recovery
• Optimization of mean-field spin glasses
• Optimal low-degree hardness of maximum independent set
• Efficient approximation of branching random walk Gibbs measures
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian
• Algorithmic pure states for the negative spherical perceptron
• Optimization of the Sherrington--Kirkpatrick Hamiltonian
• Un-inverting the Parisi formula
• Shattering in the Ising p-spin glass model
• A spatially-dependent fragmentation process
• Efficient approximation of the CREM Gibbs measure and the hardness threshold
• A CLuP algorithm to practically achieve 0.76 SK-model ground state free energy
• Sharp phase transitions for the overlap gap property
• Sharp thresholds for the overlap gap property: Ising p-spin Glass and random k-SAT

This page was built for publication: The algorithmic hardness threshold for continuous random energy models

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