Embedding hard learning problems into Gaussian space

DOI10.4230/LIPICS.APPROX-RANDOM.2014.793MaRDI QIDQ2969663zbMATH OpenFDO

Authors Adam R. Klivans, Pravesh Kothari

Publication date 22 March 2017

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2014.793

zbMATH Keywords

agnostic learningdistribution-specific hardness of learningGaussian spacehalfspace-learning

Mathematics Subject Classification ID

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

Recommendations

• Agnostically Learning Halfspaces
• Complexity theoretic limitations on learning halfspaces
• Hardness of learning halfspaces with noise
• On agnostic learning of parities, monomials, and halfspaces

Cited in

(4)

• Four heads are better than three
• Depth separations in neural networks: what is actually being separated?
• Distribution-specific hardness of learning neural networks
• New statistical and computational results for learning junta distributions

This page was built for publication: Embedding hard learning problems into Gaussian space

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