CCSI Reading Group: Overlap Gap Property

This reading group will explore techniques that harness the Overlap Gap Property (OGP) to show algorithmic hardness in average-case problems.

Meeting Time: Tuesdays, 2-3pm PT

Location: Calvin Lab, Room 116; Zoom link available upon request

Organizers: Brice Huang, Eren Kızıldağ

Schedule of Talks

Speaker: Alex Wein
Title: Low-Degree Hardness of Maximum Independent Set
Abstract: (show/hide)

Low-degree hardness of random optimization problems, in particular the maximum independent set problem. The proof has two ingredients: (1) (Multi, Ensemble) Overlap Gap Property and (2) Stability of Low-Degree Polynomials.

Based on arXiv:2004.12063 and arXiv:2010.06563.

Speaker: Eren Kızıldağ
Title: Algorithmic Obstructions in the Number Partitioning Problem
Abstract: (show/hide)

We consider the algorithmic problem of finding a near-optimal solution for the number partitioning problem (NPP). This problem appears in many practical applications, including the design of randomized controlled trials, multiprocessor scheduling, and cryptography; and is also of theoretical significance. The NPP possesses the so-called statistical-to-computational gap: when its input has distribution N(0,I_n), the optimal value of NPP is \Theta(2^{-n}) w.h.p.; whereas the best polynomial-time algorithm achieves the objective value of only 2^{-\Theta(\log^2 n)}, w.h.p.

In this work, we initiate the study of the nature of this gap for the NPP. Inspired by insights from statistical physics, we study the landscape of the NPP and establish the presence of the Overlap Gap Property (OGP), an intricate geometric property which is known to be a rigorous evidence of an algorithmic hardness for large classes of algorithms. By leveraging the OGP, we establish that (a) any sufficiently stable algorithm, appropriately defined, fails to find a near-optimal solution with energy below 2^{-\omega(n \log^{-1/5} n)}; and (b) a very natural Markov Chain Monte Carlo dynamics fails for find near-optimal solutions.

OGP regards the overlap structure of m-tuples of solutions achieving a certain objective value. When m is constant, we prove the presence of OGP for the objective values of order 2^{-\Theta(n)}, and the absence of it in the regime 2^{-o(n)}. Interestingly, though, by considering overlaps with growing values of m we prove the presence of the OGP up to the level 2^{-\omega(\sqrt{n\log n})}. Our proof of the failure of stable algorithms at values 2^{-\omega(n \log^{-1/5} n)} employs methods from Ramsey Theory from the extremal combinatorics and is of independent interest.

Based on arXiv:2103.01369. Joint work with David Gamarnik.

Speaker: Brice Huang
Title: How to Design a Multi-OGP for Optimal Algorithmic Hardness
Abstract: (show/hide)

The Overlap Gap Property (OGP) is the condition that in a problem's solution space, no two solutions are a medium distance apart. In many random optimization problems with information-computation gaps, OGP has been shown to imply failure of stable algorithms at a threshold well below the existential limit, but still above the algorithmic limit.

A multi-OGP is an enhancement of OGP whose forbidden structure involves several solutions. In several random optimization problems, recent work has shown that an appropriately designed multi-OGP implies failure of stable algorithms at or just beyond the algorithmic limit.

The goal of this talk is to show how to design such a multi-OGP, and to demonstrate the energy computations involved in choosing the forbidden structure. As an illustrative example, we will discuss the multi-OGP for maximum independent set constructed by Alex Wein, which implies optimal hardness against low degree polynomials.

Based on arXiv:2010.06563, "Optimal Low-Degree Hardness of Maximum Independent Set" by Alex Wein.

Speaker: Eren Kızıldağ
Title: Leveraging OGP to Establish Algorithmic Hardness: Ramsey Argument and Free Energy Wells
Abstract: (show/hide)

The Overlap Gap Property (OGP) is an intricate geometric/topological property asserting (in the context of random combinatorial optimization problems) that two nearly optimal solutions are either too close or too far apart (with respect to the natural notion of distance); and is known to be a rigorous barrier for certain classes of algorithms. Establishing algorithmic hardness via the OGP consists essentially of two main steps: (a) establishing the OGP (which, often times, is done by the so-called first moment method); and (b) leveraging the OGP to rule out specific classes of algorithms (often by a contradiction argument).

In this talk, we focus on the technical details of the latter step while using the random number partitioning problem as a running example. Specifically, we will show (a) how to leverage the multi-OGP (m-OGP) to rule out stable algorithms, appropriately defined; and (b) how to leverage the ``vanilla” 2-OGP to establish the existence of Free Energy Wells (FEW) which implies slow mixing for a very natural Monte Carlo Markov Chain dynamics at sufficiently low temperatures. Interestingly, our proof of the failure of stable algorithms via m-OGP employs methods from Ramsey Theory from the extremal combinatorics and is of independent interest.

Speaker: Ilias Zadik
Title: The Overlap Gap Property for Estimation
Abstract: (show/hide)

In this talk we will discuss a line of work that tries to define and analyze the Overlap Gap Property (OGP) in the context of estimation of a hidden structure. We will discuss some of the results and intuition (as well as some cool open problems) which arise from the study of OGP in the context of the conjectured “hard” regimes of sparse regression, planted clique and sparse PCA.

Speaker: Subhabrata Sen
Title: OGP in planted submatrix recovery: the proportional sparsity regime
Abstract: (show/hide)

