Abstract:
We study the problems of learning and testing junta distributions on $\{-1,1\}^n$ with respect to the uniform distribution, where a distribution $p$ is a $k$-junta if its probability mass function $p(x)$ depends on a subset of at most $k$ variables.
The main contribution is an algorithm for finding relevant coordinates in a $k$-junta distribution with subcube conditioning (Bhattacharyya et al 2018., Canonne et al. 2019). We give two applications:
\begin{itemize}
\item
An algorithm for learning
$k$-junta distributions with
$\tilde{O}(k/\eps^2) \log n + O(2^k/\eps^2)$ subcube conditioning queries, and
\item
An algorithm for testing $k$-junta distributions with
$\tilde{O}((k + \sqrt{n})/\eps^2)$
subcube conditioning queries.
\end{itemize}
All our algorithms are optimal up to poly-logarithmic factors.
Our results show that subcube conditioning, as a natural model for accessing high-dimensional distributions, enables significant savings in
learning and testing junta distributions compared to the standard sampling model.
This addresses an open question posed by Aliakbarpour et al 2016.
