Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2013 | Published + Supplemental Material
Journal Article Open

Learning Policies for Contextual Submodular Prediction


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.

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.

Attached Files

Supplemental Material - ross13b-supp.pdf

Published - ross13b.pdf


Files (711.5 kB)
Name Size Download all
233.4 kB Preview Download
478.1 kB Preview Download

Additional details

August 19, 2023
August 19, 2023