Learning Coverage Functions and Private Release of Marginals

Vitaly Feldman, Pravesh Kothari

Proceedings of The 27th Conference on Learning Theory, PMLR 35:679-702, 2014.

Abstract

We study the problem of approximating and learning coverage functions. A function c: 2^[n] →\mathbfR^+ is a coverage function, if there exists a universe U with non-negative weights w(u) for each u ∈U and subsets A_1, A_2, \ldots, A_n of U such that c(S) = \sum_u ∈\cup_i ∈S A_i w(u). Alternatively, coverage functions can be described as non-negative linear combinations of monotone disjunctions. They are a natural subclass of submodular functions and arise in a number of applications. We give an algorithm that for any γ,δ>0, given random and uniform examples of an unknown coverage function c, finds a function h that approximates c within factor 1+γon all but δ-fraction of the points in time poly(n,1/γ,1/δ). This is the first fully-polynomial algorithm for learning an interesting class of functions in the demanding PMAC model of Balcan and Harvey (2011). Our algorithms are based on several new structural properties of coverage functions. Using the results in (Feldman and Kothari, 2014), we also show that coverage functions are learnable agnostically with excess \ell_1-error εover all product and symmetric distributions in time n^\log(1/ε). In contrast, we show that, without assumptions on the distribution, learning coverage functions is at least as hard as learning polynomial-size disjoint DNF formulas, a class of functions for which the best known algorithm runs in time 2^\tildeO(n^1/3) (Klivans and Servedio, 2004). As an application of our learning results, we give simple differentially-private algorithms for releasing monotone conjunction counting queries with low \em average error. In particular, for any k ≤n, we obtain private release of k-way marginals with average error \barα in time n^O(\log(1/\barα)).

Cite this Paper

BibTeX

@InProceedings{pmlr-v35-feldman14a,
title = {Learning Coverage Functions and Private Release of Marginals},
author = {Feldman, Vitaly and Kothari, Pravesh},
booktitle = {Proceedings of The 27th Conference on Learning Theory},
pages = {679--702},
year = {2014},
editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba},
volume = {35},
series = {Proceedings of Machine Learning Research},
address = {Barcelona, Spain},
month = {13--15 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v35/feldman14a.pdf},
url = {https://proceedings.mlr.press/v35/feldman14a.html},
abstract = {We study the problem of approximating and learning coverage functions. A function c: 2^[n] →\mathbfR^+ is a coverage function, if there exists a universe U with non-negative weights w(u) for each u ∈U and subsets A_1, A_2, \ldots, A_n of U such that c(S) = \sum_u ∈\cup_i ∈S A_i w(u). Alternatively, coverage functions can be described as non-negative linear combinations of monotone disjunctions. They are a natural subclass of submodular functions and arise in a number of applications. We give an algorithm that for any γ,δ>0, given random and uniform examples of an unknown coverage function c, finds a function h that approximates c within factor 1+γon all but δ-fraction of the points in time poly(n,1/γ,1/δ). This is the first fully-polynomial algorithm for learning an interesting class of functions in the demanding PMAC model of Balcan and Harvey (2011). Our algorithms are based on several new structural properties of coverage functions. Using the results in (Feldman and Kothari, 2014), we also show that coverage functions are learnable agnostically with excess \ell_1-error εover all product and symmetric distributions in time n^\log(1/ε). In contrast, we show that, without assumptions on the distribution, learning coverage functions is at least as hard as learning polynomial-size disjoint DNF formulas, a class of functions for which the best known algorithm runs in time 2^\tildeO(n^1/3) (Klivans and Servedio, 2004). As an application of our learning results, we give simple differentially-private algorithms for releasing monotone conjunction counting queries with low \em average error. In particular, for any k ≤n, we obtain private release of k-way marginals with average error \barα in time n^O(\log(1/\barα)). }
}

Endnote

