Poster
Submodular Function Minimization with Noisy Evaluation Oracle
Shinji Ito
East Exhibition Hall B, C #170
Keywords: [ Computational Complexity ] [ Algorithms; Optimization -> Convex Optimization; Optimization -> Stochastic Optimization; Theory ] [ Submodular Optimization ] [ Optimization ]
[
Abstract
]
Abstract:
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.
Live content is unavailable. Log in and register to view live content