We prove that any submodular function f: 0,1 ^n -> 0,1,...,k can be represented as a pseudo-Boolean 2k-DNF formula. Pseudo-Boolean DNFs are a natural generalization of DNF representation for functions with integer range. Each term in such a formula has an associated integral constant. We show that an analog of Hastad's switching lemma holds for pseudo-Boolean k-DNFs if all constants associated with the terms of the formula are bounded. This allows us to generalize Mansour's PAC-learning algorithm for k-DNFs to pseudo-Boolean k-DNFs, and hence gives a PAC-learning algorithm with membership queries under the uniform distribution for submodular functions of the form f: 0,1 ^n -> 0,1,...,k . Our algorithm runs in time polynomial in n, k^ O(k k ) , 1 and log(1 ) and works even in the agnostic setting. The line of previous work on learning submodular functions [Balcan, Harvey (STOC '11), Gupta, Hardt, Roth, Ullman (STOC '11), Cheraghchi, Klivans, Kothari, Lee (SODA '12)] implies only n^ O(k) query complexity for learning submodular functions in this setting, for fixed epsilon and delta. Our learning algorithm implies a property tester for submodularity of functions f: 0,1 ^n -> 0, ..., k with query complexity polynomial in n for k=O(( n n)^ 1 2 ) and constant proximity parameter .
Cheraghchi al @cite_23 also work with additive error . Their learner is agnostic and only uses statistical queries . It produces a hypothesis which (with probability at least @math ) has the expected additive error @math with respect to a product distribution , where @math is the error of the best concept in the class. Their algorithm runs in time polynomial in @math and @math .
@cite_23
2942689850 2017753243 2106458073 1591252468
We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt an @math -fraction of the samples. Such questions have a rich history spanning statistics, machine learning, and theoretical computer science. Even in the most basic settings, the only known approaches are either computationally inefficient or lose dimension-dependent factors in their error guarantees. This raises the following question: Is high-dimensional agnostic distribution learning even possible, algorithmically? In this work, we obtain the first computationally efficient algorithms with dimension-independent error guarantees for agnostically learning several fundamental classes of high-dimensional distributions: (1) a single Gaussian, (2) a product distribution on the hypercube, (3) mixtures of two product distributions (under a natural balancedness condition), and (4) mixtures of spherical Gaussians. Our algorithms achieve error that is independent of the dimension, an... Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property of means to expectations uniformly over classes of random variables. Classes of real-valued functions enjoying such a property are also known as uniform Glivenko-Cantelli classes. In this paper, we prove, through a generalization of Sauer's lemma that may be interesting in its own right, a new characterization of uniform Glivenko-Cantelli classes. Our characterization yields Dudley, Gine´, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a Gine´, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a simple combinatorial quantity generalizing the Vapnik-Chervonenkis dimension. We apply this result to obtain the weakest combinatorial condition known to imply PAC learnability in the statistical regression (or “agnostic”) framework. Furthermore, we find a characterization of learnability in the probabilistic concept model, solving an open problem posed by Kearns and Schapire. These results show that the accuracy parameter plays a crucial role in determining the effective complexity of the learner's hypothesis class. We give a computationally efficient algorithm that learns (under distributional assumptions) a halfspace in the difficult agnostic framework of Kearns, Schapire, and Sellie [Mach. Learn., 17 (1994), pp. 115-141], where a learner is given access to a distribution on labelled examples but where the labelling may be arbitrary (similar to malicious noise). It constructs a hypothesis whose error rate on future examples is within an additive @math of the optimal halfspace, in time poly @math for any constant @math , for the uniform distribution over @math or unit sphere in @math as well as any log-concave distribution in @math . It also agnostically learns Boolean disjunctions in time @math with respect to any distribution. Our algorithm, which performs @math polynomial regression, is a natural noise-tolerant arbitrary-distribution generalization of the well-known “low-degree” Fourier algorithm of Linial, Mansour, and Nisan. We observe that significant improvements on the running time of our algorithm would yield the fastest known algorithm for learning parity with noise, a challenging open problem in computational learning theory. Given some arbitrary distribution D over 0, 1 n and arbitrary target function c∗, the problem of agnostic learning of disjunctions is to achieve an error rate comparable to the error OPTdisj of the best disjunction with respect to (D, c∗). Achieving error O(n · OPTdisj) + ǫ is trivial, and Winnow [13] achieves error O(r ·OPTdisj) + ǫ, where r is the number of relevant variables in the best disjunction. In recent work, Peleg [14] shows how to achieve a bound of O( √ n ·OPTdisj)+ ǫ in polynomial time. In this paper we improve on Peleg’s bound, giving a polynomial-time algorithm achieving a bound of O(n ·OPTdisj) + ǫ for any constant α > 0. The heart of the algorithm is a method for weak-learning when OPTdisj = O(1 n), which can then be fed into existing agnostic boosting procedures to achieve the desired guarantee.