On hardness of learning intersection of two halfspaces

ABSTRACT

We show that unless NP = RP, it is hard to (even) weakly PAC-learn intersection of two halfspaces in Rⁿ using a hypothesis which is a function of up to l linear threshold functions for any integer l. Specifically, we show that for every integer l and an arbitrarily small constant ε > 0, unless NP = RP, no polynomial time algorithm can distinguish whether there is an intersection of two halfspaces that correctly classifies a given set of labeled points in Rⁿ, or whether any function of l linear threshold functions can correctly classify at most 1/2+ε fraction of the points.

REFERENCES

• 1: A. Blum , A. Frieze, A polynomial-time algorithm for learning noisy linear threshold functions, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.330, October 14-16, 1996
• 2: Adam Tauman Kalai , Adam R. Klivans , Yishay Mansour , Rocco A. Servedio, Agnostically Learning Halfspaces, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.11-20, October 23-25, 2005 [doi>10.1109/SFCS.2005.13]
• 3: Avrim L. Blum , Ravindran Kannan, Learning an intersection of a constant number of halfspaces over a uniform distribution, Journal of Computer and System Sciences, v.54 n.2, p.371-380, April 1997 [doi>10.1006/jcss.1997.1475]
• 4: Santosh Vempala, A Random Sampling based Algorithm for Learning the Intersection of Half-spaces, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.508, October 19-22, 1997
• 5: Adam Klivans , Ryan O'Donnell , Rocco A. Servedio, Learning Intersections and Thresholds of Halfspaces, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.177-186, November 16-19, 2002
• 6: A. Klivans and R. Servedio, Learning Intersections of Halfspaces with a Margin, Proc. COLT, 2004, 348--362.
• 7: Rosa I. Arriaga , Santosh Vempala, An Algorithmic Theory of Learning: Robust Concepts and Random Projection, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.616, October 17-18, 1999
• 8: Vitaly Feldman , Parikshit Gopalan , Subhash Khot , Ashok Kumar Ponnuswami, New Results for Learning Noisy Parities and Halfspaces, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.563-574, October 21-24, 2006 [doi>10.1109/FOCS.2006.51]
• 9: Venkatesan Guruswami , Prasad Raghavendra, Hardness of Learning Halfspaces with Noise, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.543-552, October 21-24, 2006 [doi>10.1109/FOCS.2006.33]
• 10: Avrim Blum , Ronald L. Rivest, Training a 3-Node Neural Network is NP-Complete, Machine Learning: From Theory to Applications - Cooperative Research at Siemens and MIT, p.9-28, January 1993
• 11: Misha Alekhnovich , Mark Braverman , Vitaly Feldman , Adam R. Klivans , Toniann Pitassi, Learnability and Automatizability, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.621-630, October 17-19, 2004 [doi>10.1109/FOCS.2004.36]
• 12: Adam R. Klivans , Alexander A. Sherstov, Cryptographic Hardness for Learning Intersections of Halfspaces, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.553-562, October 21-24, 2006 [doi>10.1109/FOCS.2006.24]
• 13: Parikshit Gopalan , Subhash Khot , Rishi Saket, Hardness of Reconstructing Multivariate Polynomials over Finite Fields, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.349-359, October 21-23, 2007 [doi>10.1109/FOCS.2007.31]
• 14: Subhash Khot, Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.23-32, November 16-19, 2002
• 15: Jonas Holmerin , Subhash Khot, A new PCP outer verifier with applications to homogeneous linear equations and max-bisection, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007362]
• 16: Subhash Khot , Rishi Saket, A 3-Query Non-Adaptive PCP with Perfect Completeness, Proceedings of the 21st Annual IEEE Conference on Computational Complexity, p.159-169, July 16-20, 2006 [doi>10.1109/CCC.2006.5]
• 17: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 18: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 19: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 20: V. Vapnik and A. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory of Probability and its Applications, 16, 2, 264--280, 1971.
• 21: Anat Levin , Amnon Shashua, Principal Component Analysis over Continuous Subspaces and Intersection of Half-Spaces, Proceedings of the 7th European Conference on Computer Vision-Part III, p.635-650, May 28-31, 2002
• 22: Owen Murphy , Bert Brooks , Thomas Kite, Computing nearest neighbor pattern classification perceptrons, Information Sciences—Intelligent Systems: An International Journal, v.83 n.3-4, p.133-142, March 1995 [doi>10.1016/0020-0255(94)00066-K]
• 23: Ulrich Ruckert , Lothar Richter , Stefan Kramer, Quantitative Association Rules Based on Half-Spaces: An Optimization Approach, Proceedings of the Fourth IEEE International Conference on Data Mining, p.507-510, November 01-04, 2004
• 24: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 25: Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
• 26: I. Benjamin and G. Kalai and O. Schramm, Noise sensitivity of boolean functions and applications to percolation, Inst. Hautes Etudes Sci. Publ. Math., 90, 1999, 5--43

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
approximation, halfspaces, hardness, learning