article

Boosting and Hard-Core Set Construction

Authors:

Adam R. Klivans,

Rocco A. ServedioAuthors Info & Claims

Machine Learning, Volume 51, Issue 3

Pages 217 - 238

https://doi.org/10.1023/A:1022949332276

Published: 01 June 2003 Publication History

Abstract

This paper connects hard-core set construction, a type of hardness amplification from computational complexity, and boosting, a technique from computational learning theory. Using this connection we give fruitful applications of complexity-theoretic techniques to learning theory and vice versa. We show that the hard-core set construction of Impagliazzo (1995), which establishes the existence of distributions under which boolean functions are highly inapproximable, may be viewed as a boosting algorithm. Using alternate boosting methods we give an improved bound for hard-core set construction which matches known lower bounds from boosting and thus is optimal within this class of techniques. We then show how to apply techniques from Impagliazzo (1995) to give a new version of Jackson's celebrated Harmonic Sieve algorithm for learning DNF formulae under the uniform distribution using membership queries. Our new version has a significant asymptotic improvement in running time. Critical to our arguments is a careful analysis of the distributions which are employed in both boosting and hard-core set constructions.

References

[1]

Babai, L., Fortnow, L., Nisan, N., & Wigderson, A. (1993). BPP has subexponential time simulations unless exptime has publishable proofs. Computational Complexity, 3, 307-318.]]

Digital Library

[2]

Blum, A., Furst, M., Jackson, J., Kearns, M., Mansour, Y., & Rudich, S. (1994). Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In Proceedings of the Twenty-Sixth Annual Symposium on Theory of Computing (pp. 253-262). ACM.]]

Digital Library

[3]

Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. (1989). Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36:4, 929-965.]]

Digital Library

[4]

Boneh, D., & Lipton, R. (1993). Amplification of weak learning over the uniform distribution. In Proceedings of the Sixth Annual Workshop on Computational Learning Theory (pp. 347-351). ACM.]]

Digital Library

[5]

Bshouty, N., Jackson, J., & Tamon, C. (1999). More efficient PAC learning of DNF with membership queries under the uniform distribution. In Proceedings of the Twelfth Annual Conference on Computational Learning Theory (pp. 286-295).]]

Digital Library

[6]

Drucker, H., & Cortes, C. (1996). Boosting decision trees. In Advances in Neural Information Processing Systems 8 (pp. 479-485).]]

[7]

Drucker, H., Cortes, C., Jackel, L. D., Lecun, Y., & Vapnik, V. (1994). Boosting and other ensemble methods. Neural Computation, 6:6, 1289-1301.]]

Digital Library

[8]

Drucker, H., Schapire, R., & Simard, P. (1993a). Boosting performance in neural networks. International Journal of Pattern Recognition and Machine Intelligence, 7:4, 705-719.]]

[9]

Drucker, H., Schapire, R., & Simard, P. (1993b). Improving performance in neural networks using a boosting algorithm. In Advances in Neural Information Processing Systems 5 (pp. 42-49).]]

Digital Library

[10]

Freund, Y. (1990). Boosting a weak learning algorithm by majority. In Proceedings of the Third Annual Workshop on Computational Learning Theory (pp. 202-216).]]

Digital Library

[11]

Freund, Y. (1992). An improved boosting algorithm and its implications on learning complexity. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory (pp. 391-398).]]

Digital Library

[12]

Freund, Y. (1995). Boosting a weak learning algorithm by majority. Information and Computation, 121:2, 256-285.]]

Digital Library

[13]

Freund, Y., & Schapire, R. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55:1, 119-139.]]

Digital Library

[14]

Goldreich, O., Nisan, N., & Wigderson, A. (1995). On Yao's xor-lemma. Electronic Colloquium on Computational Complexity, TR95-050.]]

[15]

Impagliazzo, R. (1995). Hard-core distributions for somewhat hard problems. In Proceedings of the Thirty-Sixth Annual Symposium on Foundations of Computer Science (pp. 538-545). IEEE.]]

Digital Library

[16]

Impagliazzo, R., & Widgerson, A. (1997). P = BPP unless E has subexponential circuits: Derandomizing the xor lemma. In Proceedings of the Twenty-Ninth Annual Symposium on Theory of Computing (pp. 220-229).]]

Digital Library

[17]

Jackson, J. (1995). The Harmonic sieve: A novel application of Fourier analysis to machine learning theory and practice. Ph.D. Thesis, Carnegie Mellon University.]]

Digital Library

[18]

Jackson, J. (1997). An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. Journal of Computer and System Sciences, 55, 414-440.]]

Digital Library

[19]

Jackson, J. (2002). Personal communication.]]

[20]

Jackson, J., & Craven, M. (1996). Learning sparse perceptrons. In Advances in Neural Information Processing Systems 8 (pp. 654-660).]]

[21]

Kearns, M., & Valiant, L. (1994). Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM, 41:1, 67-95.]]

Digital Library

[22]

Klivans, A., & Servedio, R. (2001). Learning DNF in time 2<sup>O˜(n<sup>1/3</sup>)</sup>. In Proceedings of the Twenty-Sixth Annual Symposium on Theory of Computing (pp. 258-265).]]

Digital Library

[23]

Levin, L. (1986). Average case complete problems. SIAM Journal on Computing, 15:1, 285-286.]]

Digital Library

[24]

Muller, D., & Preparata, F. (1975). Bounds to complexities of networks for sorting and for switching. Journal of the ACM, 22:2, 195-201.]]

Digital Library

