Abstract
In this paper, we investigate computational power of threshold circuits and other theoretical models of neural networks in terms of the following four complexity measures: size (the number of gates), depth, weight and energy. Here, the energy of a circuit measures sparsity of their computation, and is defined as the maximum number of gates outputting nonzero values taken over all the input assignments.
As our main result, we prove that any threshold circuit C of size s, depth d, energy e and weight w satisfies log(rk(M_C)) ≤ ed (log s + log w + log n), where rk(M_C) is the rank of the communication matrix M_C of a 2nvariable Boolean function that C computes. Thus, such a threshold circuit C is able to compute only a Boolean function of which communication matrix has rank bounded by a product of logarithmic factors of s, w and linear factors of d, e. This implies an exponential lower bound on the size of even sublineardepth and sublinearenergy threshold circuit. For example, we can obtain an exponential lower bound s = 2^Ω(n^{1/3}) for threshold circuits of depth n^{1/3}, energy n^{1/3} and weight 2^o(n^{1/3}). We also show that the inequality is tight up to a constant factor when the depth d and energy e satisfies ed = o(n/log n).
For other models of neural networks such as a discretized ReLU circuits and descretized sigmoid circuits, we define energy as the maximum number of gates outputting nonzero values. We then prove that a similar inequality also holds for a discretized circuit C: rk(M_C) = O(ed(log s + log w + log n)³). Thus, if we consider the number gates outputting nonzero values as a measure for sparse activity of a neural network, our results suggest that larger depth linearly helps neural networks to acquire sparse activity.
BibTeX  Entry
@InProceedings{uchizawa_et_al:LIPIcs.MFCS.2023.85,
author = {Uchizawa, Kei and Abe, Haruki},
title = {{Exponential Lower Bounds for Threshold Circuits of SubLinear Depth and Energy}},
booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages = {85:185:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772921},
ISSN = {18688969},
year = {2023},
volume = {272},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18619},
URN = {urn:nbn:de:0030drops186192},
doi = {10.4230/LIPIcs.MFCS.2023.85},
annote = {Keywords: Circuit complexity, disjointness function, equality function, neural networks, threshold circuits, ReLU cicuits, sigmoid circuits, sparse activity}
}
Keywords: 

Circuit complexity, disjointness function, equality function, neural networks, threshold circuits, ReLU cicuits, sigmoid circuits, sparse activity 
Collection: 

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) 
Issue Date: 

2023 
Date of publication: 

21.08.2023 