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?

  • 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 '16 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 '16 at 22:10

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


Your Answer

