# Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases

arXiv: https://arxiv.org/abs/2010.00439 · HTML: https://mlsanity.com/paper/2010.00439/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Oct 2020.

## Built on by (most cited first, 7 of 7)

- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [Learning to Understand: Identifying Interactions via the M"obius Transform](https://mlsanity.com/paper/2402.02631/) (2024)
- [Advances in Set Function Learning: A Survey of Techniques and Applications](https://mlsanity.com/paper/2501.14991/) (2025)
- [Learning Set Functions with Implicit Differentiation](https://mlsanity.com/paper/2412.11239/) (2024)
- [CUBE: Contrastive Understanding by Balanced Experiments](https://mlsanity.com/paper/2509.10825/) (2025)
- [Adaptive Sparse M"obius Transforms for Learning Polynomials](https://mlsanity.com/paper/2602.06246/) (2026)
- [Advancing Optimal Subset Oracle via Learning Relaxation of Neural Set Functions](https://mlsanity.com/paper/2607.11555/) (2026)

## Abstract (arXiv)

Many applications of machine learning on discrete domains, such as learning preference functions in recommender systems or auctions, can be reduced to estimating a set function that is sparse in the Fourier domain. In this work, we present a new family of algorithms for learning Fourier-sparse set functions. They require at most nk - k log2 k + k queries (set function evaluations), under mild conditions on the Fourier coefficients, where n is the size of the ground set and k the number of non-zero Fourier coefficients. In contrast to other work that focused on the orthogonal Walsh-Hadamard transform, our novel algorithms operate with recently introduced non-orthogonal Fourier transforms that offer different notions of Fourier-sparsity. These naturally arise when modeling, e.g., sets of items forming substitutes and complements. We demonstrate effectiveness on several real-world applications.