License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.85
URN: urn:nbn:de:0030-drops-186192
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18619/
Uchizawa, Kei ;
Abe, Haruki
Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy
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 non-zero 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 2n-variable 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 sublinear-depth and sublinear-energy 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 non-zero 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 non-zero 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 Sub-Linear Depth and Energy}},
booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages = {85:1--85:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-292-1},
ISSN = {1868-8969},
year = {2023},
volume = {272},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18619},
URN = {urn:nbn:de:0030-drops-186192},
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 |
