2014/05/27 by Vitaly Feldman, Feldman, Vitaly, Pravesh K. Kothari +1
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1405.6791
openalex publication_date 2014/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of approximating and learning disjunctions (or equivalently, conjunctions) on symmetric distributions over \0,1\n. Symmetric distributions are distributions whose PDF is invariant under any permutation of the variables. We give a simple proof that for every symmetric distribution D, there exists a set of n^O(log(1/ε)) functions S, such that for every disjunction c, there is function p, expressible as a linear combination of functions in S, such that p ε-approximates c in ℓ1 distance on D or Ex ∼ D[ |c(x)-p(x)|] ≤ ε. This directly gives an agnostic learning algorithm for disjunctions on symmetric distributions that runs in time n^O( log(1/ε)). The best known previous bound is nO(1/ε4) and follows from approximation of the more general class of halfspaces (Wimmer, 2010). We also show that there exists a symmetric distribution D, such that the minimum degree of a polynomial that 1/3-approximates the disjunction of all n variables is ℓ1 distance on D is Ω( √(n)). Therefore the learning result above cannot be achieved via ℓ1-regression with a polynomial basis used in most other agnostic learning algorithms. Our technique also gives a simple proof that for any product distribution D and every disjunction c, there exists a polynomial p of degree O(log(1/ε)) such that p ε-approximates c in ℓ1 distance on D. This was first proved by Blais et al. (2008) via a more involved argument.