CaltechAUTHORS
  A Caltech Library Service

On Algebraic Constructions of Neural Networks with Small Weights

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

[img] 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:
URLURL TypeDescription
https://doi.org/10.1109/ISIT50566.2022.9834401DOIArticle
https://arxiv.org/abs/2205.08032arXivDiscussion Paper
ORCID:
AuthorORCID
Sima, Jin0000-0003-4588-9790
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2022 IEEE. This research was partially supported by The Carver Mead New Adventure Fund.
Funders:
Funding AgencyGrant Number
Carver Mead New Adventures FundUNSPECIFIED
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