On Learning vs. Refutation

Salil Vadhan
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:1835-1848, 2017.

Abstract

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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v65-vadhan17a, title = {On Learning vs. Refutation}, author = {Vadhan, Salil}, booktitle = {Proceedings of the 2017 Conference on Learning Theory}, pages = {1835--1848}, year = {2017}, editor = {Kale, Satyen and Shamir, Ohad}, volume = {65}, series = {Proceedings of Machine Learning Research}, month = {07--10 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v65/vadhan17a/vadhan17a.pdf}, url = { http://proceedings.mlr.press/v65/vadhan17a.html }, abstract = {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.} }
Endnote
%0 Conference Paper %T On Learning vs. Refutation %A Salil Vadhan %B Proceedings of the 2017 Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Satyen Kale %E Ohad Shamir %F pmlr-v65-vadhan17a %I PMLR %P 1835--1848 %U http://proceedings.mlr.press/v65/vadhan17a.html %V 65 %X 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.
APA
Vadhan, S.. (2017). On Learning vs. Refutation. Proceedings of the 2017 Conference on Learning Theory, in Proceedings of Machine Learning Research 65:1835-1848 Available from http://proceedings.mlr.press/v65/vadhan17a.html .

Related Material