Source-linked AI summary
Optimization of the Sherrington-Kirkpatrick Hamiltonian
Andrea Montanari
TL;DR
The paper asks whether the Sherrington–Kirkpatrick optimization problem on Gaussian random matrices can be solved approximately despite its complex energy landscape. It introduces a structured message-passing algorithm and proves that, under an assumption on the Parisi measure, it finds a (1−ε)-optimal binary solution in O(n^2) time with high probability, while also producing approximate TAP solutions.
Problem
The paper studies whether near-optimal maximization of the Sherrington–Kirkpatrick Hamiltonian over binary vectors can be achieved efficiently for random Gaussian matrices.
Method
The paper introduces an incremental approximate message-passing algorithm whose analysis relies on the assumed connected support of the Parisi measure.
Results
(1−ε) of the optimum is achieved with high probability using at most C(ε)n^2 floating-point operations.
Takeaways & Limitations
The results indicate that this random optimization problem is substantially easier on average than its worst-case complexity suggests, and the iteration also constructs approximate TAP solutions.
Takeaways & Limitations
The universality argument requires polynomial update functions, while the main theorem is stated under the Parisi-measure support assumption and focuses primarily on Gaussian matrices.
Abstract
from arXiv · showhide
Let ${\boldsymbol A}\in{\mathbb R}^{n\times n}$ be a symmetric random matrix with independent and identically distributed Gaussian entries above the diagonal. We consider the problem of maximizing $\langle{\boldsymbol σ},{\boldsymbol A}{\boldsymbol σ}\rangle$ over binary vectors ${\boldsymbol σ}\in\{+1,-1\}^n$. In the language of statistical physics, this amounts to finding the ground state of the Sherrington-Kirkpatrick model of spin glasses. The asymptotic value of this optimization problem was characterized by Parisi via a celebrated variational principle, subsequently proved by Talagrand. We give an algorithm that, for any $\varepsilon>0$, outputs ${\boldsymbol σ}_*\in\{-1,+1\}^n$ such that $\langle{\boldsymbol σ}_*,{\boldsymbol A}{\boldsymbol σ}_*\rangle$ is at least $(1-\varepsilon)$ of the optimum value, with probability converging to one as $n\to\infty$. The algorithm's time complexity is $C(\varepsilon)\, n^2$. It is a message-passing algorithm, but the specific structure of its update rules is new. As a side result, we prove that, at (low) non-zero temperature, the algorithm constructs approximate solutions of the Thouless-Anderson-Palmer equations.
1 Introduction and main result
The paper studies near-optimal optimization of the Sherrington–Kirkpatrick Hamiltonian for Gaussian random matrices and proves that a message-passing algorithm achieves a (1−ε)-optimal binary solution in quadratic time under a structural assumption on the Parisi measure.
- Problem: The problem maximizes the quadratic form over binary vectors for a GOE random matrix, corresponding to the Sherrington–Kirkpatrick spin-glass model.The associated energy function is H_n(σ)=⟨σ,Aσ⟩/2.
- Background: Parisi’s variational principle, rigorously established by Talagrand and Panchenko, characterizes the asymptotic value of the optimization problem.The principle is formulated through a Parisi functional involving a nonlinear PDE and a variational minimization.
- Assumption: The main theorem assumes that, at sufficiently large inverse temperature, the Parisi measure has connected support [0,q*] with a strictly increasing distribution function.This is the continuous or full replica symmetry breaking assumption, which the paper treats as widely believed but not fully resolved.
- Main result: C(ε)n^2 floating-point operations suffice for an algorithm that outputs a binary vector achieving at least (1−ε) of the optimum with high probability.The result applies under Assumption 1 and establishes an average-case algorithmic guarantee for GOE instances.
- Extensions: The same message-passing iteration constructs approximate solutions of the TAP equations and extends, through universality, to symmetric matrices with independent subgaussian entries.The paper also derives a consequence for MAXCUT on dense Erdős–Rényi random graphs, with complexity at most C(ε)n^2.
- Algorithm: The algorithm uses a new incremental approximate message-passing construction whose analysis exploits the support of the overlap distribution.Its update structure is dictated by the message-passing viewpoint and is designed to match the value predicted by Parisi’s formula.
2 A general message passing algorithm
The paper develops incremental approximate message passing (IAMP), a structured AMP iteration whose large-system behavior is characterized through state evolution and an associated SDE.
- State evolution: For Lipschitz AMP functions, empirical coordinate observables converge to expectations under a Gaussian state-evolution process with recursively determined covariance.The covariance of the Gaussian process is determined recursively from the AMP functions and their correlations.
- Incremental AMP: The truncation [u_k]_M ensures Lipschitz continuity, enabling the AMP state-evolution analysis, while its removal is left as a possible generalization.The authors expect weaker regularity assumptions might permit replacing [u_k]_M by u_k and eliminating M.
- Continuous limit: In the small-step limit δ→0, the state evolution is described by an SDE for coupled processes X_t and Z_t driven by Brownian motion.The processes satisfy dX_t=v(X_t,t)dt+s(X_t,t)dB_t and dZ_t=g(X_t,t)dB_t.
- Guarantees: Theorem 3 characterizes the objective values and observables achievable by incremental AMP when δ is sufficiently small and M sufficiently large.The theorem supplies thresholds δ*(ε) and M*(ε,δ), with limits in probability given by non-random quantities.
3 Proof of the main theorem
The proof selects Parisi-informed SDE nonlinearities for incremental AMP, establishes their state evolution and hypercube control, and then rounds the resulting approximate vector to obtain the main optimization guarantee.
- Choosing the nonlinearities: The SDE coefficients are chosen to maximize the achieved energy while keeping the terminal process inside [−1, 1].The construction sets v(x, t) = β^2µ(t)∂xΦ(t, x), s(x, t) = β, and g(x, t) = β∂xxΦ(t, x).
- Choosing the nonlinearities: The selected coefficients satisfy the required regularity conditions, and the resulting process obeys P(Zt ∈[−1, 1]) = 1.The proof uses regularity properties of the Parisi PDE solution and derives the bound |Zt| ≤ 1 almost surely.
- Choosing the nonlinearities: Theorem 4 yields an incremental AMP vector with energy approaching the target value and vanishing squared distance from the hypercube as discretization and iteration parameters are chosen appropriately.The construction uses δ and M depending on ε and gives convergence in probability to non-random limits.
- Sequential rounding and putting everything together: The rounding procedure projects onto [−1, 1]^n and sequentially updates coordinates to increase the Hamiltonian, taking O(n^2) operations.Projection is coordinatewise, while the Hamiltonian is linear in each coordinate during the sequential updates.
- Putting everything together: At β = 10/ε, the constructed vector achieves energy at least E∗−ε/4 with high probability and has squared distance at most ε^2/10^6 from the hypercube.The proof combines the large-β energy estimates with Theorem 4 before applying the rounding procedure.
- Putting everything together: The resulting binary vector meets the main theorem’s near-optimality target with high probability.The proof reduces the desired statement to producing σ∗ with Hn(σ∗)/n ≥ E∗−ε/3.
4 Relation with the TAP equations
The same incremental AMP construction is analyzed at low non-zero temperature and shown to produce approximate solutions of the TAP equations under the paper’s assumption.
- Setup: The TAP analysis uses the same AMP iteration with the Parisi-derived coefficients and q∗ = q∗(β).The coefficients are v(x, t) = β^2µ(t)∂xΦ(t, x), s(x, t) = β, and g(x, t) = β∂xxΦ(t, x).
- Setup: The PDE solution on (q∗, 1] is represented using the Cole-Hopf transformation, with Φ(q∗, x) = log 2 cosh(x) + (1−q∗)/2.This representation is repeatedly used in the TAP-equation derivation.
- Derivation: The proof combines state-evolution identities and SDE relations to derive the limits required for the TAP equations.The argument repeatedly invokes Lemma 2.2, Lemma 2.4, and Eq. (3.5).
- Result: Theorem 5 states that, for suitable discretization and iteration parameters, the AMP output approximates solutions of the TAP equations with high probability.The approximation is obtained for any ε > 0 after choosing δ and M according to ε and δ.
5 Universality
Universality extends the near-optimal optimization result from Gaussian matrices to symmetric matrices with independent centered subgaussian entries, using polynomial approximations to the AMP dynamics.
- Assumptions: The universality argument considers symmetric matrices with zero diagonal and independent centered subgaussian off-diagonal entries.These conditions are summarized in Assumption 2, including variance scaling of order 1/n.
- Universality argument: For such matrices, AMP state evolution remains available when the update functions are fixed polynomials independent of n.Proposition 5.1 gives the corresponding pseudo-Lipschitz convergence statement.
- Generalized theorem: The generalized algorithm retains the main guarantee: complexity at most C(ε)n^2 and objective value at least (1−ε) times the optimum.Theorem 6 applies under Assumptions 1 and 2.
- Universality argument: The original nonlinear AMP dynamics are approximated by polynomial functions indexed by the discretization and approximation parameters.The proof constructs polynomial approximations to the coefficients and preserves the relevant state-evolution limits.
- MAXCUT consequence: The universality result yields a consequence for MAXCUT by applying the theorem to a suitably centered and normalized adjacency matrix.The graph construction balances the algorithm’s output before comparing its cut value with the optimum.
A Proof of Proposition 2.1
The appendix places the AMP iteration within the established AMP framework and identifies its asymptotic coordinate distribution through state evolution.
- Specialization: The paper’s Proposition 2.1 follows by choosing an n-independent time horizon and matching the specialized update functions to this framework.The recursion in the appendix is inherited from the cited general AMP theorem.
- AMP framework: The general AMP framework represents rowwise updates through functions Ft applied to the iterates and auxiliary data vectors.The matrix-valued update is defined row by row from Ft(xi, zi).
- Specialization: The iteration starts from x0 = 0 with data vectors z = (u0, y), and its update functions reproduce the paper’s recursion.The appendix matches the specialized iteration to the general AMP form.
- State evolution: Under independence of the initialization and data from A, the empirical distribution of AMP iterates is characterized asymptotically.The limiting description is given by a Gaussian process under Wasserstein-2 convergence assumptions.
B A simplified version of the algorithm
The simplified IAMP algorithm uses the Parisi minimizer and PDE solution to iteratively update vectors, then rounds the result to produce a near-optimal SK Hamiltonian configuration.
- Algorithm overview: Algorithm 1 takes A ∼ GOE(n) and parameters δ, β, then returns a near-optimal σ* ∈ {+1, −1}^n.Its inputs include the Parisi-functional minimizer, PDE solution, Edwards–Anderson parameter, and initialized Gaussian and auxiliary vectors.
- Algorithm overview: The procedure computes the minimizer µβ of the Parisi functional, solves the associated PDE, and sets q*(β) from the support of µβ.These quantities determine the temperature-dependent initialization and iteration range.
- Iterative updates: At each iteration, uk+1 is updated using A(gk−1 ⊙ uk) together with a memory correction involving bk, gk−2, and uk−1.The update is part of the incremental approximate message-passing dynamics.
- Computational scope: The pseudo-code omits the procedures for minimizing the Parisi functional and solving the PDE, which are treated as computationally feasible based on strong convexity, continuity, and prior numerical work.The cited numerical solutions are highly accurate but lack rigorous analysis.
- Rounding: The algorithm also requires a separate rounding procedure that clips intermediate values and ultimately assigns signs based on the resulting local fields.The displayed steps include entrywise clipping followed by sign-based rounding.