Improper learning by refuting

DOI10.4230/LIPICS.ITCS.2018.55MaRDI QIDQ4993325zbMATH OpenFDO

Authors Pravesh Kothari, Roi Livni

Publication date 15 June 2021

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2018.55

zbMATH Keywords

learning theoryRademacher complexitycomputational learning

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Recommendations

• scientific article; zbMATH DE number 2077179
• From average case complexity to improper learning complexity
• Complexity theoretic limitations on learning halfspaces
• On learning of functions refutably.
• On agnostic learning of parities, monomials, and halfspaces

Cites work

• 10.1162/153244303321897690
• A decision-theoretic generalization of on-line learning and an application to boosting
• Agnostically Learning Halfspaces
• Complexity theoretic limitations on learning halfspaces
• Computational Sample Complexity
• Computational and statistical tradeoffs via convex relaxation
• Computational limitations on learning from examples
• From average case complexity to improper learning complexity
• Optimal detection of sparse principal components in high dimension
• Property testing and its connection to learning and approximation
• Relations between average case complexity and approximation complexity
• Strongly refuting random CSPs below the spectral threshold

Cited in

(6)

• scientific article; zbMATH DE number 2080665 (Why is no real title available?)
• scientific article; zbMATH DE number 7758323 (Why is no real title available?)
• scientific article; zbMATH DE number 2077179 (Why is no real title available?)
• scientific article; zbMATH DE number 7561750 (Why is no real title available?)
• A moment-matching approach to testable learning and a new characterization of Rademacher complexity
• Learning with refutation

This page was built for publication: Improper learning by refuting

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