Testing Distributions Against Bounded Distinguishers

2026-07-17 · Source: Machine Learning · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences · Depth: Expert, quick

Summary

A new distribution testing method, "identity testing with respect to fooling distance," is proposed for high-dimensional or continuous domains. This approach uses samples from an unknown distribution P to decide if P equals a fixed reference distribution P_ref, or if a distinguisher f from a bounded class F reveals a separation where |E_P[f] - E_{P_ref}[f]| > ε. The method offers sample-efficient algorithms and reveals connections between testable learning, verification of learning algorithms, and testing of structured distributions, extending the "A_k-testing" model. New results include testable proper learners for halfspaces and decision trees, a lower bound for testable PAC verification based on Rademacher complexity, a distribution-free verification protocol for disjoint unions of k multidimensional rectangles, and identity testers for decision tree distributions and low-degree polynomial densities over Boolean and continuous hypercube domains.

Key takeaway

For research scientists developing robust distribution comparison methods or verifying learning algorithms, this work introduces "identity testing with respect to fooling distance." This framework offers a sample-efficient approach for high-dimensional data, extending existing models. You should explore this method to improve the efficiency and applicability of your distribution testing protocols, especially when dealing with complex data structures like decision trees or polynomial densities over Boolean and continuous hypercube domains.

Key insights

The paper introduces "identity testing with respect to fooling distance" for high-dimensional distribution comparison.

Principles

• Testing with fooling distance is sample-efficient in high dimensions.
• Fooling distance connects testable learning and verification algorithms.
• Bounded distinguisher classes enable robust distribution comparisons.

Method

Use samples from an unknown distribution P to test against a reference P_ref by checking if a distinguisher f from a bounded class F shows |E_P[f] - E_{P_ref}[f]| > ε.

In practice

• Develop testable proper learners for halfspaces.
• Implement identity testers for decision tree distributions.
• Apply verification protocols for k multidimensional rectangles.

Topics

• Distribution Testing
• Fooling Distance
• Testable Learning
• Learning Algorithm Verification
• High-Dimensional Domains
• Computational Complexity

Best for: AI Scientist, Research Scientist

Related on AIssential

• Interactive Proofs for General Distribution Properties — Interactive proof systems can efficiently verify general distribution properties using limited samples and resources.
• Minimax Optimal Two-Sample Testing under Local Differential Privacy — Minimax optimal two-sample tests under LDP are developed for multinomial and continuous data.
• Incomplete U-Statistics of Equireplicate Designs: Berry-Esseen Bound and Efficient Construction — A hypergraph-theoretic approach enables Gaussian limiting distributions for incomplete U-statistics, even in degenerate cases.
• Identifying Information from Observations with Uncertainty and Novelty — Identification and sample complexity are unified across computational, statistical, and PAC-Bayes learning frameworks.
• Learning general conditional independence structures via the neighbourhood lattice — The neighbourhood lattice decomposition enables nonparametric, high-dimensional conditional independence learning without faithfulness assumptions.
• Zero-Flow Two-Sample Tests — The ZF2ST uses local sample misalignment and directional patterns for robust two-sample distribution testing with neural networks.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Machine Learning.