%0 Conference Paper
%T Learning Coverage Functions and Private Release of Marginals
%A Vitaly Feldman
%A Pravesh Kothari
%B Proceedings of The 27th Conference on Learning Theory
%C Proceedings of Machine Learning Research
%D 2014
%E Maria Florina Balcan
%E Vitaly Feldman
%E Csaba Szepesvári
%F pmlr-v35-feldman14a
%I PMLR
%P 679--702
%U https://proceedings.mlr.press/v35/feldman14a.html
%V 35
%X We study the problem of approximating and learning coverage functions. A function c: 2^[n] →\mathbfR^+ is a coverage function, if there exists a universe U with non-negative weights w(u) for each u ∈U and subsets A_1, A_2, \ldots, A_n of U such that c(S) = \sum_u ∈\cup_i ∈S A_i w(u). Alternatively, coverage functions can be described as non-negative linear combinations of monotone disjunctions. They are a natural subclass of submodular functions and arise in a number of applications. We give an algorithm that for any γ,δ>0, given random and uniform examples of an unknown coverage function c, finds a function h that approximates c within factor 1+γon all but δ-fraction of the points in time poly(n,1/γ,1/δ). This is the first fully-polynomial algorithm for learning an interesting class of functions in the demanding PMAC model of Balcan and Harvey (2011). Our algorithms are based on several new structural properties of coverage functions. Using the results in (Feldman and Kothari, 2014), we also show that coverage functions are learnable agnostically with excess \ell_1-error εover all product and symmetric distributions in time n^\log(1/ε). In contrast, we show that, without assumptions on the distribution, learning coverage functions is at least as hard as learning polynomial-size disjoint DNF formulas, a class of functions for which the best known algorithm runs in time 2^\tildeO(n^1/3) (Klivans and Servedio, 2004). As an application of our learning results, we give simple differentially-private algorithms for releasing monotone conjunction counting queries with low \em average error. In particular, for any k ≤n, we obtain private release of k-way marginals with average error \barα in time n^O(\log(1/\barα)).

RIS

TY - CPAPER
TI - Learning Coverage Functions and Private Release of Marginals
AU - Vitaly Feldman
AU - Pravesh Kothari
BT - Proceedings of The 27th Conference on Learning Theory
DA - 2014/05/29
ED - Maria Florina Balcan
ED - Vitaly Feldman
ED - Csaba Szepesvári
ID - pmlr-v35-feldman14a
PB - PMLR
DP - Proceedings of Machine Learning Research
VL - 35
SP - 679
EP - 702
L1 - http://proceedings.mlr.press/v35/feldman14a.pdf
UR - https://proceedings.mlr.press/v35/feldman14a.html
AB - We study the problem of approximating and learning coverage functions. A function c: 2^[n] →\mathbfR^+ is a coverage function, if there exists a universe U with non-negative weights w(u) for each u ∈U and subsets A_1, A_2, \ldots, A_n of U such that c(S) = \sum_u ∈\cup_i ∈S A_i w(u). Alternatively, coverage functions can be described as non-negative linear combinations of monotone disjunctions. They are a natural subclass of submodular functions and arise in a number of applications. We give an algorithm that for any γ,δ>0, given random and uniform examples of an unknown coverage function c, finds a function h that approximates c within factor 1+γon all but δ-fraction of the points in time poly(n,1/γ,1/δ). This is the first fully-polynomial algorithm for learning an interesting class of functions in the demanding PMAC model of Balcan and Harvey (2011). Our algorithms are based on several new structural properties of coverage functions. Using the results in (Feldman and Kothari, 2014), we also show that coverage functions are learnable agnostically with excess \ell_1-error εover all product and symmetric distributions in time n^\log(1/ε). In contrast, we show that, without assumptions on the distribution, learning coverage functions is at least as hard as learning polynomial-size disjoint DNF formulas, a class of functions for which the best known algorithm runs in time 2^\tildeO(n^1/3) (Klivans and Servedio, 2004). As an application of our learning results, we give simple differentially-private algorithms for releasing monotone conjunction counting queries with low \em average error. In particular, for any k ≤n, we obtain private release of k-way marginals with average error \barα in time n^O(\log(1/\barα)).
ER -

APA

Feldman, V. & Kothari, P.. (2014). Learning Coverage Functions and Private Release of Marginals. Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:679-702 Available from https://proceedings.mlr.press/v35/feldman14a.html.