Learning DNF Expressions from Fourier Spectrum

Vitaly Feldman
Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:17.1-17.19, 2012.

Abstract

Since its introduction by Valiant in 1984, PAC learning of DNF expressions remains one of the central problems in learning theory. We consider this problem in the setting where the underlying distribution is uniform, or more generally, a product distribution. Kalai, Samorodnitsky, and Teng (2009b) showed that in this setting a DNF expression can be efficiently approximated from its “heavy” low-degree Fourier coefficients alone. This is in contrast to previous approaches where boosting was used and thus Fourier coefficients of the target function modified by various distributions were needed. This property is crucial for learning of DNF expressions over smoothed product distributions, a learning model introduced by Kalai et al. (2009b) and inspired by the seminal smoothed analysis model of Spielman and Teng (2004). We introduce a new approach to learning (or approximating) a polynomial threshold functions which is based on creating a function with range [-1, 1] that approximately agrees with the unknown function on low-degree Fourier coefficients. We then describe conditions under which this is sufficient for learning polynomial threshold functions. Our approach yields a new, simple algorithm for approximating any polynomial-size DNF expression from its “heavy” low-degree Fourier coefficients alone. This algorithm greatly simplifies the proof of learnability of DNF expressions over smoothed product distributions and is simpler than all previous algorithm for PAC learning of DNF expression using membership queries. We also describe an application of our algorithm to learning monotone DNF expressions over product distributions. Building on the work of Servedio (2004), we give an algorithm that runs in time poly((\emphs⋅ log (\emphs/ε))^log (\emphs/ε), \emphn), where \emphs is the size of the DNF expression and ε is the accuracy. This improves on poly((\emphs⋅ log (\emphns/ε))^log (\emphs/ε)⋅ log(1/ε), \emphn) bound of Servedio (2004).

Cite this Paper

