Testing Halfspaces
This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e., a function of the form f(x)=sgn(w [dot] x-theta). We consider halfspaces over the continuous domain R[superscript n] (endowed with the standard multivariate Gaussian distribution) as well as halfspa...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2012
|
| Online Access: | http://hdl.handle.net/1721.1/69873 https://orcid.org/0000-0002-4353-7639 |
| _version_ | 1811079155660357632 |
|---|---|
| author | Matulef, Kevin M. O'Donnell, Ryan Rubinfeld, Ronitt Servedio, Rocco A. |
| 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 A. |
| author_sort | Matulef, Kevin M. |
| collection | MIT |
| description | This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e., a function of the form f(x)=sgn(w [dot] x-theta). We consider halfspaces over the continuous domain R[superscript n] (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1,1}[superscript n] (endowed with the uniform distribution). In both cases we give an algorithm that distinguishes halfspaces from functions that are epsilon-far from any halfspace using only poly([fraction 1 over epsilon]) queries, independent of the dimension $n$. Two simple structural results about halfspaces are at the heart of our approach for the Gaussian distribution: The first gives an exact relationship between the expected value of a halfspace f and the sum of the squares of f's degree-1 Hermite coefficients, and the second shows that any function that approximately satisfies this relationship is close to a halfspace. We prove analogous results for the Boolean cube {-1,1}[superscript n] (with Fourier coefficients in place of Hermite coefficients) for balanced halfspaces in which all degree-1 Fourier coefficients are small. Dealing with general halfspaces over {-1,1}[superscript n] poses significant additional complications and requires other ingredients. These include “cross-consistency” versions of the results mentioned above for pairs of halfspaces with the same weights but different thresholds; new structural results relating the largest degree-1 Fourier coefficient and the largest weight in unbalanced halfspaces; and algorithmic techniques from recent work on testing juntas [E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky, Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, 2002, pp. 103–112]. |
| first_indexed | 2024-09-23T11:10:52Z |
| format | Article |
| id | mit-1721.1/69873 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:10:52Z |
| publishDate | 2012 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/698732022-09-27T17:40:24Z Testing Halfspaces Matulef, Kevin M. O'Donnell, Ryan Rubinfeld, Ronitt Servedio, Rocco A. 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 Matulef, Kevin M. This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e., a function of the form f(x)=sgn(w [dot] x-theta). We consider halfspaces over the continuous domain R[superscript n] (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1,1}[superscript n] (endowed with the uniform distribution). In both cases we give an algorithm that distinguishes halfspaces from functions that are epsilon-far from any halfspace using only poly([fraction 1 over epsilon]) queries, independent of the dimension $n$. Two simple structural results about halfspaces are at the heart of our approach for the Gaussian distribution: The first gives an exact relationship between the expected value of a halfspace f and the sum of the squares of f's degree-1 Hermite coefficients, and the second shows that any function that approximately satisfies this relationship is close to a halfspace. We prove analogous results for the Boolean cube {-1,1}[superscript n] (with Fourier coefficients in place of Hermite coefficients) for balanced halfspaces in which all degree-1 Fourier coefficients are small. Dealing with general halfspaces over {-1,1}[superscript n] poses significant additional complications and requires other ingredients. These include “cross-consistency” versions of the results mentioned above for pairs of halfspaces with the same weights but different thresholds; new structural results relating the largest degree-1 Fourier coefficient and the largest weight in unbalanced halfspaces; and algorithmic techniques from recent work on testing juntas [E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky, Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, 2002, pp. 103–112]. National Science Foundation (U.S.) (NSF grant 0514771) National Science Foundation (U.S.) (0732334) National Science Foundation (U.S.) (grant 0728645) National Science Foundation (U.S.) (NSF Graduate fellowship) National Science Foundation (U.S.) (NSF-CAREER Award CCF-0347282) National Science Foundation (U.S.) (Award CCF-0523664) Alfred P. Sloan Foundation (Research Fellowship) 2012-03-28T14:50:04Z 2012-03-28T14:50:04Z 2010-02 2009-07 Article http://purl.org/eprint/type/JournalArticle 0097-5397 1095-7111 http://hdl.handle.net/1721.1/69873 Matulef, Kevin et al. “Testing Halfspaces.” SIAM Journal on Computing 39.5 (2010): 2004. https://orcid.org/0000-0002-4353-7639 en_US http://dx.doi.org/10.1137/070707890 SIAM Journal on Computing Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Society for Industrial and Applied Mathematics Amy Stout / webpage |
| spellingShingle | Matulef, Kevin M. O'Donnell, Ryan Rubinfeld, Ronitt Servedio, Rocco A. Testing Halfspaces |
| title | Testing Halfspaces |
| title_full | Testing Halfspaces |
| title_fullStr | Testing Halfspaces |
| title_full_unstemmed | Testing Halfspaces |
| title_short | Testing Halfspaces |
| title_sort | testing halfspaces |
| url | http://hdl.handle.net/1721.1/69873 https://orcid.org/0000-0002-4353-7639 |
| work_keys_str_mv | AT matulefkevinm testinghalfspaces AT odonnellryan testinghalfspaces AT rubinfeldronitt testinghalfspaces AT servedioroccoa testinghalfspaces |