Learning Boolean functions with concentrated spectra
This paper discusses the theory and application of learning Boolean functions that are concentrated in the Fourier domain. We first estimate the VC dimension of this function class in order to establish a small sample complexity of learning in this case. Next, we propose a computationally efficient method of empirical risk minimization, and we apply this method to the MNIST database of handwritten digits. These results demonstrate the effectiveness of our model for modern classification tasks. We conclude with a list of open problems for future investigation.
Code (0)
등록된 구현이 없습니다.
Tasks
General ClassificationSimilar Papers 제목 키워드 기반
A Sharper Picture of Generalization in Transformers
We study transformers' generalization behavior on boolean domains from the perspective of the Fourier spectra of their target functions. In contrast to prior work (Edelman et al., 2022; Trauger & Tosh, 2024), which deriv…
The More the Merrier: On Evolving Five-valued Spectra Boolean Functions
Evolving Boolean functions with specific properties is an interesting optimization problem since, depending on the combination of properties and Boolean function size, the problem can range from very simple to (almost) i…
NegaBent, No Regrets: Evolving Spectrally Flat Boolean Functions
Negabent Boolean functions are defined by having a flat magnitude spectrum under the nega-Hadamard transform. They exist in both even and odd dimensions, and the subclass of functions that are simultaneously bent and neg…
A Search for Nonlinear Balanced Boolean Functions by Leveraging Phenotypic Properties
In this paper, we consider the problem of finding perfectly balanced Boolean functions with high non-linearity values. Such functions have extensive applications in domains such as cryptography and error-correcting codin…
Spatial-Slepian Transform on the Sphere
We present spatial-Slepian transform~(SST) for the representation of signals on the sphere to support localized signal analysis. We use well-optimally concentrated Slepian functions, obtained by solving the Slepian spati…