BibTeX
@InProceedings{pmlr-v23-feldman12b, title = {Learning DNF Expressions from Fourier Spectrum}, author = {Feldman, Vitaly}, booktitle = {Proceedings of the 25th Annual Conference on Learning Theory}, pages = {17.1--17.19}, year = {2012}, editor = {Mannor, Shie and Srebro, Nathan and Williamson, Robert C.}, volume = {23}, series = {Proceedings of Machine Learning Research}, address = {Edinburgh, Scotland}, month = {25--27 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v23/feldman12b/feldman12b.pdf}, url = {https://proceedings.mlr.press/v23/feldman12b.html}, abstract = {Since its introduction by Valiant in 1984, PAC learning of DNF expressions remains one of the central problems in learning theory. We consider this problem in the setting where the underlying distribution is uniform, or more generally, a product distribution. Kalai, Samorodnitsky, and Teng (2009b) showed that in this setting a DNF expression can be efficiently approximated from its “heavy” low-degree Fourier coefficients alone. This is in contrast to previous approaches where boosting was used and thus Fourier coefficients of the target function modified by various distributions were needed. This property is crucial for learning of DNF expressions over smoothed product distributions, a learning model introduced by Kalai et al. (2009b) and inspired by the seminal smoothed analysis model of Spielman and Teng (2004). We introduce a new approach to learning (or approximating) a polynomial threshold functions which is based on creating a function with range [-1, 1] that approximately agrees with the unknown function on low-degree Fourier coefficients. We then describe conditions under which this is sufficient for learning polynomial threshold functions. Our approach yields a new, simple algorithm for approximating any polynomial-size DNF expression from its “heavy” low-degree Fourier coefficients alone. This algorithm greatly simplifies the proof of learnability of DNF expressions over smoothed product distributions and is simpler than all previous algorithm for PAC learning of DNF expression using membership queries. We also describe an application of our algorithm to learning monotone DNF expressions over product distributions. Building on the work of Servedio (2004), we give an algorithm that runs in time poly((\emphs⋅ log (\emphs/ε))^log (\emphs/ε), \emphn), where \emphs is the size of the DNF expression and ε is the accuracy. This improves on poly((\emphs⋅ log (\emphns/ε))^log (\emphs/ε)⋅ log(1/ε), \emphn) bound of Servedio (2004).} }
Endnote
%0 Conference Paper %T Learning DNF Expressions from Fourier Spectrum %A Vitaly Feldman %B Proceedings of the 25th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2012 %E Shie Mannor %E Nathan Srebro %E Robert C. Williamson %F pmlr-v23-feldman12b %I PMLR %P 17.1--17.19 %U https://proceedings.mlr.press/v23/feldman12b.html %V 23 %X Since its introduction by Valiant in 1984, PAC learning of DNF expressions remains one of the central problems in learning theory. We consider this problem in the setting where the underlying distribution is uniform, or more generally, a product distribution. Kalai, Samorodnitsky, and Teng (2009b) showed that in this setting a DNF expression can be efficiently approximated from its “heavy” low-degree Fourier coefficients alone. This is in contrast to previous approaches where boosting was used and thus Fourier coefficients of the target function modified by various distributions were needed. This property is crucial for learning of DNF expressions over smoothed product distributions, a learning model introduced by Kalai et al. (2009b) and inspired by the seminal smoothed analysis model of Spielman and Teng (2004). We introduce a new approach to learning (or approximating) a polynomial threshold functions which is based on creating a function with range [-1, 1] that approximately agrees with the unknown function on low-degree Fourier coefficients. We then describe conditions under which this is sufficient for learning polynomial threshold functions. Our approach yields a new, simple algorithm for approximating any polynomial-size DNF expression from its “heavy” low-degree Fourier coefficients alone. This algorithm greatly simplifies the proof of learnability of DNF expressions over smoothed product distributions and is simpler than all previous algorithm for PAC learning of DNF expression using membership queries. We also describe an application of our algorithm to learning monotone DNF expressions over product distributions. Building on the work of Servedio (2004), we give an algorithm that runs in time poly((\emphs⋅ log (\emphs/ε))^log (\emphs/ε), \emphn), where \emphs is the size of the DNF expression and ε is the accuracy. This improves on poly((\emphs⋅ log (\emphns/ε))^log (\emphs/ε)⋅ log(1/ε), \emphn) bound of Servedio (2004).
RIS
TY - CPAPER TI - Learning DNF Expressions from Fourier Spectrum AU - Vitaly Feldman BT - Proceedings of the 25th Annual Conference on Learning Theory DA - 2012/06/16 ED - Shie Mannor ED - Nathan Srebro ED - Robert C. Williamson ID - pmlr-v23-feldman12b PB - PMLR DP - Proceedings of Machine Learning Research VL - 23 SP - 17.1 EP - 17.19 L1 - http://proceedings.mlr.press/v23/feldman12b/feldman12b.pdf UR - https://proceedings.mlr.press/v23/feldman12b.html AB - Since its introduction by Valiant in 1984, PAC learning of DNF expressions remains one of the central problems in learning theory. We consider this problem in the setting where the underlying distribution is uniform, or more generally, a product distribution. Kalai, Samorodnitsky, and Teng (2009b) showed that in this setting a DNF expression can be efficiently approximated from its “heavy” low-degree Fourier coefficients alone. This is in contrast to previous approaches where boosting was used and thus Fourier coefficients of the target function modified by various distributions were needed. This property is crucial for learning of DNF expressions over smoothed product distributions, a learning model introduced by Kalai et al. (2009b) and inspired by the seminal smoothed analysis model of Spielman and Teng (2004). We introduce a new approach to learning (or approximating) a polynomial threshold functions which is based on creating a function with range [-1, 1] that approximately agrees with the unknown function on low-degree Fourier coefficients. We then describe conditions under which this is sufficient for learning polynomial threshold functions. Our approach yields a new, simple algorithm for approximating any polynomial-size DNF expression from its “heavy” low-degree Fourier coefficients alone. This algorithm greatly simplifies the proof of learnability of DNF expressions over smoothed product distributions and is simpler than all previous algorithm for PAC learning of DNF expression using membership queries. We also describe an application of our algorithm to learning monotone DNF expressions over product distributions. Building on the work of Servedio (2004), we give an algorithm that runs in time poly((\emphs⋅ log (\emphs/ε))^log (\emphs/ε), \emphn), where \emphs is the size of the DNF expression and ε is the accuracy. This improves on poly((\emphs⋅ log (\emphns/ε))^log (\emphs/ε)⋅ log(1/ε), \emphn) bound of Servedio (2004). ER -
APA
Feldman, V.. (2012). Learning DNF Expressions from Fourier Spectrum. Proceedings of the 25th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 23:17.1-17.19 Available from https://proceedings.mlr.press/v23/feldman12b.html.

Related Material