by , , , ,
Abstract:
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 \log_2 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 (WHT), our novel algorithms operate with recently introduced \em 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.
Reference:
Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases C. Wendler, A. Amrollahi, B. Seifert, A. Krause, M. PuschelIn Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021
Bibtex Entry:
@inproceedings{andisheh2021_nonorthogonal_fourierthat 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.},
	author = {Chris Wendler and Andisheh Amrollahi and Bastian Seifert and Andreas Krause and Markus Puschel},
	booktitle = {Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI)},
    month = {February},
	title = {Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases},
	year = {2021}}