The uniform hardcore lemma via approximate Bregman projections

ABSTRACT

We give a simple, more efficient and uniform proof of the hard-core lemma, a fundamental result in complexity theory with applications in machine learning and cryptography. Our result follows from the connection between boosting algorithms and hard-core set constructions discovered by Klivans and Servedio [11]. Informally stated, our result is the following: suppose we fix a family of boolean functions. Assume there is an efficient algorithm which for every input length and every smooth distribution (i.e. one that doesn't assign too much weight to any single input) over the inputs produces a circuit such that the circuit computes the boolean function noticeably better than random. Then, there is an efficient algorithm which for every input length produces a circuit that computes the function correctly on almost all inputs.

Our algorithm significantly simplifies previous proofs of the uniform and the non-uniform hard-core lemma, while matching or improving the previously best known parameters. The algorithm uses a generalized multiplicative update rule combined with a natural notion of approximate Bregman projection. Bregman projections are widely used in convex optimization and machine learning. We present an algorithm which efficiently approximates the Bregman projection onto the set of high density measures when the Kullback-Leibler divergence is used as a distance function. Our algorithm has a logarithmic runtime over any domain from which we can efficiently sample. High density measures correspond to smooth distributions which arise naturally, for instance, in the context of online learning. Hence, our technique may be of independent interest.

REFERENCES

• 1: Yair Al Censor , Stavros A. Zenios, Parallel Optimization: Theory, Algorithms and Applications, Oxford University Press, 1997
• 2: Yoav Freund, Boosting a weak learning algorithm by majority, Proceedings of the third annual workshop on Computational learning theory, p.202-216, August 06-08, 1990, Rochester, New York, United States
• 3: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
• 4: Mark Herbster , Manfred K. Warmuth, Tracking the best linear predictor, The Journal of Machine Learning Research, 1, p.281-309, 9/1/2001 [doi>10.1162/153244301753683726]
• 5: Thomas Holenstein, Key agreement from weak bit agreement, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060689]
• 6: Thomas Holenstein. Pseudorandom generators from one-way functions: A simple construction for any hardness. In Proc. of 3rd TCC. Springer, 2006.
• 7: R. Impagliazzo, Hard-core distributions for somewhat hard problems, Proceedings of the 36th Annual Symposium on Foundations of Computer Science, p.538, October 23-25, 1995
• 8: Russell Impagliazzo , Ragesh Jaiswal , Valentine Kabanets, Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.187-196, October 21-24, 2006 [doi>10.1109/FOCS.2006.13]
• 9: Russell Impagliazzo , Ragesh Jaiswal , Valentine Kabanets , Avi Wigderson, Uniform direct product theorems: simplified, optimized, and derandomized, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374460]
• 10: Satyen Kale. Boosting and hard-core set constructions: a simplified approach. Electronic Colloquium on Computational Complexity (ECCC), (131), 2007.
• 11: Adam R. Klivans , Rocco A. Servedio, Boosting and Hard-Core Set Construction, Machine Learning, v.51 n.3, p.217-238, June 2003 [doi>10.1023/A:1022949332276]
• 12: Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
• 13: Rocco A. Servedio, Smooth boosting and learning with malicious noise, The Journal of Machine Learning Research, 4, p.633-648, 12/1/2003 [doi>10.1162/153244304773936072]
• 14: Luca Trevisan, List-Decoding Using The XOR Lemma, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.126, October 11-14, 2003
• 15: Luca Trevisan, On uniform amplification of hardness in NP, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060595]
• 16: Manfred K. Warmuth and Dima Kuzmin. Randomized pca algorithms with regret bounds that are logarithmic in the dimension. In In Proc. of NIPS, 2006.
• 17: Andrew C. Yao, Theory and application of trapdoor functions, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, p.80-91, November 03-05, 1982

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms