Submodular functions are noise stable

Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin K. Lee

Research output: Chapter in Book/Report/Conference proceedingConference contribution

27 Scopus citations

Abstract

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

Original languageEnglish (US)
Title of host publicationProceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
PublisherAssociation for Computing Machinery
Pages1586-1592
Number of pages7
ISBN (Print)9781611972108
DOIs
StatePublished - 2012
Event23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan
Duration: Jan 17 2012Jan 19 2012

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
CountryJapan
CityKyoto
Period1/17/121/19/12

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Submodular functions are noise stable'. Together they form a unique fingerprint.

  • Cite this

    Cheraghchi, M., Klivans, A., Kothari, P., & Lee, H. K. (2012). Submodular functions are noise stable. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 (pp. 1586-1592). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973099.126