SiGeo: Sub-One-Shot NAS via Information Theory and Geometry of Loss Landscape

Thank you for your comprehensive review and constructive feedback on our manuscript. We appreciate the recognition of SiGeo's ability to bridge zero-shot and one-shot NAS, as well as the theoretical analysis we provided.

1. Novelty of SiGeo: We understand your concern regarding the novelty of SiGeo. We aim to clarify that SiGeo is not merely a combination of these elements but an innovative integration that leverages each component to address specific challenges in NAS. SiGeo's novelty lies in how these elements are unified into a coherent sub-one-shot framework, offering new insights and capabilities beyond their individual applications.

   • We clarify that the contribution of this work is not a new zero-shot proxy. Instead, we focus on showing the significance of the sub-one-shot and warm-up procedures, along with SiGeo's capacity to leverage information acquired as the candidate network improves with training.
   • We clarify that the objective of our zero-shot NAS benchmark experiments was not necessarily to demonstrate superior performance to the zero-shot approaches. Rather, our aim was to validate its "backward" comparability to the zero-shot setting.
   • We further included additional experiments; see the comment "New Experiments". To summarize, our experiments have shown an enhancement in the performance of the Fisher-Rao norm and training loss as the warm-up level increases.
   • Our key results in Table 1 and Figure 3 demonstrate that SiGeo with a 1% warm-up of supernet can achieve significantly better performance than ZiCo and comparable performance to one-shot NAS methods with a significant reduction in computational costs.
   • We also direct the reviewer to General Clarification of Contribution.

2. Utilization of Warm-Up in Main Experiments: Your observation about the lack of warm-up analysis in the main experiments is well-taken.

   • In response, we included an in-depth analysis of the correlation between warm-up periods and search accuracy in NAS benchmarks and CIFAR datasets. This will provide a clearer understanding of SiGeo's performance in various warm-up scenarios and its distinction from the ZiCo approach.
   • We also want to emphasize the novelty of this paper lies in the coherent integration of SiGeo proxy with weight-sharing NAS.

3. Experiments on NAS-Bench-201 and ImageNet: We agree that including experiments on NAS-Bench-201 and the ImageNet dataset would strengthen our findings. Some of our experiments in Section 4.3 were conducted on NAS-Bench-201 benchmark and datasets.

Responses to Questions

1. It seems a bit inconsistent that SiGeo utilizes both gradient mean and variance since Theorem 1 only provides gradient variance in the bound.

   • Response: We acknowledge the need for better clarity on this aspect. The absolute value of the gradient mean was appeared in the Theorem 2. as part of the lower bound of the minimal achievable training loss.

2. Theorem 2 only offers a lower bound analysis. It would be better to provide an upper-bound analysis

   • Response: Your suggestion for an upper bound analysis is valuable. We will explore this in our future work, thereby providing a more balanced theoretical perspective.

3. In section 4.2, is there a trade-off between a longer warm-up period (e.g., 60%, 80%) and consistency of SiGeo, or does a longer warm-up period consistently improve consistency?

   • Response: As two reviewers asked the same question, we have performed a side experiment study to illustrate the consistency of SiGeo. The results have been posted in the comment above "New Experiments".

Addressing Weaknesses:

1. Novelty of SiGeo: We understand your concern regarding the novelty of SiGeo, particularly in relation to its similarities with ZiCo, Fisher-Rao (FR) norm, and loss functions. We aim to clarify that SiGeo is not merely a combination of these elements but an innovative integration that leverages each component to address specific challenges in NAS. SiGeo's novelty lies in how these elements are unified into a coherent sub-one-shot framework, offering new insights and capabilities beyond their individual applications.
   • We clarify that the contribution of this work is not a new zero-shot proxy. Instead, we focus on showing the significance of the sub-one-shot and warm-up procedures, along with SiGeo's capacity to leverage information acquired as the candidate network improves with training.
   • We clarify that the objective of our zero-shot NAS benchmark experiments was not necessarily to demonstrate superior performance to the state-of-the-art (SOTA) zero-shot approaches. Rather, our aim was to validate its "backward" comparability to the zero-shot setting.
   • To better demonstrate the contribution of this work, we included additional experiments; see the comment above "New Experiments". It provides a more comprehensive comparison of our method against ZiCo under sub-one-shot setting in various NAS benchmarks. To summarize, our experiments have shown an enhancement in the performance of the Fisher-Rao norm and training loss as the warm-up level increases. Specifically, in the NAS-201 benchmark, the ranking correlation of the Fisher-Rao norm rose from 0.35 to 0.78 with an increase in warm-up from 0% to 20%. In contrast, the Zico proxy shows limited improvement with additional training.
   • Our key results are presented in Table 1 and Figure 3. It demonstrates that SiGeo with a 1% warm-up of supernet can achieve comparable performance to one-shot NAS methods but with a significant reduction in computational costs. In addition, SiGeo shows significant performance improvement over the SOTA zero-shot proxy ZiCo with a negligible increase in computational time.
