Learning Boolean functions with concentrated spectra
This work addresses classification problems in machine learning, but appears incremental as it builds on existing Fourier-based methods.
The paper tackles learning Boolean functions with concentrated Fourier spectra by estimating VC dimension for sample complexity and proposing an efficient empirical risk minimization method, demonstrating effectiveness on MNIST classification tasks.
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.