Abstract
We study distributionfree property testing and learning problems where the unknown probability distribution is a product distribution over ℝ^d. For many important classes of functions, such as intersections of halfspaces, polynomial threshold functions, convex sets, and kalternating functions, the known algorithms either have complexity that depends on the support size of the distribution, or are proven to work only for specific examples of product distributions. We introduce a general method, which we call downsampling, that resolves these issues. Downsampling uses a notion of "rectilinear isoperimetry" for product distributions, which further strengthens the connection between isoperimetry, testing and learning. Using this technique, we attain new efficient distributionfree algorithms under product distributions on ℝ^d:
1) A simpler proof for nonadaptive, onesided monotonicity testing of functions [n]^d → {0,1}, and improved sample complexity for testing monotonicity over unknown product distributions, from O(d⁷) [Black, Chakrabarty, & Seshadhri, SODA 2020] to O(d³).
2) Polynomialtime agnostic learning algorithms for functions of a constant number of halfspaces, and constantdegree polynomial threshold functions;
3) An exp{O(dlog(dk))}time agnostic learning algorithm, and an exp{O(dlog(dk))}sample tolerant tester, for functions of k convex sets; and a 2^O(d) samplebased onesided tester for convex sets;
4) An exp{O(k√d)}time agnostic learning algorithm for kalternating functions, and a samplebased tolerant tester with the same complexity.
BibTeX  Entry
@InProceedings{harms_et_al:LIPIcs.ICALP.2022.71,
author = {Harms, Nathaniel and Yoshida, Yuichi},
title = {{Downsampling for Testing and Learning in Product Distributions}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {71:171:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16412},
URN = {urn:nbn:de:0030drops164123},
doi = {10.4230/LIPIcs.ICALP.2022.71},
annote = {Keywords: property testing, learning, monotonicity, halfspaces, intersections of halfspaces, polynomial threshold functions}
}
Keywords: 

property testing, learning, monotonicity, halfspaces, intersections of halfspaces, polynomial threshold functions 
Collection: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 
Issue Date: 

2022 
Date of publication: 

28.06.2022 