Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant’s Algorithm

This paper investigates the sample complexity of Valiant's algorithm for learning an unknown (k, d)-CNF formula when given only i.i.d. uniform random solutions. Specifically, the authors seek to determine the full power of this classical algorithm under the structural condition of bounded degree (d) and clause width (k), without requiring additional restrictions like pairwise clause-intersection bounds.

Valiant's algorithm learns a CNF formula by starting with all possible candidate clauses and iteratively removing any clause violated by an observed sample. The authors analyze this process under the Lovász local lemma regime, parameterized by a real number t >= 1, where the clause width satisfies k >= (1 + 1/t) log d. The analysis involves three main steps:

1. Partitioning: Separating candidate clauses into 'frequent' clauses (which are eliminated by samples) and 'rare' clauses (which contribute to the total variation error).
2. Overlap Analysis: Grouping rare clauses based on their large overlaps with target clauses, which limits the number of classes to a polynomial in n.
3. Recursive Refinement: Using a tree-based refinement procedure to bound the aggregate violation probability of rare clauses within each class, ensuring the total variation distance remains below epsilon.

The authors also provide matching lower bounds for Valiant's algorithm and an improved information-theoretic lower bound for the general problem of learning CNF formulas.

This work provides a near-tight phase diagram for the sample complexity of Valiant's algorithm. It demonstrates that the exponent of n in the sample complexity increases by one whenever the parameter t crosses an integer, revealing a sequence of phase transitions. At t=1, the algorithm achieves near-linear sample complexity, which is information-theoretically optimal. This result clarifies the limits of Valiant's algorithm and provides a rigorous foundation for approximate learning in the local lemma regime.