Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors consider the problem of designing accurate and computationally efficient deep sparse networks (DSNs), which are an important problem in applications with sparse features such as click-through rate or movie recommendation. The authors propose a new approach based on neural architecture search (NAS) using two techniques: distillation of the search space (of cross-features), and a progressive search algorithm. They show that their approach leads to improvements in both accuracy and inference time, on three datasets.
main_review: ## Strengths
- Machine learning problems with sparse features have popular applications, and so empirical improvements could have high impact.
- The two parts of the algorithm, distillation of the search space and progressive search over feature orders, appears to be well-suited to the problem.
- The results are strong. The authors pick a varied list of first-, second-, and high-order methods for comparison, as well as AutoFIS, the only other NAS-based DSN work that is open-source.  Table 1 and Figure 3 seem convincing.

## Points that could be improved
- Novelty/Impact. NAS has been applied to DSNs at least twice before, as cited by the authors. The ideas of distillation, and progressive search, have been known in the NAS community, although not used the same way as this work (e.g. [1] uses a technique to compress a DARTS-like search space). The main novelty/impact is combining and applying these ideas to the DSN setting, and showing that it leads to strong empirical performance. The technique is tailored to this application.
- Reproducibility: the authors give specific implementation details in the appendix, which is good. However, they do not release their code? They mention in the checklist (twice) that the code is released, but I could not find it. Can somebody correct me if I am wrong? Reproducibility is an important consideration, both in the field of NAS where reproducibility is a problem, and also for papers in which the largest contributions are empirical and application-specific, such as this paper. For example, open-source code can lead to higher impact.
- The authors conduct ablation studies for both the progressive search strategy and the distillation strategy, as well as a few more in the appendix (different ranks, output layer, embedding size), which is excellent. However, it would be helpful to put these ablation studies onto one plot, to better answer the question: which of the main techniques helped more (e.g. distillation or progressive search)?
- The paper is written okay. There are some places that could be made clearer. Section 3.3. seems a bit out of place, and related work shows up in different places, and for example, the footnotes on page 7 could me moved to the appendix.

## Overall
The paper is okay. The authors study DSNs using NAS, and the techniques are not extremely novel, but the execution of the techniques is well-done and leads to strong performance. Reproducibility could be improved. The decision could go either way, and currently I lean towards weak reject.

[1] https://arxiv.org/abs/1906.02869

limitations_and_societal_impact: The authors did not explicitly discuss limitations, as far as I could tell. Societal impact was addressed in the checklist.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a neural architecture search approach, PROFIT,  for deep sparse networks.  PROFIT introduces a distilled low-rank search space and a progressive search algorithm from the lower orders. The proposed method is evaluated on three benchmark datasets and the authors conduct extensive ablation study and discussion on the method. The paper is well written and very easy to follow even for people without a NAS background.
 

main_review: 1. Originality: Are the tasks or methods new? Is the work a novel combination of well-known techniques? (This can be valuable!) Is it clear how this work differs from previous contributions? Is related work adequately cited?

Neural architecture search is no longer a new task. However, this work proposes a very reasonable solution to address the high cost of neural architecture search. It also puts the focus on interpretable sparse architecture search, which seems to be a novel and interesting perspective.  The discussion with the previous work is extensive and also easy to follow. 

2. Quality: Is the submission technically sound? Are claims well supported (e.g., by theoretical analysis or experimental results)? Are the methods used appropriate? Is this a complete piece of work or work in progress? Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?

The submission is technically sound.  The authors provide an extensive evaluation of three benchmark datasets. For example,  they provide motivating plots (e.g., Figure 2) to help the readers understand their approach, which is very helpful.  The method itself is kind of straightforward, but it's well-motivated and also quite effective. 

3. Clarity: Is the submission clearly written? Is it well organized? (If not, please make constructive suggestions for improving its clarity.) Does it adequately inform the reader? (Note that a superbly written paper provides enough information for an expert reader to reproduce its results.)

This paper is very well written and very easy to follow. Even readers outside the NAS community can understand it.  The paper structure is clear.  There are a few typos in the paper, though. For example, the Aycronm PROFIT directly pops up in the abstract without reference. Line 260 extra space in the word "evaluate".  

4. Significance: Are the results important? Are others (researchers or practitioners) likely to use the ideas or build on them? Does the submission address a difficult task in a better way than previous work? Does it advance the state of the art in a demonstrable way? Does it p
rovide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?


The results seem important and  it also achieves the state-of-the-art performance on three datasets.    It might be inspiring for others in the NAS field  and the deep  sparse networks. 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a method for searching for the interaction of the feature columns in a CTR prediction application. The paper title suggests an application for deep sparse networks but it doesn’t seem to be explicitly tied with the requirement of the input being sparse. To this end, the paper proposes an iterative algorithm that incrementally learns the interaction tensor from lower rank to higher rank, and from lower order to higher order. Empirically it observes some benefits compared to current competitive methods on Criteo, Avazu and ML1M datasets.
main_review: ### Strengths
- The paper is clearly written.
- The proposed method is clear and relatively simple.
- It seems to outperform existing methods on several benchmarks.

---------------------------------------------
### Weaknesses
- **Significance of results:** While the proposed method almost achieves the best result across the board, I am not sure how significant it is. If we look at the AUC score, then it only improves upon the second best by 0.0002, 0.0027, 0.0008. I am no expert on these benchmarks but it still seems too small of a difference. How much difference does this bring in practice?
- **Limited scope and comparison to a more general architecture like Transformer:** As I mentioned in the summary, the paper focuses on the application of CTR prediction using a deep sparse network, but there is nothing in the method that actually relies on the input feature being sparse. In other words, the proposed method can be applied to anything that aims to look for high-order interactions among different dense features, but the scope is intentionally narrowed down for no reason. The compared methods are all densely populated in a very narrow domain. The author could also compare it with more general architecture like Transformers. One layer of the transformer allows pairwise interactions, and more layers can allow higher-order interactions. It is unintuitive what would be the benefit to directly learn an interaction tensor via the proposed approximation, as opposed to a more general method that involves attention.
- **Entangling rank vs. order:** I found it strange that the paper entangles the two concepts of rank and order. According to Algorithm 1, it is unclear why we want to increase both the rank and the order by 1. Alternatively, you could increase the order by 1 but have a rank-3 approximation throughout. But the current algorithm learns one vector at a time, so it means that the rank is also the same as the order.
- **Comparison to asymmetric low-rank space:** There can be an additional comparison in between “full space” and “PROFIT’s space,” where the space is low rank but asymmetric. In other words, it is unclear what benefit the assumption of symmetric tensors brings.

---------------------------------------------
### Conclusion
In conclusion, the contribution of this paper is clear. But I am not sure about its significance in terms of the results as well as the scope of the paper. Therefore, my initial rating is slightly below the bar.

Update: the rebuttal addresses most of my concerns and I increased the score from 5 to 6.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper targets applying NAS to Deep Sparse Network (DSN) domain. To search for a good DSN, previous methods that apply DARTS based method to search an encoding vector, where each element represents the probability to select feature-interaction. Due to the interaction grows in a factorial way, the search parameters will soon become intractable. This work proposes to decompose this vector into multiple low-rank ones, to reduce the search space dramatically.

Experiments on various datasets show a clear improvement comparing to the previous baseline AutoFIS. I would recommend accepting this one but since I am not really familiar with the DSN domain, I might change my mind based on other reviews.
main_review: # Strength

+ Interesting idea to consider order-priotity property in DSN
+ Reasonable toy-case demonstration, showing that the matrix of second-order interaction exploits a low-rank property comparing to randomly generated matrices, this makes the proposed low-rank method conceptually meaningful.
+ This method reduce the search parameters from O(M^O) to O(MO).
+ Results shows constant improvement over the previous baseline AutoFIS.

# Weakness

- Motivation
This work observes the previous baselines (AutoFIS and another one) that applies NAS technique to deep sparse network have extreme high search cost. However, I read the AutoFIS paper that uses DARTS as search strategy, where they only need maximum 12 min in their Table 1. To me this is not extremely high cost. What's the value of your work in terms of this? 

In addition, in Line 40 you go back to discuss the human-designed DSNs that has poor computational cost accuracy trade-off. As your method is not the first one apply NAS into DSN domain, to me, what's more interesting is to discuss the methods with NAS. Are they also suffering from this? Could you provide concrete numbers rather than `inferior efficiency`?

- Comparision with other methods
In the section 2.2, What's the difference in terms of methodology of other DSN with NAS baselines with your PROFIT? In other words, what makes your method search fast? If I understand correctly, it's your contribution to formulate the space encoding into low-rank PCA-like vectors to reduce the cost. Anyway, adding this info here might further enhance this section. And you probably want to emphasize this in the introduction as well.

- order-priority property, any justification?
The results shown in fig 2 only shows comparing to random matrices. This may not be sufficient to show the real order-priority property isn't it? 

## minor issues
- AutoDSN search space
The paper claims C is relatively large that burdens the search cost, isn't this true for any NAS problem? DARTs for example has a space with billions of architectures. I remotely sense that this search space is somehow different with the traditional one, as the feature interactions may not be simplified by the weight sharing approach. But this is not really clear to me, hope the authors can clarify further why this space is a NP-hard problem and why the traditional NAS approach cannot resolve this. I saw section 3.1 answers part of my problem. Please correct me if I understand anything wrong.


- Writing issues
Page 2 Line 38 - 39
> However, these works require extremely large search cost.... 

This line is redundant with the previous sentence 
> these methods are suffering from high search
38 costs, resulting in limited prediction performance and application value

limitations_and_societal_impact: Nothing special.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors study the problem of deep sparse prediction based on NAS.
In order to reduce the search cost, they propose a distilled search space, which is a low-rank approximation of the full space.
They also propose a progressive differentiable search to capture the order-priority in sparse prediction.
Numerous experiments are conducted to demonstrate the effectiveness of the proposed method.

main_review: In general, the paper is written well and easy to follow. However, I still have several concerns that the authors need to address:
1. **Questions about distilling the search space.**
(1) As Figure 2 shows, the authors only use the second-order interaction to conduct the experiment, so does the higher-order interaction also have similar properties? Please give some theoretical proofs or display the experimental results;
(2) Equation 5 is very confusing. Please explain the following questions in detail: 
    - Why A can be approximately equal to this form? 
    - What conditions are needed to meet this approximation and how about the error? 
    - What is the specific meaning of R, and how to set the value of R in the experiments. 
    - Please give the detailed proof and deduction process of equation 5.

2. **Questions about efficiency.**
(1) In lines 213-214, the authors point that only N_0 important weights are retained. What is the basis for the selection of N0, what is the specific value, and how the selection of N_0 affects the accuracy and effectiveness? Please give more detailed experiments and explanations.
(2) In lines 262-263, the authors point that the experiment only evaluated the inference time and the size of the models. I hope that the author should also give the computation cost during training and inferences, such as FLOPs or MACs or other indicators to illustrate the efficiency.
(3) The author just compared only one NAS-based baseline in terms of efficiency. More challenging baselines are needed, such as the methods based on pruning [1,2].

3. **Questions about experiments.**
(1) The performance improvement in Table 1 seems limited. For example, the AUC in the Criteo dataset is only increased by 0.0001 compared with AFN.
(2) In lines 112-113, the author mentioned that some similar NAS-based methods usually require a large search cost, but the author did not compare the search efficiency with these methods in the experiment.

[1] Liu, Siyi, et al. "Learnable Embedding Sizes for Recommender Systems." arXiv preprint arXiv:2101.07577 (2021).
[2] Zhao, Xiangyu, et al. "Memory-efficient embedding for recommendations." arXiv preprint arXiv:2006.14827 (2020).

limitations_and_societal_impact: Please refer to the main review.
review_title: null

Meta-review: This paper proposes using NAS for learning the feature interaction space for deep sparse networks that are used for high dimensional sparse networks commonly encountered in recommendation systems. The discovered architectures have higher efficiency compared to the baselines. 

During discussion period some points of confusion consistently came up regarding order-vs-rank and the fact that it was not explicitly clear that the search space in feature-interactions is several orders of magnitude bigger than that used in DARTS for CNNs due to the cardinality of the operators (7 or so in DARTs vs. 39 here).  This is a point that the authors can make clearer in the paper in the beginning itself. Otherwise the difficulty of the problem does not come about till later. 

Reviewers have also pointed out various ways to make presentation better like not using forward references to acronyms before definition. Since the main contribution of this paper is the search space and the progressive search over feature orders and not the NAS search technique the authors should emphasize that part explicitly and play to the strengths of the paper in presentation. 
Decision: Accept (Poster)