Focused Stochastic Local Search and the Lovász Local Lemma

Dimitris Achlioptas, Fotis Iliopoulos

TL;DR

This paper provides a powerful, unified framework for analyzing focused stochastic local search—algorithms that find "perfect" objects by repeatedly identifying and fixing specific flaws. By generalizing the Lovász Local Lemma (LLL), the authors show how to design and prove the convergence of search algorithms for arbitrary probability measures and complex constraint dependencies, even when the underlying space doesn't naturally fit the standard LLL requirements.

What Problem Does This Paper Address?

In combinatorics and computer science, we often want to find an object (like a graph coloring or a satisfying assignment) that satisfies many constraints simultaneously. The Lovász Local Lemma (LLL) is a famous non-constructive tool that proves such objects exist if the constraints aren't too "tangled."

While the LLL was originally a purely existential proof, recent breakthroughs (like the Moser-Tardos algorithm) made it constructive, providing a recipe for local search: if a constraint is violated, "resample" the variables involved. However, these algorithms were largely restricted to "product measures" (where variables are independent) and specific "variable settings."

The challenge addressed here is: How do we analyze local search when the constraints are complex, the variables are dependent, or the state space doesn't have a simple variable-based structure?

Methods

The authors introduce a general framework based on flaws (violations) and actions (moves to fix them). Key technical contributions include:

  • Focused Search: The algorithm only moves to a new state to address a specific, currently present flaw.
  • Harmonic Walks: A novel way to choose transition probabilities. If you have a target probability measure $\mu$ over your states, a "harmonic" walk moves to a new state with a probability proportional to its weight under $\mu$.
  • Atomicity: They define "atomic" action graphs where each action (fixing a flaw) leads to a unique state. They prove that atomicity dramatically simplifies the analysis and allows the algorithm to start from an arbitrary initial state rather than a random sample.
  • Causality Digraphs: A tool to track how fixing one flaw might accidentally trigger another. The sparsity of this graph determines how quickly the algorithm converges.
  • Flaw Charges ($\gamma_i$): A new accounting method that quantifies the "cost" of a flaw, allowing the analysis to work even when the search doesn't perfectly "regenerate" the target measure $\mu$.

Datasets

As a theoretical computer science paper, it does not use traditional datasets. Instead, it evaluates its framework by applying it to hard combinatorial problems. Specifically, it focuses on Acyclic Edge Coloring (AEC) for graphs.

Key Insights and Ideas

  • Beyond Regeneration: Previous "algorithmic LLL" results required a property called "measure regeneration," which is often too restrictive. This paper shows you can trade off the "sophistication" of your measure against the "sparsity" of your causality graph.
  • Atomicity is Natural: While it sounds restrictive, "atomic" actions (where fixing a flaw has a deterministic-like quality in the state space) are actually common in many local search heuristics and simplify the math significantly.
  • Responsibility Shifting: By using a recursive version of the search algorithm, the authors show how to "shift responsibility" between flaws, leading to much tighter convergence bounds than simple Markovian search.

Key Results

  • Unified Framework: The paper provides a single theorem (Theorem 4) that subsumes almost all previous algorithmic LLL results and the authors' own prior work on the "flaws/actions" framework.
  • Acyclic Edge Coloring (AEC): The authors prove that any $d$-degenerate graph with maximum degree $\Delta$ has an acyclic edge coloring with $\lceil (2 + \epsilon)\Delta \rceil$ colors, where $\epsilon$ depends on the degeneracy.
  • Algorithmic Efficiency: They demonstrate that these colorings can be found in polynomial time, whereas standard LLL-based approaches often struggle to reach these lower color bounds or lack efficient algorithms.

Limitations and Future Work

  • Finding the Measure: The framework's success depends on choosing a "good" measure $\mu$ and action graph $D$. While the paper provides guidance (like using harmonic walks), there is no automated way to find the optimal $\mu$ for a brand-new problem.
  • Charge Calculation: For non-regenerative cases, calculating the "flaw charge" $\gamma_i$ can be mathematically intensive.
  • Future Directions: The authors suggest that this framework could be applied to other areas where the LLL has been used non-constructively, such as Latin transversals or complex scheduling problems, potentially turning many more existential proofs into efficient algorithms.

Summary updated

Abstract

We develop tools for analyzing focused stochastic local search algorithms. These are algorithms which search a state space probabilistically by repeatedly selecting a constraint that is violated in the current state and moving to a random nearby state which, hopefully, addresses the violation without introducing many new ones. A large class of such algorithms arise from the algorithmization of the Lov\'asz Local Lemma, a non-constructive tool for proving the existence of satisfying states. Here we give tools that provide a unified analysis of such algorithms and of many more, expressing them as instances of a general framework.
BibTeX
@inproceedings{achlioptas2016focused,
  author = {Dimitris Achlioptas and Fotis Iliopoulos},
  title = {{Focused Stochastic Local Search and the Lovász Local Lemma}},
  booktitle = {SODA},
  year = {2016},
  url = {https://openreview.net/forum?id=MW4ZipZ38La},
}

Loading related content...

Figure