New Statistical and Computational Results for Learning Junta Distributions
This addresses a foundational problem in computational learning theory, with implications for understanding the hardness of distribution learning, but it is incremental in building on prior work on LPN.
The paper tackles the problem of learning junta distributions on binary vectors, showing it is computationally equivalent to learning parity with noise (LPN) and designing an algorithm with optimal statistical complexity up to polylog factors.
We study the problem of learning junta distributions on $\{0, 1\}^n$, where a distribution is a $k$-junta if its probability mass function depends on a subset of at most $k$ variables. We make two main contributions: - We show that learning $k$-junta distributions is \emph{computationally} equivalent to learning $k$-parity functions with noise (LPN), a landmark problem in computational learning theory. - We design an algorithm for learning junta distributions whose statistical complexity is optimal, up to polylogarithmic factors. Computationally, our algorithm matches the complexity of previous (non-sample-optimal) algorithms. Combined, our two contributions imply that our algorithm cannot be significantly improved, statistically or computationally, barring a breakthrough for LPN.