Risk-Sensitive Submodular Optimization

Authors

  • Bryan Wilder University of Southern California

DOI:

https://doi.org/10.1609/aaai.v32i1.12121

Keywords:

Submodularity, risk aversion, CVaR

Abstract

The conditional value at risk (CVaR) is a popular risk measure which enables risk-averse decision making under uncertainty. We consider maximizing the CVaR of a continuous submodular function, an extension of submodular set functions to a continuous domain. One example application is allocating a continuous amount of energy to each sensor in a network, with the goal of detecting intrusion or contamination. Previous work allows maximization of the CVaR of a linear or concave function. Continuous submodularity represents a natural set of nonconcave functions with diminishing returns, to which existing techniques do not apply. We give a (1 - 1/e)-approximation algorithm for maximizing the CVaR of a monotone continuous submodular function. This also yields an algorithm for submodular set functions which produces a distribution over feasible sets with guaranteed CVaR. Experimental results in two sensor placement domains confirm that our algorithm substantially outperforms competitive baselines.

Downloads

Published

2018-04-26

How to Cite

Wilder, B. (2018). Risk-Sensitive Submodular Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.12121

Issue

Section

AAAI Technical Track: Reasoning under Uncertainty