Minimizing Functions Close to Submodularity

We study the minimization of set functions that are uniformly close to submodular functions. Given value-oracle access to a function $\tilde{f}: 2^{[n]} \to \mathbb{R}$ satisfying $\lVert\tilde{f} - f\rVert_\infty\leq\Delta$ for some submodular function $f: 2^{[n]} \to [-M, M]$, we ask how accurately $\tilde{f}$ can be minimized using a polynomial number of queries. We give a randomized algorithm achieving expected suboptimality $O(\min\lbrace M,n\Delta,M^{1/3}(\sqrt{n}\Delta)^{2/3}\rbrace)$, where the last term is obtained via a new quantization argument based on Shapley vectors. We also show that, even when the underlying submodular function is modular, polynomially many value queries cannot in general achieve error better than $\widetilde{\Omega}(\min\lbrace M,\sqrt{n}\Delta\rbrace)$. Finally, for functions uniformly close to convex functions that are $M$-Lipschitz with respect to $\ell_2$, we adapt a known lower bound to the hypercube and obtain polynomial-query hardness $\widetilde{\Omega}(\min\lbrace M,n\Delta,M^{1/2}(\sqrt{n}\Delta)^{1/2}\rbrace)$, under a different geometric normalization.