On Learning vs. Refutation

Building on the work of Daniely et al. (STOC 2014, COLT 2016), we study the connection between computationally efficient PAC learning and refutation of constraint satisfaction problems. Specifically, we prove that for every concept class $\mathcal{P}$, PAC-learning $\mathcal{P}$ is \em polynomially equivalent to “random-right-hand-side-refuting” (“RRHS-refuting”) a dual class $\mathcal{P}^*$, where RRHS-refutation of a class $\mathcal{Q}$ refers to refuting systems of equations where the constraints are (worst-case) functions from the class $\mathcal{Q}$ but the right-hand-sides of the equations are uniform and independent random bits. The reduction from refutation to PAC learning can be viewed as an abstraction of (part of) the work of Daniely, Linial, and Shalev-Schwartz (STOC 2014). The converse, however, is new, and is based on a combination of techniques from pseudorandomness (Yao ‘82) with boosting (Schapire ‘90). In addition, we show that PAC-learning the class of $\mathit{DNF}$ formulas is polynomially equivalent to PAC-learning its dual class $\mathit{DNF}^*$, and thus PAC-learning $\mathit{DNF}$ is equivalent to RRHS-refutation of $\mathit{DNF}$, suggesting an avenue to obtain stronger lower bounds for PAC-learning $\mathit{DNF}$ than the quasipolynomial lower bound that was obtained by Daniely and Shalev-Schwartz (COLT 2016) assuming the hardness of refuting $k$-SAT.