Submodular Functions Are Noise Stable
| Autor: | Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin K. Lee |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2011 |
| Předmět: |
FOS: Computer and information sciences
Computer Science::Machine Learning cs.CC cs.LG TheoryofComputation_GENERAL 0102 computer and information sciences 02 engineering and technology Computational Complexity (cs.CC) 01 natural sciences Machine Learning (cs.LG) Computer Science - Learning Computer Science - Computational Complexity cs.GT 010201 computation theory & mathematics Computer Science - Computer Science and Game Theory 020204 information systems 0202 electrical engineering electronic engineering information engineering Computer Science and Game Theory (cs.GT) |
| Zdroj: | Scopus-Elsevier Annual ACM-SIAM Symposium on Discrete Algorithms |
| Popis: | 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). Copyright © SIAM. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|