.png){kind=icon}
.png){kind=icon}
Return
Online risk-averse submodular maximization
.png){kind=icon}
OA
AI
DOI：10.1007/s10479-022-04835-9.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 Omega( root T ) space. We extend our online algorithm to portfolio optimization for monotone 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.
Keywords:
Conditional value at risk
Submodular function
Stochastic optimization
Online learning
Journal
IF:
4.5
Papers:
8.0K
Citations:
2.1W