Memorization Capacity of Neural Networks with Conditional Computation
Authors: Erdem Koyuncu
Venue: ICLR 2023 poster (2023)
Keywords: Memorization capacity
conditional computation.

Abstract: Many empirical studies have demonstrated the performance benefits of conditional computation in neural networks, including reduced inference time and power consumption. We study the fundamental limits of neural conditional computation from the perspective of memorization capacity. For Rectified Linear Unit (ReLU) networks without conditional computation, it is known that memorizing a collection of $n$ input-output relationships can be accomplished via a neural network with $O(\sqrt{n})$ neurons. Calculating the output of this neural network can be accomplished using $O(\sqrt{n})$ elementary arithmetic operations of additions, multiplications and comparisons for each input. Using a conditional ReLU network, we show that the same task can be accomplished using only $O(\log n)$ operations per input. This represents an almost exponential improvement as compared to networks without conditional computation. We also show that the $\Theta(\log n)$ rate is the best possible. Our achievability result utilizes a general methodology to synthesize a conditional network out of an unconditional network in a computationally-efficient manner, bridging the gap between unconditional and conditional architectures. 

Published as a conference paper at ICLR 2023
MEMORIZATION CAPACITY OF NEURAL NETWORKS WITH CONDITIONAL COMPUTATION
Erdem Koyuneu
Department of Electrical and Computer Engineering University of Illinois Chicago
ekoyuncul ui c.edu
ABSTRACT
Many empirical studies have demonstrated the performance benefits of conditional computation in neural networks, including reduced inference time and power consumption. We study the fundamental limits of neural conditional computation from the perspective memorization capacity. For Rectified I. Linear Unit (Rel.) networks without conditional computation, it is known that memorizing collection of n input-output relationships can be accomplished via a neural network with (VT)) neurons. Calculating the output of this neural network can be accomplished using (n) elementary arithmetic operations of additions, multiplications and comparisons for each input. Using a conditional ReLU network, we show that the same task can be accomplished using only Ollog n) operations per input. This represents an almost exponential improvement as compared to networks without conditional computation. We also show that the (log n)) rate is the best possible. Our achievability result utilizes general methodology to synthesize a conditional network out of an unconditional network in a computationally -ffficcient manner, bridging the gap between unconditional and conditional architectures.
INTRODUCTION
CONDITIONAL COMPUTATION
Conditional computation refers to utilizing only certain parts of neural network, in an input-adaptive
fashion (Davis & Arel, 2013] Bengio et al.) 2013 Eigen et al. 2013). This can be done through gating mechanisms combined with a tree-structured network, as in the case of "conditional networks" (loannou et al. 2016) or neural trees and forests (Tanno al. 2019; Yang et al., 2018 Kontschieder al. 2015). Specifically, depending the inputs some features extracted from the inputs, gate can choose its output sub-neural networks that will further process the gate's 's input features. Another family of conditional computation methods are the so-called early-exit architectures (Teerapittayanon jet al.] 2016 Kaya et al. 2019: Gormez et al.) 2022). In this case, one typically places classifiers at intermediate layers of large network. This makes possible exit at certain layer to reach final verdict on classification, if the corresponding classifier is confident enough of its decision.
Several other sub-techniques of conditional computation exist and have been well-studied, including layer skipping (Graves) 2016), channel skipping in convolutional neural networks (Gao et al. 2019), or reinforcement learning methods for input-dependent dropout policies (Bengio et al. 2015). Although there are many diverse methods (Han et al.) 202I). the general intuitions as to why conditional computation can improve the performance of neural networks remain the same: First, the computation units are chosen in an adaptive manner to process the features that are particular to the given input pattern. For example, cat image is ideally processed by only "neurons that are specialized to cats." " Second, one allocates just enough computation units to given input, avoiding a waste of resources. The end result is various benefits relative to a network without conditional computation, including reduced computation time. and power/energy consumption (Kim & Seo 2020). Achieving these benefits are especially critical in edge networks with resource-limited devices (Li et al.) (021a|b) Moreover, conditioning incurs minimal loss, in cases, no loss in learning performance.

---