2. Experimental Results Comparison: We acknowledge your observation about the lack of significant gains over ZiCo in CV tasks. In response, we have conducted additional experiments to more comprehensively compare our method against ZiCo under sub-one-shot setting; see the results in the comment above "New Experiments".

Responses to Questions:

1. The theoretical verification in Figure 2 is mainly conducted on a two-layer MLP-ReLU network, so whether this theory applicable to more complex networks? For example, for the architectures in NAS-Bench-201, what about the ranking consistency when warming up with 0%, 10%, and 40% data?

   • Response: we have performed the side experiment study to illustrate the consistency of SiGeo. The results have been posted in the comment above "New Experiments".

2. The experiments on the CV task only consider the zero-shot settings. What about the performance when involving SiGeo proxy under the sub-one-shot NAS framework?

   • Response: new experiments have been added to indicate the performance of SiGeo under the sub-one-shot NAS.

3. Similarly, in the RecSys experiments of Figure 3, the zero-shot NAS with SiGeo should also be compared.

   • Response: The zero-shot result of SiGeo is listed in Table 5 in Appendix I. We observe that without warm-up SiGeo performs on par with ZiCo in RecSys benchmarks.

4. Can the SiGeo proxy search for more complex networks on ImageNet, such as in the MobiletNet search space or the Transformer search space?

   • Response: Recognizing that the regularity assumptions of initiation, local convexity, and almost everywhere differentiability are generally easily met, we are confident in the applicability of SiGeo across various search spaces within the sub-one-shot setting. In our future work, we aim to thoroughly explore and validate this applicability. In the revised version of our manuscript, we will include preliminary findings and insights that underscore the potential and versatility of SiGeo in these broader contexts.

5. Since when $\lambda_2$ and $\lambda_2$ in Formula (7) are set to zero, SiGeo is simplified to ZiCo. Can other existing zero-shot proxies also improve performance by adding the two items?

   • Response: Theoretically speaking, when the candidate architecture has been warmed up, we believe that the integration of the two terms from Formula (7) could offer improvements in other contexts as well.

Dear Reviewer DixF,

Thank you for your insightful and constructive feedback. As the discussion period is drawing to a close, we wish to make the most of this remaining time to engage in a fruitful dialogue regarding our paper. We hope you have had the opportunity to review our responses to your comments, where we endeavored to thoroughly address each of your concerns.

Should you require any further information or clarifications, please do not hesitate to let us know. We are eager to provide any additional details that might assist in your evaluation.

Thanks again! Authors of Paper 5974

Thank you for your detailed review and constructive feedback on our manuscript. We value your comments and would like to address weaknesses you've identified.

1. Assumptions and Theoretical Foundations: We acknowledge your concerns about the assumptions (A3-A4). However, we would like to offer some clarifications that might shed light on our approach:
   • Assumption 2: The “ball” is a typo, we will change it to “set” in our revised manuscript.
   • Assumption 3: We would like to clarify our differentiability assumption by using a rigorous definition of "differentiable almost everywhere." This means that, apart from a negligible set with zero measure, the loss function associated with candidate architectures maintains differentiability. The entire theoretical framework would still hold. In fact, the assumption is commonly implicitly assumed in the field of modern deep learning, as without it, the gradient of loss function might not exist and the foundation of gradient descent-based optimization methods would be undermined.
   • Assumption 4: the Hessian matrix being positive-definitive locally in a compact set $\mathbb{B}$ (a small region near a local minimum) only implies the objective function is locally convex (instead of global convexity). This assumption is justified by the recent theoretical works that have proven “the loss will escape the saddle points and reside near a certain local minimum”; see the discussion in the first paragraph of Section 3.
