5
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ 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 $\endgroup$
    – Chandra Chekuri
    Jun 8, 2016 at 1:45
  • $\begingroup$ @ChandraChekuri Thank you! After contacting him, it appears that very little is known (if anything) on the "non-adversarial noisy oracle" model for minimization. $\endgroup$
    – Clement C.
    Jun 13, 2016 at 22:10

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.