• Login
    View Item 
    •   SMARTech Home
    • College of Computing (CoC)
    • Algorithms and Randomness Center (ARC)
    • ARC Talks and Events
    • View Item
    •   SMARTech Home
    • College of Computing (CoC)
    • Algorithms and Randomness Center (ARC)
    • ARC Talks and Events
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Variations of Submodularity and Diversity: from Robust Optimization to Markov Chains

    Thumbnail
    View/Open
    jegelka.mp4 (467.6Mb)
    jegelka_videostream.html (985bytes)
    Date
    2017-09-25
    Author
    Jegelka, Stefanie
    Metadata
    Show full item record
    Abstract
    The combinatorial concept of submodular set functions has proved to be a very useful discrete structure for optimization in machine learning and its applications. In this talk, I will show recent work on generalizations and specializations of this structure, and its connections to robustness and efficiency in machine learning. First, generalizations to integer and continuous functions lead to algorithms for solving a special class of nonconvex optimization problems. We show how, with further work, this generalization can be leveraged for introducing robustness to uncertainty in budget allocation and bipartite influence maximization problems. The resulting algorithm solves a nonconvex minimax game. Second, log-submodular discrete probability measures that induce diversity, repulsion and strong notions of negative dependence find applications from randomized matrix approximations and model sketching for large-scale learning to experiment design and interpretable unsupervised learning. But practical sampling methods have hitherto been lagging behind. I will outline how connections to real stable polynomials lead to fast-mixing Markov Chains for practical sampling and to solving an open problem posed by Avron and Boutsidis (2013). This talk is based on joint work with Matthew Staib, Chengtao Li and Suvrit Sra.
    URI
    http://hdl.handle.net/1853/58818
    Collections
    • ARC Talks and Events [84]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    • About
    • Terms of Use
    • Contact Us
    • Emergency Information
    • Legal & Privacy Information
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    • Login
    Georgia Tech

    © Georgia Institute of Technology

    • About
    • Terms of Use
    • Contact Us
    • Emergency Information
    • Legal & Privacy Information
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    • Login
    Georgia Tech

    © Georgia Institute of Technology