Learning intersections of halfspaces with a margin
From MaRDI portal
Publication:2462501
DOI10.1016/j.jcss.2007.04.012zbMath1131.68052OpenAlexW2018199527MaRDI QIDQ2462501
Rocco A. Servedio, Adam R. Klivans
Publication date: 30 November 2007
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2007.04.012
computational learning theoryrandom projectionmarginpolynomial threshold functionintersections of halfspacesKernel Perceptron
Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05)
Related Items (6)
On the proliferation of support vectors in high dimensions* ⋮ On the hardness of learning intersections of two halfspaces ⋮ The hardest halfspace ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Cryptographic hardness for learning intersections of halfspaces ⋮ New cryptographic hardness for learning intersections of halfspaces over Boolean cubes with membership queries
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Learning intersections and thresholds of halfspaces
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
- Learning an intersection of a constant number of halfspaces over a uniform distribution
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- PP is closed under intersection
- Classification by polynomial surfaces
- Large margin classification using the perceptron algorithm
- An algorithmic theory of learning: Robust concepts and random projection
- Rational approximation to \(|x|\)
- Extensions of Lipschitz mappings into a Hilbert space
- Learnability and the Vapnik-Chervonenkis dimension
- A theory of the learnable
- Learning DNF in time
- New degree bounds for polynomial threshold functions
This page was built for publication: Learning intersections of halfspaces with a margin
