# Metadata

- Title: No-regret algorithms for online k-submodular maximization
- Authors: Tasuku Soma
- Year: 2018
- Venue: arXiv preprint (`arXiv:1807.04965v1`, July 13, 2018)
- Primary group: k-submodular
- Secondary tags: online-learning, no-regret, monotone, Blackwell-approachability, OLO
- Problem: online maximization of k-submodular functions against oblivious or adaptive adversaries
- Main guarantee: gives polynomial-time algorithms with expected `1 / 2`-regret `O(n k sqrt(T))` for online non-monotone k-submodular maximization and expected `k / (2k - 1)`-regret `O(n k sqrt(T))` for the monotone case
- Key techniques: reduction to k-submodular selection games, Blackwell approachability theorem, valid halfspace oracles via LPs, and online linear optimization through online gradient descent
- Status: processed-deep
- Tags: #k-submodular #online-learning #no-regret #Blackwell #OLO #monotone #arXiv
- Inbox source: inbox/1807.04965v1.pdf