[25]

Nisan, N., & Wigderson, A. (1994). Hardness versus randomness. Journal of Computer and System Sciences, 49, 149-167.]]

Digital Library

[26]

Schapire, R. (1990). The strength of weak learnability. Machine Learning, 5:2, 197-227.]]

Digital Library

[27]

Schapire, R., & Singer, Y. (1998). Improved boosting algorithms using confidence-rated predictions. In Proceedings of the Eleventh Annual Conference on Computational Learning Theory (pp. 80-91).]]

Digital Library

[28]

Servedio, R. (2001). Smooth boosting and learning with malicious noise. In Proceedings of the Fourteenth Annual Conference on Computational Learning Theory (pp. 473-489).]]

Digital Library

[29]

Shaltiel, R. (2001). Towards proving strong direct product theorems. In Proceedings of the Sixteenth Conference on Computational Complexity (pp. 107-117).]]

Digital Library

[30]

Sudan, M., Trevisan, L., & Vadhan, S. (2001) Pseudorandom generators without the xor lemma. Journal of Computer and System Sciences, 62:2, 236-266.]]

Digital Library

[31]

Valiant, L. (1984). A theory of the learnable. Communications of the ACM, 27:11, 1134-1142.]]

Digital Library

[32]

Wigderson, A. (1999). Personal communication.]]

Cited By

Ben-David SBlais E(2023)A New Minimax Theorem for Randomized AlgorithmsJournal of the ACM10.1145/362651470:6(1-58)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3626514
Lovett SWu KZhang J(2021)Decision List Compression by Mild Random RestrictionsJournal of the ACM10.1145/348500768:6(1-17)Online publication date: 31-Dec-2021
https://dl.acm.org/doi/10.1145/3485007
Hirahara SAceto L(2020)Non-disjoint promise problems from meta-computational view of pseudorandom generator constructionsProceedings of the 35th Computational Complexity Conference10.4230/LIPIcs.CCC.2020.20(1-47)Online publication date: 28-Jul-2020
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2020.20
Show More Cited By

Index Terms

Boosting and Hard-Core Set Construction

Recommendations

Complexity of Hard-Core Set Proofs

We study a fundamental result of Impagliazzo (FOCS’95) known as the hard-core set lemma. Consider any function $${f:\{0,1\}^n\to\{0,1\}}$$ which is “mildly hard”, in the sense that any circuit of size s must disagree with f on at least a δ fraction of ...
On the complexity of hard-core set constructions
ICALP'07: Proceedings of the 34th international conference on Automata, Languages and Programming

We study a fundamental result of Impagliazzo (FOCS'95) known as the hard-core set lemma. Consider any function f : {0, 1}ⁿ → {0, 1} which is "mildly-hard", in the sense that any circuit of size s must disagree with f on at least δ fraction of inputs. ...
The inapproximability of non-NP-hard optimization problems

The inapproximability of non-NP-hard optimization problems is investigated. Techniques are given to show that the problems LOG DOMINATING SET and LOG HYPERGRAPH VERTEX COVER cannot be approximated to a constant ratio in polynomial time unless the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Machine Language

Machine Language Volume 51, Issue 3

June 2003

82 pages

ISSN:0885-6125

Issue’s Table of Contents

Copyright © Copyright © 2003 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 June 2003

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ben-David SBlais E(2023)A New Minimax Theorem for Randomized AlgorithmsJournal of the ACM10.1145/362651470:6(1-58)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3626514
Lovett SWu KZhang J(2021)Decision List Compression by Mild Random RestrictionsJournal of the ACM10.1145/348500768:6(1-17)Online publication date: 31-Dec-2021
https://dl.acm.org/doi/10.1145/3485007
Hirahara SAceto L(2020)Non-disjoint promise problems from meta-computational view of pseudorandom generator constructionsProceedings of the 35th Computational Complexity Conference10.4230/LIPIcs.CCC.2020.20(1-47)Online publication date: 28-Jul-2020
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2020.20
Lovett SWu KZhang JMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Decision list compression by mild random restrictionsProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384241(247-254)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384241
Jain AKorb AManohar NSahai A(2020)Amplifying the Security of Functional Encryption, UnconditionallyAdvances in Cryptology – CRYPTO 202010.1007/978-3-030-56784-2_24(717-746)Online publication date: 17-Aug-2020
https://dl.acm.org/doi/10.1007/978-3-030-56784-2_24
Vadhan S(2019)Computational entropyProviding Sound Foundations for Cryptography10.1145/3335741.3335767(693-726)Online publication date: 4-Oct-2019
https://dl.acm.org/doi/10.1145/3335741.3335767
Viola E(2019)Constant-Error Pseudorandomness Proofs from Hardness Require MajorityACM Transactions on Computation Theory10.1145/332281511:4(1-11)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3322815
Rossman BZuckerman D(2015)Correlation bounds against monotone NCProceedings of the 30th Conference on Computational Complexity10.5555/2833227.2833247(392-411)Online publication date: 17-Jun-2015
https://dl.acm.org/doi/10.5555/2833227.2833247
Watson T(2015)Advice Lower Bounds for the Dense Model TheoremACM Transactions on Computation Theory10.1145/26766597:1(1-18)Online publication date: 13-Jan-2015
https://dl.acm.org/doi/10.1145/2676659
Watson T(2015)Query Complexity in Errorless Hardness AmplificationComputational Complexity10.1007/s00037-015-0117-424:4(823-850)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1007/s00037-015-0117-4
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents