Skip to content
conftrace_
2009 NeurIPS NeurIPS 2009

Beyond Convexity: Online Submodular Minimization

Abstract

We consider an online decision problem over a discrete space in which the loss function is submodular. We give algorithms which are computationally efficient and are Hannan-consistent in both the full information and bandit settings.

🌉 Interdisciplinary Bridge - Artificial Intelligence and Mathematics & Optimization
📈 Trend Setter - Submodular Optimization
🧭 Keyword Pioneer - bandit feedback
🐣 Hot Topic Early Bird - bandit feedback

Authors

Elad Hazan, Satyen Kale

Topics

Machine Learning > Optimization & Theory > Optimization Mathematics & Optimization > Optimization > Online Algorithms Machine Learning > Learning Types > Online Learning Machine Learning > Optimization & Theory > Online Algorithms Mathematics & Optimization > Optimization > Discrete Optimization Mathematics & Optimization > Optimization > Submodular Optimization

Keywords

submodular optimization online learning discrete optimization online optimization submodular minimization bandit feedback hannan consistency bandit setting
Download PDF

More from NeurIPS 2009

All NeurIPS 2009 papers →
Semi-supervised Regression using Hessian energy with an application to semi-supervised dimensionality reduction
Localizing Bugs in Program Executions with Graphical Models
Human Rademacher Complexity
Learning from Multiple Partially Observed Views - an Application to Multilingual Text Categorization
Measuring model complexity with the prior predictive
Nonparametric Bayesian Texture Learning and Synthesis