Abstract: We study support recovery for a hidden k \times k principal submatrix with elevated mean in a symmetric Gaussian N \times N matrix. Throughout we assume that we are in a proportional sparsity regime, i.e. $k = N \rho$, $\rho \in (0,1)$. We will characterize the information theoretic threshold for non-trivial support recovery, and provide some evidence for a hard phase via OGP. As a consequence, we will rule out a natural family of MCMC algorithms.

I'll mainly focus on the use of variational methods (based on the Parisi formula) to establish OGP. I'll also connect our results with subsequent work, and highlight some open questions.

Based on joint work with David Gamarnik (MIT) and Aukosh Jagannath (UWaterloo).

Speaker: Mark Sellke
Title: Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
Abstract: (show/hide)

We study the problem of algorithmically optimizing the Hamiltonian H_N of a spherical or Ising mixed p-spin glass. The maximum asymptotic value OPT of H_N/N is characterized by a variational principle known as the Parisi formula, proved first by Talagrand and in more generality by Panchenko. Recently developed approximate message passing algorithms efficiently optimize H_N/N up to a value ALG given by an extended Parisi formula, which minimizes over a larger space of functional order parameters. These two objectives are equal for spin glasses exhibiting a no overlap gap property. However, ALG < OPT can also occur, and no efficient algorithm producing an objective value exceeding ALG is known.

We prove that for mixed even p-spin models, no algorithm satisfying an overlap concentration property can produce an objective larger than ALG with non-negligible probability. This property holds for all algorithms with suitably Lipschitz dependence on the disorder coefficients of H_N. It encompasses natural formulations of gradient descent, approximate message passing, and Langevin dynamics run for bounded time and in particular includes the algorithms achieving ALG mentioned above. To prove this result, we substantially generalize the overlap gap property framework introduced by Gamarnik and Sudan to arbitrary ultrametric forbidden structures of solutions.

Speaker: David Gamarnik
Title: Quantum Approximate Optimization Algorithm (QAOA) Needs to See the Whole Graph
Abstract: (show/hide)

QAOA is a quantum algorithm which holds a lot of promise since it can be implemented, and in fact was implemented in current quantum computers, with low overhead. It is designed to solve combinatorial optimization problems with local cost structure. We will discuss the limits of QAOA when run on random graphs. We will show that the algorithm cannot solve the largest independent set problem in a sparse random graph up to a multiplicative constant, if the number of layers of the QAOA (which I will define) is at most logarithmic in the problem size with a small multiplier. Namely the algorithm needs to "see the entire graph" so to speak.

The proof is based on the presence of the Overlap Gap Property for the independent set problem coupled with the long range independence exhibited by the QAOA output at logarithmic depth.

Joint work with Edward Farhi and Sam Gutmann.

Relevant Papers

As a primer to OGP, we recommend arXiv:1304.1831 and the parts of arXiv:2004.12063 on maximum independent set.

Classic and Ensemble OGP
  • David Gamarnik, Madhu Sudan. Limits of local algorithms over sparse random graphs. arXiv:1304.1831
  • David Gamarnik, Quan Li. Finding a Large Submatrix of a Gaussian Random Matrix. arXiv:1602.08529
  • Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, Mustazee Rahman. Suboptimality of local algorithms for a class of max-cut problems. arXiv:1707.05386
  • David Gamarnik, Aukosh Jagannath. The Overlap Gap Property and Approximate Message Passing Algorithms for p-spin models. arXiv:1911.06943
  • David Gamarnik, Aukosh Jagannath, Alex Wein. Low-Degree Hardness of Random Optimization Problems. arXiv:2004.12063
  • David Gamarnik, Aukosh Jagannath, Alex Wein. Circuit Lower Bounds for the p-Spin Optimization Problem. arXiv:2109.01342
  • Mustazee Rahman, Bálint Virág. Local algorithms for independent sets are half-optimal. arXiv:1402.0485
  • David Gamarnik, Madhu Sudan. Performance of Sequential Local Algorithms for the Random NAE-K-SAT Problem. (link)
  • Alex Wein. Optimal Low-Degree Hardness of Maximum Independent Set. arXiv:2010.06563
  • David Gamarnik, Eren Kızıldağ. Algorithmic Obstructions in the Random Number Partitioning Problem. arXiv:2103.01369
  • Guy Bresler, Brice Huang. The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials. arXiv:2106.02129
  • Brice Huang, Mark Sellke. Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses. arXiv:2110.07847
OGP in Planted Problems and Regression
  • David Gamarnik, Ilias Zadik. High-Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition. arXiv:1701.04455
  • David Gamarnik, Ilias Zadik. The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property. arXiv:1904.07174
  • David Gamarnik, Aukosh Jagannath, Subhabrata Sen. The Overlap Gap Property in Principal Submatrix Recovery. arXiv:1908.09959
  • Gérard Ben Arous, Alex Wein, Ilias Zadik. Free Energy Wells and Overlap Gap Property in Sparse PCA. arXiv:2006.10689
OGP and Quantum Computation
  • Edward Farhi, David Gamarnik, Sam Gutmann. The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case. arXiv:2004.09002
  • Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, Jonathan Shi. Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond. arXiv:2108.06049
  • David Gamarnik. The Overlap Gap Property: a Topological Barrier to Optimizing over Random Structures. (link)