Submodular Function Minimization with Dueling Oracle

We consider submodular function minimization using a dueling oracle, a noisy pairwise comparison oracle that provides relative feedback on function values between two queried sets. The oracle's responses are governed by a transfer function, which characterizes the relationship between differences in function values and the parameters of the response distribution. For a linear transfer function, we propose an algorithm that achieves an error rate of O(n where n is the size of the ground set and T denotes the number of oracle calls. We establish a lower bound: Under the constraint that differences between queried sets are bounded by a constant, any algorithm incurs an error of at least Ω(n Without such a constraint, the lower bound becomes Ω(n/ √ T ). These results show that our algorithm is optimal up to constant factors for constrained algorithms. For a sigmoid transfer function, we design an algorithm with an error rate of O(n 7 5 /T 2 5 ), and establish lower bounds analogous to the linear case. 1 INTRODUCTION Let f be a set function defined on subsets of a finite set [n] = 1, • • • , n. A function f is called submodular if it satisfies f (X) + f (Y ) ≥ f (X ∪ Y ) + f (X ∩ Y ) for all X, Y ⊆ [n].