Large-scale optimistic adaptive submodularity

Victor Gabillon, Branislav Kveton, Zheng Wen, Brian Eriksson, S. Muthukrishnan

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    Maximization of submodular functions has wide applications in artificial intelligence and machine learning. In this paper, we propose a scalable learning algorithm for maximizing an adaptive submodular function. The key structural assumption in our solution is that the state of each item is distributed according to a generalized linear model, which is conditioned on the feature vector of the item. Our objective is to learn the parameters of this model. We analyze the performance of our algorithm, and show that its regret is polylogarithmic in time and quadratic in the number of features. Finally, we evaluate our solution on two problems, preference elicitation and face detection, and show that high-quality policies can be learned sample efficiently.

    Original languageEnglish (US)
    Title of host publicationProceedings of the National Conference on Artificial Intelligence
    PublisherAI Access Foundation
    Pages1816-1823
    Number of pages8
    ISBN (Electronic)9781577356790
    StatePublished - 2014
    Event28th AAAI Conference on Artificial Intelligence, AAAI 2014, 26th Innovative Applications of Artificial Intelligence Conference, IAAI 2014 and the 5th Symposium on Educational Advances in Artificial Intelligence, EAAI 2014 - Quebec City, Canada
    Duration: Jul 27 2014Jul 31 2014

    Publication series

    NameProceedings of the National Conference on Artificial Intelligence
    Volume3

    Conference

    Conference28th AAAI Conference on Artificial Intelligence, AAAI 2014, 26th Innovative Applications of Artificial Intelligence Conference, IAAI 2014 and the 5th Symposium on Educational Advances in Artificial Intelligence, EAAI 2014
    CountryCanada
    CityQuebec City
    Period7/27/147/31/14

    ASJC Scopus subject areas

    • Software
    • Artificial Intelligence

    Fingerprint Dive into the research topics of 'Large-scale optimistic adaptive submodularity'. Together they form a unique fingerprint.

  • Cite this

    Gabillon, V., Kveton, B., Wen, Z., Eriksson, B., & Muthukrishnan, S. (2014). Large-scale optimistic adaptive submodularity. In Proceedings of the National Conference on Artificial Intelligence (pp. 1816-1823). (Proceedings of the National Conference on Artificial Intelligence; Vol. 3). AI Access Foundation.