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 -additive approximate solution in expectation, where and 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 . Indeed, we show that any algorithm will suffer additive errors of in the worst case. Further, we consider an extended problem setting with \textit{multiple-point feedback} in which we can get the feedback of function values with each oracle call. Under the additional assumption that each noisy oracle is submodular and that , we provide an algorithm with an -additive error bound as well as a worst-case analysis including a lower bound of , 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