# Minimizing a submodular function given noisy oracle access

Let $f\colon 2^{[n]} \to \mathbb{R}$ be a submodular function (one can assume $f$ is bounded, if this helps). We are given noisy oracle access to $f$: on any $S$ and for any $\tau > 0$, one can obtain an additive $\tau$-approximation of $f(S)$ (at cost $\operatorname{poly}(1/\tau)$).

I am interested in what is known in minimizing (up to some arbitrary (additive) accuracy $\alpha>0$) $f$, given this sort of access:

If we had exact oracle access, then this could be done in polynomial time, exactly; what about robustness to approximate queries? Is there any algorithm (or, on the other side of the spectrum, lower bounds) for it?

• Yaron Singer has been looking at some of these problems. See his recent publications including a paper with Jan Vondrak in NIPS 2005. They don't seem to directly address minimization in that paper but I recall a talk where Yaron mentioned some results - you may want to contact him. people.seas.harvard.edu/~yaron/publications.html – Chandra Chekuri Jun 8 '16 at 1:45
• @ChandraChekuri Thank you! After contacting him, it appears that very little is known (if anything) on the "non-adversarial noisy oracle" model for minimization. – Clement C. Jun 13 '16 at 22:10

Corollary 5.4. Let $g\colon 2^{[m]} \to \mathbb{R}$ be a submodular function. There exists an algorithm that, when given access to an approximate oracle $\mathcal{O}^{\pm}_g$ for $g$, and for input parameters $\xi, \delta\in(0,1)$, returns with probability at least $9/10-2\delta$ a value $\nu \in \mathbb{R}$ such that $\nu\leq \min_{S \subseteq [m]} \{g(S)\} + \xi$.
The algorithm performs $m\log\left(\frac{mM}{\xi}\right)$ calls to $\mathcal{O}^{\pm}_g$ with parameters $\frac{\xi^2}{128m^5M^2}$ and $\frac{\delta}{Cm^2\log\left(\frac{mM}{\xi} \right)}$, where $M\stackrel{\rm def}{=} \max\left\{{2}\max_{S \subseteq [m]}\{\lvert{g(S)}\rvert\},\xi/2 \right\}$ and $C>0$ is an absolute constant.
The running time of the algorithm is $$O\!\left( m^2\cdot \Phi_g\left( \frac{\xi^2}{128m^{5}M^2}, \frac{\delta}{Cm^2\log\frac{mM}{\xi}} \right)\log{\frac{mM}{\xi}} + m^3 \log^{O(1)}\frac{mM}{\xi}\right) \;,$$ where $\Phi_g$ is the running time of $\mathcal{O}^{\pm}_g$.