High Probability Bounds for Stochastic Continuous Submodular Maximization
This work addresses the reliability of stochastic optimization algorithms for submodular functions, which is important for applications like resource allocation, but it is incremental as it builds on existing methods with improved analysis.
The paper tackles the problem of maximizing stochastic monotone continuous submodular functions, where existing algorithms only provide guarantees in expectation, leading to potentially poor solutions in practice. It provides the first high-probability analysis for several methods, showing that they converge to known approximation ratios but at slower rates than expected solutions, with empirical validation on non-concave quadratic programming and optimal budget allocation.
We consider maximization of stochastic monotone continuous submodular functions (CSF) with a diminishing return property. Existing algorithms only guarantee the performance \textit{in expectation}, and do not bound the probability of getting a bad solution. This implies that for a particular run of the algorithms, the solution may be much worse than the provided guarantee in expectation. In this paper, we first empirically verify that this is indeed the case. Then, we provide the first \textit{high-probability} analysis of the existing methods for stochastic CSF maximization, namely PGA, boosted PGA, SCG, and SCG++. Finally, we provide an improved high-probability bound for SCG, under slightly stronger assumptions, with a better convergence rate than that of the expected solution. Through extensive experiments on non-concave quadratic programming (NQP) and optimal budget allocation, we confirm the validity of our bounds and show that even in the worst-case, PGA converges to $OPT/2$, and boosted PGA, SCG, SCG++ converge to $(1 - 1/e)OPT$, but at a slower rate than that of the expected solution.