On the complexity of function learning

DOI10.1007/BF00993410MaRDI QIDQ1900975zbMATH OpenFDO

Authors Peter Auer, Philip M. Long, Wolfgang Maass, Gerhard J. Woeginger

Publication date 29 October 1995

Published in Machine Learning (Search for Journal in Brave)

zbMATH Keywords

learning algorithmstheory of learning functions

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Parallel algorithms in computer science (68W10)

Recommendations

• On the learnability of rich function classes
• Bounds on the Number of Examples Needed for Learning Functions
• Characterizations of learnability for classes of \(\{0,\dots,n\}\)-valued functions
• Improved bounds about on-line learning of smooth-functions of a single variable
• Improved bounds about on-line learning of smooth functions of a single variable

Cites work

• scientific article; zbMATH DE number 35425 (Why is no real title available?)
• scientific article; zbMATH DE number 67638 (Why is no real title available?)
• scientific article; zbMATH DE number 3420728 (Why is no real title available?)
• A Learning Theorem for Linear Operators
• Composite geometric concepts and polynomial predictability
• Coping with errors in binary search procedures
• Lower bound methods and separation results for on-line learning models
• On the density of families of sets
• Present Position and Potential Developments: Some Personal Views: Statistical Theory: The Prequential Approach
• Simulating access to hidden information while learning
• Toward efficient agnostic learning
• Ulam's searching game with a fixed number of lies
• Universal forecasting algorithms
• Universal prediction of individual sequences

Cited in

(9)

• scientific article; zbMATH DE number 1149407 (Why is no real title available?)
• Maximal width learning of binary functions
• Sharp bounds on the price of bandit feedback for several models of mistake-bounded online learning
• Learning Behaviors of Functions
• A note on the price of bandit feedback for mistake-bounded online learning
• New bounds on the price of bandit feedback for mistake-bounded online multiclass learning
• Learning-Related Complexity of Linear Ranking Functions
• Learning Nested Halfspaces and Uphill Decision Trees
• Automatic functions, linear time and learning

This page was built for publication: On the complexity of function learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1900975)