aiqbench analysis
This research resolves a longstanding open problem by extending Boolean Fourier-based learning techniques to a broad class of non-product distributions via Bayesian network representations. The authors establish the learnability of DNF and decision trees under these generalized settings, providing an algorithm that functions even when the underlying distribution is unknown. While theoretically significant, the work remains confined to learning theory and does not yet offer immediate practical applications for current AI systems.
Learning DNF through Generalized Fourier Representations
arXiv:2506.01075v2 Announce Type: replace-cross Abstract: The Boolean Fourier representation has been widely used in learning theory, particularly for learning Disjunctive Normal Form (DNF) under uniform and product distributions. Extending these results to non-product distributions has remained a longstanding open problem. We address this challenge by introducing a generalized Fourier representation that enables learning under a broad class of non-product distributions. Our approach represents any distribution $D$ as a Bayesian network (BN) and derives a corresponding Fourier expansion. We show that standard Fourier-based learning techniques using membership queries to identify heavy coefficients can be adapted to this generalized representation with minor modifications. We prove that the $L_1$ spectral norm of conjunctions remains bounded under this expansion for difference-bounded tree BNs, significantly generalizing the known result for uniform distributions; matching lower bounds demonstrate the necessity of these constraints. Using these results, we establish the learnability of DNF and the agnostic learnability of decision trees under such distributions. Finally, we present an algorithm for learning difference-bounded tree BN distributions, extending our results to settings where the distribution is unknown.
Abstract:The Boolean Fourier representation has been widely used in learning theory, particularly for learning Disjunctive Normal Form (DNF) under uniform and product distributions. Extending these results to non-product distributions has remained a longstanding open problem. We address this challenge by introducing a generalized Fourier representation that enables learning under a broad class of non-product distributions. Our approach represents any distribution $D$ as a Bayesian network (BN) and derives a corresponding Fourier expansion. We show that standard Fourier-based learning techniques using membership queries to identify heavy coefficients can be adapted to this generalized representation with minor modifications. We prove that the $L_1$ spectral norm of conjunctions remains bounded under this expansion for difference-bounded tree BNs, significantly generalizing the known result for uniform distributions; matching lower bounds demonstrate the necessity of these constraints. Using these results, we establish the learnability of DNF and the agnostic learnability of decision trees under such distributions. Finally, we present an algorithm for learning difference-bounded tree BN distributions, extending our results to settings where the distribution is unknown.
Data Structures and Algorithms (cs.DS); Information Theory (cs.IT); Machine Learning (cs.LG)
arXiv:2506.01075 [cs.DS]
(or arXiv:2506.01075v2 [cs.DS] for this version)
https://doi.org/10.48550/arXiv.2506.01075 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 271 words
Related coverage
The Role of Fine-grained Harm Signals in LLM Safety
arXiv · Sep 18, 2026
The Generalized BEADS Representation: An Informationally Complete Visualization of Mixed Quantum States
arXiv · Oct 15, 2026
Generalized PINN-Based Inverse Estimation of Spatially Varying Heat Transfer Coefficients with Transfer Learning
arXiv · Oct 14, 2026
Differentiated Aggregation to Improve Generalization in Federated Learning
arXiv · Aug 27, 2026