A random-sampling-based algorithm for learning intersections of halfspaces

DOI10.1145/1857914.1857916MaRDI QIDQ2999781zbMATH OpenOpenAlexFDO

Authors Santosh S. Vempala

Publication date 16 May 2011

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1857914.1857916

zbMATH Keywords

complexityrandom projectionPAC learningintersections of halfspaces

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• Learning an intersection of a constant number of halfspaces over a uniform distribution
• On the hardness of learning intersections of two halfspaces
• Learning intersections and thresholds of halfspaces
• Learning intersections of halfspaces with a margin
• Learning Theory

Cited in

(15)

• The hardest halfspace
• scientific article; zbMATH DE number 774005 (Why is no real title available?)
• On Exact Learning Halfspaces with Random Consistent Hypothesis Oracle
• Learning Theory
• Baum’s Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions
• Attribute-efficient learning of halfspaces with malicious noise: near-optimal label complexity and noise tolerance
• Learning kernel-based halfspaces with the 0-1 loss
• The average sensitivity of an intersection of half spaces
• Improved Lower Bounds for Learning Intersections of Halfspaces
• Fooling Polytopes
• Learning intersections and thresholds of halfspaces
• On the hardness of learning intersections of two halfspaces
• The average sensitivity of an intersection of half spaces
• Unconditional lower bounds for learning intersections of halfspaces
• Learning intersections of halfspaces with a margin

This page was built for publication: A random-sampling-based algorithm for learning intersections of halfspaces

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