CaltechAUTHORS
  A Caltech Library Service

Learning Policies for Contextual Submodular Prediction

Ross, Stephane and Zhou, Jiaji and Yue, Yisong and Dey, Debadeepta and Bagnell, J. Andrew (2013) Learning Policies for Contextual Submodular Prediction. Proceedings of Machine Learning Research, 28 (3). pp. 1364-1372. ISSN 1938-7228. http://resolver.caltech.edu/CaltechAUTHORS:20190327-085831526

[img] PDF - Published Version
See Usage Policy.

466Kb
[img] PDF - Supplemental Material
See Usage Policy.

227Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20190327-085831526

Abstract

Many prediction domains, such as ad placement, recommendation, trajectory prediction, and document summarization, require predicting a set or list of options. Such lists are often evaluated using submodular reward functions that measure both quality and diversity. We propose a simple, efficient, and provably near-optimal approach to optimizing such prediction problems based on noregret learning. Our method leverages a surprising result from online submodular optimization: a single no-regret online learner can compete with an optimal sequence of predictions. Compared to previous work, which either learn a sequence of classifiers or rely on stronger assumptions such as realizability, we ensure both data-efficiency as well as performance guarantees in the fully agnostic setting. Experiments validate the efficiency and applicability of the approach on a wide range of problems including manipulator trajectory optimization, news recommendation and document summarization.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://proceedings.mlr.press/v28/ross13b.htmlPublisherArticle
http://arxiv.org/abs/1305.2532arXivArticle
ORCID:
AuthorORCID
Yue, Yisong0000-0001-9127-1989
Additional Information:© 2013 by the author(s). This research was supported in part by NSF NRI Purposeful Prediction project and ONR MURIs Decentralized Reasoning in Reduced Information Spaces and Provably Stable Vision-Based Control. Yisong Yue was also supported in part by ONR (PECASE) N000141010672 and ONR Young Investigator Program N00014-08-1-0752. We gratefully thank Martial Hebert for valuable discussions and support.
Funders:
Funding AgencyGrant Number
NSFUNSPECIFIED
Office of Naval Research (ONR)N000141010672
Office of Naval Research (ONR)N00014-08-1-0752
Record Number:CaltechAUTHORS:20190327-085831526
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20190327-085831526
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94187
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:27 Mar 2019 22:54
Last Modified:27 Mar 2019 23:03

Repository Staff Only: item control page