Testing piecewise functions

DOI10.1016/J.TCS.2018.05.019zbMATH Open1400.68260arXiv1706.07669OpenAlexW2963411165MaRDI QIDQ1786590FDOQ1786590

Authors: Steve Hanneke, Liu Yang 

Publication date: 24 September 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: This work explores the query complexity of property testing for general piecewise functions on the real line, in the active and passive property testing settings. The results are proven under an abstract zero-measure crossings condition, which has as special cases piecewise constant functions and piecewise polynomial functions. We find that, in the active testing setting, the query complexity of testing general piecewise functions is independent of the number of pieces. We also identify the optimal dependence on the number of pieces in the query complexity of passive testing in the special case of piecewise constant functions.

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

Recommendations

• On active and passive testing
• Parameterized property testing of functions
• Parameterized property testing of functions
• Testing properties of graphs and functions
• Property testing and its connection to learning and approximation

zbMATH Keywords

learning theoryproperty testingreal-valued functionsactive testing

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Randomized algorithms (68W20)

Cites Work

• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Learnability and the Vapnik-Chervonenkis dimension
• Property testing and its connection to learning and approximation
• Spot-checkers
• Testing and reconstruction of Lipschitz functions with applications to data privacy
• Algorithmic and analysis techniques in property testing
• Testing monotonicity
• A theory of the learnable
• Title not available (Why is that?)
• A general lower bound on the number of examples needed for learning
• Theory of Classification: a Survey of Some Recent Advances
• Theory of Disagreement-Based Active Learning
• Active learning
• Optimal unateness testers for real-valued functions: Adaptivity helps
• Introduction to Property Testing
• Testing problems with sublearning sample complexity
• The optimal sample complexity of PAC learning
• Testing surface area

Cited In (2)

• On active and passive testing
• Testing elementary function identities using CAD

This page was built for publication: Testing piecewise functions

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