Article

A general lower bound on the number of examples needed for learning

Authors:

A. Ehrenfeucht,

David Haussler,

Michael Kearns,

Leslie ValiantAuthors Info & Claims

COLT '88: Proceedings of the first annual workshop on Computational learning theory

Pages 139 - 154

Published: 01 December 1988 Publication History

Abstract

No abstract available.

Cited By

View all

Sabato SSrebro NTishby N(2010)Tight sample complexity of Large-margin learningProceedings of the 23rd International Conference on Neural Information Processing Systems - Volume 210.5555/2997046.2997123(2038-2046)Online publication date: 6-Dec-2010
https://dl.acm.org/doi/10.5555/2997046.2997123
Franco MKrasnogor NBacardit JPelikan MBranke J(2010)Analysing bioHEL using challenging boolean functionsProceedings of the 12th annual conference companion on Genetic and evolutionary computation10.1145/1830761.1830817(1855-1862)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1145/1830761.1830817
Wah B(1999)Generalization and Generalizability MeasuresIEEE Transactions on Knowledge and Data Engineering10.1109/69.75562611:1(175-186)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.1109/69.755626
Show More Cited By

Index Terms

A general lower bound on the number of examples needed for learning
1. Computing methodologies
  1. Machine learning
  2. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

General Bounds on the Number of Examples Needed for Learning Probabilistic Concepts

Given a p-concept classC, we define two important functionsdC( ),d C( ) (related to the notion of -shattering). We prove a lower bound of ((dC( ) 1)/( 2)) on the number of examples required for learningCwith an ( , )-good model of probability. We prove ...
On the topological lower bound for the multichromatic number

In 1976, Stahl [14] defined the m-tuple coloring of a graph G and formulated a conjecture on the multichromatic number of Kneser graphs. For m=1 this conjecture is Kneser's conjecture, which was proved by Lovasz in 1978 [10]. Here we show that Lovasz's ...
A New Lower Bound for the Bipartite Crossing Number withApplications

Comments

Information & Contributors

Information

Published In

COLT '88: Proceedings of the first annual workshop on Computational learning theory

December 1988

433 pages

Editors:
David Haussler
Univ. of California, Santa Cruz
,
Leonard Pitt
Univ. of Illinois, Urbana

Publisher

Morgan Kaufmann Publishers Inc.

San Francisco, CA, United States

Publication History

Published: 01 December 1988

Check for updates

Qualifiers

Article

Conference

COLT88

Sponsor:

SIGAI

COLT88: 1988 Working on Computational Learning Theory

August 3 - 5, 1988

Massachusetts, MIT, Cambridge, USA

Acceptance Rates

Overall Acceptance Rate 35 of 71 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Sabato SSrebro NTishby N(2010)Tight sample complexity of Large-margin learningProceedings of the 23rd International Conference on Neural Information Processing Systems - Volume 210.5555/2997046.2997123(2038-2046)Online publication date: 6-Dec-2010
https://dl.acm.org/doi/10.5555/2997046.2997123
Franco MKrasnogor NBacardit JPelikan MBranke J(2010)Analysing bioHEL using challenging boolean functionsProceedings of the 12th annual conference companion on Genetic and evolutionary computation10.1145/1830761.1830817(1855-1862)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1145/1830761.1830817
Wah B(1999)Generalization and Generalizability MeasuresIEEE Transactions on Knowledge and Data Engineering10.1109/69.75562611:1(175-186)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.1109/69.755626
Srinivasan A(1999)A Study of Two Sampling Methods for Analyzing Large Datasets with ILPData Mining and Knowledge Discovery10.1023/A:10098241234623:1(95-123)Online publication date: 1-Mar-1999
https://dl.acm.org/doi/10.1023/A%3A1009824123462
Kearns M(1998)Efficient noise-tolerant learning from statistical queriesJournal of the ACM10.1145/293347.29335145:6(983-1006)Online publication date: 1-Nov-1998
https://dl.acm.org/doi/10.1145/293347.293351
Bshouty NTamon CLeighton FBorodin A(1995)On the Fourier spectrum of monotone functionsProceedings of the twenty-seventh annual ACM symposium on Theory of computing10.1145/225058.225125(219-228)Online publication date: 29-May-1995
https://dl.acm.org/doi/10.1145/225058.225125
Kearns MKosaraju RJohnson DAggarwal A(1993)Efficient noise-tolerant learning from statistical queriesProceedings of the twenty-fifth annual ACM symposium on Theory of Computing10.1145/167088.167200(392-401)Online publication date: 1-Jun-1993
https://dl.acm.org/doi/10.1145/167088.167200
Benedek GItai AHaussler D(1992)Dominating distributions and learnabilityProceedings of the fifth annual workshop on Computational learning theory10.1145/130385.130413(253-264)Online publication date: 1-Jul-1992
https://dl.acm.org/doi/10.1145/130385.130413
Kearns MValiant L(1989)Crytographic limitations on learning Boolean formulae and finite automataProceedings of the twenty-first annual ACM symposium on Theory of computing10.1145/73007.73049(433-444)Online publication date: 1-Feb-1989
https://dl.acm.org/doi/10.1145/73007.73049

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

General Bounds on the Number of Examples Needed for Learning Probabilistic Concepts

On the topological lower bound for the multichromatic number

A New Lower Bound for the Bipartite Crossing Number withApplications

Comments

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Conference

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

Login options

Full Access

Abstract

Cited By

Index Terms

Recommendations

General Bounds on the Number of Examples Needed for Learning Probabilistic Concepts

On the topological lower bound for the multichromatic number

A New Lower Bound for the Bipartite Crossing Number withApplications

Comments

Information

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations