(Online) Subgradient Methods for Structured Prediction

Nathan Ratliff, J. Andrew (Drew) Bagnell, and Martin Zinkevich
Eleventh International Conference on Artificial Intelligence and Statistics (AIStats), March, 2007.


Download
  • Adobe portable document format (pdf) (375KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
Promising approaches to structured learning problems have recently been developed in the maximum margin framework. Unfortunately, algorithms that are computationally and memory efficient enough to solve large scale problems have lagged behind. We propose using simple subgradient-based techniques for optimizing a regularized risk formulation of these problems in both online and batch settings, and analyze the theoretical convergence, generalization, and robustness properties of the resulting techniques. These algorithms are are simple, memory efficient, fast to converge, and have small regret in the online setting. We also investigate a novel convex regression formulation of structured learning. Finally, we demonstrate the benefits of the subgradient approach on three structured prediction problems.

Keywords
structured prediction, optical character recognition, subgradient methods, convex optimization, value function approximation, imitation learning

Notes
Sponsor: DARPA
Grant ID: Learning for Locomotion
Associated Center(s) / Consortia: Center for the Foundations of Robotics
Associated Lab(s) / Group(s): Planning and Autonomy Lab
Associated Project(s): Learning Locomotion

Text Reference
Nathan Ratliff, J. Andrew (Drew) Bagnell, and Martin Zinkevich, "(Online) Subgradient Methods for Structured Prediction," Eleventh International Conference on Artificial Intelligence and Statistics (AIStats), March, 2007.

BibTeX Reference
@inproceedings{Ratliff_2007_5690,
   author = "Nathan Ratliff and J. Andrew (Drew) Bagnell and Martin Zinkevich",
   title = "(Online) Subgradient Methods for Structured Prediction",
   booktitle = "Eleventh International Conference on Artificial Intelligence and Statistics (AIStats)",
   month = "March",
   year = "2007",
}