Optimization of random cost functions and statistical physics

Andrea MontanariarXiv 2024 · DOI · arXiv

TL;DR

This paper reviews four decades of progress in minimizing high-dimensional random cost functions, tracing the journey from heuristic physics conjectures to rigorous mathematical proofs. It reveals that the "geometry" of a problem—specifically how solutions are clustered in space—is the fundamental factor determining whether an efficient algorithm can find a global minimum.

What Problem Does This Paper Address?

In fields ranging from machine learning to materials science, we often need to find the "best" configuration of a system—minimizing an energy or cost function $H(\sigma)$. When the number of variables $N$ is huge, this is like trying to find the lowest point in a vast, jagged mountain range.

Standard computer science focuses on the worst-case: "Can we build an algorithm that works for any possible mountain range?" The answer is often a resounding "No" (it's NP-hard). However, statistical physics asks about the average-case: "If the mountain range is generated randomly, can we find the bottom most of the time?" This paper bridges these two worlds, explaining how the structural properties of random landscapes dictate algorithmic success or failure.

Methods

The paper synthesizes several key algorithmic and theoretical frameworks:

  • Message Passing Algorithms: Derived from the "cavity method" in physics, these include Belief Propagation (BP) and Survey Propagation (SP). They work by having variables "talk" to their neighbors to estimate their most likely state.
  • Approximate Message Passing (AMP): A more recent evolution used for dense problems (like spin glasses), which allows for precise tracking of the algorithm's progress in the high-dimensional limit.
  • Convex Relaxations: Techniques like Semidefinite Programming (SDP) that try to approximate a jagged, non-convex landscape with a smooth, bowl-shaped one that is easier to optimize.
  • Interpolation Methods: A mathematical "trick" used to prove hardness. By slowly morphing one random problem into another, researchers can show that if an algorithm could solve one, it would have to "survive" a phase transition where the solution space shatters into pieces.

Datasets

As a theoretical review, the paper focuses on mathematical models rather than empirical datasets. The primary "benchmarks" discussed are:

  • Random $k$-SAT: A classic problem in logic and computer science where one tries to satisfy a set of random constraints.
  • Mixed $p$-spin models: The "gold standard" for studying spin glasses, where variables interact in groups of $p$.
  • The Sherrington-Kirkpatrick (SK) Model: A famous model of disordered magnets that serves as a playground for testing optimization theories.

Key Insights and Ideas

  • The Geometry of Solutions: The most profound insight is that the "shape" of the set of good solutions changes as the problem gets harder. In easy regimes, solutions form one big "cloud." In hard regimes, they "shatter" into exponentially many tiny, isolated islands (a process called Shattering).
  • The Overlap Gap Property (OGP): This is the "smoking gun" for algorithmic hardness. If any two "good" solutions are either very close together or very far apart—with a forbidden "gap" in between—local algorithms (like gradient descent or message passing) are almost guaranteed to fail.
  • Full Replica Symmetry Breaking (FRSB): Physics models with "no overlap gap" (continuous FRSB) are actually optimizable in polynomial time. The algorithm can "descend the tree" of states, making a sequence of decisions that lead to a near-global minimum.
  • The Algorithmic Barrier (ALG): There is a mathematically defined energy level called ALG. For many random problems, we can prove that polynomial-time algorithms can reach ALG, but going even a tiny bit lower requires exponential time.

Key Results

  • Rigorous Thresholds: The paper highlights recent proofs (e.g., by Subag, Montanari, and others) that characterize the exact energy levels reachable by efficient algorithms in spin glass models.
  • Tightness of Lipschitz Algorithms: For mixed $p$-spin models, it has been proven that a broad class of "stable" (Lipschitz) algorithms cannot beat the predicted physics threshold.
  • The Success of Parisi’s Formula: The review notes that the famous Parisi formula for ground state energy—once a controversial physics heuristic—has now been fully proven as a rigorous limit in mathematics.

Limitations and Future Work

  • Beyond Gaussianity: Most current rigorous results rely on "simple" randomness (like Gaussian distributions). The author notes that extending these to "richer," more structured distributions (like those found in real-world neural networks) is a major frontier.
  • The Sampling Challenge: While we are getting better at finding one minimum (optimization), sampling uniformly from all possible minima is significantly harder and remains poorly understood in many glassy regimes.
  • Refutation vs. Search: There is still a gap between algorithms that find a solution and those that can prove no better solution exists (refutation). Bridging this gap using SDP hierarchies is an ongoing area of research.

Summary updated

Abstract

This is the text of my report presented at the 29th Solvay Conference on Physics on `The Structure and Dynamics of Disordered Systems' held in Bruxelles from October 19 to 21, 2023. I consider the problem of minimizing a random energy function $H(σ)$, where $σ$ is an $N$-dimensional vector, in the high-dimensional regime $N\gg 1$. Using as a reference point a 1986 paper by Fu and Anderson, I take stock of the progress on this question over the last 40 years. In particular, I focus on the influence and ramifications of ideas originating from statistical physics. My own conclusion is that several of the most fundamental questions in this area (which in 1986 were barely formulated) have now received mathematically rigorous answers, at least in simple -- yet highly nontrivial -- settings. Instrumental to this spectacular progress was the dialogue between different research communities: physics, computer science, mathematics.
BibTeX
@misc{montanari2024optimization,
  author = {Andrea Montanari},
  title = {{Optimization of random cost functions and statistical physics}},
  year = {2024},
  eprint = {2401.11348},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2401.11348},
}
Figure