Learning with Distributional Inverters

Eric Binnendyk, Marco Carmosino, Antonina Kolokolova, R Ramyaa, Manuel Sabin
Proceedings of The 33rd International Conference on Algorithmic Learning Theory, PMLR 167:90-106, 2022.

Abstract

We generalize the ``indirect learning'' technique of Furst et al. (1991) to reduce from learning a concept class over a samplable distribution $\mu$ to learning the same concept class over the uniform distribution. The reduction succeeds when the sampler for $\mu$ is both contained in the target concept class and efficiently invertible in the sense of Impagliazzo and Luby (1989). We give two applications. We show that $\mathsf{AC}^0[q]$ is learnable over any succinctly-described product distribution. $\mathsf{AC}^0[q]$ is the class of constant-depth Boolean circuits of polynomial size with AND, OR, NOT, and counting modulo $q$ gates of unbounded fanins. Our algorithm runs in randomized quasi-polynomial time and uses membership queries. If there is a strongly useful natural property in the sense of Razborov and Rudich (1997) — an efficient algorithm that can distinguish between random strings and strings of non-trivial circuit complexity — then general polynomial-sized Boolean circuits are learnable over any efficiently samplable distribution in randomized polynomial time, given membership queries to the target function.

Cite this Paper

BibTeX
@InProceedings{pmlr-v167-binnendyk22a, title = {Learning with Distributional Inverters}, author = {Binnendyk, Eric and Carmosino, Marco and Kolokolova, Antonina and Ramyaa, R and Sabin, Manuel}, booktitle = {Proceedings of The 33rd International Conference on Algorithmic Learning Theory}, pages = {90--106}, year = {2022}, editor = {Dasgupta, Sanjoy and Haghtalab, Nika}, volume = {167}, series = {Proceedings of Machine Learning Research}, month = {29 Mar--01 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v167/binnendyk22a/binnendyk22a.pdf}, url = {https://proceedings.mlr.press/v167/binnendyk22a.html}, abstract = {We generalize the ``indirect learning'' technique of Furst et al. (1991) to reduce from learning a concept class over a samplable distribution $\mu$ to learning the same concept class over the uniform distribution. The reduction succeeds when the sampler for $\mu$ is both contained in the target concept class and efficiently invertible in the sense of Impagliazzo and Luby (1989). We give two applications. We show that $\mathsf{AC}^0[q]$ is learnable over any succinctly-described product distribution. $\mathsf{AC}^0[q]$ is the class of constant-depth Boolean circuits of polynomial size with AND, OR, NOT, and counting modulo $q$ gates of unbounded fanins. Our algorithm runs in randomized quasi-polynomial time and uses membership queries. If there is a strongly useful natural property in the sense of Razborov and Rudich (1997) — an efficient algorithm that can distinguish between random strings and strings of non-trivial circuit complexity — then general polynomial-sized Boolean circuits are learnable over any efficiently samplable distribution in randomized polynomial time, given membership queries to the target function.} }
Endnote
%0 Conference Paper %T Learning with Distributional Inverters %A Eric Binnendyk %A Marco Carmosino %A Antonina Kolokolova %A R Ramyaa %A Manuel Sabin %B Proceedings of The 33rd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Sanjoy Dasgupta %E Nika Haghtalab %F pmlr-v167-binnendyk22a %I PMLR %P 90--106 %U https://proceedings.mlr.press/v167/binnendyk22a.html %V 167 %X We generalize the ``indirect learning'' technique of Furst et al. (1991) to reduce from learning a concept class over a samplable distribution $\mu$ to learning the same concept class over the uniform distribution. The reduction succeeds when the sampler for $\mu$ is both contained in the target concept class and efficiently invertible in the sense of Impagliazzo and Luby (1989). We give two applications. We show that $\mathsf{AC}^0[q]$ is learnable over any succinctly-described product distribution. $\mathsf{AC}^0[q]$ is the class of constant-depth Boolean circuits of polynomial size with AND, OR, NOT, and counting modulo $q$ gates of unbounded fanins. Our algorithm runs in randomized quasi-polynomial time and uses membership queries. If there is a strongly useful natural property in the sense of Razborov and Rudich (1997) — an efficient algorithm that can distinguish between random strings and strings of non-trivial circuit complexity — then general polynomial-sized Boolean circuits are learnable over any efficiently samplable distribution in randomized polynomial time, given membership queries to the target function.
APA
Binnendyk, E., Carmosino, M., Kolokolova, A., Ramyaa, R. & Sabin, M.. (2022). Learning with Distributional Inverters. Proceedings of The 33rd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 167:90-106 Available from https://proceedings.mlr.press/v167/binnendyk22a.html.

Related Material