No-Regret Algorithms for Online $k$-Submodular Maximization
Abstract
We present a polynomial time algorithm for online maximization of $k$-submodular maximization. For online (nonmonotone) $k$-submodular maximization, our algorithm achieves a tight approximate factor in the approximate regret. For online monotone $k$-submodular maximization, our approximate-regret matches to the best-known approximation ratio, which is tight asymptotically as $k$ tends to infinity. Our approach is based on the Blackwell approachability theorem and online linear optimization.
Cite
Text
Soma. "No-Regret Algorithms for Online $k$-Submodular Maximization." Artificial Intelligence and Statistics, 2019.Markdown
[Soma. "No-Regret Algorithms for Online $k$-Submodular Maximization." Artificial Intelligence and Statistics, 2019.](https://mlanthology.org/aistats/2019/soma2019aistats-noregret/)BibTeX
@inproceedings{soma2019aistats-noregret,
title = {{No-Regret Algorithms for Online $k$-Submodular Maximization}},
author = {Soma, Tasuku},
booktitle = {Artificial Intelligence and Statistics},
year = {2019},
pages = {1205-1214},
volume = {89},
url = {https://mlanthology.org/aistats/2019/soma2019aistats-noregret/}
}