Unconditional lower bounds for learning intersections of halfspaces

DOI10.1007/S10994-007-5010-1MaRDI QIDQ1009217zbMATH OpenOpenAlexFDO

Authors Adam R. Klivans, Alexander A. Sherstov

Publication date 31 March 2009

Published in Machine Learning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10994-007-5010-1

zbMATH Keywords

query learningPAC learningpolynomial threshold functionshalfspace learningharmonic sieveintersections of halfspaceslower bounds for learningSQ learningstatistical queries

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Improved Lower Bounds for Learning Intersections of Halfspaces
• Learning intersections and thresholds of halfspaces
• On the hardness of learning intersections of two halfspaces
• A random-sampling-based algorithm for learning intersections of halfspaces
• Learning an intersection of a constant number of halfspaces over a uniform distribution

Cites work

• scientific article; zbMATH DE number 446494 (Why is no real title available?)
• scientific article; zbMATH DE number 46318 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• A polynomial-time algorithm for learning noisy linear threshold functions
• A theory of the learnable
• Cryptographic hardness for learning intersections of halfspaces
• Efficient noise-tolerant learning from statistical queries
• Harmonic Analysis of Polynomial Threshold Functions
• Hyperplane cuts of an n-cube
• Learning Decision Trees Using the Fourier Spectrum
• Learning Theory
• Learning intersections and thresholds of halfspaces
• New degree bounds for polynomial threshold functions
• New lower bounds for statistical query learning
• Noise-tolerant learning, the parity problem, and the statistical query model
• On the Fourier spectrum of monotone functions
• On the computational power of depth-2 circuits with threshold and modulo gates
• PAC learning intersections of halfspaces with membership queries
• PP is closed under intersection
• The expressive power of voting polynomials
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis

Cited in

(17)

• Learning Theory
• Learning intersections and thresholds of halfspaces
• A complete characterization of statistical query learning with applications to evolvability
• On the hardness of learning intersections of two halfspaces
• A Borsuk-Ulam lower bound for sign-rank and its applications
• Improved Lower Bounds for Learning Intersections of Halfspaces
• On XOR lemmas for the weight of polynomial threshold functions
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• The unbounded-error communication complexity of symmetric functions
• The average sensitivity of an intersection of half spaces
• scientific article; zbMATH DE number 2089966 (Why is no real title available?)
• A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
• Learning intersections of halfspaces with a margin
• A Uniform Lower Error Bound for Half-Space Learning
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• The average sensitivity of an intersection of half spaces
• Cryptographic hardness for learning intersections of halfspaces

This page was built for publication: Unconditional lower bounds for learning intersections of halfspaces

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