Approximate resilience, monotonicity, and the complexity of agnostic learning

DOI10.1137/1.9781611973730.34zbMath1371.68130arXiv1405.5268OpenAlexW1924023668MaRDI QIDQ5363038

Andrew Wan, Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan, Karl Wimmer

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1405.5268

Mathematics Subject Classification ID

Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25)

Related Items

On the Power of Learning from k-Wise Queries ⋮ Adversarial manifold estimation ⋮ BKW meets Fourier new algorithms for LPN with sparse parities ⋮ Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions