Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
The 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.

The authors perform some small scale experiments to back up and verify their theoretical findings.

######## POST REBUTTAL ######
Thanks 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.
strengths_and_weaknesses: Strengths:
1. Relevant Problem
- 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.

2. LSH (locally sensitive hashing)
- Authors propose to use LSH for gating. This can actually be quite promising in my opinion because it takes the local vicinity into consideration. 

3. Well written
- It is a very well written paper and is easy to follow
- 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.

Weaknesses:
1. Weak Experimental Evaluation
- I think that LSH is infact good. Authors need to perform more experiments to show its effectiveness.
- I am not suggesting to go to the huge model sizes but atleast medium scale models and datasets should be evaluated.


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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: From my understanding, the main contribution of the paper is as follows:

1. the authors capture the sparsity structure of these popular transformers. They model the transformers into DSM models.
2. They show that the DSM model can represent the LSH model. 
3. They provide theory on the LSH model. These theories can be used to interpret the success of Switch and Scaling Transformers.
4. Motivated by the theory, they proposed a new LSH-based model and run toy experiments to show its efficacy.




strengths_and_weaknesses: See my comments below. 
questions: See my comments below. 
limitations: I have the following concerns: 

1.  In the current  manuscript, the connection between contribution 1==>2==> 3==>4 is still a bit vague (see my comments in the **Summary** part) .
When 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?" 

For 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. 

2. 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. 

3. 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?


4. In line 255, why is random d-degree polynomial a Lipschitz function?
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strength:
1. The paper is the first work to treat sparsely activated networks theoretically, thus novel to me. 
2. The paper is well-organized.

Weaknesses:
1. 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.
2. 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.
3. 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.
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.

I 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. 

[Minor issues:]
1. Line 141: Why non-linearity \sigma is left out?
2. Line 143: I am not very sure why mask(x) is left out.
3. Line 272: maybe a typo 'qualtify'?
limitations: Yes, the authors have addressed the limitations and potential negative societal impact of the work.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 


####
I have increased the rating from 4 to 5 after rebuttal.
strengths_and_weaknesses: # Clarity: 
## Strengths: 
This paper offers a detailed introduction to the LSM model and other background knowledge. 
## Weaknesses:
If 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.

I 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.

# Originality:
I am not familiar with this domain, so I may not be able to judge this point.

But 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.

# Quality:
## Strengths:
The 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.

## Weaknesses:
### Weird experiment setting:
1. 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.
2. Needs more detailed ablation study. Specifically, detailed study on how sparsity parameter s influence the model accuracy, approximation MSE, and inference time.
3. 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.
4. 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.

### Theoretical Settings need clarify and adjustments.
1. 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)?
2. Now that the proof is based on Euclidean LSH, it should be clearly stated in the theorems.

# Significance:
The theory results is good, but needs stronger empirical evidence to support it.

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.
2. Experiments on SOTA neural networks will be much appreciated.
3. Needs a more detailed ablation study to justify the theory results.
review_title: null

Meta-review: metareview: The paper provides a theoretical analysis of sparsely activated neural networks. They introduce LSH (local sensitive hashing) as a new routing function for theoretical analysis and proved a few results on representation power and inference time. One reviewer pointed out that the theoretical results are expected and do not provide much interesting insight, which I agree with. Nevertheless, this is one of the early papers that study sparsely activated networks and may serve as a starting point. I recommend acceptance. 

confidence: Less certain
Decision: Accept