Arithmetic circuits, structured matrices and (not so) deep learning

DOI10.1007/S00224-022-10112-WMaRDI QIDQ6109070zbMATH OpenOpenAlexFDO

Authors Atri Rudra

Publication date 26 July 2023

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.12490

zbMATH Keywords

linear arithmetic circuit complexityneural networkspolynomial transforms

Mathematics Subject Classification ID

Basic linear algebra (15Axx) Numerical linear algebra (65Fxx) Theory of computing (68Qxx)

Abstract: 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.

Recommendations

• Circuits, matrices, and nonassociative computation
• Learning arithmetic circuits via partial derivatives.
• scientific article; zbMATH DE number 5899249
• Rethinking arithmetic for deep neural networks
• Deep learning architectures. A mathematical approach
• Circuits arithmétiques et calculs tensoriels
• Constant depth circuits, Fourier transform, and learnability
• Arithmetic circuits: a survey of recent results and open questions
• On the complexity of computing and learning with multiplicative neural networks
• Arithmetic circuits: a chasm at depth 3

Cites work

• A two-pronged progress in structured dense matrix vector multiplication
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Butterfly factorization
• Complexity Lower Bounds using Linear Algebra
• Displacement ranks of matrices and linear equations
• Displacement Structure: Theory and Applications
• Fourier and circulant matrices are not rigid
• scientific article; zbMATH DE number 1682655 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 2187726 (Why is no real title available?)
• scientific article; zbMATH DE number 3225079 (Why is no real title available?)
• Kronecker products, low-depth circuits, and matrix rigidity
• Neural Network Learning
• Optimal Rearrangeable Multistage Connecting Networks
• Probabilistic rank and matrix rigidity
• Robust principal component analysis?
• The complexity of partial derivatives
• Why Are Big Data Matrices Approximately Low Rank?

Cited in

(1)

• scientific article; zbMATH DE number 5899249 (Why is no real title available?)

This page was built for publication: Arithmetic circuits, structured matrices and (not so) deep learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6109070)