On the Evolution of Monotone Conjunctions: Drilling for Best Approximations

Abstract

We study the evolution of monotone conjunctions using local search; the fitness function that guides the search is correlation with Boolean loss. Building on the work of Diochnos and Turán [ 6 ], we generalize Valiant’s algorithm [ 19 ] for the evolvability of monotone conjunctions from the uniform distribution ${\mathcal U}_n$ to binomial distributions ${\mathcal B}_n$ . With a drilling technique, for a frontier q , we exploit a structure theorem for best q -approximations. We study the algorithm using hypotheses from their natural representation ( $\mathcal H = \mathcal C $ ), as well as when hypotheses contain at most q variables ( $\mathcal H = \mathcal C _{\le q}$ ). Our analysis reveals that ${\mathcal U}_n$ is a very special case in the analysis of binomial distributions with parameter p , where $p\in \mathcal {F} = \{2^{-1/k} \ | \ k\in \mathbb N ^*\}$ . On instances of dimension n , we study approximate learning for $0< p < 2^{-\frac{1}{n-1}}$ when $\mathcal H = \mathcal C $ and for $0< p < \root n-1 \of {2/3}$ when $\mathcal H = \mathcal C _{\le q}$ . Thus, in either case, approximate learning can be achieved for any $0< p < 1$ , for sufficiently large n .