Unitary Branching Programs: Learnability and Lower Bounds

Fidel Ernesto Diaz Andino, Maria Kokkou, Mateus De Oliveira Oliveira, Farhad Vadiee
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:297-306, 2021.

Abstract

Bounded width branching programs are a formalism that can be used to capture the notion of non-uniform constant-space computation. In this work, we study a generalized version of bounded width branching programs where instructions are defined by unitary matrices of bounded dimension. We introduce a new learning framework for these branching programs that leverages on a combination of local search techniques with gradient descent over Riemannian manifolds. We also show that gapped, read-once branching programs of bounded dimension can be learned with a polynomial number of queries in the presence of a teacher. Finally, we provide explicit near-quadratic size lower-bounds for bounded-dimension unitary branching programs, and exponential size lower-bounds for bounded-dimension read-once gapped unitary branching programs. The first lower bound is proven using a combination of Neciporuk’s lower bound technique with classic results from algebraic geometry. The second lower bound is proven within the framework of communication complexity theory.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-andino21a, title = {Unitary Branching Programs: Learnability and Lower Bounds}, author = {Andino, Fidel Ernesto Diaz and Kokkou, Maria and De Oliveira Oliveira, Mateus and Vadiee, Farhad}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {297--306}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/andino21a/andino21a.pdf}, url = {https://proceedings.mlr.press/v139/andino21a.html}, abstract = {Bounded width branching programs are a formalism that can be used to capture the notion of non-uniform constant-space computation. In this work, we study a generalized version of bounded width branching programs where instructions are defined by unitary matrices of bounded dimension. We introduce a new learning framework for these branching programs that leverages on a combination of local search techniques with gradient descent over Riemannian manifolds. We also show that gapped, read-once branching programs of bounded dimension can be learned with a polynomial number of queries in the presence of a teacher. Finally, we provide explicit near-quadratic size lower-bounds for bounded-dimension unitary branching programs, and exponential size lower-bounds for bounded-dimension read-once gapped unitary branching programs. The first lower bound is proven using a combination of Neciporuk’s lower bound technique with classic results from algebraic geometry. The second lower bound is proven within the framework of communication complexity theory.} }
Endnote
%0 Conference Paper %T Unitary Branching Programs: Learnability and Lower Bounds %A Fidel Ernesto Diaz Andino %A Maria Kokkou %A Mateus De Oliveira Oliveira %A Farhad Vadiee %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-andino21a %I PMLR %P 297--306 %U https://proceedings.mlr.press/v139/andino21a.html %V 139 %X Bounded width branching programs are a formalism that can be used to capture the notion of non-uniform constant-space computation. In this work, we study a generalized version of bounded width branching programs where instructions are defined by unitary matrices of bounded dimension. We introduce a new learning framework for these branching programs that leverages on a combination of local search techniques with gradient descent over Riemannian manifolds. We also show that gapped, read-once branching programs of bounded dimension can be learned with a polynomial number of queries in the presence of a teacher. Finally, we provide explicit near-quadratic size lower-bounds for bounded-dimension unitary branching programs, and exponential size lower-bounds for bounded-dimension read-once gapped unitary branching programs. The first lower bound is proven using a combination of Neciporuk’s lower bound technique with classic results from algebraic geometry. The second lower bound is proven within the framework of communication complexity theory.
APA
Andino, F.E.D., Kokkou, M., De Oliveira Oliveira, M. & Vadiee, F.. (2021). Unitary Branching Programs: Learnability and Lower Bounds. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:297-306 Available from https://proceedings.mlr.press/v139/andino21a.html.

Related Material