PaperlayerView exact revision on arXiv

Source-linked AI summary

The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures

David Gamarnik

arXiv:2109.14409v1cs.CCmath.PR

TL;DR

Random optimization problems often have well-characterized optima but lack known fast algorithms and standard worst-case hardness explanations. The paper introduces the Overlap Gap Property, a topological disconnectivity condition on near-optimal solutions, and uses it to rule out broad stable algorithm classes. Its discussion connects OGP with clustering and algorithmic phase transitions across random constraint and optimization problems.

  • Problem

    Random structures frequently have optimization optima that are known probabilistically, while fast algorithms and formal complexity-theoretic hardness results remain limited.

  • Method

    The paper develops the Overlap Gap Property, based on disconnectivity in pairwise distances among near-optimal solutions, as a geometric theory of algorithmic hardness.

  • Results

    The paper reports that OGP is verified or connected with clustering and phase-transition behavior across random models and can rigorously rule out large classes of algorithms, including stable algorithms.

  • Takeaways & Limitations

    Input-stable algorithms, including low-degree polynomial methods, are identified as important classes that OGP-based arguments can exclude for random optimization and constraint problems.

  • Takeaways & Limitations

    Existing hardness theories and methods do not cover all settings: weak clustering may leave exception sets, and frozen-variable theory does not apply to optimization problems.

Abstract

from arXiv · show

The problem of optimizing over random structures emerges in many areas of science and engineering, ranging from statistical physics to machine learning and artificial intelligence. For many such structures finding optimal solutions by means of fast algorithms is not known and often is believed not possible. At the same time the formal hardness of these problems in form of say complexity-theoretic $NP$-hardness is lacking. In this introductory article a new approach for algorithmic intractability in random structures is described, which is based on the topological disconnectivity property of the set of pair-wise distances of near optimal solutions, called the Overlap Gap Property. The article demonstrates how this property a) emerges in most models known to exhibit an apparent algorithmic hardness b) is consistent with the hardness/tractability phase transition for many models analyzed to the day, and importantly c) allows to mathematically rigorously rule out large classes of algorithms as potential contenders, in particular the algorithms exhibiting the input stability (insensitivity).

The Largest Clique of a Random Graph: the Most ”Embarrassing” Open Problem in Random Structures

Random maximum clique exemplifies the gap between a probabilistically characterized optimum and the difficulty of finding it efficiently. Related random optimization problems show the same persistent gap, while existing hardness results remain limited.

  • Random maximum clique: In G(N,1/2), the largest clique is typically near 2 log_2 N, but finding such a clique efficiently remains problematic.The graph has N nodes, with each edge present independently with probability 1/2.
  • Broader random optimization gaps: Random optimization problems commonly exhibit a gap between the optimum c* and the best known polynomial-time value cALG, with cALG < c*.Examples include random K-SAT, independent set, graph coloring, spin glasses, community detection, sparse estimation, graph matching, and number partitioning.
  • Number Partitioning: Number Partitioning minimizes the absolute difference between the total weights of two groups and is more tractable under independent Gaussian weights than in the worst case.The weights are independently drawn from N(0,1).
  • Number Partitioning: For Gaussian Number Partitioning, the optimum is typically N2^-N, while the Karmarkar–Karp algorithm achieves order 2^-N/2.The supplied passages report these as c* and cALG, respectively.
  • Number Partitioning: The resulting multiplicative gap is exponential, with cALG/c* = 2^(N-O(log^2 N)).Multidimensional extensions have been considered, but no improvement or algorithmic hardness result is known in the supplied passage.

In Search of the ”Right” Algorithmic Complexity Theory

