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.

Related Material