## Abstract

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) = 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 n^{log(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 n^{O(og(l/α¯))}.

Original language | English (US) |
---|---|

Pages (from-to) | 679-702 |

Number of pages | 24 |

Journal | Journal of Machine Learning Research |

Volume | 35 |

State | Published - 2014 |

Event | 27th Conference on Learning Theory, COLT 2014 - Barcelona, Spain Duration: Jun 13 2014 → Jun 15 2014 |

## All Science Journal Classification (ASJC) codes

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