Learning coverage functions and private release of marginals

Vitaly Feldman, Pravesh Kothari

Research output: Contribution to journalConference articlepeer-review

19 Scopus citations


We study the problem of approximating and learning coverage functions. A function c: 2[n] → R+ is a coverage function, if there exists a universe U with non-negative weights w(u) for each u ∈ U and subsets A1, A2,..., An of U such that c(S) = 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 (2012). 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 ^i-error e over all product and symmetric distributions in time nlog(l/ε). 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Õ(n1/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 average error. In particular, for any k ≤ n, we obtain private release of k-way marginals with average error α¯ in time nO(og(l/α¯)).

Original languageEnglish (US)
Pages (from-to)679-702
Number of pages24
JournalJournal of Machine Learning Research
StatePublished - 2014
Event27th Conference on Learning Theory, COLT 2014 - Barcelona, Spain
Duration: Jun 13 2014Jun 15 2014

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence


Dive into the research topics of 'Learning coverage functions and private release of marginals'. Together they form a unique fingerprint.

Cite this