We show that all non-negative submodular functions have high {\em
noise-stability}. As a consequence, we obtain a polynomial-time learning
algorithm for this class with respect to any product distribution on
$\{-1,1\}^n$ (for any constant accuracy parameter $\epsilon$). Our algorithm
also succeeds in the agnostic setting. Previous work on learning submodular
functions required either query access or strong assumptions about the types of
submodular functions to be learned (and did not hold in the agnostic setting).

The basic goal in combinatorial group testing is to identify a set of up to
$d$ defective items within a large population of size $n >> d$ using a pooling
strategy. Namely, the items can be grouped together in pools, and a single
measurement would reveal whether there are one or more defectives in the pool.
The threshold model is a generalization of this idea where a measurement
returns positive if the number of defectives in the pool passes a fixed
threshold $u$, negative if this number is below a fixed lower threshold $\ell
\leq u$, and may behave arbitrarily otherwise.