Arithmetic Circuits, Structured Matrices and (not so) Deep Learning
It connects complexity theory to deep learning for researchers interested in model compression, but is incremental as it synthesizes existing work.
This survey formalizes the research question of replacing unstructured weight matrices in neural networks with structured ones to reduce model size, and shows how combining arithmetic circuit complexity, structured matrices, and deep learning essentially answers this question.
This survey presents a necessarily incomplete (and biased) overview of results at the intersection of arithmetic circuit complexity, structured matrices and deep learning. Recently there has been some research activity in replacing unstructured weight matrices in neural networks by structured ones (with the aim of reducing the size of the corresponding deep learning models). Most of this work has been experimental and in this survey, we formalize the research question and show how a recent work that combines arithmetic circuit complexity, structured matrices and deep learning essentially answers this question. This survey is targeted at complexity theorists who might enjoy reading about how tools developed in arithmetic circuit complexity helped design (to the best of our knowledge) a new family of structured matrices, which in turn seem well-suited for applications in deep learning. However, we hope that folks primarily interested in deep learning would also appreciate the connections to complexity theory.