Agnostically learning Boolean functions with finite polynomial representation

DOI10.4230/LIPICS.ISAAC.2017.29MaRDI QIDQ5136248zbMATH OpenOpenAlexFDO

Authors Ning Ding

Publication date 25 November 2020

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/8272/pdf/LIPIcs-ISAAC-2017-29.pdf/

zbMATH Keywords

Boolean functionslow-degree polynomialsagnostic learning

Mathematics Subject Classification ID

Computational learning theory (68Q32) Boolean functions (06E30)

Recommendations

• Lower bounds for agnostic learning via approximate rank
• On agnostic learning of parities, monomials, and halfspaces
• A Lower Bound for Agnostically Learning Disjunctions
• Agnostically Learning Halfspaces
• Agnostic learning of disjunctions on symmetric distributions

Cites work

• scientific article; zbMATH DE number 5485565 (Why is no real title available?)
• A theory of the learnable
• Agnostically Learning Halfspaces
• An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
• Constant depth circuits, Fourier transform, and learnability
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Learnability beyond AC ⁰
• Learning DNF in time
• Learning and lower bounds for AC\(^{0}\) with threshold gates
• Learning intersections and thresholds of halfspaces
• On PAC learning algorithms for rich Boolean function classes
• On the Fourier spectrum of monotone functions
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the degree of Boolean functions as real polynomials
• Toward efficient agnostic learning
• When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one

Cited in

(3)

• scientific article; zbMATH DE number 1804109 (Why is no real title available?)
• scientific article; zbMATH DE number 1966612 (Why is no real title available?)
• Approximate resilience, monotonicity, and the complexity of agnostic learning

This page was built for publication: Agnostically learning Boolean functions with finite polynomial representation

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