Testing halfspaces

ABSTRACT

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 · x - θ). We consider halfspaces over the continuous domain Rⁿ (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {−1, 1}ⁿ (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.

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}ⁿ (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}ⁿ 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 [FKR⁺02].

REFERENCES

• 1: Andreas Birkendorf , Eli Dichterman , Jeffrey Jackson , Norbert Klasner , Hans Ulrich Simon, On Restricted-Focus-of-Attention Learnability of Boolean Functions, Machine Learning, v.30 n.1, p.89-123, Jan. 1998 [doi>10.1023/A:1007458528570]
• 2: {Blo62} H. Block. The Perceptron: a model for brain functioning. Reviews of Modern Physics, 34:123--135, 1962.
• 3: {Cho61} C. K. Chow. On the characterization of threshold functions. In Proceedings of the Symposium on Switching Circuit Theory and Logical Design (FOCS), pages 34--38, 1961.
• 4: Ilias Diakonikolas , Homin K. Lee , Kevin Matulef , Krzysztof Onak , Ronitt Rubinfeld , Rocco A. Servedio , Andrew Wan, Testing for Concise Representations, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.549-558, October 21-23, 2007 [doi>10.1109/FOCS.2007.70]
• 5: Eldar Fischer , Guy Kindler , Dana Ron , Shmuel Safra , Alex Samorodnitsky, Testing Juntas, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.103-112, November 16-19, 2002
• 6: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 7: Paul W. Goldberg, A Bound on the Precision Required to Estimate a Boolean Perceptron from Its Average Satisfying Assignment, SIAM Journal on Discrete Mathematics, v.20 n.2, p.328-343, 2006 [doi>10.1137/S0895480103426765]
• 8: András Hajnal , Wolfgang Maass , Pavel Pudlák , György Turán , Márió Szegedy, Threshold circuits of bounded depth, Journal of Computer and System Sciences, v.46 n.2, p.129-154, April 1993 [doi>10.1016/0022-0000(93)90001-D]
• 9: Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O’Donnell, Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?, SIAM Journal on Computing, v.37 n.1, p.319-357, April 2007 [doi>10.1137/S0097539705447372]
• 10: S. R. Kulkarni , S. K. Mitter , J. N. Tsitsiklis, Active Learning Using Arbitrary Binary Valued Queries, Machine Learning, v.11 n.1, p.23-35, April 1993 [doi>10.1023/A:1022627018023]
• 11: {MORS07} K. Matulef, R. O'Donnell, R. Rubinfeld, and R. Servedio. Testing Halfspaces. Technical Report 128, Electronic Colloquium in Computational Complexity, 2007.
• 12: {MP68} M. Minsky and S. Papert. Perceptrons: an introduction to computational geometry. MIT Press, Cambridge, MA, 1968.
• 13: {Nov62} A. Novikoff. On convergence proofs on perceptrons. In Proceedings of the Symposium on Mathematical Theory of Automata, volume XII, pages 615--622, 1962.
• 14: Ryan O'Donnell , Rocco A. Servedio, The chow parameters problem, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374450]
• 15: Michal Parnas , Dana Ron , Alex Samorodnitsky, Testing Basic Boolean Formulae, SIAM Journal on Discrete Mathematics, v.16 n.1, p.20-46, 2003 [doi>10.1137/S0895480101407444]
• 16: {Ron07} D. Ron. Property testing: A learning theory perspective. COLT 2007 Invited Talk, slides available at http://www.eng.tau.ac.il/danar/Public-ppt/colt07.ppt, 2007.
• 17: {San08} R. Santhanam. Personal communication, 2008.
• 18: Rocco A. Servedio, Every Linear Threshold Function has a Low-Weight Approximator, Proceedings of the 21st Annual IEEE Conference on Computational Complexity, p.18-32, July 16-20, 2006 [doi>10.1109/CCC.2006.18]
• 19: Rocco A. Servedio, Every Linear Threshold Function has a Low-Weight Approximator, Computational Complexity, v.16 n.2, p.180-209, May 2007 [doi>10.1007/s00037-007-0228-7]
• 20: {STC00} J. Shawe-Taylor and N. Cristianini. An introduction to support vector machines. Cambridge University Press, 2000.
• 21: A. C. -C. Yao, ON ACC and threshold circuits, Proceedings of the 31st Annual Symposium on Foundations of Computer Science, p.619-627 vol.2, October 22-24, 1990 [doi>10.1109/FSCS.1990.89583]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions