On agnostic boosting and parity learning

ABSTRACT

The motivating problem is agnostically learning parity functions, i.e., parity with arbitrary or adversarial noise. Specifically, given random labeled examples from an *arbitrary* distribution, we would like to produce an hypothesis whose accuracy nearly matches the accuracy of the best parity function. Our algorithm runs in time 2^{O(n/log n)}, which matches the best known for the easier cases of learning parities with random classification noise (Blum et al, 2003) and for agnostically learning parities over the uniform distribution on inputs (Feldman et al, 2006).

Our approach is as follows. We give an agnostic boosting theorem that is capable of nearly achieving optimal accuracy, improving upon earlier studies (starting with Ben David et al, 2001). To achieve this, we circumvent previous lower bounds by altering the boosting model. We then show that the (random noise) parity learning algorithm of Blum et al (2000) fits our new model of agnostic weak learner. Our agnostic boosting framework is completely general and may be applied to other agnostic learning problems. Hence, it also sheds light on the actual difficulty of agnostic learning by showing that full agnostic boosting is indeed possible.

REFERENCES

• 1: Miklós Ajtai , Ravi Kumar , D. Sivakumar, A sieve algorithm for the shortest lattice vector problem, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.601-610, July 2001, Hersonissos, Greece [doi>10.1145/380752.380857]
• 2: Shai Ben-David , Philip M. Long , Yishay Mansour, Agnostic Boosting, Proceedings of the 14th Annual Conference on Computational Learning Theory and and 5th European Conference on Computational Learning Theory, p.507-516, July 16-19, 2001
• 3: Avrim Blum , Merrick Furst , Michael Kearns , Richard J. Lipton, Cryptographic primitives based on hard learning problems, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.278-291, January 1994, Santa Barbara, California, United States
• 4: Avrim Blum , Adam Kalai , Hal Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model, Journal of the ACM (JACM), v.50 n.4, p.506-519, July 2003 [doi>10.1145/792538.792543]
• 5: 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]
• 6: Dmitry Gavinsky, Optimally-smooth adaptive boosting and application to agnostic learning, The Journal of Machine Learning Research, 4, p.101-117, 12/1/2003
• 7: Oded Goldreich , Ronitt Rubinfeld , Madhu Sudan, Learning Polynomials with Queries: The Highly Noisy Case, SIAM Journal on Discrete Mathematics, v.13 n.4, p.535-570, Oct. 2000 to Nov. 2000 [doi>10.1137/S0895480198344540]
• 8: David Haussler , Michael Kearns, Equivalence of models for polynomial learnability, Information and Computation, v.95 n.2, p.129-161, Dec. 1991 [doi>10.1016/0890-5401(91)90042-Z]
• 9: Nicholas J. Hopper , Manuel Blum, Secure Human Identification Protocols, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.52-66, December 09-13, 2001
• 10: Ari Juels and Stephen A. Weis. Authenticating pervasive devices with human protocols. In CRYPTO, pages 293--308, 2005.
• 11: 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]
• 12: Adam Tauman Kalai , Rocco A. Servedio, Boosting in the presence of noise, Journal of Computer and System Sciences, v.71 n.3, p.266-290, October 2005 [doi>10.1016/j.jcss.2004.10.015]
• 13: Michael Kearns, Efficient noise-tolerant learning from statistical queries, Journal of the ACM (JACM), v.45 n.6, p.983-1006, Nov. 1998 [doi>10.1145/293347.293351]
• 14: Michael Kearns , Yishay Mansour, On the boosting ability of top-down decision tree learning algorithms, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.459-468, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237994]
• 15: Michael Kearns , Yishay Mansour, On the boosting ability of top-down decision tree learning algorithms, Journal of Computer and System Sciences, v.58 n.1, p.109-128, Feb. 1999 [doi>10.1006/jcss.1997.1543]
• 16: Michael J. Kearns , Robert E. Schapire , Linda M. Sellie, Toward Efficient Agnostic Learning, Machine Learning, v.17 n.2-3, p.115-141, Nov./Dec. 1994 [doi>10.1007/BF00993468]
• 17: Vadim Lyubashevsky. The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In APPROX--RANDOM, pages 378--389, 2005.
• 18: Y. Mansour and D. McAllester. Boosting using branching programs. Journal of Computer and System Sciences, 64(1):103--112, 2002.
• 19: Elchanan Mossel , Sébastien Roch, Learning nonsingular phylogenies and hidden Markov models, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060645]
• 20: Oded Regev, On lattices, learning with errors, random linear codes, and cryptography, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060603]
• 21: Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
• 22: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
agnostic boosting, agnostic learning, learning parity with noise, sub-exponential algorithms