  We consider the maximization of a submodular objective function
$f:2^U\to\mathbb{R}_{\geq 0}$, where the objective $f$ is not accessed as a
value oracle but instead subject to noisy queries. We introduce a versatile
adaptive sampling procedure called which determines whether the marginal gain
of the function $f$ is approximately above or below an input threshold with
high probability in as few noisy samples as possible. Using the sampling
procedure as a subroutine, we propose sample efficient algorithms for monotone
submodular maximization with cardinality and matroid constraints, as well as
unconstrained non-monotone submodular maximization. The proposed algorithms
achieve approximation guarantees arbitrarily close to those of the standard
value oracle setting. We further provide an experimental evaluation on real
instances of submodular maximization and demonstrate the sample efficiency of
our proposed algorithm relative to alternative approaches.
