---
title: "Online Risk-Averse Submodular Maximization"
authors:
  - "Tasuku Soma"
  - "Yuichi Yoshida"
doi: "10.24963/ijcai.2021/411"
url: "https://ijcai.org/proceedings/2021/411"
pdf: "https://ijcai.org/proceedings/2021/0411.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "2988-2994"
track: "Main Track"
keywords:
  - "Machine Learning: Online Learning"
  - "Heuristic Search and Game Playing: Combinatorial Search and Optimisation"
---

# Online Risk-Averse Submodular Maximization

Tasuku Soma, Yuichi Yoshida

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 2988-2994. DOI: [10.24963/ijcai.2021/411](https://doi.org/10.24963/ijcai.2021/411)

## 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.