Testing (subclasses of) halfspaces
We address the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x) = sgn(w . x − θ). We consider halfspaces over the continuous domain R n (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube { ...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72033 https://orcid.org/0000-0002-4353-7639 |
| _version_ | 1826193325340753920 |
|---|---|
| author | Matulef, Kevin M. O'Donnell, Ryan Rubinfeld, Ronitt Servedio, Rocco |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Matulef, Kevin M. O'Donnell, Ryan Rubinfeld, Ronitt Servedio, Rocco |
| author_sort | Matulef, Kevin M. |
| collection | MIT |
| description | We address the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x) = sgn(w . x − θ). We consider halfspaces over the continuous domain R n (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube { − 1,1} n (endowed with the uniform distribution). In both cases we give an algorithm that distinguishes halfspaces from functions that are ε-far from any halfspace using only poly(1) queries, independent of the dimension n.
In contrast to the case of general halfspaces, we show that testing natural subclasses of halfspaces can be markedly harder; for the class of { − 1,1}-weight halfspaces, we show that a tester must make at least Ω(logn) queries. We complement this lower bound with an upper bound showing that O(√n) queries suffice. |
| first_indexed | 2024-09-23T09:37:11Z |
| format | Article |
| id | mit-1721.1/72033 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:37:11Z |
| publishDate | 2012 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/720332022-09-30T15:43:22Z Testing (subclasses of) halfspaces Matulef, Kevin M. O'Donnell, Ryan Rubinfeld, Ronitt Servedio, Rocco Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Rubinfeld, Ronitt Rubinfeld, Ronitt We address the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x) = sgn(w . x − θ). We consider halfspaces over the continuous domain R n (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube { − 1,1} n (endowed with the uniform distribution). In both cases we give an algorithm that distinguishes halfspaces from functions that are ε-far from any halfspace using only poly(1) queries, independent of the dimension n. In contrast to the case of general halfspaces, we show that testing natural subclasses of halfspaces can be markedly harder; for the class of { − 1,1}-weight halfspaces, we show that a tester must make at least Ω(logn) queries. We complement this lower bound with an upper bound showing that O(√n) queries suffice. National Basic Research Program of China (grant 2007CB807900) National Basic Research Program of China (grant 2007CB807901) National Natural Science Foundation (China) (grant 60553001) 2012-08-08T15:59:10Z 2012-08-08T15:59:10Z 2010-01 Article http://purl.org/eprint/type/JournalArticle 978-3-642-16366-1 http://hdl.handle.net/1721.1/72033 Matulef, Kevin et al. “Testing (Subclasses of) Halfspaces.” Property Testing. Ed. Oded Goldreich. (Lecture Notes in Computer Science : Vol. 6390). Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. 334–340. https://orcid.org/0000-0002-4353-7639 en_US http://dx.doi.org/10.1007/978-3-642-16367-8_27 Proceedings of the ITCS Mini-workshop on Property Testing (2010 : Beijing, China) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer-Verlag Rubinfeld via Amy Stout |
| spellingShingle | Matulef, Kevin M. O'Donnell, Ryan Rubinfeld, Ronitt Servedio, Rocco Testing (subclasses of) halfspaces |
| title | Testing (subclasses of) halfspaces |
| title_full | Testing (subclasses of) halfspaces |
| title_fullStr | Testing (subclasses of) halfspaces |
| title_full_unstemmed | Testing (subclasses of) halfspaces |
| title_short | Testing (subclasses of) halfspaces |
| title_sort | testing subclasses of halfspaces |
| url | http://hdl.handle.net/1721.1/72033 https://orcid.org/0000-0002-4353-7639 |
| work_keys_str_mv | AT matulefkevinm testingsubclassesofhalfspaces AT odonnellryan testingsubclassesofhalfspaces AT rubinfeldronitt testingsubclassesofhalfspaces AT servediorocco testingsubclassesofhalfspaces |