Testing piecewise functions

DOI10.1016/J.TCS.2018.05.019MaRDI QIDQ1786590zbMATH OpenOpenAlexFDO

Authors Steve Hanneke, Liu Yang

Publication date 24 September 2018

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

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

zbMATH Keywords

learning theoryproperty testingreal-valued functionsactive testing

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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)