Agnostic Learning from Tolerant Natural Proofs
Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova
Abstract
We generalize the ``learning algorithms from natural properties'' framework of Carmosino et al. (CCC, 2016) to get agnostic learning algorithms from natural properties with extra features. We show that if a natural property (in the sense of Razborov and Rudich (JCSS, 1997)) is useful also against functions that are \emph{close} to the class of ``easy'' functions, rather than just against ``easy'' functions, then it can be used to get an agnostic learning algorithm over the uniform distribution with membership queries.
- For $AC^0[q]$, any prime $q$ (constant-depth circuits of polynomial size, with AND, OR, NOT, and MOD$_q$ gates of unbounded fanin), which happens to have a natural property with the requisite extra feature by [Razborov'87, Smolensky'87, Razborov Rudich '97], we obtain the first agnostic learning algorithm for $AC^0[q]$, for every prime $q$. Our algorithm runs in randomized quasi-polynomial time, uses membership queries, and outputs a circuit for a given boolean function $f\colon\{0,1\}^n\to\{0,1\}$ that agrees with $f$ on all but at most $(poly\log n)\cdot opt$ fraction of inputs, where $opt$ is the relative distance between $f$ and the closest function $h$ in the class $AC^0[q]$.
- For the ideal case, a natural proof of strongly exponential correlation circuit lower bounds against a circuit class $C$ containing $AC^0[2]$ (i.e., circuits of size $\exp(\Omega(n))$ cannot compute some $n$-variate function even with $\exp(-\Omega(n))$ advantage over random guessing) would yield a polynomial-time query agnostic learning algorithm for $C$ with the approximation error $O(opt)$.
Versions
- conference version in RANDOM 2017.