TL;DR
This paper proves a tight lower bound for a specific type of mathematical optimization problem related to the Sherrington-Kirkpatrick (SK) model, a fundamental model in statistical physics. The authors demonstrate that a common computational technique, the degree 4 sum-of-squares relaxation, is surprisingly limited in its ability to find optimal solutions for this problem, achieving a bound that is only slightly better than a trivial one.
What Problem Does This Paper Address?
The paper tackles the problem of finding the maximum value of a quadratic form $\frac{1}{N} \mathbf{x}^\top \mathbf{W} \mathbf{x}$, where $\mathbf{W}$ is a random matrix from the Gaussian Orthogonal Ensemble (GOE) and $\mathbf{x}$ is a vector with entries restricted to $\pm 1$. This problem is a simplified version of finding the ground state energy of the SK model, a key model in understanding disordered systems like spin glasses. While the expected value of this quadratic form is well-understood, efficiently finding the exact maximum for a given random matrix $\mathbf{W}$ is computationally hard.
A related question is whether we can efficiently certify an upper bound on this maximum value. This is where "sum-of-squares" (SOS) relaxations come in. These are a hierarchy of convex optimization problems that approximate the original hard problem. The "spectral certificate" (simply finding the largest eigenvalue of $\mathbf{W}$) gives a trivial upper bound of approximately 2. The authors investigate how much better a more sophisticated SOS relaxation, specifically of degree 4, can do. They ask: can degree 4 SOS provide a significantly better upper bound than the spectral certificate?
Methods
The core of the paper is constructing a "pseudomoment matrix" that serves as a witness to the limitations of the degree 4 SOS relaxation. This construction is inspired by a previous result for degree 2 SOS relaxations (the Montanari-Sen witness). The authors adapt this witness by adding a small perturbation towards the identity matrix, creating a matrix that is "almost" a valid degree 4 pseudomoment matrix.
The construction involves several steps:
- Heuristic Pseudomoments: Based on insights from equiangular tight frames (ETFs) and conditional covariance of Gaussian matrices, they propose a formula for the degree 4 pseudomoment matrix.
- Correction for Linear Constraints: They adjust the proposed matrix to precisely satisfy certain linear constraints required for a pseudomoment matrix.
- Correction for Positive Semidefiniteness: A final adjustment is made to ensure the matrix is positive semidefinite, a crucial property for it to be a valid pseudomoment matrix. This step involves a careful analysis of the matrix's eigenvalues.
The proof of the main result relies on showing that this constructed matrix, with high probability, is a valid degree 4 pseudomoment matrix that achieves a value close to the spectral bound of 2. This implies that the degree 4 SOS relaxation cannot certify a better bound.
Datasets
Not discussed in the paper. The problem is theoretical and deals with random matrices drawn from a specific distribution (GOE).
Key Insights and Ideas
- Surprising Limitation of SOS: The most striking insight is that even a degree 4 SOS relaxation, which is a significant step up from the basic spectral certificate, offers only a marginal improvement in bounding the SK Hamiltonian. This suggests that for this particular problem, higher-degree SOS relaxations might not offer a substantial advantage over simpler methods.
- Connection to ETFs: The paper draws an interesting connection between the construction of pseudomoment matrices for the SK model and equiangular tight frames (ETFs). This suggests that insights from geometric and combinatorial structures can inform the analysis of random matrix problems.
- "Nudged" Witness: The strategy of taking the existing degree 2 witness and nudging it towards the identity matrix is a clever way to adapt previous results and construct a candidate for the degree 4 pseudomoment matrix.
- Pseudomoment Construction as a General Tool: The paper proposes a general framework for constructing pseudomoment matrices, which could be applicable to other problems beyond the SK model.
Key Results
- Tight Degree 4 Lower Bound: The paper proves that for the Sherrington-Kirkpatrick Hamiltonian under GOE random matrices, the degree 4 sum-of-squares relaxation cannot certify an upper bound better than approximately 2 (the spectral bound) with high probability. This means the spectral certificate is asymptotically optimal for degree 4 SOS.
- Conjecture for Higher Degrees: The authors conjecture that this limitation extends to any fixed degree SOS relaxation as $N \to \infty$.
- Explicit Construction: They provide an explicit construction of a degree 4 pseudomoment matrix that serves as evidence for their lower bound.
Limitations and Future Work
- Conjecture for Higher Degrees: While the paper provides strong evidence and a construction technique, the conjecture that this limitation holds for any fixed degree SOS relaxation remains unproven. The authors note that analyzing higher-degree pseudomoment matrices becomes significantly more challenging due to the complexity of symmetric tensor spaces.
- Specific Problem: The results are specific to the Sherrington-Kirkpatrick Hamiltonian with GOE matrices. Extending these findings to other random matrix ensembles or related optimization problems would be a natural next step.
- Practical Implications: The paper is primarily theoretical. While it sheds light on the limitations of SOS relaxations for this specific problem, its direct practical implications for solving SK instances efficiently are limited, as the focus is on the certification of bounds rather than finding the exact solution.
Summary updated