Existing worst-case and geometric theories do not fully explain algorithmic gaps in random structures. The paper develops the Overlap Gap Property as a geometric barrier that supports rigorous exclusions of broad algorithm classes.

  • Limits of existing theories: Worst-case P versus NP theory does not explain why random graphs permit a polynomial-time factor 1/2 while general-graph approximation remains harder.The contrast concerns largest-clique approximation in all graphs versus random G(N,1/2).
  • Satisfiability transitions: Random K-SAT has a sharp satisfiability threshold αSAT, with satisfiability below and unsatisfiability above the threshold with overwhelming probability as N→∞.For K=3, αSAT is approximately 4.26.
  • Satisfiability transitions: For large K, αSAT is approximately 2^K log 2, whereas known algorithms stall at αALG = (2^K/K) log K.The passage reports clustering near αALG and exclusions of sequential local, low-degree polynomial, Survey Propagation, and WalkSAT algorithms.
  • Clustering: Weak clustering holds above αClust, near αALG, when almost all satisfying assignments partition into well-separated clusters with possible exception sets.Assignments are connected when one can be obtained from the other by flipping O(1) variables.
  • Clustering: Strong clustering removes the exception set, and its known onset bounds are of order 2^K rather than 2^K/K.Weak and strong clustering therefore appear on different K scales.
  • Algorithmic implications: Weak clustering alone may be irrelevant to algorithms because algorithm outputs need not be uniformly random and may lie in exception sets.Strong clustering instead places every solution in a cluster, enabling an input-stability argument via correlated instances.
  • Overlap Gap Property: The Overlap Gap Property provides a new approach that can rigorously rule out large algorithm classes, especially stable or low-input-sensitivity algorithms.Low-degree polynomial algorithms are identified as a broad and powerful stable class.

A generic formulation of the optimization problem

The paper formulates random optimization as minimizing a random objective over a high-dimensional metric solution space. The formulation accommodates discrete encodings for clique and Number Partitioning.

  • Generic formulation: The generic problem is min_σ L(σ, ΞN), where L is the objective and ΞN represents the instance randomness.The solution space is denoted ΣN.
  • Generic formulation: ΣN is a typically high-dimensional solution space equipped with a metric ρN measuring distances between solutions.The dimension is encoded by N, and the space may be discrete.
  • Problem encodings: For maximum clique, ΣN = {0,1}N encodes selected vertices, while invalid clique encodings can be assigned infinite objective value.The random graph G(N,1/2) is included in ΞN.
  • Problem encodings: For Number Partitioning, ΣN = {-1,1}N represents the two group assignments and ΞN is the distribution of independent random weights.The objective is the absolute imbalance between the groups.
  • Optimal value: The optimum is represented as c* = min_σ∈ΣN L(σ, ΞN).The supplied passage introduces this notation in the Number Partitioning formulation.

The OGP and its variants

The Overlap Gap Property (OGP) states that pairwise distances among near-optimal solutions avoid an intermediate interval, creating a topological disconnectivity. Its ensemble and multi-overlap variants extend this restriction across different instances and collections of solutions.

  • The OGP: The OGP requires every pair of µ-optimal solutions to be either within distance ν1 or at least distance ν2 apart.Thus, pairwise distances in the interval (ν1, ν2) are excluded.
  • The OGP: The OGP is a topological discontinuity in the set of distances among solutions that are close to optimality.The parameters µ, ν1, and ν2 are problem-dependent and may vary with problem size.
  • Geometric interpretation: An OGP landscape separates solutions into clusters whose diameters are smaller than the distances between clusters.A landscape without the OGP can contain a cluster whose diameter exceeds the distance between another pair of clusters.
  • Variants: The ensemble OGP applies the same near-optimal distance gap to solutions drawn from two possibly different instances.It requires every µ-optimal solution pair across the two instances to be either close or far.
  • Variants: The m-OGP requires that among m near-optimal solutions for m instances, at least one pair lies outside the intermediate distance interval.Equivalently, one cannot have all m(m −1)/2 pairwise distances inside (ν1, ν2).

OGP is an obstruction to stability

