Lower bounds on learning random structures with statistical queries

DOI10.1007/978-3-642-16108-7_18MaRDI QIDQ4930699zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

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
• scientific article; zbMATH DE number 2089365 (Why is no real title available?)

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)