Learning Fourier Sparse Set Functions

Peter Stobbe, Andreas Krause
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:1125-1133, 2012.

Abstract

Can we learn a sparse graph from observing the value of a few random cuts? This and more general problems can be reduced to the challenge of learning set functions known to have sparse Fourier support contained in some collection. We prove that if we choose O(k log^4 n) sets uniformly at random, then with high probability, observing any k-sparse function on those sets is sufficient to recover that function exactly. We further show that other properties, such as symmetry or submodularity imply structure in the Fourier spectrum, which can be exploited to further reduce sample complexity. One interesting special case is that it suffices to observe O(|E| log^4 |V|) values of a cut function to recover a graph. We demonstrate the effectiveness of our results on two real-world reconstruction problems: graph sketching and obtaining fast approximate surrogates to expensive submodular objective functions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-stobbe12, title = {Learning Fourier Sparse Set Functions}, author = {Stobbe, Peter and Krause, Andreas}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {1125--1133}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/stobbe12/stobbe12.pdf}, url = {https://proceedings.mlr.press/v22/stobbe12.html}, abstract = {Can we learn a sparse graph from observing the value of a few random cuts? This and more general problems can be reduced to the challenge of learning set functions known to have sparse Fourier support contained in some collection. We prove that if we choose O(k log^4 n) sets uniformly at random, then with high probability, observing any k-sparse function on those sets is sufficient to recover that function exactly. We further show that other properties, such as symmetry or submodularity imply structure in the Fourier spectrum, which can be exploited to further reduce sample complexity. One interesting special case is that it suffices to observe O(|E| log^4 |V|) values of a cut function to recover a graph. We demonstrate the effectiveness of our results on two real-world reconstruction problems: graph sketching and obtaining fast approximate surrogates to expensive submodular objective functions.} }
Endnote
%0 Conference Paper %T Learning Fourier Sparse Set Functions %A Peter Stobbe %A Andreas Krause %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-stobbe12 %I PMLR %P 1125--1133 %U https://proceedings.mlr.press/v22/stobbe12.html %V 22 %X Can we learn a sparse graph from observing the value of a few random cuts? This and more general problems can be reduced to the challenge of learning set functions known to have sparse Fourier support contained in some collection. We prove that if we choose O(k log^4 n) sets uniformly at random, then with high probability, observing any k-sparse function on those sets is sufficient to recover that function exactly. We further show that other properties, such as symmetry or submodularity imply structure in the Fourier spectrum, which can be exploited to further reduce sample complexity. One interesting special case is that it suffices to observe O(|E| log^4 |V|) values of a cut function to recover a graph. We demonstrate the effectiveness of our results on two real-world reconstruction problems: graph sketching and obtaining fast approximate surrogates to expensive submodular objective functions.
RIS
TY - CPAPER TI - Learning Fourier Sparse Set Functions AU - Peter Stobbe AU - Andreas Krause BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-stobbe12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 1125 EP - 1133 L1 - http://proceedings.mlr.press/v22/stobbe12/stobbe12.pdf UR - https://proceedings.mlr.press/v22/stobbe12.html AB - Can we learn a sparse graph from observing the value of a few random cuts? This and more general problems can be reduced to the challenge of learning set functions known to have sparse Fourier support contained in some collection. We prove that if we choose O(k log^4 n) sets uniformly at random, then with high probability, observing any k-sparse function on those sets is sufficient to recover that function exactly. We further show that other properties, such as symmetry or submodularity imply structure in the Fourier spectrum, which can be exploited to further reduce sample complexity. One interesting special case is that it suffices to observe O(|E| log^4 |V|) values of a cut function to recover a graph. We demonstrate the effectiveness of our results on two real-world reconstruction problems: graph sketching and obtaining fast approximate surrogates to expensive submodular objective functions. ER -
APA
Stobbe, P. & Krause, A.. (2012). Learning Fourier Sparse Set Functions. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:1125-1133 Available from https://proceedings.mlr.press/v22/stobbe12.html.

Related Material