ML Anthology

Learning Set Functions with Limited Complementarity

Hanrui Zhang
AAAI 2019 pp. 5749-5756
doi:10.1609/AAAI.V33I01.33015749 /aaai/2019/zhang2019aaai-learning-a/

Abstract

We study PMAC-learning of real-valued set functions with limited complementarity. We prove, to our knowledge, the first nontrivial learnability result for set functions exhibiting complementarity, generalizing Balcan and Harvey’s result for submodular functions. We prove a nearly matching information theoretical lower bound on the number of samples required, complementing our learnability result. We conduct numerical simulations to show that our algorithm is likely to perform well in practice.

PDF AAAI Semantic Scholar

Cite

Text

Zhang. "Learning Set Functions with Limited Complementarity." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33015749

Markdown

[Zhang. "Learning Set Functions with Limited Complementarity." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/zhang2019aaai-learning-a/) doi:10.1609/AAAI.V33I01.33015749

BibTeX

@inproceedings{zhang2019aaai-learning-a,
  title     = {{Learning Set Functions with Limited Complementarity}},
  author    = {Zhang, Hanrui},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {5749-5756},
  doi       = {10.1609/AAAI.V33I01.33015749},
  url       = {https://mlanthology.org/aaai/2019/zhang2019aaai-learning-a/}
}