Learning Submodular Functions
Abstract
Submodular functions are discrete functions that model laws of diminishing returns and enjoy numerous algorithmic applications that have been used in many areas, including combinatorial optimization, machine learning, and economics. In this work we use a learning theoretic angle for studying submodular functions. We provide algorithms for learning submodular functions, as well as lower bounds on their learnability. In doing so, we uncover several novel structural results revealing both extremal properties as well as regularities of submodular functions, of interest to many areas.
Cite
Text
Balcan and Harvey. "Learning Submodular Functions." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2012. doi:10.1007/978-3-642-33486-3_61Markdown
[Balcan and Harvey. "Learning Submodular Functions." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2012.](https://mlanthology.org/ecmlpkdd/2012/balcan2012ecmlpkdd-learning/) doi:10.1007/978-3-642-33486-3_61BibTeX
@inproceedings{balcan2012ecmlpkdd-learning,
title = {{Learning Submodular Functions}},
author = {Balcan, Maria-Florina and Harvey, Nicholas J. A.},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2012},
pages = {846-849},
doi = {10.1007/978-3-642-33486-3_61},
url = {https://mlanthology.org/ecmlpkdd/2012/balcan2012ecmlpkdd-learning/}
}