ECCC-Report TR11-090https://eccc.weizmann.ac.il/report/2011/090Comments and Revisions published for TR11-090en-usTue, 16 Oct 2012 00:52:01 +0200
Revision 2
| Submodular Functions Are Noise Stable |
Mahdi Cheraghchi,
Adam Klivans,
Homin Lee,
Pravesh Kothari
https://eccc.weizmann.ac.il/report/2011/090#revision2We show that all non-negative submodular functions have high 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).
Additionally we give simple algorithms that efficiently release
differentially private answers to all Boolean conjunctions and to all
halfspaces with constant average error, subsuming and improving the
recent work due to Gupta, Hardt, Roth and Ullman (STOC~2011).Tue, 16 Oct 2012 00:52:01 +0200https://eccc.weizmann.ac.il/report/2011/090#revision2
Revision 1
| Submodular Functions Are Noise Stable |
Mahdi Cheraghchi,
Adam Klivans,
Homin Lee,
Pravesh Kothari
https://eccc.weizmann.ac.il/report/2011/090#revision1We show that all non-negative submodular functions have high 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).
Mon, 13 Jun 2011 16:32:14 +0300https://eccc.weizmann.ac.il/report/2011/090#revision1
Paper TR11-090
| Submodular Functions Are Noise Stable |
Mahdi Cheraghchi,
Adam Klivans,
Homin Lee,
Pravesh Kothari
https://eccc.weizmann.ac.il/report/2011/090We show that all non-negative submodular functions have high 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).
Fri, 10 Jun 2011 17:03:54 +0300https://eccc.weizmann.ac.il/report/2011/090