Learning with distributional inverters
This addresses learning theory problems for computational complexity researchers, offering incremental advances in distributional learning reductions.
The paper generalizes an indirect learning technique to reduce learning over samplable distributions to uniform distributions, showing that AC0[q] is learnable over succinct product distributions in randomized quasi-polynomial time with membership queries, and that if a strongly useful natural property exists, general polynomial-sized Boolean circuits are learnable over any efficiently samplable distribution in randomized polynomial time with membership queries.
We generalize the "indirect learning" technique of Furst et. al., 1991 to reduce from learning a concept class over a samplable distribution $μ$ to learning the same concept class over the uniform distribution. The reduction succeeds when the sampler for $μ$ is both contained in the target concept class and efficiently invertible in the sense of Impagliazzo & Luby, 1989. We give two applications. - We show that AC0[q] is learnable over any succinctly-described product distribution. AC0[q] is the class of constant-depth Boolean circuits of polynomial size with AND, OR, NOT, and counting modulo $q$ gates of unbounded fanins. Our algorithm runs in randomized quasi-polynomial time and uses membership queries. - If there is a strongly useful natural property in the sense of Razborov & Rudich 1997 -- an efficient algorithm that can distinguish between random strings and strings of non-trivial circuit complexity -- then general polynomial-sized Boolean circuits are learnable over any efficiently samplable distribution in randomized polynomial time, given membership queries to the target function