Agnostically learning Boolean functions with finite polynomial representation

DOI10.4230/LIPICS.ISAAC.2017.29zbMATH Open1457.68132OpenAlexW2783848884MaRDI QIDQ5136248FDOQ5136248

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/

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

zbMATH Keywords

Boolean functionslow-degree polynomialsagnostic learning

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• Approximate resilience, monotonicity, and the complexity of agnostic learning
• Title not available (Why is that?)
• Title not available (Why is that?)

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)