Learning Coverage Functions

Summary

It is proved that any coverage function can be ǫ-approximated in l1 by a coverage function that depends only on O(1/ǫ) variables, which is tight up to a constant factor.

Keywords

Computer science

References

Learning Decision Trees Using the Fourier Sprectrum (Extended Abstract)Eyal Kushilevitz, Yishay Mansour — 1991
A note on concentration of submodular functionsJ. Vondrák — 2010
Selection of Relevant Features and Examples in Machine LearningAvrim L. Bluma, Pat Langley — 1997
Learning pseudo-Boolean k-DNF and submodular functionsSofya Raskhodnikova, Grigory Yaroslavtsev — 2012
On the degree of boolean functions as real polynomialsNoam Nisan, Márió Szegedy — 1992
MATROIDS AND SUBMODULAR FUNCTIONSFrank Dunstan — 1976
Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate AlgorithmsGérard Cornuéjols, Marshall L. Fisher, George L. Nemhauser — 1977
A combinatorial, strongly polynomial-time algorithm for minimizing submodular functionsSatoru Iwata, Lisa Fleischer, Satoru Fujishige — 2000
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingMichel X. Goemans, David P. Williamson — 1995
A Multiplicative Weights Mechanism for Privacy-Preserving Data AnalysisMoritz Hardt, Guy N. Rothblum — 2010
Optimal approximation for the submodular welfare problem in the value oracle modelJan Vondrák — 2008
On maximizing welfare when utility functions are subadditiveUriel Feige — 2006
Efficient noise-tolerant learning from statistical queriesMichael Kearns — 1998
Near-optimal sensor placements in Gaussian processesCarlos Guestrin, Andreas Krause, Ajit Paul Singh — 2005
A threshold of ln n for approximating set cover (preliminary version)Uriel Feige — 1996
Combinatorial auctions with decreasing marginal utilitiesBenny Lehmann, Daniel Lehmann, Noam Nisan — 2001
Practical privacy: the SuLQ frameworkAvrim Blum, Cynthia Dwork, Frank McSherry — 2005
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and JuntasGregory Valiant — 2012
On the degree of polynomials that approximate symmetric Boolean functions (preliminary version)Ramamohan Paturi — 1992
Optimal Bounds on Approximation of Submodular and XOS Functions by JuntasVitaly Feldman, Jan Vondrák — 2013

Cited by

Influence Function Learning in Information Diffusion NetworksNan Du, Yingyu Liang, Maria Florina Balcan — 2014
Nearly Tight Bounds on ℓ1 Approximation of Self-Bounding FunctionsVitaly Feldman, Pravesh K. Kothari, J. Vondrák — 2014
Lp-testingPiotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev — 2014
Optimal Bounds on Approximation of Submodular and XOS Functions by JuntasVitaly Feldman, Jan Vondrák — 2013
Faster private release of marginals on small databasesKarthekeyan Chandrasekaran, Justin Thaler, Jonathan Ullman — 2013
Privacy and the Complexity of Simple QueriesJonathan Ullman — 2013
Learning Time-Varying Coverage FunctionsNan Du, Yingyu Liang, Maria-Florina Balcan — 2014
Tight Bounds on ℓ1 Approximation and Learning of Self-Bounding FunctionsVitaly Feldman, Pravesh K. Kothari, J. Vondrák — 2014
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision TreesVitaly Feldman, Pravesh K. Kothari, J. Vondrák — 2013
Submodularity In Machine Learning and Artificial IntelligenceJeff Bilmes — 2022
Optimal bounds on approximation of submodular and XOS functions by juntasVitaly Feldman, Jan Vondrák — 2014
Privacy and the Complexity of Simple QueriesJ. Robert — 2016

Related papers

Privately releasing conjunctions and the statistical query barrierAnupam Gupta, Moritz Hardt, Aaron Roth — 2010
Learning pseudo-Boolean k-DNF and submodular functionsSofya Raskhodnikova, Grigory Yaroslavtsev — 2013
Combinatorial auctions with decreasing marginal utilitiesBenny Lehmann, Daniel Lehmann, Noam Nisan — 2005
A theory of the learnableLeslie G. Valiant — 1984
MATROIDS AND SUBMODULAR FUNCTIONSFrank Dunstan — 1976
Approximating Submodular Functions EverywhereGoemans, Michel X., Harvey, Nicholas J. A., Iwata, Satoru — 2009
Submodular Functions: Learnability, Structure, and OptimizationMaria-Florina Balcan, Nicholas J. A. Harvey — 2010