2. Title and Information Theory Application: We appreciate your critique regarding the title's reference to information theory. The development of SiGeo was based on a significant amount of knowledge and existing work from Information theory in statistics. For example, the use of Fisher information matrix, the loss landscape, and the Fisher-Rao norm.
3. Theoretical Necessity and Proxy Design: Thank you for your thought-provoking feedback regarding the necessity of the theorem in our proxy design.
   • Indeed, the development of a new proxy might not necessarily require a theoretical framework. However, we are of the firm belief that having such a framework greatly helps both researchers and practitioners in comprehending the scope and limits of the method's applicability. This understanding is crucial for effectively applying the proxy in various contexts and for driving further innovations in the field. We have observed that the current STOA zero-shot proxies predominately focus on convolutional neural networks (such as ZiCo [1] and ZenNAS [2]) and current theoretical frameworks often lack the generality needed to effectively encompass diverse model architectures, such as Transformers. Our approach aims to bridge this gap, offering a more flexible theoretical framework that can adapt to a broader range of architectures such as RecSys domain.
   • The theoretical framework has been instrumental in guiding our search for a new proxy. Initially, our project nearly discarded the Fisher-Rao norm, as it seemed to offer no substantial improvement over ZiCo. However, further theoretical exploration suggested that the Fisher-Rao norm could be effective, provided the weight is close to the local minimum of the loss function. It motivates us to reassess the Fisher-Rao norm, particularly in the context of pre-warming the network. Indeed, without these theoretical insights, the potential of the Fisher-Rao norm might have been overlooked.

We are committed to addressing these concerns in our revised manuscript and hope that our efforts will bring the paper closer to meeting the acceptance criteria. Thank you again for your thorough review and valuable insights.

References

1. Li, Guihong, et al. "ZiCo: Zero-shot NAS via Inverse Coefficient of Variation on Gradients." ICLR (2023).
2. Lin, Ming, et al. "Zen-nas: A zero-shot nas for high-performance image recognition." Proceedings of the IEEE/CVF International Conference on Computer Vision. 2021.

Thanks for the responses which resolve my concerns to some extent, while I am still concerned for the assumptions and theorems.

At first, if the authors assume local convexity, it typically requires training sufficiently many epochs rather than holding in the initial stage or warm-up for a short period of time. Meanwhile, the paper is written to discuss loss function landscape, which is a concept describing the overall loss function, but the local convexity actually concentrates on a small region.

Secondly, the theorems proposed in the paper are not new for me. If this is a theoretical optimization paper, theorem 1 & 2 actually serve as lemmas, but not main contributing theorems. The underlying story presented in the paper need improvements.

Due to the above, I decide to keep my rating though I appreciate the authors' throughout responses.

1. Theoretical Background and Novelty: We acknowledge your concerns about the theoretical aspects of our paper. We clarify our theoretical contribution:

   • Our primary theoretical contribution is on expressing minimal achievable training loss/expected training loss in terms of gradient variance, Fisher-Rao norm, and gradient mean. It provides a foundation for our proxy and offers a justification for the necessity of network warm-up.
   • Our theoretical results stand out in their flexibility compared to state-of-the-art (SOTA) methods. For example, the theory of ZiCo is applicable under strong assumptions of linear models or MLPs with ReLu activation functions while ZenNAS is tailored to convolutional neural networks. In contrast, our framework requires only local convexity and differentiability almost everywhere (a.e), significantly broadening its scope.
   • We revised the manuscript to condense the theoretical background and focus more on the novel aspects of our work, specifically the new experiment of the Fisher-Rao norm and training loss.

2. Improvement upon ZiCo Metric: Regarding the marginal improvements compared to ZiCo, we appreciate your observation. We aim to clarify that SiGeo is not merely a combination of these elements but an innovative integration that leverages each component to address specific challenges in NAS. In specific,

   • We clarify that the contribution of this work is not a new zero-shot proxy. Instead, we focus on showing the significance of the sub-one-shot and warm-up procedures, along with SiGeo's capacity to leverage information acquired as the candidate network improves with training.
   • We clarify that the objective of our zero-shot NAS benchmark experiments was not necessarily to demonstrate superior performance to the zero-shot approaches. Rather, our aim was to validate its "backward" comparability to the zero-shot setting.
   • We further included additional experiments; see the comment "New Experiments". To summarize, our experiments have shown an enhancement in the performance of the Fisher-Rao norm and training loss as the warm-up level increases.
   • Our key results in Table 1 and Figure 3 demonstrate that SiGeo with a 1% warm-up of supernet can achieve significantly better performance than ZiCo and comparable performance to one-shot NAS methods but with a significant reduction in computational costs.
   • We also direct the reviewer to General Clarification of Contribution.

3. Evaluation on NAS-Bench-Suite-Zero: Your suggestion to evaluate our ZC proxy on NAS-Bench-Suite-Zero is well-taken. In fact, we indeed used NAS-Bench-Suite-Zero in our current benchmark (ref. Section 4.3.1).

4. Code Availability: We apologize for the absence of the code. We have attached the code as supplementary material alongside the revised manuscript.

Regarding your specific questions:

