Timezone: »

 
Poster
Submodular Function Minimization with Noisy Evaluation Oracle
Shinji Ito

Wed Dec 11 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #170
in Optimization -- Submodular Optimization »
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(n^{3/2}/\sqrt{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/\sqrt{n})$. Indeed, we show that any algorithm will suffer additive errors of $\Omega(n/\sqrt{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 \leq k = O(1)$, we provide an algorithm with an $O(n/\sqrt{T})$-additive error bound as well as a worst-case analysis including a lower bound of $\Omega(n/\sqrt{T})$, which together imply that the algorithm achieves an optimal error bound up to a constant.
Keywords: Submodular Optimization · Computational Complexity · Optimization · Algorithms; Optimization -> Convex Optimization; Optimization -> Stochastic Optimization; Theory
[ Paper]  [ Poster] 

Author Information

Shinji Ito (NEC Corporation)

More from the Same Authors