Published as a conference paper at ICLR 2023
Numerous empirical studies have demonstrated the benefits of conditional computation in many different settings. Understanding the fundamental limits of conditional computation in neural networks is thus erucial, but has not been well- cell-investigate in the literature. There is wide body of work theoretical analysis of decision tree learning (Maimon & Rokach 2014), which can be considered as instance of conditional computation. These results are, however, not directly applicable to neural networks, In In/ & Bengio (2014), a feature vector is multiplied by different weight matrices, depending on the significant bits of the feature vector, resulting in an exponential increase in the number of free parameters of the network (referred to as the capacity of the network in Cho & Bengio (2014)). On the other hand, the potential benefits of this scheme have not been formally analyzed.
1.2 MEMORIZATION CAPACITY
In this work, we consider the problem of neural conditional computation from the perspective of memorization capacity. Here, the capacity refers to the maximum number of input-output pairs of ceasonably-genert position that neural network of given size can learn. It is typically expressed as the minimum number of neurons or weights required for a given dataset of size, say n.
Early work on memorization capacity of neural networks include Baum (1988), : Mitchison & Durbin (989);[Sontap 1990). In particular, [Baum (1988) shows that, for thresholds networks, O(n) neurons and weights are sufficient for memorization. This sufficiency result is later improved to (Vv)) neurons and (n) weights by Vershynin (2020); Rajput et al. (021). There are also several studies on other activation functions, especially the Rectified Linear Unit (ReLU), given its practicality and wide utilization in deep learning applications. Initial works ZZang et al. (2017); Hardt & Ma (2016) show that ((n) neurons and weights are sufficient for memorization in the case of ReLU networks. This is improved to ((yn) weights and (nz) neurons in Yun et al. (2019). In addition, Park et al. 1202 proves the sufficiency of (33 weights and neurons, and finally. Vardi et al. (2022) shows that memorization can be achieved with only O weights and neurons, up to logarithmic factors. For the sigmoid activation function, it is known that O (Vn)) neurons and (n) weights (Huang) 2003), or (n²/33) weights and neurons (Park et al. 2021) are sufficient. Memorization and expressivity have also been studied in the context of specific network architectures such as convolutional neural
networks (Cohen & Shashua, 2016 Nguyen & Hein 2018).
The aforementioned achievability results have also been proven to be tight in certain cases. A very useful tool in this context is the Vapnik- Shenikk-Chhrvonnniss (VC) dimension (Vapnik & Chervonenkis! 2015). In fact, applying the VC dimension theory to neural networks (Amthony et 1999), it can be shown that the number of neurons and weights should be both polynomial in the size of the dataset for successful memorization. Specifically, 22 (())) weights and ((n)/44) neurons are optimal for ReLU networks, up to logarithmic factors. We will justify this statement later on for completeness.
1.3 SCOPE, MAIN RESULTS, AND ORGANIZATION
We analyze the memorization capacity of neural networks with conditional computation. We describe neural network and the associated computational complexity complexity models in Section 2 We describe
general method to synthesize conditional networks from unconditional networks in Section 3 We provide our main achievability and converse results for memorization capacity in Sections 4 and 5 respectively. We draw our main conclusions in Section 6 Some of the technical proofs are provided in the supplemental material.
We note that this paper is specifically on analyzing the theoretical limits on neural conditional compu- tation. In particular, we show that n input-output relationships can be memorized using a conditional network that needs only Ollog n) operations per input or inference step. The best unconditional architecture requires O(y operations for the same task. This suggests that conditional models can offer significant time/energy savings as compared to unconditional architectures. In general, understanding the memorization capacity of neural networks is well-studied problem of fundamental importance and is related to the expressive power of neural networks. A related but separate problem is generalization, i.e. how to design conditional networks that can not only recall the memory patterns with reasonable accuracy but also generalize unseen examples. The -touble-descent" phenomenon (Belkin et al. 2019; Nakkiran et al. 202I) suggests that the goals of memorization and generalization are not contradictory and that a memorizing network can potentially also generalize well. A further
2

---

Published as a conference paper at ICLR 2023
investigation of this phenomenon in the context of conditional networks, and the design of conditional networks for practical datasets remains beyond the scope of the present work.
Unless specified otherwise, all vector variables are column vectors. We use ordinary font (such as u) for vectors, and the distinction between a vector and scalar will be clear from the context. The symbols O, S2, and θ are the standard Machmann-Landar symbols. Specifically, fn. (gn) means there is a constant C' > O such that fn I Cg,, for sufficiently large n. On the other hand, constant C such that fa > Cgn. for sufficiently large n.. We write Jn E (ga) if Jn E Ogg)) and fn E (g(g)). The set IP is the set of all p-dimensional real-valued column vectors. The superscript (-)7 is the matrix transpose. The function 1(-) is the indicator function, and [-] is the ceiling operator. A function f(z) of variable r is alternatively expressed as the mapping x >> (()) Operator rank(.) the rank of matrix. Finally, || the Fuclidean norm.
Notation:
Ln E (gn)). then there
SYSTEM MODEL
2.1 UNCONDITIONAL FEEDFORWARD NETWORKS
Consider an ordinary unconditional feedforward network of a homogeneous set of neurons, all of which have the same functionality. We also allow skip connections, which are mainly utilized for the generality of the model for converse results (The construction in our achievability results also skip layers, but at most one layer time). Formally, we consider an L-layer network with the ReLU operation (<x) = max (0, æ). and the input-output relationships
y = o We [v] -.. -."'"=''' -
(1)
where yo is the input to the neural network, ye is the output at Layer e, and yr. is the neural network output. Also, We is the weight matrix at Layer l of appropriate dimensions.
2.2 MEASURING THE COST OF COMPUTATION
A recurring theme of the paper will be to calculate the output of a neural network given an arbitrary input, however with low computational complexity. particular, in (T). given the outputs of Layer é 1-1 1, the calculation of the outputs of Layer & can be accomplished through multiplication with matrix We, followed by the activation functions. Each ReLU activation function can be implemented via a simple comparison given local fields. Hence, calculation of the output of Layer & can be accomplished with O(dimW,, operations (multiplications, additions, and comparisons), and the output yz of the entire network can be calculated using OiE, dimWe) operations. Here, dimWe represents the product of the number of rows and columns in We. In other words, dimwe is the number of dimensions in We. Hence, in unconditional architectures, the number of operations to calculate the output of the network is essentially the same (up to constant multipliers) as the number of weights in the network. With regards to our basic measure of complexity, which relies counting the number of operations, one can argue that multiplication is more complex than addition or comparison, and hence should be assigned a larger complexity. We hasten to note that the relative difficulty of different operations will not affect our final results, which will have an asymptotic nature.
It is instructive to combine the O(E, dimW') complexity baseline with the memorization results described in Section [ Let X = (II,..., In C RR. be a dataset of inputs. Let di...., dx E R' be the corresponding desired outputs. In the memorization task, one wishes design a network that can provide an output of d; for an input of x; for each i E f1....,22 n2.. It is known that, up to logarithmic factors, ((vn) weights and neurons are sufficient for memorization of n patterns (Vardi et al. 2022). It follows from the discussion in the paragraph above that O(yn) operations sufficient to recall a stored memory pattern (i.e. to calculate the output of the neural network for a given 2;)). The goal of this paper is to accomplish the same task using much fewer operations required per input. Specifically, we will show how to do perfect recall using only O(log operations per input. We shall later show that G(log n) is, in fact, the best possible rate.
2.3 CONDITIONAL NETWORKS
In order to achieve perfect recall using a subpolynomial number of operations, we use the idea of conditional computation. The conditioning model that we utilize in this work is simple but
3

---

Published as a conference paper at ICLR 2023
general scenario where we allow executing different sub-neural networks depending on how an intermediate output of the network compares to some real number. Each conditioning is thus counted as operation. Formally,
describe conditional neural network via a rooted full binary tree where every vertex has either 0 or 2 children. Every vertex is a sequence of operations of the form Vn+1 < (B,,V, +.... 3Iv1), where -1....; 3r, are weights, and variables Vi,-..; Vn either (i) inputs to the neural network, or (ii) defined as new variables preceding Va+1 at the same vertex or one of the ancestor vertices. Every edge is conditioning v B, where v should be defined at any one of the vertices that connects the edge to the root node, 8 is constant weight, and E < > 23. We assume that the two edges connected to the same vertex correspond to complementary conditions; e.g. < 3 and vi 2 3.
An example conditional network, expressed in algorithmic form, is provided in Algorithm 1 where represents the input, o is the output, and the subscripts are the vector components. For example, if the input is a vector with 41 > 3. resulting in an intermediate feature vector with 23 of 5, then two operations are incurred due to the conditionings in Lines I and 5, and O(dim(W,) + dimmm (22) dis)Ws)) operations are accumulated due to neural computations.
Our model encompasses various neural conditional computation models in the literature. One example is early exit architectures Teerapitayanon et al. 2016 Kaya et al., 2019 Gormez & Koyuncu 2022). As described in Section I typical scenario is where
places intermediate classifiers to deep
neural network. If an intermediate classifier is confident enough of decision, then "early exit" is performed with the corresponding class decision. Here, one skips subsequent layers, saving computa- tion resources. The decision to exit is often a simple threshold check, e.g. whether one of the soft probability outputs of the intermediate classifier exceeds a certain threshold. Hence, most early exit net- works can be modeled via the simple if-else architecture described
Algorithm An example con- ditional neural network
1:
if m1 then
2:
2 = Φ (Wzo(Wn (Wiu)
3:
if 23 5 then
4:
o = (W4z)
above. Mixture of experts (MoH) architectures [Shazeer et al. (2017); Fedus et al. 2022) can also be realized under our model. In this case, there are multiple gating networks, each of which is responsible for one expert. One routes a feature vector to only subset of experts whose gating networks have the largest outputs. The choice of ex- perts can be accomplished through if-else statements. For example, for two gates and experts, the gate with the largest output can be found by comparing the difference between the two gates' outputs against zero Another gating approach that can be realized as a special case of our model can be found in Cho & Bengio (011)).
5:
else
6:
0 = (Wsz)
7:
end if
8: else
9:
0 0= (Wau)
10: end if
SYNTHESIZING A CONDITIONAL NETWORK OUT OF AN UNCONDITIONAL NETWORK
Consider an arbitrary unconditional network as in (1. whose implementation requires OEE, dimWe) operations, as discussed in Section 2.2] Suppose that the network well-trained in the sense that it can already provide the output d; for given input z; for every i E {1....,n} Out of such an unconditional network, we describe here a general methodology to synthesize a conditional network that requires much fewer than OlE, dimWe) operations, while keeping the input-output relationships x; + d,, i E (I,..., intact.
We first recall some standard terminology (Haykin 2008 +EE, z,w,). We refer to Ii...., In as the neuron ippus, and wi...., Wn. as the neuron weights. We can now provide the following definition.
Consider the neuron [Ir,...., [n)
Definition 1. Suppose that the activation function satisfies o(0) 0. Given some fixed input neural network, a neuron with at least one non-zero input is called an active neuron. A neuron that is not active is called inactive deactivated neuron. weight is called active if it connects an active neuron to another active neuron and is non-zero. A weight is called inactive if it is not active.
The source of the phrase "inactive" is the following observation: Consider an input to the neural network and the corresponding output. By definition, we will obtain the same output after removing all inactive neurons from the network for the same input. We can simply "ignore" inactive neurons. I Likewise, remove any inactive weight and obtain the same output.
4

---

Published as a conference paper at ICLR 2023
Our idea is to condition the computation on the set of active neurons and the corresponding active weights. Note that removing the inactive weights and neurons does not change the network output. Moreover, often the number of active weights given an input can be significantly lower than the overall number of neurons of the unconditional architecture (which determines the number of operations required to perform inference on the unconditional network), resulting in huge computational savings. The complication in this context is that the set of inactive weights depends on the network input. Fortunately, it turns out that determining the set of active weights can be accomplished with fewer operations than actually computing the local fields or outputs of the corresponding active neurons. The final result is provided by the following theorem.
Theorem 1. Consider an arbitrary dataset X = (II...,,In'] IP of inputs. Let di..... dn E RT be the corresponding desired outputs. Suppose that the unconditional neural network defined by 7 satisfies the desired input-outpin output relationships the sense that for any i, ihe input to the network is Ts then the oulput is d.. Also suppose that the input x; results in wa active weights. Then, there is a conditional network that similarly satisfies all desired input output relationships, and for every i, performs at most p + Awa operations given input 24.-
Proof. (Sketch) By input configuration," we mean certain subset of neurons that are active at certain layer of the unconditional "base" network. We represent input configurations by binary vectors where "0" represents an inactive neuron, while "1" represents an active neuron. As an example, the input configuration [1 101] 11]" refers to a scenario where only the first and the third neurons at the layer is active. Analogous to input configurations, "output configurations" are binary vectors that represent whether neurons provide zero or non-zero outputs. For example, an output configuration of [1 0)T means that only the first and the second neurons provide non-zero output.
Consider first an unconditional network without skip connections. The key idea is to observe that, given the output configuration of Layer f. 1, one can uniquely obtain the input configuration of Layer l. Hence, conditional network can be designed to operate in the following manner: Given an input, we first find the output configur indiiuratiinn OC2 at Layer O, which is nothing but the non-zero components of the input vector. This can be done by p conditioning statements, where p is the input dimension. The result is a unique input configuration IC₁ at Layer 1. Meanwhile, we can obtain the output yn of Layer 1 by only calculating the outputs of neurons that correspond to the non-zero components of IC,, since other neurons at Layer 1 are guaranteed to have all-zero inputs and thus provide zero output. This can be accomplished via (a1)) multiplications and additions. where ay represents the number of active weights in Layer f. Then, we find the output configuration 0C, at Layer I, using [C| conditioning statements on /1. Having obtained DC2, we can similarly find the Layer 2 input configuration and output. The conditional network processes the remaining layers recursively in the same manner. The functionality of the unconditional network is reproduced exactly so all input-output relationships are satisfied. Given that >, ag wi, the total complexity is p + Ou,;). We refer to the complete proof in Appendix A for the precise bound and generalization to networks with skip connections.
The proof of the theorem in Appendix A suggests that the true complexity is closer 2w3 than the actual formal upper bound provided in the theorem statement. The number 2w, stems from the Wa additions and W; multiplications that are necessary to calculate the local fields of active neurons.
Theorem I shows that a design criterion to come up with low computational-comple
neural networks might be to put a constraint on the number of active weights given any training input to an ordinary, unconditional feedforward architecture. Using the theorem, we can synthesize a conditional neural network with the same functionality as the unconditional feedforward network. In the next section, we will apply this idea to the problem of memorization capacity.
We conclude this section by noting that Theorem | may prove to be useful in other applications. For example, any method that results in sparse representations or weights, such pruning, will result in many inactive neurons and weights. Sparsity is useful; however, unstructured sparsity is difficult to exploit: For example, multiplying by matrix half of whose entries are zero at random positions will likely be as difficult as multiplying by a random matrix without sparsity constraints. The construction in Theorem mma provide computational savings for such scenarios.
Another observation is how Theorem caan potentially simplify the design of conditional networks. In any conditional architecture, an important question is where to place the decision gates that route
5

---

Published as a conference paper at ICLR 2023
information to different parts of the network. It is combinatorially very difficult if not impossible to optimize a heterogeneous collection of "ordinary neurons" " and "gates." Such an optimization is also completely unsuitable for a gradient approach. Hence, most previous works provide some empirical guidelines for gate placement, and do not optimize over the gate locations once they are placed according to these guidelines. The message of Theorem [is that there is need distinguish between gates and neurons, All that needs to be done is to train an unconditional network consisting only of ordinary neurons to be as "inactive" as possible, e.g. by increased weight sparsity through regularization Louizos et al. (2118). The theorem can then construct a conditional network that can exploit the sparsity to the fullest, placing the gates automatically.
4 MEMORIZATION WITH Low COMPUTATIONAL COMPLEXITY
In this section, we introduce our ReLU network to memorize the input-output relationships z; H> d; i= ,,...,,k. R. Our network will only yield Ollogn) n) active neurons and weights per input. Application of Theorem[] [ then imply a conditional network that can achieve perfect recall with only Ollogn) n) operations per imput, as desired.
Given a neural network f. and an input x to f. let A(x; and Wa;; f) denote the number of active neurons and active weights, respectively. Our feedforward ReLU network construction is provided by the following theorem.
Theorem Let X = .........n] C E. be a dataset of input patterns such that for every i E [I.....n] with i + j. have I; + Iz. Let ã; m; E RR, where q 1 ++ p. be the augmented dataset patterns for biasing purposes. Let di....,dd dn E R² be the corresponding desired outpus.. Suppose every component of di is non-negative for each E {l..... Then, there is neural network f : + R" such that for every i E .n]. we have f(īx)) d,
A(#x f) $ 2(q + 1) [lgg n1 + E O(r + glog n),
(2)
W W f) - 12 + I) n1 + (r + 2)4 + r - 2 O(rg + g² logn).
(3)
Proof. (Sketch) We provide an illustrative sketch of the proof. Suppose we wish to memorize the two-dimensional dataset given by Fig. Ta We can divide the datasets to two parts via a line, the resulting two parts to further two sub-parts, and so on, until reaching singletons, as shown in Fig. lb The overall network architecture that achieves the performance in the statement of the theorem is then shown Fig. 2 The initial block T is a basic preprocessing translation. The "switch" S.j corresponds to the line parameterized by weights Way in Fig. 1b The switch S.y routes the zero vector to one output path and copy its input to the other output path, depending on the side of the wxy-line its input vector resides. The switches are followed by ReI.U neurons with weights % These neurons map the corresponding input pattern on the active path to its desired output. Finally, the output of the ne-nnuos are accumulated. As an example, the signals the graph for input pattern Fg is provided, with Fe A T(7.). In general, all input-output relationships are satisfied with Oloog n) active neurons per dataset sample. We refer to the complete proof in Appendix B for the precise bounds.
Corollary 1. Let Fi, di, i = 1..... n be a sequence of arbitrary input-output pairs as stated in Theorem 2 Then, there is conditional network that, for every i, provides an output of de whenever the inpul is v; by performing only O(rq + q² logn) operations.
Proof. We apply the synthesis procedure in Theorem | to the network constructed in Theorem 2 An alternative more "direct" proof (that does not need Theorem 1 is to implement the gating blocks S.y in Fig. via if-else conditioning statements, resulting in a similar architecture.
We recall that for ReLU networks without conditional computation, the best achievability result (Vardi et al. (202) requires O( / n log n.) neurons and weights for memorizing a dataset of size n. Since the construction in Vardi et al. (2022) is not optimized for conditional computation, it is easily observed that every input activates all O
log neurons and weights of the network, resulting in O(yn log n) active weights per input. In fact, the remarkable construction in Vardi et al. (2022 is a narrow network of finite width of only 12. but depth O( n log n). Even if every input activates only one neuron at each layer, one obtains O ((vzz n log n) active neurons or arithmetic operations per input. In contrast, we only need Olog n) active weights or operations (via Corollary 1) per input.

---

Published as a conference paper at ICLR 2023
The fact that one cannot fundamentally achieve sub- sub-polynomial number of neurons without con- ditional computation is an easy consequence of the VC dimension theory. In our setting, the VC dimension corresponds to the cardinality of the largest dataset that can be memorized. Hence, upper bounds on the VC dimension translate to lower bounds on the memorization capacity. In this context, Anthony al. 1999 Theorem 8.6) provides ((n upper bound on the VC dimension for ReLUU networks, where now denotes the number of weights in the network. Since any upper bound on the VC dimension is also an upper bound on the cardinality of the largest possible dataset that can be memorized, we have n E ) It follows that nu E (((n) weights are the best possible for ReLU networks without conditional computation, meaning that the results of Vardi al. (2022) are optimal up to logarithmic factors. Also, using the bound Thw S nne where ne is the number of neurons in the network (equality holds the extreme scenario where every neuron is connected to every other neuron, including itself), we obtain the necessity of (2(2/44) neurons.
M3
3
7
W1 0
7
W
1
4
33
0
W22
(a) Dividing set of point to two equal subsets. (b) Continued divisions until reaching singletons.
Figure 1: The divide and conquer strategy.
72
S
77
S
76
S
73
Zg
T
S1
dg
74
0
0
Sz2
0
711
0
S33
76
Figure 2: An example network architecture for the achievability result. The block T represents the transformation in Step 1. Blocks S.y are the routing switches. Blocks 7/ represent ReL.U neurons with weights 7 and the Σ block represents a ReLU neuron with all-one weights.
In contrast to the deep and narrow architecture that is optimal for unconditional computation, the network that achieves the performance in Theorem is considerably wider but much shallower. In fact, the proof in Appendix B reveals that our network has width Onz), with (nn) nodes, and depth Ologg m). These numbers are consequence of the classical binary decision tree that we utilize in our network construction. Thanks to conditional computation, although the network has O(n) nodes, every dataset pattern activates only (log n.) neurons instead of O ((vn) neurons without conditional computation. Note that the function log n grows much slower than / so that the number of neurons activated by the conditional computation is asymptotically negligible relative to an unconditional network. Moreover, every neuron in the conditional computation network has bounded number of q weights. The two facts translate to big savings in terms of the cost of computation, thanks to Theorem I. An interesting open problem that shall leave future work is whether one achieve the
7

---

Published as a conference paper at ICLR 2023
same performance with much smaller network size, e.g. with O(vn) neurons, which is known to be optimal. This will also help reduce the size of the network synthesized by Theorem I
It should be mentioned that the bounds (2) and as stated in Theorem 2 holds only for input patterns that belong to the dataset. For such patterns, only one path from the input to the output of the neural network is activated. The global behavior of the neural network for arbitrary inputs is more complex. A careful analysis of the construction in Appendix B reveals that near the decision boundaries (the lines in Fig. [b), multiple paths of the network are activated, This will result in more active neurons and weights than what is suggested by the upper bounds in 2 and (3). respectively. However, the measure of such pathological inputs can be made arbitrarily small by tuning the switches appropriately.
the number of active neurons and weights
5 ULTIMATE COMPUTATIONAL LIMITS TO MEMORY RECALL
In the previous section, we showed that Ollog n) operations is sufficient to perfectly recall one of n input-output relationships. We now analyze the necessary number of operations per input for successful recall. Our main result in this context is provided by the following theorem.
Theorem 3. Let the input vectors #1...., In E IP and the corresponding desired output vectors d d, E IR satisfy the following property:
* .The matrix
Tig de,
Tipt1 has rank + 1 for any subset (1111..;(+11) of nn.....,.... digui
Suppose that a conditional network f satisfies the desired input-output relationships: For every i, the output of the network is de whenever the input is I3. Also, assume that the number of operations performed on each F, is bounded above by some a 2 0. Then, we have a 2 loog2 OOlog n).
Proof. Since there are at most operations per input, there are most a comparisons per input as well, counting the comparisons needed to implement the neuron activation functions. We can represent the entire conditional computation graph/network as a binary tree where the distance between the root and leaf node is at most This results in tree of at most 2 Icaf nodes. Each node of the tree compares real numbers to intermediate variables, which are lincar functions of network inputs other intermediate variables. Assume now the contrary to the statement of the theorem, i.c. the number of operations for every input is at most a, all input-output relationships are satisfied, but 2 p. Since there at most 2 leaf nodes, there is least one leaf node that admits 1 inputs (i.e. there are 1 + input patterns of the dataset such that the corresponding path over the tree ends at the leaf node). Without loss of generality, suppose the indices for these inputs are {l...., p). Writing down the input output relationship of the network for the leaf node, we obtain
[d] dp+pl = Wo[m .....ppp
(4)
for some q p matrix Wo. This relationship follows, as by fixing path on the tree, we obtain the unique linear transformation Wo that maps the inputs to the neural network to its outputs. According to the Rouché-Cappee theorem (Shatarevich & Remizov 2012 for the existence of Wo to solve is
Theorem 2.38), a necessary condition
rank([r ... :.+1)) = rank ([2
Ip+1 dp+1
(5)
On the other hand, result of the rank condition stated in the theorem, the left hand side rank evaluates to p. while the right hand side evaluates to 1 + We arrive at a contradiction, which concludes the proof of the theorem.
The condition on the dataset and the desired outputs that appear in the statement of Theorem is, up to a certain extent, necessary for the lower bound to hold. For example, if the desired outputs can simply be obtained number of operations for each input to obtain the desired outputs, and the lower bound becomes invalid. In this context, the rank condition ensures that subsets of outputs cannot be obtained as linear functions of inputs. However, it should also be mentioned that the condition is not particularly restrictive in limiting the class of datasets where the theorem holds. For example, if the components
linear transformation of inputs, then one only needs to perform a constant
8

---

Published as a conference paper at ICLR 2023
of the dataset members and the corresponding desired outputs are sampled in independent and identically distributed manner over any continuous distribution with positive support, it can be shown that the rank condition will hold with probability 1. Hence, it can be argued that almost all datasets satisfy the rank condition and thus obey the converse result.
Corollary has shown that patterns be memorized using O(log n) operations per input. The matching (log n)) lower bound in Theorem 3 proves that the (log n) rate is the best possible. However, the two results do not resolve how the number of operations should scale with respect to the input and output dimensions This aspect of the problem is left as future work.
6 CONCLUSIONS AND DISCUSSIONS
We have studied the fundamental limits to the memorization capacity of neural networks with conditional computation. First, we have described general procedure to synthesize a conditional network out of an ordinary unconditional feedforward network. According to the procedure, the number of operations required to perform inference on an input in the synthesized conditional network becomes proportional to the number of so-called "active weights" of the unconditional network given the same input. This reduces the problem of designing good conditional networks to the problem of designing ordinary feedforward networks with a low number of active weights or nodes. Using this idea, we have shown that for ReLU networks, O(log n.) operations per input is necessary and sufficient for memorizing a dataset of n patterns. An unconditional network requires (VVn) operations achieve the same performance. We also described method to synthesize conditional network out of an unconditional network in a computationally-efffeeee -ffficient manner.
One direction for future work is to study the memorization capacity for sum-constraint, as opposed to per-input constraint on the number of operations. While a per-input constraint makes sense for delay-sensitive applications, the sum-constrained scenario is also relevant for early-exit architectures, where there is a lot of variation on the size of active components of the network. Extensions of our results to different activation functions or to networks with bounded bit complexity can also be considered, In this context, Vardi et al. (022) shows that, for every E [0, 2). O(r²) weights with O(n bit complexity is optimal for memorizing n patterns, up to logarithmic factors. This result was proven under a mild separability condition, which restricts distinct dataset patterns to be 5-separated in terms of Euclidean distance. The optimality of the results of Vardi et al. (2022) suggests that under a similar separability condition, the bit complexity of our designs can also potentially be reduced without loss of optimality. This will remain another interesting direction for future work.
Many neural network architectures rely heavily on batch computation because matrix multiplications can be performed very efficiently modern processors. In this context, one disadvantage of conditional architectures is their general misalignment with the idea of batching. Nevertheless, if there are not too many branches on the network, and if the branch loads are balanced, each subbranch can still receive relatively large batch size. Fortunately, only a few gates can promise significant performance gains (Fedus et al., 2022). More work needed, however, to make networks with aggressive conditioning more efficient in the batch setting. In this context, our synthesis theorem can potentially enable conditional networks to trained as if they are unconditional, enabling batch computation. We note that in techniques like soft-gating (Shazeer et al. (017). a batch also traverses the entire computation graph during training (Kaya et al. (019)).
The main goal of this paper has been to derive theoretical bounds on the memorization capacity. More research is clearly needed for practical methods to train neural networks that can effectively utilize conditional computation and also generalize well. We hope that the constructions and theoretical bounds provided in this paper will motivate further research in the area.
ACKNOWLEDGMENT
This work was supported in part by National Science Foundation (NSF) under Grant CNS-2148182 and in part by Army Research Lab (ARL) under Grant W91
Although Theorem only considers scalar desired outputs, it can easily be extended to the multi- ditttiiddmesionall case, In fact, a successful memorization of, say, two- tro-dimensional output vectors with o(log n) active neurons would imply the successful memorization of scalar outputs with the same number of neurons (simply by ignoring
the neurons that provide the second component of the output), contradicting Theorem 3

---

Published as a conference paper at ICLR 2023
REFERENCES
Martin Anthony, Peter Bartlett, Peter I, Bartlett, et al. Neural network learning: Theoretical foundations. Cambridge University Press, 1999.
Eric B Baum. On the capabilities of multilayer perceptrons. Journal of Complexity, 403):1332155, 1988.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical biri-variance trade-off. Proceedings of the National Academy of Sciences, 116632):15499-15885 2019.
Emmanuel Bengio, Pierre-Luc Bacon, Joelle Pineau, and Doina Precup. Conditional computation in neural networks for faster models. arXiv preprint arXiv:1511.0629) 2015.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv: 2013.
Kyunghyun Cho and Yoshua Bengio. Exponentially increasing the capacity-oo-computtion ratio for conditional computation in deep learning. arXiv preprint 1406 7362, 2014.
Nadav Cohen and Amnon Shashua. Convolutional rectifier networks as generalized tensor decompo- sitions. In International Conference on Machine Learning, pp. 955-963. PMLR, 2016.
Andrew Davis and Itamar Arel. Low-rank approximations for conditional feedforward computation in deep neural networks. arXiv preprint arXiv: 2013.
David Eigen, Mare' Aurelio Ranzato, and Ilya Sutskever. Learning factored representations in deep mixture of experts. arXiv preprini 13/2.4311 2013.
William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. JMLR, 23(120):1-39, 2022.
Xitong Gao, Yiren Zhao, tukasz Dudziak, Robert Mullins, and Cheng-zhong Xu. Dynamic channel pruning: Feature boosting and suppression. In ICIR,, May 2019.
Alperen Gormez and Erdem Koyuncu. Class based thresholding in early exit semantic segmentation networks. 10. 15621, 2022.
Alperen Gormez, Venkat Dasari, and Erdem Koyuneu. Class means early exit decision mechanism. In IJCNN, 2022.
Alex Graves. Adaptive computation time for recurrent neural networks. arXiv preprint arXiv: 1oXi::6603.0883. 2016.
Yizeng Han, Gao Huang, Shiji Song, Le Yang, Honghui Wang, and Yulin Wang. Dynamic neural networks: A survey. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2021.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. In International Conference on Learning Representations, 2016.
Simon Haykin. Neural networks and learning machines, 3rd edition. Pearson, 2008
Guang-Bit Bin Huang. Learning capability and storage capacity of two-hidden-layer feedforward networks. IEEE Transactions on Neural Networks, 14(2):744-281, 2003.
Yani Ioannou, Duncan Robertson, Darko Zikic, Peter Kontschieder, Jamie Shotton, Matthew Brown, and Antonio Criminisi. Decision forests, convolutional networks and the models in-between. Microsoft Research Technical Report, 2016.
Yigitcan Kaya, Sanghyun Hong, and Tudor Dumitras. Shallow-deep networks: Understanding and mitigating network overthinking. In International Conference Machine Learning, June 2019.
Minkyu Kim and Mne-Sun Seo. An energy- efficceef deep convolutional neural network accelerator featuring conditional computing and low external memory access. IEEE Journal of Solid-Stare Circuits, 56(3):803-813 2020.
10

---

Published as a conference paper at ICLR 2023
Peter Kontschieder, Madalina Fiterau, Antonio Criminisi, and Samuel Rota Bulo. Deep neural decision forests. In IEEE International Conference on Computer Vision, December 2015.
Pengzhen Li, Erdem Koyuncu, and Hulya Seferoglu. Respipe: Resilient model-distributed dnn training edge networks. In ICASSP, 2021a.
Pengzhen Li, Hulya Seferoglu, Venkat Dasari, and Erdem Koyuncu. Model-distributed dnn training for memory--constrained edge computing devices, In LANMAN, 2021b.
Christos Louizos, Max Welling, and Diederik P Kingma. Learning sparse neural networks through LO regularization. International Conference on Learning Representations, 2018.
Oded Z Maimon and Lior Rokach. Duta mining with decision trees: theory and applications. World scientific, 2014.
GJ Mitchison and RM Durbin. Bounds the learning capacity of some multi-layer networks. Biological Cybernetiss, 60(5):345-36 1989.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang. Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, (12) 2021.
Quynh Nguyen and Matthias Hein. Optimization landscape and expressivity of deep cnns. In International conference on machine learning, pp. 3730-3739, PMLR, 2018.
Sejun Park, Jaeho Lee, Chulhee Yun, and Jinwoo Shin. Provable memorization via deep neural networks using sub-linear parameters. In Conference on Learning Theory, August 2021.
Shashank Rajput, Kartik Sreenivasan, Dimitris Papailiopoulos, and Amin Karbasi. An exponential improvement on the memorization capacity of deep threshold networks. Neurips, 2021.
Igor R Shafarevich and Alexey O Remizov. Linear algebra and geometry. Springer Science & Business Media, 2012.
Noam Shazeer, Azalia Mirhoseini, Kızysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. International Conference on Learning Representations, 2017. arXiv preprint arXiv:1701.06520
Eduardo Sontag. Remarks on interpolation and recognition using neural nets. Advances in Neural Information Processing Systems, 3, 1990.
Ryutaro Tanno, Kai Arulkumaran, Daniel Alexander, Antonio Criminisi, and Aditya Nori. Adaptive neural trees. In International Conference on Muchine Leurning, June 2019.
Surat Tcerapitaaannon, Bradley McDanel, and "siang-Tsung Kung. Branchynet: Fast inference via early exiting from deep neural networks. In ICPR, December 2016.
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of Complexity. 2015.
Gal Vardi, Gilad Yehudai, and Ohad Shamir. On the optimal memorization power of ReLU neural networks. In International Conference Learning Representations, April 2022.
Roman Vershynin. Memory capacity of neural networks with threshold and rectified linear unit activations. SIAM Journal on Mathematics of Data Science, 2(4):1004-1033 2020.
Yongxin Yang, Irene Garcia Morillo, and Timothy M Hospedales. Deep neural decision trees. arXiv preprint arXiv:1806. 06988, 2018.
Chulhee Yun, Suvrit Sra, and Ali Jadhabaie. Small relu networks are powerful memorizers: a tight analysis of memorization capacity. Advances in Neural Information Processing Systems, 32, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. In International Conference on Learning Representations, April 2017.
11


Reviews:
[{"review_id": "WggOH8zI03", "reviewer": "Reviewer_4ix4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the memorization capacity of conditional ReLU networks. By a conditional network we mean a network that allows \"branching\" of the flow of computation by conditional expressions (i.e., if-else statements). \n\n- The paper develops a general recipe that converts a general fully-connected unconditional neural network to a conditional network that only utilizes \"active neurons\" used for computing the output of a given input (Theorem 1).\n\n- Based on that, the paper then constructs an unconditional ReLU network $f$ which memorizes $n$ arbitrary input-output pairs $(x_i, d_i)$ where each pair requires the use of only $O(\\log n)$ \"active neurons\" to compute the correct output $d_i = f(x_i)$ (Theorem 2).\n\n- Theorems 1 and 2 together yield Corollary 1, which establishes the existence of a conditional ReLU network which memorizes $n$ input-output pairs and computes the output $d_i = f(x_i)$ in $O(\\log n)$ operations.\n\n- Theorem 3 shows that $\\Omega(\\log n)$ operations are in fact necessary for memorizing and recalling $n$ points.", "summary_of_the_review": "This paper studies memorization capacity of conditional neural networks. It develops a conditional ReLU network that can memorize a given dataset and compute the output of each data point in $O(\\log n)$ operations, and this number of operations is tight in terms of $n$. While a tight characterization in $n$ is valuable, I honestly think that the results are not significant enough to merit acceptance. Also, the paper has several clarity issues which makes it difficult to read and understand the paper. Therefore, I recommend rejection.", "strength_and_weaknesses": "I have not seen any theoretical results on conditional neural networks and I believe this paper is one of the first to tackle theoretical problems for conditional networks; this is a plus. However (perhaps because I'm a theory person), I am not sure if this class of architecture involving explicit if-else branching is really widely used in practice.\n\nThe paper constructs a conditional ReLU network that recalls a memorized output in $O(\\log n)$ operations, and shows that these many operations are actually necessary. Hence, this paper develops a tight characterization of the \"operation complexity\" for memorizing datasets with conditional networks.\n\nHowever, my honest opinion is that both the sufficiency and necessity results are not significant enough to merit acceptance. For sufficiency results, one can easily prove the same statement by constructing a conditional network in the following way:\n1) Since the $x_i$'s are all distinct, we can choose a vector $w$ such that the $n$ scalars $w^T x_1, \\dots, w^T x_n$ are all distinct. This is a standard first step in many results on memorization.\n2) Next, we can construct the \"binary decision tree\" that divides the $n$ data points to $n$ different leaves, which can be implemented with the if-else clauses of a conditional network. The tree can be constructed in a way that each data point $x_i$ goes through $\\lceil \\log_2 n \\rceil$ conditioning operations.\n3) At each leaf corresponding to $w^T x_i$, we choose appropriate network parameters to map $w^T x_i$ to $y_i$.\n\nOf course, the paper does it in a different way, by proving a conversion theorem from unconditional to conditional (Theorem 1) and then proving a construction of an unconditional ReLU network (Theorem 2). However, the main idea is the same; to construct a binary decision tree that we can deal with each example separately. To me, Theorems 1 and 2 look like a detour to prove a simple thing in an unnecessarily more complicated way.\n\nAlso, for Theorem 3, the tightness of the construction is proven only in terms of $n$; rather counterintuitively, the lower bound $\\Omega(\\log \\frac{n}{p})$ obtained in Theorem 3 decays with increasing input dimension $p$. This suggests that the theorem could be further improved to capture the right dependence on input/output dimension, as also noted by the authors.\n\nAnother weakness is that the paper is not cleanly written, especially the proof part. I have read all the proofs and got the main idea, but there are several clarity issues that make them confusing to read. More on that in the \"Clarity\" part below.\n\nIn terms of the literature review part, it looks to me that the paper cites most of the noteworthy papers on memorization capacity of neural networks, but I spotted two papers are missing.\n- \"Optimization landscape and expressivity of deep CNNs\" establishes memorization results for CNNs.\n- \"Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity\" shows sufficiency of $O(\\sqrt{n})$ neurons and $O(n)$ weights for ReLU networks.\n\nMinor comments:\n- When defining unconditional feedforward networks, the authors say that skip connections are \"allowed for generality,\" and from Eq (1) we can see that the model is allowing skip connections of arbitrary length (i.e., denseNet-style jump connections). However, for expressive power results, I do not think that allowing/exploiting skip connections necessarily improves the generality of the theorem, because skip connections are usually quite useful for reducing the number of weights/neurons required to construct a certain network. I have checked Theorem 2 and it seems the results can actually hold without using skip connections, at the cost of slightly increased number of operations.\n\n- The proof of Theorem 1 left me with three questions. First, why should all the $2^{\\alpha_{i\\ell}}$ output edges be drawn even if many of the arrows are left unused (i.e., does not make it all the way to the output layer/leaf node)? When you construct the conditional network, what do you do to the unused edges that do not extend all the way to the output layer? Lastly, although the theorem allows arbitrary skip connections, the construction of the configuration tree seems to only take into account the connections between adjacent layers. How do you deal with faraway skip connections?\n\n- Lemma 1 seems to use $2q+2$ neurons instead of $q+2$? Also, the statement says \"two-layer network\" which is a synonym to \"one-hidden-layer\" to many authors, whereas the actual construction involves two hidden layers.\n\nP2: A very useful too -> tool\n\nP6: In Step-2, what is $d$? If you meant the input dimension it should be $p$.\n\nThm 2: every neuron in network $f$ has at most $q$ weights—add \"incoming\" before weights?\n\nP7: $n_w$ and $n_e$ are both defined to be \"the number of weights of the network,\" the difference is not at all clear\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "GjBD_uxqhX", "reviewer": "Reviewer_snry", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors focus on neural networks with conditional computation and study the memorization capacity of these networks. The authors show that conditional ReLU networks can memorize n input-output relations in just $O(\\log n)$ operations, which is also shown to be the best rate possible.", "summary_of_the_review": "Overall, the paper is interesting, and very timely and relevant for the community. The results also seem significant. So I vote for accept.", "strength_and_weaknesses": "## Strengths:\n\n- The paper is well written and clear\n- The result seems significant, especially since conditional neural networks are becoming more mainstream.\n\n## Weaknesses\n\n- The authors don't include the mixture of experts model (Fedus et al. 2021) in their discussion of conditional computation.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "3xgBX4pOVRd", "reviewer": "Reviewer_DoNR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers the well studied problem of memorization using deep neural networks from the perspective of the minimum number of computations required per input specifically in the conditional computation framework. They show that $\\mathcal{O}(\\log{n})$ operations are sufficient to memorize $n$ arbitrary (input, output) pairs using a conditional ReLU network.", "summary_of_the_review": "I feel there are some minor flaws in the paper and I have a few clarifying questions. If those are handled satisfactorily, I will recommend acceptance.", "strength_and_weaknesses": "**Strenghts:**\n1. The problem of memorization is well studied and this bound represents an exponential improvement in the minimum number of computations required to memorize a given dataset.\n2. The literature survey is thorough and well written, giving proper credit to past work. Since this is a problem with a rich history, it is good to see that it has been given the right treatment.\n3. The paper is fairly well written, but the proofs could be better explained.\n\n**Weaknesses:**\n1. The previous tight bounds (Rajput et al. for threshold networks, Vardi et al. for ReLU networks) considered the problem of minimizing the number of parameters required for memorization and considered traditional neural networks. The framework of conditional computation, while interesting is not particularly prevalent. So this bound leverages an architecture which may not be practical.\n2. The proofs and descriptions in the paper rely a little too much on exmaples. I would encourage the authors to try to find a more formal way of describing ideas such as Conditional Networks in Section 2.3.\n3. If I understand correctly, the final architecture is essentially a binary decision tree for every input. This network is quite large ($\\mathcal{O}(n \\log n)$) parameters and the bit complexity of each weight in it can be arbitrarily large.\n    - The prior bounds all need to make some assumption on separation of the data points. Usually something like $||x_i - x_j|| \\geq \\delta\\; \\forall i\\neq j$. This result requires no such assumption and I suspect this is because the notion of separation is implicitly absorbed in the biases which have infinite precision.\n4. The notion of conditional computation breaks down for any kind of batch operation. Most neural networks rely heavily on batch computations because matrix multiplications have been heavily optimized. Such an architecture will not be able to leverage such optimizations and will have to resort to going over the samples serially.\n5. Minor:\n    - Page 6 has a typo - \"configurationtree\"\n    - Please replicate Figure 4 in the appendix as well to make it easier to go through the proof. I would also encourage you to rewrite Step 3 of the proof to make it easier to parse.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "0n7WZ06Vlv", "reviewer": "Reviewer_6Yt2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proves that conditional ReLU networks can memorize any dataset of size n, in such a way that performing inference with this network requires only $O(\\log{n})$ operations per input. It also proves that this is the best possible result, assuming mild conditions on the dataset. The best known results for unconditional ReLU networks, on the other hand, are that datasets of size n can be memorized with $O(\\sqrt{n})$ weights and $O(\\sqrt{n})$ neurons, with the best possible result being $O(\\sqrt{n})$ weights and $O(n^{1/4})$ neurons. Thus, the results in this paper prove the almost exponential improvement in inference efficiency that can be attained by using conditional computation.\n\nThe constructions in this paper define conditional ReLU networks with $O(n)$ neurons and $O(n)$ weights. Thus, the paper identifies an important open question for future work: can the $O(\\log{n})$ inference time result can be attained with asymptotically fewer neurons/weights (e.g., $O(\\sqrt{n})$)?\n", "summary_of_the_review": "This paper proves important theoretical results about the efficiency with which conditional ReLU networks can memorize datasets compared with unconditional ReLU networks. These results have important practical implications for the design of neural networks. As a result, I recommend acceptance for this paper (although my review is only medium confidence, given that I am not super familiar with the related work).", "strength_and_weaknesses": "Strengths\n- In my opinion, the fact that conditional ReLU networks can attain asymptotically better efficiency than unconditional ReLU networks (when memorizing a dataset of size n) is an important theoretical result, with significant practical implications for the design of neural networks. In particular, these results provide strong justification for designing neural networks with conditional branches (e.g., mixtures of experts), in cases where one cares more about inference computation time/energy than about the size of the model.\n- The theoretical results/proofs are quite general and elegant.\n- Although I found the details in certain sections hard to follow (more comments below), overall I found the main ideas of the paper quite clear, and the results compelling.\n\nWeaknesses:\n- The clarity of the paper could be improved. For example:\n  1. I found the construction in the proof of theorem 1 hard to follow (I had to read it many times); care should be given to making this a lot clearer, and explaining the “why” in addition to the “how” better. I think this is the most important section to make clearer.\n  2. It would be helpful to comment on the constant C > 0 from Theorem 1 (what is its value, and why?).\n  3. I think the section connecting VC dimension to memorization capacity in section 4 could be made clearer (it also has a typo: In the last sentence of that paragraph, n_e is twice described as the number of weights instead of as the number of neurons).\nThere are currently no empirical results in this paper.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster