Efficiently Learning Fourier Sparse Set Functions
Efficiently Learning Fourier Sparse Set Functions
复制标题
高效学习傅里叶稀疏集函数
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
A. Krause
中科院分区：
文献类型：
--
作者：
Andisheh Amrollahi;A. Zandieh;M. Kapralov;A. Krause
学习集函数在许多领域都是一个关键的挑战，从示意图到带有离散参数的黑盒优化。在这篇文章中，我们考虑定义在大小为$n$的基本集合上且在富里叶域中是稀疏的(比如$k$-稀疏)的集合函数的有效学习问题。这是一个广泛的类，包括图和超图割函数、决策树等。我们的主要贡献是第一个算法，它允许学习函数的傅立叶支持只包含低次(比方说次数$d=o(N)$)多项式，使用$O(K D Log N)$样本复杂性和运行时$O(kn log^2 k log n log d)$。这意味着，具有$k$边的稀疏图可以第一次从割值的$O(K Logn)$观测中学习，并且在顶点数上是线性的。我们的算法还可以有效地学习小深度的决策树(和)。该算法利用了稀疏傅里叶变换文献中的技术，并且易于实现。最后，我们还开发了一个高效的健壮版本的算法，并证明了在没有任何关于噪声的统计假设的情况下，$ell_2/ell_2$近似保证。
Learning set functions is a key challenge arising in many domains, ranging from sketching graphs to black-box optimization with discrete parameters. In this paper we consider the problem of efficiently learning set functions that are defined over a ground set of size $n$ and that are sparse (say $k$-sparse) in the Fourier domain. This is a wide class, that includes graph and hypergraph cut functions, decision trees and more. Our central contribution is the first algorithm that allows learning functions whose Fourier support only contains low degree (say degree $d=o(n)$) polynomials using $O(k d log n)$ sample complexity and runtime $O( kn log^2 k log n log d)$. This implies that sparse graphs with $k$ edges can, for the first time, be learned from $O(k log n)$ observations of cut values and in linear time in the number of vertices. Our algorithm can also efficiently learn (sums of) decision trees of small depth. The algorithm exploits techniques from the sparse Fourier transform literature and is easily implementable. Lastly, we also develop an efficient robust version of our algorithm and prove $ell_2/ell_2$ approximation guarantees without any statistical assumptions on the noise.