An upper bound on the sample complexity of PAC-learning halfspaces with respect to the uniform distribution

DOI10.1016/S0020-0190(03)00311-9zbMath1161.68499MaRDI QIDQ1014429

Philip M. Long

Publication date: 28 April 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexitymachine learningPAC-learningsample complexityhalfspaces

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Related Items (2)

The regularized least squares algorithm and the problem of learning halfspaces ⋮ Using the doubling dimension to analyze the generalization of learning algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Learnability with respect to fixed distributions
• Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
• Approximating hyper-rectangles: Learning and pseudorandom sets
• Predicting \(\{ 0,1\}\)-functions on randomly drawn points
• A Remark on Stirling's Formula
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• Enumeration of Seven-Argument Threshold Functions
• Convergence of stochastic processes

This page was built for publication: An upper bound on the sample complexity of PAC-learning halfspaces with respect to the uniform distribution