Kilic, Kordag Mehmet and Sima, Jin and Bruck, Jehoshua
(2022)
*On Algebraic Constructions of Neural Networks with Small Weights.*
In:
2022 IEEE International Symposium on Information Theory (ISIT).
IEEE
, Piscataway, NJ, pp. 3007-3012.
ISBN 978-1-6654-2159-1.
https://resolver.caltech.edu/CaltechAUTHORS:20220804-765672000

PDF
- Accepted Version
See Usage Policy. 223kB |

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220804-765672000

## Abstract

Neural gates compute functions based on weighted sums of the input variables. The expressive power of neural gates (number of distinct functions it can compute) depends on the weight sizes and, in general, large weights (exponential in the number of inputs) are required. Studying the trade-offs among the weight sizes, circuit size and depth is a well-studied topic both in circuit complexity theory and the practice of neural computation. We propose a new approach for studying these complexity trade-offs by considering a related algebraic framework. Specifically, given a single linear equation with arbitrary coefficients, we would like to express it using a system of linear equations with smaller (even constant) coefficients. The techniques we developed are based on Siegel’s Lemma for the bounds, anti-concentration inequalities for the existential results and extensions of Sylvester-type Hadamard matrices for the constructions.We explicitly construct a constant weight, optimal size matrix to compute the EQUALITY function (checking if two integers expressed in binary are equal). Computing EQUALITY with a single linear equation requires exponentially large weights. In addition, we prove the existence of the best-known weight size (linear) matrices to compute the COMPARISON function (comparing between two integers expressed in binary). In the context of the circuit complexity theory, our results improve the upper bounds on the weight sizes for the best-known circuit sizes for EQUALITY and COMPARISON.

Item Type: | Book Section | |||||||||
---|---|---|---|---|---|---|---|---|---|---|

Related URLs: |
| |||||||||

ORCID: |
| |||||||||

Additional Information: | © 2022 IEEE. This research was partially supported by The Carver Mead New Adventure Fund. | |||||||||

Funders: |
| |||||||||

DOI: | 10.1109/isit50566.2022.9834401 | |||||||||

Record Number: | CaltechAUTHORS:20220804-765672000 | |||||||||

Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20220804-765672000 | |||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||

ID Code: | 116085 | |||||||||

Collection: | CaltechAUTHORS | |||||||||

Deposited By: | George Porter | |||||||||

Deposited On: | 12 Aug 2022 20:00 | |||||||||

Last Modified: | 12 Aug 2022 20:00 |

Repository Staff Only: item control page