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 A 1 , A 2 , . . . , A n of U such that c(S) = u∈∪i∈S Ai 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 ℓ 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Õ (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 average error. In particular, for any k ≤ n, we obtain private release of k-way marginals with average errorᾱ in time n O(log(1/ᾱ)) .
Feldman and Kothari REF gave a fully polynomial time algorithm for learning succinct coverage functions in the PMAC model if the distribution is uniform.
Learning Coverage Functions and Private Release of Marginals
COLT 2014
arXiv: Learning
Computer Science Mathematics