• Login
    View Item 
    •   SMARTech Home
    • College of Computing (CoC)
    • College of Computing Technical Reports
    • View Item
    •   SMARTech Home
    • College of Computing (CoC)
    • College of Computing Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Improved Bounds for Learning Symmetric Juntas

    Thumbnail
    View/Open
    GIT-CC-03-55.pdf (171.1Kb)
    Date
    2003
    Author
    Lipton, Richard J.
    Markakis, Evangelos
    Metadata
    Show full item record
    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).
    URI
    http://hdl.handle.net/1853/6515
    Collections
    • College of Computing Technical Reports [506]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology