A Theoretical View on Sparsely Activated Networks
Authors: Cenk Baykal
Nishanth Dikkala
Rina Panigrahy
Cyrus Rashtchian
Xin Wang
Venue: NeurIPS 2022 Accept (2022)

Abstract: Deep and wide neural networks successfully fit very complex functions today, but dense models are starting to be prohibitively expensive for inference. To mitigate this, one promising research direction is networks that activate a sparse subgraph of the network. The subgraph is chosen by a data-dependent routing function, enforcing a fixed mapping of inputs to subnetworks (e.g., the Mixture of Experts (MoE) paradigm in Switch Transformers). However, there is no theoretical grounding for these sparsely activated models. As our first contribution, we present a formal model of data-dependent sparse networks that captures salient aspects of popular architectures. Then, we show how to construct sparse networks that provably match the approximation power and total size of dense networks on Lipschitz functions. The sparse networks use much fewer inference operations than dense networks, leading to a faster forward pass. The key idea is to use locality sensitive hashing on the input vectors and then interpolate the function in subregions of the input space. This offers a theoretical insight into why sparse networks work well in practice. Finally, we present empirical findings that support our theory; compared to dense networks, sparse networks give a favorable trade-off between number of active units and approximation quality.

A Theoretical View on Sparsely Activated Networks
Cenk Baykal
Nishanth Dikkala
Google Research
Google Research
Rina Panigrahy
Cyrus Rashtchian
Xin Wang Google Research
Google Research
Google Research
Abstract
Deep and wide neural networks successfully fit very complex functions today, but dense models are starting to he prohibirively expensive for inference. To mitigate this, one promising direction networks that activate a sparse subgraph of the network. The subgraph is chosen by a data-dependent routing function, enforcing fixed mapping of inputs to subnetworks (e.g., the Mixture of Experts (MoE) paradigm in Switch Transformers). However, prior work is largely empirical, and while existing routing functions work well in practice, they do not lead to theoretical guarantees on approximation ability. We aim to provide theoretical explanation for the power of sparse networks. As our first contribution, we present formal model of data-dependent sparse networks that captures salient aspects of popular architectures. We then introduce routing function based on locality sensitive hashing (LSH) that enables us reason about how well sparse networks approximate target functions. After representing LSH-based sparse networks with model, we prove that sparse networks can match the approximation power of dense networks on Lipschitz functions. Applying LSH on the input vectors means that the experts interpolate the target function in different subregions of the input space. To support our theory, we define various datasets based on Lipschitz target functions, and show that sparse networks give a favorable trade-off between number of active units and approximation quality.
Introduction
Overparameterriee neural networks continue yield performance gains their sizes increase. This trend has been most prominent with large Transformer based language models [6. 12, 32). However, using large, dense networks makes training and inference very expensive, and computing forward pass may require trillions of floating point operations (FLOPs). It is an active area of research to improve the scalability and efficiency without decreasing the expressiveness or quality of the models.
One way to achieve this goal is to only activate part of the network at a time. For example, the Mixture of Experts (MoE) paradigm [22, 37] uses two-step approach. First, each input is mapped to a certain subnetwork, known as an expert. Then, upon receiving this input, only this particular subnetwork performs inference, leading number of parameters across all experts. Some variations of this idea map parts of an input (called tokens) individually to different experts. Another well-studied generalization is to map an input to group of subnetworks and aggregate their output in a weighted manner. Switch Transformers [14] successfully use refined version of the MoE idea, where the input may be the embedding of a token or part of a hidden layer's output. Researchers have investigated many ways to perform the mapping, such as Scaling Transformers [21] or using aseudo-random hash functions [34]. In all cases, sparsity occurs in the network because after the input is mapped to the subnetwork, only this subset of neurons
smaller number of operations compared the total
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

needs to be activated. Moreover, the computation of the mapping function, sometimes referred to as a 'routing' function, takes significantly less time than the computation across all experts.
The success of these approaches is surprising. Restricting to a subnetwork could instead reduce the expressive power and the quality of the model. However, the guiding wisdom seems be that it suffices to maximize the number of parameters while ensuring computational efficiency. Not all parameters of a network are required for the model to make its prediction for any given example. Our goal is to provide a theoretical explanation for the power of sparse models on concrete examples.
Our Results. Our first contribution is a formal model of networks that have one or more sparsely activated layers. These sparse layers are data dependent: the subset of network activations and their weight coefficients depend on the input. We formally show that our model captures popular architectures (c.g.. Switch and Scaling Transformers) by simulating the sparse layers in these models.
We next prove that the above class of sparsely activated models can learn a large class of functions more efficiently than dense models. As our main proof technique, we introduce new routing function, based on locality sensitive hashing (LSH), that allows us to theoretically analyze sparsely activated layers in network. LSH maps points in a metric space (e.g., Rd)) to 'buckets' such that nearby points map to same bucket. The total number of buckets used by a LSH function is referred to as the size of the hash table. Prior work has already identified many routing functions that work well in practice. We do not aim to compete with these highly-optimized methods, but rather we aim to use LSH-based routing as a way to reason about the approximation ability of sparse networks.
In Theorem 4.1, we show that LSH-based sparse models can approximate real-valued Lipschitz functions in _ Although real data often lives in high dimensions, the underlying manifold where the inputs are supported is often assumed to be low-dimensional (e.g. the manifold of natural images vs 2224x224 for 224 x 224 image). We model this by assuming that our inputs lie in k-dimensional manifold within Rd. To get c approximation error, we need an LSH table of size approximately (( (((vik/(e**) but a forward pass only requires time (dl log(1 (ce) as only one of the ((VVll non-empty buckets are accessed for any given example.
In Theorem 4.3, we complement our upper bounds by proving lower bound of (((2Vd/)) on the size needed for both dense and sparse models (when points live in k dimensions). This also transforms into a lower bound on the number of samples required to learn these functions using dense model. This lower bound implies that forward pass dense model takes time (2d((2 V )*), which is exponentially worse than the time taken by the sparse model. Altogether, we show that for the general class of Lipschitz functions, sparsely activated layers are expressive as dense layers, while performing significantly fewer floating point operations (FLOPs) per example.
To support our theory, we perform experiments in Section 5 on approximating Lipschitz functions with sparse networks. We identify several synthetic datasets where models with data-dependent sparse layers outperform dense models of the same size. Moreover, we achieve these results with relatively small networks. This provides a few minimum working examples of when sparsity is beneficial. Our results complement the existing work that has already shown the success of very large MoE models on real-world NLP and vision tasks [14, 21, 333. Our experiments also generalize the intuition from Figure la, where the model outputs different constant value for each bucket. A puzzling empirical result was observed in [34] where a pseudo-randon uniform hash function is used to route input tokens to experts. Intuitively, this might map very nearby or similar points to distinct experts, leading to a potentially non- smooth behavior. We show that on our synthetic, Lipschitz datasets, the LSH model outperforms uniform random hashing, which further corroborates theory.
Related Work. Sparsely activated networks have had enormous empirical success [1. 5, 13, 25, 29, 33, 37, 40]. The Switch Transformer [14] is one of the first major, contemporary applications of the sparsely activated layers. Follow-up works such as Scaling Transformers [21] and other hash functions [34] aim to improve the sparse layers. These papers build upon seminal MoE works [19, 20, 22], and other uses of the MoE paradigm [27, 36]. There has been work on using statistical mechanics to analyze the generalization of MoE models [23]. However, to the best of our knowledge, there is no systematic theoretical study of modern sparsely activated networks.
The above work on dynamic sparsity builds on previous static sparsity efforts, e.g. weight quantiza- tion [28], dropout [38], and pruning (see the survey [18] and references). Static sparsity means that

---

27
danse (wieth + a-axis values)
24
Mean Squared Emrr
1024]
21
DBM [total width 2048)
1.8
(total width 4096)
DSM (total wicth 8192)
1.5
12
0.6
0.05
0.3
0.00
1024
4096
16884
(Input features)
Number activated (log scale)
(a) ID example
(b) sparse/dense scaling hehavior
Figure I: Learning polynomial functions with data-depended sparse models: (a) Dashed curve is the target function graph, piecewise constant curve is the learned LSH model output, and different LSH buckets are indicated by different colors. Note neighboring points are hashed to the same bucket, where a simple constant can learned to approximate target function values; (b) Scaling behavior of data-dependent sparse models (DSM) versus dense models, in which sparse models outperform dense models of the same size, see Section 2 and Section for details.
the subnetwork activation does not change in data-dependent way. The focus is on generalization and compression, instead of achieving fast inference time with huge number of parameters.
Our work builds on locality sensitive hashing (LSH), a well-studied technique for approximate nearest neighbor search (see the survey [4] or the book [16] and references therein for LSH background). A seminal and popular LSH family uses random hyperplanes to partition the space [3, 7]. Another option is to use balls centered at lattice points, which works well for f2 distance [2]. We use these ideas to design sparse networks. For uses of LSH in deep learning, sketch-based memory improves network capacity [15, 30]. Other empirical work uses LSH to improve dense network training time memory [8, 9, 31]. Our work differs from the prior studies because implement the LSH-based approach with sparsely activated networks, with the goal of reducing inference time and achieving low regression error. LSH-based sparsity may be most relevant for vision transformers [24, 33, 42], using distance metrics and routing functions tailored to images, or for time series analysis [41].
2 Preliminaries
Let f -
+ E be multivariate real-valued function that want learn with a neural network. We consider regression, and we aim to minimize the mean-squared error or the foo error. For parameter E N+, a set T, function
r R and estimator fn. r + IR, we define || folloo = sup (f() (x)]- For some results, approximate on subset V S Rd. For example, V may be the intersection of [-1, 1] and a k-dimensional subspace. We say that is L-liischitz if [xx f(x') s L. || x 21112 for all a, a' Rdd Let [n] = =1,,....,,
2.1 Data-Dependent Sparse Model
A dense neural network with fully connected final layer can be expressed as g(x) = A Φ(x) where E Rixt is a matrix and Φ IRd - RR. is a function (e.g., & captures the representation learned up until the final layer). Here, / the width of the final layer and is the input dimensionality.
Our focus is on the types of networks captured by what we call the Data- Metaa-Deennent Sparse Model (DSM). This is network with sparsely activated final layer. Formally, let be the width, and let 8 < f be a sparsity parameter. Then, we consider functions g of the form g(x) = A" 6(x) where A E I 1xt and Φ d + R The crux of the model the final layer. The sparsity comes from letting A A mask(æ), (x), where mask(z) E (0. 1 is s-sparse indicator vector, and "o" is the entry-wise product. The mask zeroes out certain positions, and A contains the learned weights but no longer depends Intuitively, the mask is the "routing function" for the sparse activations, To do

---

so, we define mask(x)) o (zx) ) to mean that we zero out element of the vector o(x). Then, we have
g (z) = (A o (a = (mmas((z) Φ(x)).
Under the above definitions, let DSM 8, be the set of functions = (A o mask(x)) ((x).. In what follows,
A shorthand for A mask(z)).
In the DSM model, we wish to understand the effect of sparsity on how well the network can approximate certain functions. It is important to allow the final layer A E gxxt to be data-dependent. The values in A depend on the target function f, and we learn this from training data.
Real-worid transformers may have multiple sparse layers. To capture this, we can compose DSM functions. For example, two sparse layers comes from (xx) A o maskg o Φ2 (mask, (2) o Φ (z)). For simplicity, we focus a single sparse layer in what follows, which suffices for our main results.
2.2 Hash-based Routing
Prior sparse models compute hash functions of the input vector x to determine mask and the network activations [34]. Our main theorem uses this strategy, considering LSH families. LSH has the property that nearby points are more likely to end up in the same hash bucket than far away points. We can use LSH to define a general class of efficient regression functions. In Section 3, we prove that the DSM model captures popular sparse architectures and the following LSH model.
LSH Model. We review an LSH framework based on sign patterns. Let hı,..., hm Rd - 1-1,1}
be m distinct hash functions. Partition the space into 2 buckets based on the m sign patterns Za = (hr (z).... (x))) over all x E IR Then, for each { ! we specify function (x(),, where the goal is for Is to approximate the target function f in the part of space associated with = (i.e., points that have pattern under h.,..., hm). More generally, we allow sets of such hash functions (hi....//,, N, and 8 sets of these approximation functions ......... F2-) for i i= l...... S. On input æ, we compute the sign patterns 2!, ...... 2 and output g(x) = Ei=ı agg", (z). Further, we can restrict each g to be degree A 2 0 polynomial. For a fixed LSH family of possible hash functions, we let LSH 8, m, A) denote this class of functions. In many cases, we only need G. to be a constant function, i.e., A = O, and we shorten this as LSH(d, s, m. 0) == LSH(d,, s, m). Our goal is understand the trade-off's of the "memory" parameter m and the "sparsity" amount 8 that we need to approximate large classes of d-dimensional functions (i.e., I--Lipschitz functions supported k-dimensional manifold).
Euclidean LSH Model [11]. This is a popular LSH family for points in Rdd In this case, each hash function outputs an integer (instead of +1 above). Each bucket in this model is defined by set of hyperplane inequalities. There are two parameters (m') e) with m' E N+ and e E (0, 1]. We sample m' random directions d1,... ... a'n' with each coordinate of each a; being an independent standard normal random variable. In addition, we sample b; ~ Unif c] independently for E [m']. For a point x E Rd, we compute an index into a bucket via a function by : RRd + Z defined as
a x b
hx(x)= =
Here, the index ranges over i E [mn'), leading to a vector of D integers.
3 Simulating Models with DSM
We formally justify the DSM(d, s, model by simulating other models using it. We start with simple examples (interpolation and & nearest neighbor (k-NN) regression), then move on to transformers and the LSH model. For the simple examples, we only need one hidden layer, where Φ(x) = o (Bx) for matrix B E I and lineaiiy a.
Interpolation. We show how to compute f at points 21....,:1. where b, is the ith row of B.
Zt- We only need sparsity and a is simply the identity function. We set A, = fx,)) Further, we let mask(x;) ) have one in the ith position and zeroes elsewhere. Then, define g(xx) = (A o mask(x:)) Br; = f(x), which computes f at the / input points.
1
Sparse networks perform K-NN regression.

---

We sketch how the DSM(d, k n)) model can simulate k-NN with g(z) = (A o mask(r)) (Bz)) when the dataset contains vectors with unit & norm. Let the rows of B be set of n unit vectors b1,...,h, An E IRd. For the target function f. let A = [(()),...... . [(b,)) )) Define a (Bx) to have ones the top largest values in Br and zeroes elsewhere. For a unit vector x; these h positions correspond to the k largest inner products (x. b,)- Since || bull2 = 2 - 2(x, b,). the non-zero positions in or (B) encode the k nearest neighbors of x in {b1.....6 ..,,.. Thus, g(x) computes the average of f at these k points, which is exactly k-NN regression. Moreover, only k entries of A are used for any input, since (Ba) is k-sparse; however, computing a (Bz) takes ((nd) time. While there is computational advantage from the sparsity in this case, the fact that DSM can simulate k-NN indicates the power of the model.
3.1 Simulating transformer models with DSM
Real-world networks have many hidden layers and multiple sparse layers. For concreteness, we describe how to simulate sparsely activated final layer. As mentioned above, we can compose functions in the DSM model to simulate multiple sparse layers.
Switch Transformers [14]. The sparse activations in transformers depend on routing function R: IR + {1....,&) f). where R(x) specifies the subnetwork that is activated (for work on the best choice of R, see e.g., [34]). To put this under the DSM 8,() model, consider a of trainable matrices Al...., A E R Rixx, where the total width is t s l for integral i 2 1. On input æ, we think of A 1 X matrix with s non-zero entries equal to An(x). In other words, A is the concatenation of A . ; Ag, and mask(x)) is non-zero on the positions corresponding to AR(a)-
Scaling Transformers [21]. The key difference between Switch and Scaling transformers is that the latter imposes block structure on the sparsity pattern. Let / be the width, and let s be the number of blocks (each of size = 1/s). Scaling Transformers use only one activation in each of the 8 blocks. In the DSM s, t) model, we capture this with A as follows. Let C₃ E {0, 13 denote the standard basis vector (i.e., one-hot encoding of i E [t]). The sparsity pattern is specified by indices (fi,..., i.). Then, A (ajei) Obei,) for scalars a),..., Ct. E R.
3.2 Simulating the LSH model using DSM
We explain how represent the LSH model using the DSM model. The key aspect is that A depends on the LSH buckets that contain x, where we have non-zero weights for the s buckets that contain each input. This resembles the Scaling Transformer, where we use the LSH buckets to define routing function. In the LSH(d, s, m, A) model, there are s sets of m hash functions, leading to s 2n hash buckets. We use width t 2 for the DSM(d, s, t) network. The entries of A are in one-to-one mapping with the buckets, where only s entries will be non-zero depending on the s buckets that x hashes to, that is, the values (h) (z), ... hi, (z)) E (-1,1) for 1.2....,
We now determine the values of these & non-zero entries. We store a degree A polynomial g(x) _ + R associated with each bucket. For our upper bounds, we only need degree mention the general case for completeness. If A = O, then ğ is simply a constant a depending on the bucket. An input hashes to s buckets, associated with s scalars (a1,..., a.).. To form A3, set s entries to the a; values, with positions corresponding to the buckets. For degree A > 1, we store coefficients of the polynomials ÿ. leading to more model parameters. Section contains details on using LSH to approximate Lipschitz functions with sparse networks.
but we
Computing and storing the LSH buckets. Determining the non-zero positions in A only requires (ss)) hash computations, each taking (d) time with standard I.SH families (e.g.. hyperplane LSH). We often take m be large constant. Thus, the total number of operations forward pass in the network (smd) 2 O(sd). The variable m above determines the total number of distinct buckets we will have (2""). For an point dataset, m O n) is a realistic setting in theory. Therefore, 2 poly(n) is often reasonable size for the hash table and moreover the dense model requires width O(2m) as well. In practice, the number of experts is usually 32-128 [14, 33]. The hash function typically adds very few parameters. For example, to hash d dimensional data into 2n buckets, LSH requires 0(md) bits and takes ((md) time as well. In summary, the LSH computation does not asymptotically increase the number of FLOPs for a forward pass in the network. We also later bound the number of non-empty LSH buckets. The memory to store the hash table comparable to the number of samples required to learn the target function.
compute a
5

---

Data-Dependent Sparse Models are more Efficient than Dense Models
For general class of Lipschitz functions, L.HH-baed learners yield similar foo enror as dense neural networks while making inference significantly more efficient. It is common belief in the machine learning community that although many of the datasets we encounter can appear to live in high- dimensional spaces, there is low-dimensional manifold that contains the inputs. To model this, we assume in our theory that the inputs lie in a k-dimensional subspace (a linear manifold) IR Here k < d. Theorem 4.1 shows that the LSH model we propose can learn high -ineenninnii Lipschitz functions with a low Ég eπrоr efficiently when the input comes from a uniform distribution on an unknown low-dimensions subspace. Theorem B. extends this result to when the imput comes from an unknown manifold with a bounded curvature. We present Theorem 4.1 here and defer Theorem B.1 to Section B. All proofs are in the appendix.
Theorem 4.1. For any f [-1,1] R that is L-Lipschitz, for input distribution D that is uniform on k-dimensional subspace in [-1, an LSH-based learner can learn to c-uniform error with O(KLVd log(Lvd/e))/t) samples using a hash table of size OLLvd [E²) with proba- bility 2 0.8. The total time required for a forward pass new test sample is O(dk log(L./d/e))
The key idea behind this theorem is to use LSH to produce a good routing function. The locality of the points hashed to an LSH bucket gives us way to control the approximation error. By using large number of buckets, we can ensure their volume is small. Then, outputting a representative value suffices locally approximate the target Lipschitz function (since its value changes slowly). The next lemma bounds the size of the sub-regions corresponding to each bucket, as well as bounding the number of non-empty buckets.
Lemma 4.2. Consider Euclidean LSH model in d dimensions with Ck hyperplanes and width parameter e where C is a large enough constant. Consider region defined by the intersection of a k- d-dimensional subspace with 1-1, We have that the LSH model defines partitioning of into buckets. Let be a constant. Then, with probability 2 0.9.
1. Projecting any bucket of the LSH onto I corresponds sub-region with diameter e/c.
O(k)
2. At most
2vdd
buckets have a non-empty intersection with I.
The above construction assumes knowledge of the dimensionality the input subspace Fortunately, any upper bound on & would also suffice. The table size of the LSH model scales exponentially in but not d. Thus, an LSH-based learner adapts to the dimensionality of the input subspace.
Theorem 4. shows that sparsely activated models (using LSH of a certain table size) are powerful enough approximate and learn Lipschitz functions. Next, we show complementary nearly matching lower bound on the width required by dense model to approximate the same class of functions. We
information theoretic argument.
f-nnciinitzfuunctions on [-1, 1]dt to loe error when Theorem 4.3. Consider the problem of learning L L-Lipschitz functions
the inputs to the function are sampled from a uniform distribution over an unknown k-dimensional subspace of Rdd n [[-1, 1]a. A dense model of width w with random bottom layer requires
( ((VVLL (Ce)*
w 0
for a constani C > 0 learn the above class of functions. The number of samples required is
k( k(VaL)* log(2VdL/Ce)
Ω
(Ce)*
Our approach for this theorem is to use counting argument. We first bound the number of distinct functions, which exponential the number of parameters (measured bits). We then construct a large family of target functions that are pairwise far apart from each other. Hence, if we learn the wrong function, we incur large error. Our function class must be large enough to represent any possible target function, and this gives lower bound on the size of the approximating network.

---

Theorem 4.3 shows a large gap in the time complexity of inference using a dense model and an LSH model. The inference times taken by a dense model vs. a sparse model differ exponentially in 1/e.
(c(222
(a 2v Cc
Sparse: O (dk log(1/e)
vs.
Dense: Ω
(1)
Overall, the above theorems show that LSH-based sparsely activated networks can approximate Lipschitz functions on a k-dimensional subspace. The size and sample complexity match between sparse and dense models, but the sparse models are exponentially more efficient for inference.
5 Experiments
To empirically verify our theoretical findings, we align our experiments with our proposed models and compare dense models, data-dependent sparse models (DSM), LSH models, and sparse models with random hash based sparse layers. While DSM and LSH models are analyzed in the previous section, random hash based layers introduce sparsity with a random hash function, as an alternative of learnable routing modules and LSH in MoE models [34]. Our goal is to show that the DSM and LSH models achieve small MSE while using much fewer activated units than dense models. We also report similar observations on the CIFAR-10 dataset.
5.1 Experimental set-up
Dense, DSM and random hash sparse models contain a random-initialized non-trainable bottom layer, Top-K layer for DSM and a random hash layer for random hash models enforce sparsity), and trainable top layer, with varying number of hidden units and sparsity levels. LSH models have non-trainable hyperplane coefficients for hashing and trainable scalar in each bucket (the sealar determines the output of the network for points in that bucket). We compare dense models and three sparse models (DSM, LSH, and random).
We evaluate with synthetic data from two random, Lipschitz target functions that are commonly used basis functions for arbitrary continuous functions. These random functions allow us empirically evaluate the construction from Theorem 4.1, while comparing different routing functions.
Random polynomial, p(z) of degree d for E IR" with sum of coefficient absolute values 1/(d). As result, we ensure that the function 1-Lipschitz over 1],
Random hypercube function. ʃ [-1, 1| IR which interpolates the indicator functions each corner with random {-1,1} 1] value each corner. Concretely, the function defined as follows: for each corner point y (-1, 1) 1)", its indicator function [x)x) = II 2
1+y.0, Sample random
values Uy {} with probability 50,5.0.5 0.5) independently for each y E (-1, the random hypercube polynomial function is f(x) = Eye(-1,1>" (z)y(z).
Random 3-layer neural net function. f [| + R is a randomly initialized 3-layer neural network with fully connected layers.
For the random polynomial (random hypercube) functions, we use n and d 4 in the this section and provide more results for other parameter settings in the appendix (especially the case when the target polynomial functions concentrate on a low dimension subspace). We also present results on real dataset, CIFAR-10, which corroborates our findings from the synthetic data experiments.
5.2 Results
MSE for random functions. Figures 2 and 3 show the scaling behavior of the MSE for DSM and LSH models on random polynomial function and hypercube function (lower is better). Sparsity helps for the DSM and LSH models, both achieving better quality than dense models using the same number of activated units. Figure 4, we compare the DSM/LSH models with the random hash sparse models, and we see random hash sparse models underperform dense models, suggesting data- dependent sparsity mechanisms (such as DSM/L.SH) are effective ways to utilize sparsity. Table shows the scaling behavior of DSM and dense models for the randomly initialized 3-layer NN target
7

---

function. We see that at the same total width a sparser DSM model can perform as well as dense model.
FLOPs. To further qualify the efficiency gain of sparse models, we compare the MSF at the same FLOPs for sparse/dense models in Table 1. The first column is the # FLOPS for the dense model; models in the 3rd and 4th columns use same # FLOPs but have more parameters (only 50% or 25% active). DSM uses only 18k FLOPs and gets smaller MSE than dense model with 73k FLOPs.
FLOPs
eval MSE (dense)
eval MSE (DSM 50% sparsity)
eval MSE (DSM 25% sparsity)
18432
0.01015
0.01014
0.009655
36864
0.01009
0.007438
0.005054
73728
0.01046
0.006115
0.001799
Table 1: FLOPs and evaluation Mean Squared Error (eval MSE).
0.25
dense (victh x-axts values)
danse (width a-as values)
Mcan Squared Error
DSM (total wicth = 1024)
Mean Squared Eroo
LSH (# buckets = 1024)
0.20
DSM (total wicth = 2048)
buckets 2048)
DSM (total widhh - 4096)
LSH (# buckets 4096)
0.15
DSM (tonal width = 8192)
0:15
LSH buckets 8192)
0.10
0.10
0.05
0.05
0.00
16
64
255
1024
4096
16584
16
64 256
1024
4096
16584
Number of activated units (log scale)
Number activated unite (log scale)
Figure 2: Scaling behavior of DSM and LSH models compared with dense models for degree 4 random polynomial with input dimension 8: (a) DSM outperforms dense model at the same number of activated units and quality improves as total width increases; (b) LSH model outperforms dense model when number of buckets large (2 2048) and quality improves as number of buckets increase.
0.04
dense (wicth = x-axts values)
dense (width - axixs values)
Squared Erar
(total wicth 1024)
Mean Squared Erar
buckets 1024)
0.03
DSM (total with = 2040)
0.09
LSH (# buckets + 2048)
(totel
4096)
buckets 4096)
DBM (total witth - 8192)
LSH (4 buckets 8192)
0.02
0.01
0.01
0.00
16
256
1024
4096
16384
0.00
16
256 Number activated (log scale)
1024
4096
16384
Number activated (log scale)
Figure 3: Scaling behavior of DSM and LSH models compared with dense models for a random hypercube function with input dimension 8. Both DSM and LSH models outperform corresponding dense models with the same number of activated units (note: # activ. units < width).
Model Width
1024
2048
4096
Dense
4.32e-5
1.76e-5
7.4e-6
DSM with sparsity 32
1.3e-4
7e-5
2.3e-5
DSM with sparsity 64
1.le-4
3.
1,9e-5
DSM with sparsity 128
1c-4
4.2e-5
1.5e-5
DSM with sparsity 256
8.7e-5
3.7e-5
1.7e-5
DSM with sparsity 512
5.8e-5
3.8e-5
1,9e-5
DSM with sparsity 1024
6e-5
2.1e-5
2.2e-5
Table 2: MSE for random 3-layer NN target function.
8

---

dence (widthh i-axis values)
dense (width a-aads values)
Mean Squared Eneor
0
hash (total width 2046)
Erer
random hash (rotal widhh 2048)
DSM (totel width 2048)
0.00
DSM (total width 2048)
LSH (# buckets
LSH (# buckets 2048)
0.20
Mean
0.01
16
256
1024
4096
16384
0.00
1024
4096
16884
Number of activated units (log scals)
Number activated units (lag scale)
(b) random hypercube function Figure 4: Scaling behavior of dense, random hash, DSM, and LSH models. DSM and LSH models outperform dense models, while random hash models underperform dense models with the same number of activated units.
(a) random polynomial
CIFAR-10. We also compare the scaling behavior of DSM and dense models on CIFAR-10 [26]. The first baseline model is CNN with 3 convolutional layers (followed by max-poolinn max-pooling)) dense layer with varying number of units, and a final dense layer that computes the logits (referred as CNN + dense). For the data-dependent sparse models, we use the same architecture, except we change the penultimate dense layer with a data-dependent sparse layer (referred as CNN + DSM). Both models are trained with ADAM optimizer for epochs and evaluated on the test dataset for model accuracy with no data augmentation; see Figure 5 and Table 3 for the accuracy versus number of activated units. As with the synthetic datasets, DSMs outperform dense models at the same number of activated units. Next we also compare the scaling behavior of DSM and dense variants of Vision Transformer models on CIFAR-10. These results are presented Table 4.
5.3 Discussion
Our experimental results (e.g., Figures 2, 3, and 4) show that sparsely activated models can efficiently approximate both random polynomials and random hypercube functions. Intuitively, the DSM and LSH models employ the sparsity as way to partition the space into nearby input points. Then, because the target function is Lipschitz, it is easy to provide to local approximation tailored to the specific sub-region of input space. On the other hand, the uniform random hash function performs poorly for these tasks precisely because it does not capture the local smoothness of the target function.
On CIFAR-10, also see that the DSM model performs comparably better than the dense network. In particular, Figure shows that the "CNN + DSM approach with total width 1024 improves upon or matches the dense model. In this case, the sparse activation allows the network to classify well while using only a fraction of the number of FLOPs. In Table 3, we see that DSM model outperforms the dense model when we control for the number of activated units in the comparison.
Limitations, Our experiments focus on small datasets and 2-layer networks as a way to align with theoretical results. Prior work sparsely activated networks has shown success for large-scale NL. and vision tasks. Our experiments complement previous results and justify the DSM and LSH models by showing their ability approximate Lipschitz functions (consistent with our theorems). would be good to further evaluate the DSM and LSH models for large-scale tasks, for example, by using them as inspiration for routing functions in MoE vision transformers, such as V-MoE [33]. It would be interesting to evaluate on larger datasets, such as ImageNet as well. We experimented with handful of hyperparameter settings, but full search may lead different relative behavior between the models (similarly, we only evaluated a few parameter settings for the random functions and the synthetic data generation, which is far from exhaustive).
Conclusion
We provided the first systematic theoretical treatment of modern sparsely activated networks. To do so, introduced the DSM model, which captures the sparsity in Mixture of Experts models, such as

---

72
Teat sccuraty
68
CNN + DSM (total widti : 250)
CNN dense (width k-acs values)
Model # activated units
256
512
CNN DSM (total width
Dense
69.79
70.79
60
1024)
DSM (50% sparse)
70.74
71.33
65
52
Number of activated units (log scale)
128
255
512
1024
DSM (25% sparse)
69.8
71.68
Figure 5: Scaling behavior of DSM compared with dense CNN models on the CIFAR- dataset. Similar to Figure 4a, DSM outperforms dense models at the same number of activated units.
Table 3: CIFAR-10 test accuracy for dSn CNN models with the same num- ber of activated units. While not strictly mono- tonic, wider and sparser models outperform narrow and dense ones.
Model
Hidden Dimension
Number of Activated Units
Sparsity
Top- Test Accuracy
Dense
768
768
0%
79.8%
DSM-512
1024
512
50%
79.9%
DSM-384
1152
384
66.7%
79.2%
DSM- 128
1408
128
90.9%
80.1%
Table CIFAR-10 test accurace for dense/DSM Vision Transformer (ViT) models with the same number of activated units.
Switch and Scaling Transformers. We showed that DSM can simulate popular architectures well as LSH-based networks. Then, we exhibited new constructions sparse networks. Our use of LSH to build these networks offers a theoretical grounding for sparse networks. We complemented our theory with experiments, showing that sparse networks can approximate various functions.
For future work, it would be interesting to implement LSH-based networks transformers for language/vision tasks. A related question is to determine the best way to interpolate in each LSSH bucket (e.g., higher degree polynomial may work better). Another question is whether a dense model is more powerful than sparse model with the same number of total trainable parameters. Theorem 4.1 only says that sparse model with similar number of parameters as a dense model can more efficiently (fewer FLOPs) represent Lipschitz functions. This does not say all functions expressible by a dense model are also expressible by sparse model. This is non con-trivial question as A depends on the input (i.e., DSM (d, t, t) may be more expressive than the dense model with width f). We expect that dense networks can be trained to perform at least as well as sparse networks, assuming the width large enough. The dense networks should optimize the weights the last layer to approximate the function, but they may not favor certain neurons depending on the input.
References
[1] James Urquhart Allingham, Florian Wenzel, Zelda E Mariet, Basil Mustafa, Joan Puigcerver, Neil Houlsby, Ghassen Jerfel, Vincent Fortuin, Balaji Lakshminarayanan, and Jasper Snoek. Sparse MOEs meet efficient ensembles. arXiv preprint arXiv:2110.03360, 2021.
[2] Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In 2006 47th annual IEEE symposium on foundations of computer science (F0CS'06), pages 459-468. IEEE, 2006.
[3] Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt, Prac- tical and optimal ish for angular distance. In Proceedings of the 28th International Conference on Neural Information Processing Systems- Volume I, pages 1225-12333 2015.
Dystems-Volume
10

---

[4] Alexandr Andoni, Piotr Indyk, and Ilya Razenshteyn. Approximate nearest neighbor search in high dimensions. Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 3287-3318. 8. World Scientific, 2018.
[5] Mikel Artetxe, Shruti Bhosale, Naman Goyal, Todor Mihaylov, Myle Ott, Sam Shleifer, Xi Vic- toria Lin, Jingfei Du, Srinivasan Iyer, Ramakamth Pasunuru, et al. Efficient large scale language modeling with mixtures of experts. arXiv preprint arXiv:2112. 2021.
[6] Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. 11000005141655 14165, 2020.
[7] Moses Charikar. Similarity estimation techniques from rounding algorithms. Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 380-388, 2002.
[8] Beidi Chen, Zichang Liu, Binghui Peng. Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, and Christopher Re. Mongoose: A learnable Ish framework for efficient neural network training. In International Conference Learning Representations, 2020.
(9] Wenlin Chen, James Wilson, Stephen Tyree, Kilian Weinberger, and Yixin Chen. Compressing neural networks with the hashing trick. In International conference on machine learning, pages 2285-2294. PMLR, 2015.
[10] Zizhong Chen and Jack Dongarra. Condition numbers of gaussian random matrices. SIAM Journal on Matrix Analysis and Applications, 27(3):603-620, 2005.
[11] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry, pages 253-262, 2004.
[12] Jacob Devlin, Ming-Wor Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:18100 0.0054 2018.
[13] Nan Du, Yanping Huang, Andrew M Dai, Simon Tong, Dmitry Lepikhin, Yuanzhong Xu, Maxim Krikun, Yanqi Zhou, Adams Wei Yu, Orhan Firat, et al. Glam: Efficient scaling of language models with mixture-of-exppe
arXiv preprint arXiv:2112.06905, 2021.
[14] William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. arXiv preprint 1XXi::2101103961, 2021.
[15] Badih Ghazi, Rina Panigrahy, and Joshua Wang. Recursive sketches for modular deep learning. In International Conference on Machine Learning, pages 2211-2220. PMLR, 2019.
[16] Sariel Har-Peled. Geometric approximation algorithms. Number 173. American Mathematical Soc., 2011.
[17] Geoffrey Hinton. Lecture Notes, Toronto, Hinton, 2012, http://www.cs cs. www.otoooooteoooeeo wtt_ssssdss_eeeeee pdf.
[18] Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. arXiv preprint a0Xiv:2102.00554, 2021.
[19] Robert A Jacobs. Methods for combining experts' probability assessments. Neural computation, 7(5):867-888, 1995.
[20] Robert A Jacobs, Michael Jordan, Steven J Nowlan, and Geoffrey E Hinton. Adaptive mixtures of local experts. Neural computation, (1):79987, 1991.
[21] Sebastian Jaszezur, Aakanksha Chowdhery, Afroz Mohiuddin, łukasz Kaiser, Wojeiech Gajew- ski, Henryk Michalewski, and Jonni Kanerva. Sparse is enough scaling transformers. Advances in Neural Information Processing Systems, 34, 2021.

---

[22] Michael Jordan and Robert A Jacobs. Hierarchical mixtures of experts and the EM algorithm. Neural computation, 6(2):181-214, 1994.
[23] Kukjin Kang and Jong-Hoon Oh. Statistical mechanics the mixture experts. Advances in neural information processing systems, 9, 1996.
[24] Salman Khan, Muzammal Naseer, Munawar Hayat, Syed Waqas Zamir, Fahad Shahbaz Khan, and Mubarak Shah. Transformers in vision: A survey, arXiv preprint arXiv:2101.01 169, 2021.
[25] Young Jin Kim and Hany Hassan Awadalla. Fastformers: Highly efficient transformer models for natural language understanding. arXiv preprint arXiv:2010. 13382, 2020.
[26] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[27] Dmitry Lepikhin, HyoukJoong Lee, Yuanzhong Xu, Dehao Chen, Orhan Firat, Yanping Huang, Maxim Krikun, Noam Shazeer, and Zhifeng Chen. Gshard: Scaling giant models with con- ditional computation and automatic sharding. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[28] Zhuohan Li, Eric Wallace, Sheng Shen, Kevin Lin, Kurt Keutzer, Dan Klein, and Joseph Gonzalez. Train large, then compress: Rethinking model size for efficient training and inference of transformers. arXiv preprint arXiv:2002. 11794, 2020.
[29] Xiaonan Nie, Shijic Cao, Xupeng Miao, Lingxiao Ma, Jilong Xue, Youshan Miao, Zichao Yang, Zhi Yang, and Bin Cui. Dense-to-sparse gate for mixture-of-experts. arXiv preprint arXiv:2112. 14397, 2021.
[30] Rina Panigrahy, Xin Wang, and Manzil Zaheer. Sketch based memory for neural networks. In International Conference on Artificial Intelligence and Statistics, pages 3169-3177. PMLR, 2021.
[31] Jack W Rae, Jonathan Hunt, Tim Harley, Ivo Danihelka, Andrew Senior, Greg Wayne, Alex Graves, and Timothy P Lillierap. Scaling eeemory-augmentt neural networks with sparse reads and writes. arXiv preprint arXiv:1610.09027, 2016.
[32] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint 1910: 10683, 2019.
[33] Carlos Riquelme, Joan Puigcerver, Basil Mustafa, Maxim Neumann, Rodolphe Jenatton, André Susano Pinto, Daniel Keysers, and Neil Houlsby. Scaling vision with sparse mixture of experts. Advances in Neural Information Processing Systems, 34, 2021.
[34] Stephen Roller, Sainbayar Sukhbaatar, Arthur Szlam, and Jason Weston. Hash layers for large sparse models. arXiv preprint 100.:22000004426,, 2021.
[35] Mark Rudelson and Roman Vershynin. Smallest singular value of a random rectangular matrix. Communications Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62(1)): 11122)::777770 707-1739, 2009.
[36] Noam Shazeer, Youlong Cheng, Niki Parmar, Dustin Tran, Ashish Vaswani, Penporn Koanan- takool, Peter Hawkins, HyoukJoong Lee, Mingsheng Hong. Cliff Young. Ryan Sepassi, and Blake Hechtman. Mesh-tensorflow: Deep learning for supercomputers. In S. Bengio, H. Wal- lach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information P Processing Systems, volume 31. Curran Associates, Inc., 2018
[37] Noam Shazeer. Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc V. Le, Geoffrey E. Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely- -attdd mixture-of- experts layer. In ICLR (Poster). OpenReview.net, 2017.
[38] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15()):1929-1958 2014.
12

---

[39] Gregory Valiant and Paul Valiant. Estimating the unseen: an n/log (n)-sample estimator for entropy and support size, shown optimal via new clts. Proceedings of the forty-thing anmual ACM symposium Theory of computing, pages 685-694, 2011.
[40] Shuohuan Wang, Yu Sun, Yang Xiang, Zhihua Wu, Siyu Ding, Weibao Gong, Shikun Feng. Junyuan Shang, Yanbin Zhao, Chao Pang, et al. Ernie 3.0 titan: Exploring larger-scale knowledge enhanced pre- vee-traiing for language understanding and generation. arXiv preprint arXiv:2112.12733 2021.
[41] Qingsong Wen, Tian Zhou, Chaoli Zhang, Weiqi Chen, Ziqing Ma. Junchi Yan, and Liang Sun. Transformers in time series: A survey. arXiv preprint arXiv:2202.07722 2022.
[42] Bichen Wu, Chenfeng Xu, Xiaoliang Dai, Alvin Wan, Peizhao Zhang, Zhicheng Yan, Masayoshi Tomizuka, Joseph Gonzalez, Kurt Keutzer, and Peter Vajda. Visual transformers: Token-based image representation and processing for computer vision. arXiv preprint arXiv:2006.0333 03677, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See sections C and 5
(b) Did you describe the limitations of your work? [Yes] See Sec. 4 and 6.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Our work is primarily theoretical, without targeted applications.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 4 and Sections B and C of the Appendix.
(b) Did you include complete proofs of all theoretical results? [Yes] See Section 4 and Sections B and C of the Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed reproduce the main exper- imental results (either in the supplemental material or as URL)? [Yes] We include details to reproduce all datasets and experiments.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Details about our experiments are in Section 5 and Section D of the Appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
13

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "dSD3TyqYARq", "reviewer": "Reviewer_R3gt", "summary": "From my understanding, the main contribution of the paper is as follows:\n\n1. the authors capture the sparsity structure of these popular transformers. They model the transformers into DSM models.\n2. They show that the DSM model can represent the LSH model. \n3. They provide theory on the LSH model. These theories can be used to interpret the success of Switch and Scaling Transformers.\n4. Motivated by the theory, they proposed a new LSH-based model and run toy experiments to show its efficacy.\n\n\n\n", "questions": "See my comments below. ", "limitations": "I have the following concerns: \n\n1.  In the current  manuscript, the connection between contribution 1==>2==> 3==>4 is still a bit vague (see my comments in the **Summary** part) .\nWhen reading the current version, it is easy to get confused about the main contribution of the paper: is it \"explaining why general sparse model like Scale transformer works well.\"? Or is it \" designing new LHS methods to save inference costs?\" \n\nFor me, the contribution of the \"explaining...\" part outweighs the \"designing.. \" part. This is because the author didn't provide any real-data experiments on LSH. If no real-data experiment is provided, LSH is a pure theoretical tool to prove the theory on DSM and the \"designing.. \" part is minor. However, the current script over-emphasizes the \"designing..\" part, causing great confusion for me. \n\n2. The performance of DSM on CIFAR-10 does not quite match the theory. To support the theory, I would suggest the authors run experiments on transformer-based NLP tasks instead of CV tasks on CIFAR. \n\n3. All the theories are built on the function Lipschitz assumption. It would be better if the authors verify the Lipschitz condition. Is it a necessary condition or it is due to the limitation of the theory?  If it is the latter case, what is the main technical challenge to relax this assumption?\n\n\n4. In line 255, why is random d-degree polynomial a Lipschitz function?\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "See my comments below. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_1x2JkFVl9V", "reviewer": "Reviewer_dumi", "summary": "This paper provides a theoretical treatment of modern sparsely activated networks with the Data-dependent Sparse Model (DSM) model. The authors show that the DSM model can simulate modern sparsely activated networks and the locality sensitive hashing (LSH) model. It is proven in the paper that the LSH model can be expressive as a dense network for approximating real-valued Lipschitz functions while requiring much fewer FLOPs. Furthermore, experiments are conducted to validate the theoretical findings on Lipschitz target functions as well as the CIFAR-10 dataset.", "questions": "See weaknesses. I am not very sure how experiment results reflect the theoretical findings in the paper. I would appreciate it if the authors could explain it.\n\nI am not very familiar with the field. Thus please correct me if I make any mistakes and I am happy to change my scores if my concerns/questions are addressed. \n\n[Minor issues:]\n1. Line 141: Why non-linearity \\sigma is left out?\n2. Line 143: I am not very sure why mask(x) is left out.\n3. Line 272: maybe a typo 'qualtify'?", "limitations": "Yes, the authors have addressed the limitations and potential negative societal impact of the work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The paper is the first work to treat sparsely activated networks theoretically, thus novel to me. \n2. The paper is well-organized.\n\nWeaknesses:\n1. The theoretical analysis is based on the assumption of the L-Lipschitz target function and I am not sure how significant the work is. Furthermore, the neural network size used in the experiment is also very small.\n2. I am not very sure about the relation between the theoretical findings and experiments. Theorem 4.1 and Theorem 4.3 conclude that LSH-based sparsely activated networks can be expressive as their dense counterparts when their size and number of samples match. As for size, the LSH model is measured using hash table size and the dense model is measured using width. As a result, in experiments, I am expecting to see the LSH model is as good as dense ones when # buckets == width of the dense network. However, in the figures, the width of dense networks is compared to the number of activated units.\n3. For comparison of DSM and dense networks, the authors mention that 'Sparsity helps in both DSM and LSH models, ... using the same number of activated units.' However, it seems that the comparison may be unfair. Specifically, with 64 activated units, DSM chooses the best 64 units out of total of 1024 units while the dense one has only 64 units in total. It seems unsurprising to me that DSM is better than its dense counterpart.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HwY4PbHEwLg", "reviewer": "Reviewer_deSo", "summary": "The paper studies the Mixture of experts (MoE) architecture which has become popular in NLP recently as a way to increase the capacity of network without increasing depth.\nThe authors aim to develop a theoretical understanding of the MoE model/conditional computation. The authors begin with a formal model for conditionally activated sparse models which can capture common existing MoE models. The authors use LSH (locally sensitive hashing) for the gating in MoE and use this to derive a few theoretical results regarding the ability to approximate real valued Lipschitz functions in Rd.\n\nThe authors perform some small scale experiments to back up and verify their theoretical findings.\n\n######## POST REBUTTAL ######\nThanks to the authors for running the experiments and for sharing the insights. Like I said earlier, it is important to study the theoretical underlining of MOEs. This paper starts with it, although as a researchers actively working in MOEs, I do not think that the paper exactly answers the key questions. The results proven are expected and not surprising, but on the other hand, as pointed by the authors, non-trivial to prove. So I would say that it is a decent paper at the moment and would suggest the authors to keep going in this direction to develop a more thorough understanding so that they can uncover some more fundamental results.", "questions": "I feel that the paper is quite borderline at the moment. It is important to have a theoretical understanding of the MoE models. The theorems prove some results which are expected and nothing surprising. On the other hand, they have not been proved. My suggestion would be to get more experiments to make the paper stronger.", "limitations": "Very well discussed.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Relevant Problem\n- MoEs are becoming very popular in NLP. Thus it is important to study their underlying theoretical and working mechanisms. The paper tackles this relevant problem.\n\n2. LSH (locally sensitive hashing)\n- Authors propose to use LSH for gating. This can actually be quite promising in my opinion because it takes the local vicinity into consideration. \n\n3. Well written\n- It is a very well written paper and is easy to follow\n- I really like the limitations section. It is good to see for a change that there is somebody who knows and writes the limitations of their work.\n\nWeaknesses:\n1. Weak Experimental Evaluation\n- I think that LSH is infact good. Authors need to perform more experiments to show its effectiveness.\n- I am not suggesting to go to the huge model sizes but atleast medium scale models and datasets should be evaluated.\n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HPdnm2kaPfJ", "reviewer": "Reviewer_yqbh", "summary": "This paper proposes the DSM model to sparsely approximate Lipschitz functions. The authors theoretically demonstrate their method in a wide range of scenarios, from one-layer shallow neural networks to switch and scale transformers. The original idea (but I am not sure as I am not familiar with this domain) of interpreting DSM as KNN is very interesting. However, :(, the experiment setting is a bit weak and seems to be finished in a rush. \n\n\n####\nI have increased the rating from 4 to 5 after rebuttal.", "questions": "Are there any potential competing methods in the related domain, especially those approaches like network pruning? Work like that may not worry about not getting sota results in performance, as it provides a new perspective for pruning networks. But providing a comparison with some competitors can make readers better understand the advantage and impact of this work.", "limitations": "1. I strongly encourage the authors to add figures to illustrate their concepts and ideas.\n2. Experiments on SOTA neural networks will be much appreciated.\n3. Needs a more detailed ablation study to justify the theory results.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Clarity: \n## Strengths: \nThis paper offers a detailed introduction to the LSM model and other background knowledge. \n## Weaknesses:\nIf the authors can further unify the usage of notations, the overall readability will be better. For example, the authors use s for the sparsity parameter, but in sec. 3.0 it switches to k, and later, k is used as the intrinsic dimension of input distributions.  The usage of notation A^x is also a bit confusing.\n\nI also recommend the authors add some figures to illustrate their idea. For example, the Euclidean LSM and sec 3.0 can be well explained by figures.\n\n# Originality:\nI am not familiar with this domain, so I may not be able to judge this point.\n\nBut still, I find the argument in sec. 3.0 interesting. It points out a potential direction in that we may interpret neural networks as KNN operators. The current content can be enhanced in some directions. The authors may try to remove the constraints of unit B rows, typical network blocks like CNNs, Attention networks, and Residual connections, do not have such unit structures. Also, extending it to deep neural networks will be more attractive.\n\n# Quality:\n## Strengths:\nThe theory analysis is careful and in depth. But some settings and assumptions need either explanation to justify the necessity or adjustment to cater the practice demands.\n\n## Weaknesses:\n### Weird experiment setting:\n1. Now that the main point is the efficiency of the proposed method, why not report inference time? FLOPS is a good metric but not enough.\n2. Needs more detailed ablation study. Specifically, detailed study on how sparsity parameter s influence the model accuracy, approximation MSE, and inference time.\n3. Now that the paper put much attention on discussing input distributions, the authors should also use input distributions on low dimensional manifold in R^n. Currently it is unclear how the input is sampled.\n4. From numerical perspectives, polynomial may not be good choices, as they tend to be extreamly ill conditioned when degree is high. The authors may consider B-spline or Bézier curve for some realistic industrial scenarios. Also, random neural networks, even shallow ones, may be good candidates.\n\n### Theoretical Settings need clarify and adjustments.\n1. It is a bit weird to assume input distributions be uniform, can it be replaced as absultely continuous with respect to the uniform distribution (Lebesgue measure)?\n2. Now that the proof is based on Euclidean LSH, it should be clearly stated in the theorems.\n\n# Significance:\nThe theory results is good, but needs stronger empirical evidence to support it.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept