<p>A FOCS'15 paper by Lee, Sidford, and Wong [LSW15] can be leveraged to obtain such minimization guarantees -- cf. Section 5 (specifically, Corollary 5.4) in our recent paper ([BCELR16]).</p>

<blockquote>
  <p><strong>Corollary 5.4.</strong> 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$. </p>
  
  <p>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&gt;0$ is an absolute constant.</p>
  
  <p>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$.</p>
</blockquote>

<hr>

<p>[LSW15] <em>A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization</em>, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong. FOCS'15. <a href="http://arxiv.org/abs/1508.04874" rel="nofollow noreferrer">http://arxiv.org/abs/1508.04874</a></p>

<p>[BCELR16] <em>Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism.</em> Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron. arXiv, 2016. <a href="https://arxiv.org/abs/1607.03938" rel="nofollow noreferrer">https://arxiv.org/abs/1607.03938</a></p>

CC BY-SA 3.0
2016-11-06T19:37:04.533Z
2016-11-06T19:42:44.453Z
2016-11-06T19:42:44.453Z
Clement C.
<p>Let $f\colon 2^{[n]} \to \mathbb{R}$ be a submodular function (one can assume $f$ is bounded, if this helps). We are given <em>noisy oracle access</em> to $f$: on any $S$ and for any $\tau &gt; 0$, one can obtain an additive $\tau$-approximation of $f(S)$ (at cost $\operatorname{poly}(1/\tau)$).</p>

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

<p>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?</p>

CC BY-SA 3.0
2016-06-08T01:45:53.660Z
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. http://people.seas.harvard.edu/~yaron/publications.html
Chandra Chekuri
CC BY-SA 3.0
2016-06-13T22:10:52.287Z
@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.
<reference-request><optimization><submodularity><minimization>
Minimizing a submodular function given noisy oracle access
Clement C.
# Minimizing a submodular function given noisy oracle access

(Asked by: username_0 on 2016-06-07)

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?

**Tags:** reference-request, optimization, submodularity, minimization
> **Comments:**
> **username_1**: 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. http://people.seas.harvard.edu/~yaron/publications.html  
> **username_0**: @ChandraChekuri Thank you! After contacting him, it appears that very little is known (if anything) on the "non-adversarial noisy oracle" model for minimization.  

---

## 1 answers

### Answer by username_0 on 2016-11-06. Score: 6 | Accepted answer

A FOCS'15 paper by Lee, Sidford, and Wong [LSW15] can be leveraged to obtain such minimization guarantees -- cf. Section 5 (specifically, Corollary 5.4) in our recent paper ([BCELR16]).

> **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$.

---

[LSW15] *A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization*, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong. FOCS'15. <http://arxiv.org/abs/1508.04874>

[BCELR16] *Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism.* Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron. arXiv, 2016. <https://arxiv.org/abs/1607.03938>


---