The OGP obstructs algorithms whose outputs change only slightly under small input perturbations. Interpolating between instances forces stable outputs to cross a forbidden distance gap, and the ensemble m-OGP yields an analogous contradiction for multiple instances.

  • Stability: A κ-stable algorithm changes its output by at most κ between consecutive instances in a parametrized sequence.The algorithm is treated as a mapping from each instance ξ to a solution A(ξ).
  • Single-instance interpolation: If the e-OGP holds, endpoint near-optimal solutions are separated, and κ < ν2 −ν1, no stable algorithm can connect the endpoint outputs.The output sequence must cross from the region within ν1 of the initial solution to the region at least ν2 away.
  • Single-instance interpolation: Stable algorithms cannot jump across the OGP gap because their incremental output distances are bounded by κ.The contradiction follows when an incremental distance would need to reach at least ν2 −ν1.
  • Ensemble interpolation: With the ensemble m-OGP, symmetric interpolations can make pairwise output distances evolve from zero to values above ν1.Stability then forces some distance into (ν1, ν2), contradicting the m-OGP.

OGP for concrete models

The OGP appears in Number Partitioning and maximum clique through forbidden intermediate overlaps among near-optimal solutions, with phase-transition behavior that tracks known algorithmic thresholds. For Number Partitioning, the OGP is established at exponential scale, while maximum clique exhibits a correlation-dependent transition in its overlap structure.

  • Number Partitioning: For every α ∈(1/2, 1), an exponentially small expectation rules out achieving value 2−αN with pairs whose scaled inner products lie in (ρ0, 1).The argument uses the expected number of pairs and shows that the relevant objective value is not achievable with overwhelming probability.
  • Number Partitioning: For Number Partitioning, pairs of near-optimal partitions cannot have scaled inner products in the interval (ρ0, 1) with overwhelming probability, yielding the OGP.The corresponding overlap-gap endpoints are ν1 = 0 and ν2 = N(1 −ρ0)/2.
  • Number Partitioning: For Number Partitioning, the m-OGP holds for every strictly positive α with a suitable constant m and extends to 2−O(√N log N) when m grows with N.The available proof techniques do not extend beyond that scale, where hardness or tractability remains unresolved.
  • Maximum clique: The maximum-clique OGP analysis is consistent with known algorithms, whose achievable clique size is roughly half the optimum, approximately log2 N versus 2 log2 N.The comparison concerns G(N, 1/2) and motivates analyzing cliques of size α log2 N for α ∈ (1, 2).
  • Maximum clique: For maximum clique, every two cliques of size α log2 N have intersection size either at least x1 log2 N or at most x2 log2 N.The roots x1(α) and x2(α) arise when α exceeds the stated threshold, and the overlap formulation gives the OGP.
  • Maximum clique: When ρ < ρ∗, maximum-clique overlaps occupy two regimes, whereas for ρ > ρ∗ the second regime disappears; for α = 1.72, ρ∗ ≈ 0.163.The transition is described as a new phase transition and is related to, but qualitatively different from, spin-glass chaos.

Stability of low-degree polynomials

The OGP rules out algorithm classes when their outputs remain stable under input perturbations, because stability forces pairs of outputs into overlap regions forbidden by the OGP. Low-degree polynomial algorithms are identified as the largest such class discussed.

  • Stability mechanism: Input stability makes an algorithm produce pairs of outputs whose overlaps fall into a region forbidden by the OGP.The failure argument therefore combines a stability proof for the algorithm class with an OGP proof for the optimization problem.
  • Low-degree polynomials: Low-degree polynomial algorithms construct each solution coordinate from a multivariate polynomial of the random instance, with a problem-dependent low maximum degree.This class includes algorithms connected to Sum-of-Squares and is described as among the strongest known classes of polynomial-time algorithms.

OGP and the problem of finding ground states of p-spin models

