Quenches in the Sherrington-Kirkpatrick model

Abstract

The Sherrington-Kirkpatrick (SK) model is a prototype of a complex non-convex energy landscape. Dynamical processes evolving on such landscapes and locally aiming to reach minima are generally poorly understood. Here, we study quenches, i.e. dynamics that locally aim to decrease energy. We analyse the energy at convergence for two distinct algorithmic classes, single-spin flip and synchronous dynamics, focusing on greedy and reluctant strategies. We provide precise numerical analysis of the finite size effects and conclude that, perhaps counter-intuitively, the reluctant algorithm is compatible with converging to the ground state energy density, while the greedy strategy is not. Inspired by the single-spin reluctant and greedy algorithms, we investigate two synchronous time algorithms, the sync-greedy and sync-reluctant algorithms. These synchronous processes can be analysed using dynamical mean field theory (DMFT), and a new backtracking version of DMFT. Notably, this is the first time the backtracking DMFT is applied to study dynamical convergence properties in fully connected disordered models. The analysis suggests that the sync-greedy algorithm can also achieve energies compatible with the ground state, and that it undergoes a dynamical phase transition.

References in corpus (18)

• Optimization with Extremal Dynamics
• Nature's Way of Optimizing
• Energy exponents and corrections to scaling in Ising spin glasses
• Parallel dynamics of disordered Ising spin systems on finitely connected random graphs
• Outer-totalistic cellular automata on graphs
• The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph
• Low temperature solution of the Sherrington-Kirkpatrick model
• Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions
• Dynamics and Correlations among Soft Excitations in Marginally Stable Glasses
• Marginal stability of soft anharmonic mean field spin glasses
• Time Dependent Local Field Distribution and Metastable States in the SK-Spin-Glass
• Relaxation, closing probabilities and transition from oscillatory to chaotic attractors in asymmetric neural networks
• On the number of limit cycles in asymmetric neural networks
• Algorithmic Thresholds in Mean Field Spin Glasses
• Dynamical Phase Transitions in Graph Cellular Automata
• Unlearnable Games and "Satisficing'' Decisions: A Simple Model for a Complex World
• Backtracking Dynamical Cavity Method
• Energy-Decreasing Dynamics in Mean-Field Spin Models

Cited by in corpus (3)

• Classical Annealing of Sherrington-Kirkpatrick Spin Glass Using Suzuki-Kubo Mean-field Ising Dynamics
• The geometry of jamming algorithms in the random Lorentz gas
• Algorithmic thresholds in combinatorial optimization depend on the time scaling