Distributional PAC-Learning from Nisan's Natural Proofs

Carmosino et al. (2016) demonstrated that natural proofs of circuit lower bounds for $\mathrm{\Lambda }$ imply efficient algorithms for learning $\mathrm{\Lambda }$-circuits, but only over $\mathit{\text{the}}\mathit{\text{uniform}}\mathit{\text{distribution}}$, with $\mathit{\text{membership}}\mathit{\text{queries}}$, and provided ${\text{AC}}^0[p]\subseteq \mathrm{\Lambda }$. We consider whether this implication can be generalized to $\mathrm{\Lambda }\supseteq ̸{\text{AC}}^0[p]$, and to learning algorithms which use only random examples and learn over arbitrary example distributions (Valiant’s PAC-learning model). We first observe that, if, for any circuit class $\mathrm{\Lambda }$, there is an implication from natural proofs for $\mathrm{\Lambda }$ to PAC-learning for $\mathrm{\Lambda }$, then standard assumptions from lattice-based cryptography do not hold. In particular, we observe that depth-2 majority circuits are a (conditional) counter example to the implication, since Nisan (1993) gave a natural proof, but Klivans and Sherstov (2009) showed hardness of PAC-learning under lattice-based assumptions. We thus ask: what learning algorithms can we reasonably expect to follow from Nisan’s natural proofs? Our main result is that all natural proofs arising from a type of communication complexity argument, including Nisan’s, imply PAC-learning algorithms in a new $\mathit{\text{distributional}}$ variant (i.e., an ``average-case’’ relaxation) of Valiant’s PAC model. Our distributional PAC model is stronger than the average-case prediction model of Blum et al. (1993) and the heuristic PAC model of Nanashima (2021), and has several important properties which make it of independent interest, such as being $\mathit{\text{boosting-friendly}}$. The main applications of our result are new distributional PAC-learning algorithms for depth-2 majority circuits, polytopes and DNFs over natural target distributions, as well as the nonexistence of encoded-input weak PRFs that can be evaluated by depth-2 majority circuits.