Lower bounds on learning random structures with statistical queries

DOI10.1007/978-3-642-16108-7_18zbMATH Open1306.68047OpenAlexW2106435631MaRDI QIDQ4930699FDOQ4930699

Authors: Dana Angluin, David Eisenstat, Lev Reyzin, Aryeh Kontorovich 

Publication date: 1 October 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16108-7_18

Recommendations

• scientific article; zbMATH DE number 2089365
• New lower bounds for statistical query learning
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• On learning random DNF formulas under the uniform distribution

Mathematics Subject Classification ID

Computational learning theory (68Q32) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cited In (10)

• VC bounds on the cardinality of nearly orthogonal function classes
• Learning a Random DFA from Uniform Strings and State Information
• General lower bounds on the query complexity within the exact learning model
• General bounds on statistical query learning and PAC learning with noise via hypothesis boosting
• The state complexity of random DFAs
• New lower bounds for statistical query learning
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• Diameter and stationary distribution of random \(r\)-out digraphs
• An inequality involving the \(\ell_1, \ell_2,\) and \(\ell_\infty\) norms
• Title not available (Why is that?)

This page was built for publication: Lower bounds on learning random structures with statistical queries

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