Improved Bounds for Learning Symmetric Juntas

Abstract

We consider a fundamental problem in computational learning theory: learning in the presence of irrelevant information. In particular we are interested in learning an arbitrary boolean function of n variables which depends only on k of them. The problem has a lot of interesting applications in artificial intelligence, neural networks and machine learning theory. The problem was first proposed by Blum [1] and Blum and Langley [2]. Ever since, the first nontrivial algorithm was given by [4], which runs in time n[superscript 0.7k] poly(log 1/δ,2[superscript k],n), for general juntas and n[supserscript 2/3k]poly(log 1/δ,2[superscript k],n) for symmetric juntas. We give an algorithm for symmetric juntas which runs in time n[superscript k/3(1+o(1))]poly(log 1/δ,2[superscript k],n). We further show that when k is bigger than some large enough constant, the algorithm runs in time n[superscript 0:18k]poly(log 1/δ,2[superscript k], n). To our knowledge, this is the best known upper bound for learning symmetric juntas under the uniform distribution. The same algorithm has also been proposed by [5]. In [5] it was shown that the running time is bounded by n[superscript k/2(1+o(1))poly(log 1/δ,2[superscript k],n). It was also shown that under a certain number theoretic assumption, the running time is n[superscript k/3]poly(log 1/δ,2[superscript k],n).