MathNAS: If Blocks Have a Role in Mathematical Architecture Design

Summary

The paper introduces MathNAS, a novel approach to Neural Architecture Search (NAS) that utilizes mathematical programming techniques. MathNAS aims to improve the efficiency and accuracy of architecture search by dividing the search space into smaller building blocks and predicting network performance based on the performance of these blocks. The authors validate the effectiveness of MathNAS on computer vision (CV) and natural language processing (NLP) tasks, showcasing its superior performance compared to state-of-the-art models.

Strengths

1. Efficient Performance Evaluation: MathNAS proposes a general framework for evaluating candidate networks by estimating block performance first and then combining them to predict network performance. This approach greatly improves evaluation efficiency . 2. Reduced Search Complexity: By establishing a mapping between block performance and network performance, MathNAS transforms NAS into an Integer Linear Programming (ILP) problem, reducing the search complexity to polynomial time . 3. Superior Results: The authors demonstrate MathNAS's capabilities by considering key performance indices such as accuracy, latency, and energy. The results show that MathNAS outperforms state-of-the-art models in terms of these metrics .

Weaknesses

1. Lack of Detailed Implementation: The paper provides a high-level overview of MathNAS but lacks detailed implementation information. More specific details about the mathematical programming techniques used and the specific algorithms employed would have been beneficial. 2. Section 2.2 of the paper presents some significant ambiguities that complicate understanding of the proposed method: a. The paper does not clearly explain the definitions of "inherent capability" and "interactive capability". This makes it challenging to understand their intended meanings and how they function within the given neural network context. b. There is a lack of clarity on how the changes in these capabilities, represented as $\Delta \phi\left(\mathcal{B}{(i, 1) \rightarrow(i, j)}\right)$ and $\Delta \Phi\left(\mathcal{B}{(i, 1) \rightarrow(i, j)}\right)$, are evaluated. The methodology for these calculations needs to be explained more explicitly. c. Equation 3 lacks clarity due to the aforementioned uncertainties. Without clear definitions and calculation methods for the terms on the right-hand side, it is impossible to meaningfully interpret or apply this equation. d. Additionally, the processes of module swapping and internal adjustment are not well-defined. More details on how these operations are performed, both in terms of selecting which modules to swap and how the internal adjustments are made post-swap, are needed for a comprehensive understanding and replication of the method. Does every module have the sample input/output shape? 3. Limited Discussion on Generalization: Although the paper mentions MathNAS's remarkable generalization capabilities in designing efficient architectures for NLP tasks, there is limited discussion on the factors contributing to this generalization and how it compares to other NAS methods.

Questions

1. Can you clarify the approach or strategy employed to divide the networks into individual modules or blocks? 2. Based on observations from Figure 1b, the Floating Point Operations Per Second (FLOPs) appear to have minimal impact on latency. Could you provide an explanation or insight into why this phenomenon occurs? 3. Have you considered implementing a Graph Neural Network (GNN) model designed to predict performance variances that may arise as a result of interchanging different modules within the network? What outcomes or implications might this approach yield?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

The paper proposes a way to perform neural architecture search (NAS) by solving an integer program to identify the constituents of a block-modular neural net, having pre-computed estimations of performance for the separate blocks by a novel method. The resulting "MathNAS" approach is demonstrated in various experiments to be able to yield competitive neural network designs compared to other state of the art NAS methods. -- update: I have read and acknowledged all other reviews and the authors rebuttals, see discussion. --

Strengths

The novel performance estimation method appears to be well-motivated and leads to the possibility of applying mixed-integer programming to compute an optimal architecture (w.r.t. the utilized performance estimates). The numerical results indicate that this works well in practice, giving somewhat better or comparable results with notable savings in training time. This new NAS pipeline also shows promise for future refinements, e.g., regarding the MIP problems used for the search once performance estimates have been pre-computed, given the inherent flexibility of MIP to model a variety of different aspects.

Weaknesses

The paper must be thoroughly proofread for English language and grammar/typos. The supplementary document is as long as the main paper, but provides mostly only some small additional information; some things I hoped to find in the supplement were however not included, e.g., an explanation for the MIP objective function and a description or at least literature reference for how to turn the fractional objective into a linear one. Math typesetting especially of optimization programs can be improved. Also, I got the impression that the authors are trying a bit too hard to "sell" their ideas; maybe tone down the language a bit (there's very many usages of words like "impressive" or "remarkable" and similar phrasings praising the paper's results). Finally, there are several parts that remained somewhat unclear to me (see "Questions"), so the presentation can also be improved in terms of clarity/rigor.

Questions

- what exactly do you mean by "polynomial-time search complexity"? It is quite confusing to read something like "...can be transformed into an integer programming problem, which further reduces the search complexity to polynomial time" -- solving IPs is generally not possible in polynomial time! I suspect the authors mean that they need to pre-compute polynomially many values (for their performance estimation scheme), but this does not really become clear. - In the same vein, it is mentioned that some neural network training is necessary, but it is never clearly stated what and when. Again, I guess training is required to pre-compute the block performance scores somehow, but the details of this are too vague; this certainly needs to be clarified. - Could you describe a bit more how flexible the block/modular architecture is? (i.e., mention earlier that blocks can be construed of essentially any (finite) number of sub-network; this is never clearly stated and only becomes more clearly apparent in the supplementary document where details on the search spaces in the different experiments are given). - You claim at several points that the integer programs were solved with Gurobi (that is the solver name; Gurobipy is merely its Python interface...) on a GPU. I am quite sure that Gurobi does not run on GPUs. MIP solvers currently do not benefit from GPU vs. CPU computations; Gurobi even explain this on their website. So, please clarify and correct/elaborate in the paper! (Also, state the Gurobi version you used.) - Please clarify what exactly is being sampled (and to what purpose exactly) in Section 2.3 - Please justify the IP objective function and clarify/give a reference for how the fractional IP can be turned into a linear IP.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

4 excellent

Limitations

Limitations have by and large been addressed sufficiently.

Summary

This paper introduces MathNAS, a mathematical programming NAS algorithm. MathNAS maps network performance to block performance, enabling the prediction of accuracy, latency, and energy consumption of large networks based on their constituent modules. This algorithm reduces the search space from n^m to m*n, allowing the NAS problem to be solved as an Integer Linear Programming problem.

Strengths

Overall, this paper is well-written and organized, making it easy to follow along. The authors did a great job explaining their methods in detail, complete with loads of equations and clear explanations. Plus, the proposed algorithm has undergone numerous experiments under different models and application fields, which consistently showcase its effectiveness.

Weaknesses

1) In all the experiments, MathNAS takes significantly less "search time" than the other methods, especially some methods need thousands of hours while MathNAS only requires several seconds, which is very impressive. Is the time for all the other methods include the model training time (either training time of supernet or the subnet)? If yes, for the fair comparison, for the MathNAS, should the time that needed to train the base model be added to this time as well? Also, as algorithm 1 shows that there are three steps for MathNAS to determine the best architecture, should the time that calculate each block's performance also be added to the total "search time"? 2) The order of the tables and the description of the experimental results in the paper do not follow the same order. For example, the text follows GNN -> CNNs (Table 2) -> ViT -> NLP (Table 1) -> Dynamic Networks (Table 3), which leads is hard to follow. 3) A typo in paragraph "MathNAS for Mobile CNNs ...", the top-1 accuracy of MathNAS-MB1 is 75.9% as shown in the table, not 76.4%.

Questions

In all the experiments, MathNAS takes significantly less "search time" than the other methods, especially some methods need thousands of hours while MathNAS only requires several seconds, which is very impressive. Is the time for all the other methods include the model training time (either training time of supernet or the subnet)? If yes, for the fair comparison, for the MathNAS, should the time that needed to train the base model be added to this time as well? Also, as algorithm 1 shows that there are three steps for MathNAS to determine the best architecture, should the time that calculate each block's performance also be added to the total "search time"?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

This paper introduces MathNAS, a blockwise NAS framework. It begins by estimating the performance of the building blocks within the search space and then predicts the overall performance of a network based on the performance of its individual building blocks. This approach effectively reduces the complexity of network search from O(n^m) to O(nm). Additionally, a block performance evaluation scheme, utilizing average FLOPs, is proposed to further reduce the time complexity from O(n^m) to O(nm). Lastly, the network search process is formulated as an Integer Linear Programming (ILP) problem.

Strengths

* Clarity: The paper is effectively written, employing appropriate mathematical notations throughout. * Quality: The experiments conducted in the paper are of high quality, as they include a comprehensive comparison with well-known networks in various domains, such as tabular search space, mobile CNN, ViT, and NLP. * Originality and significance: While the paper presents valuable contributions, there are some concerns that should be addressed. Please refer to the weaknesses section outlined below.

Weaknesses

The paper does not cite a few highly relevant papers on blockwise NAS. * LANA: Latency Aware Network Acceleration. https://arxiv.org/pdf/2107.10624.pdf * Distilling Optimal Neural Networks: Rapid Search in Diverse Spaces. https://arxiv.org/pdf/2012.08859.pdf * BLOX: Macro Neural Architecture Search Benchmark and Algorithms. https://arxiv.org/pdf/2210.07271.pdf The authors should thoroughly discuss the distinctions between their proposed approach and the previously mentioned works, while also considering the possibility of conducting experiments to compare them. Specifically, LANA adopts a constrained ILP approach that relies on block metrics derived from factors such as delta-accuracy and delta-latency. The proposed approach bears resemblance to LANA. While the authors have made an effort to explain the validity of their approach, as depicted in Figure 1 and Section C of the appendix, it remains unconvincing that Equation 2 holds true under all circumstances. Additionally, Equations 3 and 4 are similar to those presented in LANA.

Questions

* Figure 1 in the appendix requires clarification. It appears to suggest the presence of three levels of blocks, with each level accommodating parallel blocks. Could you please clarify whether the blocks are connected sequentially or in parallel? Additionally, how many levels of blocks are there? * In Algorithm 1, there is an inconsistency with the existence of b_{i,0}, which does not align with the range specified for i (i={1, m}). Is this a typographical error? * Regarding the results on NB-201, it would be beneficial to know if multiple runs were performed to obtain averages using different seeds. Similarly, for the Mobile CNN, ViT, and NLP networks, were multiple runs conducted to calculate the means and variances?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The paper does not explicitly mention the limitations and potential negative social impact of their work.

Summary

This paper presents a divide-and-conquer neural architecture search methodology that estimates DNN performance based on the individual performance of each block within a DNN. Accuracy is estimated based on the perturbed accuracy of replacing a block within the NN, and latency/energy are also used within a linear model to predict NN characteristics.

Strengths

The paper is generally well-written and the results are strong compared to the chosen baselines from both CNNs and transformer based vision models. The efficacy of the method on 4 search spaces is impressive.

Weaknesses

There are 3 main weeknesses / questions that I have regarding the paper: 1. As a blockwise NAS approach, this paper largely ignores much of the prior literature on the topic, for example, [1,2,3]. These prior works also rely on blockwise layer statistics (sometimes obtained through distillation) then the layerwise performance is assembled either with a learned predictor [1,2] or ILP [3] similar to what is proposed in this work. 2. A large part of the evaluation is done on NB201 which isn't a macro search space. I am a bit confused as to how that evaluation on NB201 demonstrates the presented blockwise methodology -- all blocks within NB201 are identical, just sized differently. Perhaps this is something the authors can clarify in the rebuttal? I understand that the plots in Fig. 1 are showing the accuracy delta when one block is replaced with another, bit this would switch out the entire network basically, right? 3. Some conclusions (e.g. line 156) may be too specific to NB201. The inverse correlation of flops and accuracy is not a hard rule and many counterexamples can be presented. On NB201 specifically, it is widely known that this holds. 4. Search cost is written as "10 minutes" does this include all the time to evaluate individual blocks and build up the model? I think this cost should be quantified clearly in the paper. [1] Distilling Optimal Neural Networks: Rapid Search in Diverse Spaces [2] Blockwisely Supervised Neural Architecture Search with Knowledge Distillation [3] LANA: Latency Aware Network Acceleration [4] BLOX: Macro Neural Architecture Search Benchmark and Algorithms

Questions

see above

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

see above