On Algebraic Constructions of Neural Networks with Small Weights
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.