Submodular Functions Are Noise Stable. Cheraghchi, M., Klivans, A., Kothari, P., & Lee, H. K. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1586–1592, 2012. Link Paper abstract bibtex 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 $ε$). 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).
@INPROCEEDINGS{ref:CKKL12,
author = {Cheraghchi, Mahdi and Klivans, Adam and Kothari,
Pravesh and Lee, Homin K.},
title = {Submodular Functions Are Noise Stable},
year = 2012,
booktitle = {Proceedings of the 23rd {Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA)}},
pages = {1586--1592},
numpages = 7,
url_Link = {https://dl.acm.org/doi/10.5555/2095116.2095242},
url_Paper = {https://eccc.weizmann.ac.il//report/2011/090/},
abstract = {We show that all non-negative submodular functions
have high \textit{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 recent work
due to Gupta, Hardt, Roth and Ullman (STOC 2011).}
}
Downloads: 0
{"_id":"a6wz74E9D9bvvwSye","bibbaseid":"cheraghchi-klivans-kothari-lee-submodularfunctionsarenoisestable-2012","authorIDs":["2n8MNophuzbeevTa8","3NEcSaujokmJYSDaa","3tFWxWs2qWeYAZx9a","4QNcMTdRiWr2gs8Sk","5KoQWR3vSjnsoZNz5","5i4QHRc5LGio8Mf5u","62bYDgAFwCxaQ4Q9T","685mTysGDdQJKGxEE","6sX76eTffL7p76peN","8NLx3B3FAvaK54hSK","9NZpjMJLG7dNWroGm","9aD4MPX9ELhsyJmaR","9aFgrqcc4j28kZn8n","A9wAgP7TPK9tw28qY","BJ6h7zrsT3L89RKSg","BWL9E9QxvrST7y7ym","Cht4qGZ9eYAvPygNC","D3NMRJpac7Z2oFz7x","EiL6Xv4GTWGB97B8H","F3Y934eNyTeEJsg6E","FDEj5Zwdm28pFcAnB","FJdyLy2TL3v973ge8","GxccwstJJuJ4rg7Dq","H4D7r27RcPALT5DCs","HP7szFXWBWFXXZhdA","HRX7xsd7ZkTNvr67D","Hj3KN5PTNMST8hD3b","JEvEPvDBYNNXgGBnp","JYpde2ppjXLva6cre","KFgC2dZG7jXYAgZ3T","NRg9mmaSB55QqzNnH","NWCEkq6XqRBCiGmMe","NpGaG45evixRFDMiF","NyDiXeBc7cuxdWrqh","P6pva6vpPZCz6ndh9","Py2jfYGNZKNt7nxL6","Q6E9aDkYPcbhngLMx","QYrXKExv3BPABZGyA","QupQWsidagmv2nu8Z","SGZ2YignSm7njeTxy","SSuyWxzudqBDgAosw","THz3CmRmH3zZ9Xfud","TTEBJzPHwrY4d2Qfi","Wzr7kB4bxMDqceidA","YedfCw6zcDLoWAWFL","YtTEuSL9GJ8pkKcZw","Z3w2d32WjDczZMeGo","aduB2YE7dcNtbHnAN","c8gPvTXFPd9NazgEw","d6HAadRZAtz97Y2so","dTBDNYCcYKNNdhqaR","ezDt3Lb3Q6Sbo2rfX","fXtxgjbjZswBmF45i","ftBpmnKRHoB2muB8u","gKxHau44e8gnmxs6v","hM29eSWZbASnmDdFf","hw7Q4GHDAHkLTAyeB","i6Ns5rSW8R3ifxeHg","jJcoL4QWRkJQ59LfW","kKvRZ55rH7sfbubS2","kdfqsAMqCFDhpuW3S","koPTGcsAkwhGbkAYe","manxWg6Q3ZC5vW4JE","pwN2yYKo5DdSDaZGs","qpSgMrJ8WQNupjbXX","sD5Wq95oeSzqGF9kn","uSGLWGoXjyDyozeEy","wCcpScxkvg5RkcmWm","xKz7kx4eXbnkHeNXP","xeiij9YsbXBbMjciP","yGxZz3yuu6krMRxgK","yjJrpKY5QmDe8SXvm","zaR6PwJ7aC9xWBpiy"],"author_short":["Cheraghchi, M.","Klivans, A.","Kothari, P.","Lee, H. K."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"propositions":[],"lastnames":["Cheraghchi"],"firstnames":["Mahdi"],"suffixes":[]},{"propositions":[],"lastnames":["Klivans"],"firstnames":["Adam"],"suffixes":[]},{"propositions":[],"lastnames":["Kothari"],"firstnames":["Pravesh"],"suffixes":[]},{"propositions":[],"lastnames":["Lee"],"firstnames":["Homin","K."],"suffixes":[]}],"title":"Submodular Functions Are Noise Stable","year":"2012","booktitle":"Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","pages":"1586–1592","numpages":"7","url_link":"https://dl.acm.org/doi/10.5555/2095116.2095242","url_paper":"https://eccc.weizmann.ac.il//report/2011/090/","abstract":"We show that all non-negative submodular functions have high <i>noise-stability</i>. 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 $ε$). 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).","bibtex":"@INPROCEEDINGS{ref:CKKL12,\n author =\t {Cheraghchi, Mahdi and Klivans, Adam and Kothari,\n Pravesh and Lee, Homin K.},\n title =\t {Submodular Functions Are Noise Stable},\n year =\t 2012,\n booktitle =\t {Proceedings of the 23rd {Annual ACM-SIAM Symposium\n on Discrete Algorithms (SODA)}},\n pages =\t {1586--1592},\n numpages =\t 7,\n url_Link =\t {https://dl.acm.org/doi/10.5555/2095116.2095242},\n url_Paper =\t {https://eccc.weizmann.ac.il//report/2011/090/},\n abstract =\t {We show that all non-negative submodular functions\n have high \\textit{noise-stability}. As a\n consequence, we obtain a polynomial-time learning\n algorithm for this class with respect to any product\n distribution on $\\{-1,1\\}^n$ (for any constant\n accuracy parameter $\\epsilon$). Our algorithm also\n succeeds in the agnostic setting. Previous work on\n learning submodular functions required either query\n access or strong assumptions about the types of\n submodular functions to be learned (and did not hold\n in the agnostic setting). Additionally we give\n simple algorithms that efficiently release\n differentially private answers to all Boolean\n conjunctions and to all halfspaces with constant\n average error, subsuming and improving recent work\n due to Gupta, Hardt, Roth and Ullman (STOC 2011).}\n}\n\n","author_short":["Cheraghchi, M.","Klivans, A.","Kothari, P.","Lee, H. K."],"key":"ref:CKKL12","id":"ref:CKKL12","bibbaseid":"cheraghchi-klivans-kothari-lee-submodularfunctionsarenoisestable-2012","role":"author","urls":{" link":"https://dl.acm.org/doi/10.5555/2095116.2095242"," paper":"https://eccc.weizmann.ac.il//report/2011/090/"},"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/"}}},"bibtype":"inproceedings","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-29T00:16:54.308Z","downloads":1,"keywords":[],"search_terms":["submodular","functions","noise","stable","cheraghchi","klivans","kothari","lee"],"title":"Submodular Functions Are Noise Stable","year":2012,"dataSources":["YZqdBBx6FeYmvQE6D"]}