Part of Advances in Neural Information Processing Systems 32 (NeurIPS 2019)
Shinji Ito
This paper considers submodular function minimization with \textit{noisy evaluation oracles} that return the function value of a submodular objective with zero-mean additive noise. For this problem, we provide an algorithm that returns an O(n3/2/√T)-additive approximate solution in expectation, where n and T stand for the size of the problem and the number of oracle calls, respectively. There is no room for reducing this error bound by a factor smaller than O(1/√n). Indeed, we show that any algorithm will suffer additive errors of Ω(n/√T) in the worst case. Further, we consider an extended problem setting with \textit{multiple-point feedback} in which we can get the feedback of k function values with each oracle call. Under the additional assumption that each noisy oracle is submodular and that 2≤k=O(1), we provide an algorithm with an O(n/√T)-additive error bound as well as a worst-case analysis including a lower bound of Ω(n/√T), which together imply that the algorithm achieves an optimal error bound up to a constant.