Online Risk-Averse Submodular Maximization

Soma, Tasuku; Yoshida, Yuichi

doi:10.24963/ijcai.2021/411

Online Risk-Averse Submodular Maximization

Tasuku Soma, Yuichi Yoshida

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 2988-2994.

https://doi.org/10.24963/ijcai.2021/411

Keywords

Machine Learning: Online Learning
Heuristic Search and Game Playing: Combinatorial Search and Optimisation

Abstract

We present a polynomial-time online algorithm for maximizing the conditional value at risk (CVaR) of a monotone stochastic submodular function. Given T i.i.d. samples from an underlying distribution arriving online, our algorithm produces a sequence of solutions that converges to a (1−1/e)-approximate solution with a convergence rate of O(T −1/4 ) for monotone continuous DR-submodular functions. Compared with previous offline algorithms, which require Ω(T) space, our online algorithm only requires O( √ T) space. We extend our on- line algorithm to portfolio optimization for mono- tone submodular set functions under a matroid constraint. Experiments conducted on real-world datasets demonstrate that our algorithm can rapidly achieve CVaRs that are comparable to those obtained by existing offline algorithms.

Tasuku Soma, and Yuichi Yoshida. 2021. Online Risk-Averse Submodular Maximization. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 2988–2994. https://doi.org/10.24963/ijcai.2021/411

@inproceedings{ijcai2021p411,
  title     = {Online Risk-Averse Submodular Maximization},
  author    = {Soma, Tasuku and Yoshida, Yuichi},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {2988--2994},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/411},
  url       = {https://doi.org/10.24963/ijcai.2021/411},
}

TY  - CPAPER
TI  - Online Risk-Averse Submodular Maximization
AU  - Soma, Tasuku
AU  - Yoshida, Yuichi
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 2988
EP  - 2994
DO  - 10.24963/ijcai.2021/411
UR  - https://doi.org/10.24963/ijcai.2021/411
ER  -