Subsampling Mathematical Relaxations and Average-case Complexity

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

TL;DR

This paper investigates whether the solutions of mathematical relaxations (like linear and semidefinite programs) for complex problems remain accurate when applied to smaller, randomly selected parts of the original problem. The authors show that for certain relaxations and problem types, this "subsampling" works well, leading to efficient average-case algorithms, particularly for problems like Max Cut on random geometric graphs.

What Problem Does This Paper Address?

Many computationally hard problems, like finding the maximum cut in a graph (Max Cut), can be approximated using mathematical relaxations such as linear programs (LP) and semidefinite programs (SDP). These relaxations provide an upper bound on the optimal solution. However, solving these relaxations can still be computationally expensive, especially for large instances. The core question this paper tackles is: Can we get a good approximation of the relaxation's value by only considering a small, randomly chosen subset of the original problem's variables and constraints? This is known as "subsampling." The authors explore when this subsampling approach preserves the relaxation's value, especially for "average-case" scenarios (i.e., on naturally occurring, rather than worst-case, problem instances).

Methods

The paper introduces the concept of "subsampling theorems" for mathematical relaxations. They distinguish between "subsampling" (where the value is preserved up to a small multiplicative error, $\Pi(P') \in (1 \pm \varepsilon)\Pi(P)$) and "weak subsampling" (where the value is preserved up to an additive error, $\Pi(P') = 1 - \Theta(\gamma)$ when $\Pi(P) = 1 - \gamma$).

Key techniques include:

  • BasicLP and BasicSDP: These are foundational LP and SDP relaxations for Constraint Satisfaction Problems (CSPs). The authors prove that subsampling holds for these basic relaxations.
  • Lasserre Hierarchy and Sherali-Adams Hierarchy: These are more powerful, "tighter" versions of SDP and LP relaxations, respectively. They show that weak subsampling holds for tighter SDPs (Lasserre) on "unique games" type CSPs, but fails for tighter LP relaxations (Sherali-Adams) even for unique games.
  • Proxy CSPs: For stronger SDPs, they introduce the idea of a "proxy CSP" (H) that "dominates" the original CSP (G). They then show that if the original CSP admits subsampling, the proxy CSP also does, which helps in proving the weak subsampling result for unique games.
  • Random Geometric Graphs: A specific application is to Max Cut on random geometric graphs, which are considered a natural, non-trivial distribution of instances. They leverage their subsampling theorems to design an efficient algorithm for certifying the Max Cut value on these graphs.

Datasets

Not discussed in the paper. The paper focuses on theoretical results for general CSPs and specific types of graphs (random geometric graphs), rather than empirical evaluation on fixed datasets.

Key Insights and Ideas

  • Subsampling is not universally applicable: Unlike preserving the objective value of a CSP (which is generally robust to subsampling), the value of mathematical relaxations can be sensitive to subsampling. The success depends heavily on the specific relaxation and the type of CSP.
  • Basic relaxations are robust: The simpler LP and SDP relaxations (BasicLP, BasicSDP) are surprisingly robust to subsampling, meaning their values are well-preserved even on small random subsets of variables.
  • Tighter relaxations have mixed results: More powerful relaxations like the Lasserre SDP hierarchy exhibit weak subsampling for unique games, but the Sherali-Adams LP hierarchy fails even for unique games. This highlights a trade-off between relaxation power and subsampling robustness.
  • Average-case complexity advantage: The ability to subsample efficiently allows for average-case algorithms. For instance, they can efficiently certify the Max Cut value for random geometric graphs, which are otherwise hard to analyze.
  • Unique Games are key: The "unique games" property of a CSP plays a crucial role in enabling subsampling for stronger SDP relaxations.

Key Results

  • Positive Results:
    • Subsampling holds for BasicLP and BasicSDP relaxations for general CSPs.
  • Weak subsampling holds for tighter SDP relaxations (Lasserre hierarchy) for CSPs of the "unique games" type.
  • Negative Results:
    • Weak subsampling fails for tighter SDP relaxations on non-unique CSPs.
  • Subsampling (even weak) fails for tighter LP relaxations (Sherali-Adams hierarchy) on unique CSPs.
  • Algorithmic Application: A polynomial-time algorithm is presented to certify that random geometric graphs with a Max Cut value of $1 - \gamma$ have a cut value of at most $1 - \gamma/10$. This is a significant result for average-case complexity.

Limitations and Future Work

  • Strong Subsampling for Strong SDPs: The paper poses an open question: whether "strong" subsampling (approximating the original value with arbitrary accuracy) holds for strong SDPs on unique CSPs. They suspect the answer is "no" but lack a proof.
  • Generalizing to other CSP types: While they show results for unique games, extending these to other types of CSPs for tighter relaxations remains an area for future work.
  • Practical implications: The theoretical results suggest potential for faster algorithms on average, but practical implementation details and performance on real-world, non-random instances are not explored.

Summary updated

Abstract

We initiate a study of when the value of mathematical relaxations such as linear and semi-definite programs for constraint satisfaction problems (CSPs) is approximately preserved when restricting the instance to a sub-instance induced by a small random subsample of the variables. Let C be a family of CSPs such as 3SAT, Max-Cut, etc., and let П be a mathematical program that is a relaxation for C, in the sense that for every instance P ∊ C, П(P) is a number in [0, 1] upper bounding the maximum fraction of satisfiable constraints of P. Loosely speaking, we say that subsampling holds for C and П if for every sufficiently dense instance P ∊ C and every ε > 0, if we let P′ be the instance obtained by restricting P to a sufficiently large constant number of variables, then П(P′) ∊ (1 ± ε)П(P). We say that weak subsampling holds if the above guarantee is replaced with П(P′) = 1 − Θ(γ) whenever П(P) = 1 − γ, where Θ hides only absolute constants. We obtain both positive and negative results, showing that: 1. Subsampling holds for the BasicLP and BasicSDP programs. BasicSDP is a variant of the semi-definite program considered by Raghavendra (2008), who showed it gives an optimal approximation factor for every constraint-satisfaction problem under the unique games conjecture. BasicLP is the linear programming analog of BasicSDP. 2. For tighter versions of BasicSDP obtained by adding additional constraints from the Lasserre hierarchy, weak subsampling holds for CSPs of unique games type. 3. There are non-unique CSPs for which even weak subsampling fails for the above tighter semi-definite programs. Also there are unique CSPs for which (even weak) subsampling fails for the Sherali-Adams linear programming hierarchy. As a corollary of our weak subsampling for strong semi-definite programs, we obtain a polynomial-time algorithm to certify that random geometric graphs (of the type considered by Feige and Schechtman, 2002) of max-cut value 1 − γ have a cut value at most 1 − γ/10. More generally, our results give an approach to obtaining average-case algorithms for CSPs using semi-definite programming hierarchies.
BibTeX
@inproceedings{barak2011subsampling,
  author = {Boaz Barak and Moritz Hardt and Thomas Holenstein and David Steurer},
  title = {{Subsampling Mathematical Relaxations and Average-case Complexity}},
  booktitle = {SODA},
  year = {2011},
  doi = {10.1137/1.9781611973082.41},
}
Figure