Testing Distributions Against Bounded Distinguishers

Motivated by the challenge of testing distributions over continuous or high-dimensional domains, we study distribution testing with respect to bounded classes of distinguishers. A representative task is to use samples from an unknown distribution P over a very large domain to decide between two cases: P = Pref for a fixed reference distribution Pref, or there exists a distinguisher f in a bounded class F which witnesses the separation |EP[f] − EPref[f]| > є. This is the task of identity testing with respect to fooling distance, a name inspired by the conceptual connection with pseudorandomness. (Formally, our model instantiates integral probability metrics from Boolean classes of bounded expressivity.) We show that testing with respect to fooling distance not only is a natural computational problem that admits sample-efficient algorithms even in high-dimensional settings, but it also reveals and underlies connections between three seemingly unrelated areas of study: testable learning, verification of learning algorithms, and testing of structured distributions (whose “Ak-testing” model our framework extends). These connections yield new results for all of these models, including 1) Testable proper learners using membership queries for halfspaces and decision trees. 2) A lower bound for testable PAC verification in terms of Rademacher complexity, and a distribution-free verification protocol for disjoint unions of k multidimensional rectangles. 3) Identity testers (with respect to total variation distance) for decision tree distributions and distributions with low-degree polynomial densities, over Boolean and continuous hypercube domains.

Paper

Similar papers

© 2026 NYSGPT2525 LLC