Unconditional lower bounds for learning intersections of halfspaces

DOI10.1007/s10994-007-5010-1zbMath1470.68056OpenAlexW2140283251MaRDI QIDQ1009217

Alexander A. Sherstov, Adam R. Klivans

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

PAC learningquery learningpolynomial threshold functionshalfspace learningharmonic sieveintersections of halfspaceslower bounds for learningSQ learningstatistical queries

Mathematics Subject Classification ID

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

Related Items (8)

Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length ⋮ Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization ⋮ The unbounded-error communication complexity of symmetric functions ⋮ A complete characterization of statistical query learning with applications to evolvability ⋮ On XOR lemmas for the weight of polynomial threshold functions ⋮ Cryptographic hardness for learning intersections of halfspaces ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio

Cites Work

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

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