Learning from Satisfying Assignments Using Risk Minimization

In this paper we consider the problem of Learning from Satisfying Assignments introduced by cite1 of finding a distribution that is a close approximation to the uniform distribution over the satisfying assignments of a low complexity Boolean function f. In a later work cite2 consider the same problem but with the knowledge of some continuous distribution D and the objective being to estimate Df, which is D restricted to the satisfying assignments of an unknown Boolean function f. We consider these problems from the point of view of parameter estimation techniques in statistical machine learning and prove similar results that are based on standard optimization algorithms for Risk Minimization.