2026-07-26T00:39:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18619 2024-03-06T11:02:17Z ddc:004 open_access

Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy Uchizawa, Kei Abe, Haruki Circuit complexity disjointness function equality function neural networks threshold circuits ReLU cicuits sigmoid circuits sparse activity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kei Uchizawa and Haruki Abe 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.85 urn:nbn:de:0030-drops-186192 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.85 eng https://creativecommons.org/licenses/by/4.0/legalcode