Valiant algorithm reaches near-optimal sample use for learning CNF formulas
Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm
Machine LearningData Structures and Algorithms
Summary
Learning logical formulas from random examples is hard because you need enough data to be sure of the rules. The authors studied a classic method called Valiant's algorithm and showed exactly how many example solutions it needs to learn well. They confirmed that this algorithm uses nearly the smallest possible number of examples to learn certain formulas. This helps us understand the limits of how efficiently some complex patterns can be learned from data.
What this means in practice
- •For machine learning engineers: Determine minimal data requirements when training models that learn logical constraints from example solutions under specific conditions.
- •For automated reasoning developers: Optimize algorithms for inferring logical formulas from random satisfying assignments with provably near-optimal sample efficiency.
A theory result. No direct application yet.
Authors
Weiming Feng, Yixiao Yu, Yiyao Zhang
Abstract
We revisit Valiant's algorithm (Commun. ACM'84) for learning $n$-variable CNF formulas with clause size $k$ and variable degree $d$ from i.i.d. uniform random solutions in the local lemma regime. For fixed $t\geq1$, under $k\gtrsim(1+1/t)\log d$, Valiant's algorithm achieves total variation error $\varepsilon$ with $\widetilde{O}(n^{\lceil t \rceil}/\varepsilon)$ sample complexity. For $t>1$, we prove a matching lower bound for Valiant's algorithm. At $t=1$ (covering $0<t<1$), we show Valiant's algorithm has optimal sample complexity up to logarithmic factors by an information-theoretic lower bound $\widetildeΩ(n/\varepsilon)$.