Improved Bounds for Learning Symmetric Juntas
Lipton, Richard J.
MetadataShow full item record
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  and Blum and Langley . Ever since, the first nontrivial algorithm was given by , 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 . In  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).