Submodular Functions Are Noise Stable

Details Submodular Functions Are Noise Stable Submodular Functions Are Noise Stable

2011-06-02

arxiv.org/abs/1106.0518v2

Computer Science

Learning

Scientific paper

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).

Affiliated with

Also associated with

No associations

Rating

Submodular Functions Are Noise Stable does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Submodular Functions Are Noise Stable, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Submodular Functions Are Noise Stable will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-222770