p-spin ground-state problems connect the OGP to both algorithmic tractability and barriers. Polynomial-time near-ground-state algorithms succeed where the OGP is absent, while low-degree polynomial methods fail in regimes exhibiting the OGP.

  • Model: In p-spin models, the objective minimizes the random multilinear form ⟨J, σ⟩ over a solution space such as the binary cube or a sphere.The randomness comes from independent standard normal entries of J; the p = 2 binary case is the Sherrington-Kirkpatrick model.
  • Algorithms and OGP: Polynomial-time algorithms find near ground states in regimes where detailed analysis indicates that the model does not exhibit the OGP.For models that do exhibit the OGP, related algorithms instead find the best solution in the non-OGP portion of the solution space.
  • Algorithms and OGP: Low-degree polynomial algorithms cannot solve the associated near-ground-state optimization problem in regimes with the OGP.The impossibility follows by verifying algorithmic stability and the OGP obstruction together.
  • Chaos: Any fixed positive fraction of flipped entries in a p-spin instance makes every near ground state of the perturbed instance nearly orthogonal to every near ground state of the original.This chaos behavior corresponds to an effectively zero ρ∗.

OGP, the clustering property, and the curious case of the perceptron model

The binary symmetric perceptron illustrates how clustering and the OGP can coexist in a random constraint problem, with OGP-based reasoning suggesting barriers for algorithmic classes.

  • The perceptron model: The binary symmetric perceptron seeks σ ∈ {±1}^N satisfying ∥Xσ∥∞ ≤ κ for a random Gaussian matrix X.The symmetric model contrasts with the asymmetric requirement Xσ ≥ κ, interpreted coordinate-wise.
  • Algorithmic versus statistical thresholds: Known algorithms for the perceptron are significantly weaker and scarcer than the rigorous threshold results.For asymmetric κ = 0, Kim and Rouche find solutions only when α < 0.005; related methods are expected to work only at sufficiently small densities in the symmetric case.
  • Clustering structure: At every positive density α > 0, the symmetric perceptron exhibits weak clustering, with each cluster consisting of a singleton.The text characterizes this subextensive cluster structure as a “needles in the haystack” phenomenon.
  • OGP and strong clustering: The pair-wise OGP implies strong clustering when near-optimal solutions occupy two separated distance ranges, with cluster diameters smaller than the gap scale.This implication follows because every pair is either close or separated by a non-vacuous larger-distance regime.
  • OGP and algorithmic hardness: The symmetric perceptron rigorously exhibits the OGP at an α strictly below the critical threshold αSAT(κ), implying strong clustering above that α.The OGP result is based on moment computation, and the paper conjectures that finding a solution is hard in this regime.
  • OGP and algorithmic hardness: OGP-based reasoning may rule out low-degree polynomial algorithms and related classes in the perceptron regime.The paper presents this as a likely extension of the stability-based barriers discussed elsewhere.

Discussion

The discussion presents OGP as both a theory predicting algorithmic hardness and a method for rigorously establishing barriers for stable algorithm classes across random structures.

  • OGP as a theory: The OGP approach predicts algorithmic hardness when the overlap gap emerges and has been verified at varying precision across many random-structure models.Table 1 summarizes models with apparent algorithmic hardness and whether OGP analysis matches current algorithmic knowledge.
  • OGP as a theory: No known model combines apparent algorithmic hardness with an absence of the OGP.The paper explicitly reports that it is unaware of such an example to date.
  • OGP as a method: The OGP provides rigorous barriers by exploiting algorithmic stability, or input insensitivity, which prevents stable algorithms from overcoming overlap gaps.The general barrier strategy is problem-independent, while the relevant stability notion and OGP analysis depend strongly on the problem.
  • OGP as a method: The mathematical analysis required by the OGP method ranges from nearly trivial to highly technical and often draws on spin-glass theory.The paper emphasizes that the exact stability condition and OGP are problem dependent.
Loading 2109.14409v1…