Skip to yearly menu bar Skip to main content


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: 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 2k=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