TY - GEN

T1 - Submodular functions are noise stable

AU - Cheraghchi, Mahdi

AU - Klivans, Adam

AU - Kothari, Pravesh

AU - Lee, Homin K.

PY - 2012

Y1 - 2012

N2 - We 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 e). 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 recent work due to Gupta, Hardt, Roth and Ullman (STOC 2011).

AB - We 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 e). 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 recent work due to Gupta, Hardt, Roth and Ullman (STOC 2011).

UR - http://www.scopus.com/inward/record.url?scp=84860183429&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860183429&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973099.126

DO - 10.1137/1.9781611973099.126

M3 - Conference contribution

AN - SCOPUS:84860183429

SN - 9781611972108

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1586

EP - 1592

BT - Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

PB - Association for Computing Machinery

T2 - 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

Y2 - 17 January 2012 through 19 January 2012

ER -