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.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Supplemental Material
See Usage Policy.


Use this Persistent URL to link to this item:


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
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.
Funding AgencyGrant Number
Office of Naval Research (ONR)N000141010672
Office of Naval Research (ONR)N00014-08-1-0752
Issue or Number:3
Record Number:CaltechAUTHORS:20190327-085831526
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94187
Deposited By: George Porter
Deposited On:27 Mar 2019 22:54
Last Modified:03 Oct 2019 21:01

Repository Staff Only: item control page