• Generalization and Convergence Theory in NAS: Our approach builds on the premise that inherited weights can provide good initial points for subnets (near some local minimum). If the inherited weight is within a locally convex region around a local minimum, then Theorem 1 and 2 can be used to derive a proxy to evaluate a candidate architecture.
  • Theorem 1 provides an upper bound for the optimality gap, and indicates that a candidate architecture with a smaller gradient variance tends to have a smaller optimality gap.
  • Theorem 2 provides a lower bound for minimal achievable training loss and indicates that the minimal achievable training loss of candidate arch could be low when the expected absolute sample gradients and the FR norm are high, or the current training loss is low.
  • Section 3.4 provides an informal analysis to clarify how the sample gradient variance is connected with the trace of Hessian and thus can serve as an indicator of a generalization error.
• Standard Deviation in Experiments: Thank you for your feedback, which we value greatly. In our In the revised manuscript, we will try to incorporate the standard deviation as much as possible. However, we must also consider the significant resource demands of these experiments and the current practice. For instance, although the search is reasonably fast, validating all top-15 candidate architectures in one ResSys experiment alone requires approximately five days per A100 GPU (we have 30 experiments in total), illustrating the extensive nature of these tasks. Given these constraints and common practice, we may need to defer some of these extensive experiments to future work.

We hope that these revisions and clarifications will adequately address your concerns and enhance the overall contribution of our work. Thank you!

Dear Reviewer wPAs,

Thank you for your insightful and constructive feedback. As the discussion period is drawing to a close, we wish to make the most of this remaining time to engage in a fruitful dialogue regarding our paper. We hope you have had the opportunity to review our responses to your comments, where we endeavored to thoroughly address each of your concerns.

Should you require any further information or clarifications, please do not hesitate to let us know. We are eager to provide any additional details that might assist in your evaluation.

Thanks again! Authors of Paper 5974

Thank you for your insightful review and constructive comments on our manuscript. We appreciate your recognition of the clear research motivation and the practical application of our method in recommender systems. In response to your concerns, we would like to address the points you raised:

1. Innovation and Relation to Prenas: We understand your concern regarding the perceived lack of significant innovation compared to Prenas. In our revised manuscript, we will emphasize the distinct aspects of our approach.
   • Compared to PreNAS: Although both methods consider combining weight-sharing NSA with zero-shot proxies. SiGeo is essentially different from PreNAS. (1) SiGeo performs the weight-sharing one-shot training to warm up the supernet first and then applies a proxy to search. In contrast, PreNAS reduces the sample space by a zero-cost selector and then performs weight-sharing one-shot training on the preferred architectures. (2) SiGeo is developed based on the idea that the warm-up of the supernet will initialize all subnets simultaneously while PreNas is developed based on the idea of using a proxy to select preferred subnets to alleviate update conflicts.
2. Improvement upon ZiCo Metric: We acknowledge your feedback regarding the incremental improvement over the ZiCo metric. While our primary contributions focus on the sub-one-shot approach, the SiGeo proxy, and novel experiments on RecSys models/benchmark, we recognize the importance of your concerns.
   • It is crucial to clarify that the contribution of this work is not a new zero-shot proxy. Instead, we focus on showing the significance of the sub-one-shot and warm-up procedures, along with SiGeo's capacity to leverage information acquired as the candidate network improves with training.
   • We clarify that the objective of our zero-shot NAS benchmark experiments was not necessarily to demonstrate superior performance to the state-of-the-art (SOTA) zero-shot approaches. Rather, our aim was to validate its "backward" comparability to the zero-shot setting.
   • To better demonstrate the contribution of this work, we included additional experiments; see the comment above "New Experiments". It provides a more comprehensive comparison of our method against ZiCo under sub-one-shot setting in various NAS benchmarks.
   • Our key results are presented in Table 1 and Figure 3. It demonstrates that SiGeo with a 1% warm-up of supernet can achieve comparable performance to one-shot NAS methods but with a significant reduction in computational costs. In addition, SiGeo shows significant performance improvement over the SOTA zero-shot proxy ZiCo with a negligible increase in computational time.
3. Comparison with Prenas: We acknowledge and appreciate the suggestion to include a comparative analysis with Prenas in our experimental evaluation. We understand the potential value this comparison could bring. However, due to the significant computational and implementation resources required, we are currently unable to incorporate this comparison into the present study. We are committed to conducting this comparison and plan to include it in our future work.

Dear Reviewer JuJh,

Thank you for your insightful and constructive feedback. As the discussion period is drawing to a close, we wish to make the most of this remaining time to engage in a fruitful dialogue regarding our paper. We hope you have had the opportunity to review our responses to your comments, where we endeavored to thoroughly address each of your concerns.

Should you require any further information or clarifications, please do not hesitate to let us know. We are eager to provide any additional details that might assist in your evaluation.

Thanks again! Authors of Paper 5974