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

    Learning Submodular Functions

    Thumbnail
    View/Open
    GT-CS-09-14.pdf (191.5Kb)
    Date
    2009
    Author
    Balcan, Maria-Florina
    Harvey, Nicholas J. A.
    Metadata
    Show full item record
    Abstract
    This paper considers the problem of learning submodular functions. A problem instance consists of a distribution on {0,1}[superscript n] and a real-valued function on {0,1}[superscript n] that is non-negative, monotone and submodular. We are given poly(n) samples from this distribution, along with the values of the function at those sample points. The task is to approximate the value of the function to within a multiplicative factor at subsequent sample points drawn from the distribution, with sufficiently high probability. We prove several results for this problem. • There is an algorithm that, for any distribution, approximates any such function to within a factor of √n on a set of measure 1 − ϵ. • There is a distribution and a family of functions such that no algorithm can approximate those functions to within a factor of Õ(n[superscript 1/3]) on a set of measure 1/2 + ϵ. • If the function is a matroid rank function and the distribution is a product distribution then there is an algorithm that approximates it to within a factor O (log(1/ϵ)) on a set of measure 1 − ϵ. Our study involves a twist on the usual learning theory models and uncovers some interesting extremal properties of submodular functions.
    URI
    http://hdl.handle.net/1853/31222
    Collections
    • College of Computing Technical Reports [506]
    • School of Computer Science Technical Reports [105]

    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