Defying Multi-model Forgetting: Orthogonal Gradient Learning to One-shot Neural Architecture Search

Weakness1: Thanks for your comments! It is true that Fig.4 is unable to see the relationships between different architectures, and we refer to [1] and find a new visualization method to show the changes of the validation accuracy of architectures and the impact between different architectures. New Figures and related descriptions have been correspondingly updated in our paper.

[1] Shuaicheng Niu, Jiaxiang Wu, Yifan Zhang, Yong Guo, Peilin Zhao, Junzhou Huang, and Mingkui Tan. Disturbance-immune weight sharing for neural architecture search. Neural Networks, 144: 553–564, 2021.

Weakness2: Thanks for your insightful and constructive advice. We agree with your opinion. The use of traditional RandomNAS as the baseline in this study is to verify the effectiveness of OGL in solving the multi-model forgetting issue. However, we think OGL will get better results with PDARTS for the following reasons. 1. PDARTS is an improvement over DARTS, especially on the storage to train large models. PDARTS divides the search process into three stages, and increases the depth of the network while reducing the types of operations. Therefore, PDARTS has lower search costs and smaller model size than others; 2. OGL projects the direction of weight update in baselines on the orthogonal direction of the gradient space, which has been proved in Lemma 1 that the orthogonal direction of weight update shows slightly influence on the performance of the previously trained architectures. In other words, the multi-model forgetting issue is largely alleviated.

Based on the reasons above. We believe that applying OGL to PDARTS (PDARTS-OGL) can get better results. We will consider PDARTS-OGL in our future work and apply OGL to more other excellent methods.

Dear Reviewer,

We would like to express our sincere gratitude for taking the time to review our paper and providing valuable feedback. We appreciate your expertise and insights, which are significant in enhancing the quality of our work.

We are eagerly awaiting your response to our rebuttal, as your comments and suggestions are crucial to the further development of our research. We understand that your time is precious, and we respect your commitment to this process.

In our rebuttal, we have thoroughly addressed the issues raised and provided comprehensive discussions and revisions. If there is any additional information you require or further clarification needed, please do not hesitate to reach out to us. We are more than willing to explain in any way possible.

Once again, we appreciate your dedication and effort in reviewing our paper. Your prompt attention to our rebuttal would be highly appreciated, as it greatly contributes to the timely progress of our research.

Thank you for your consideration, and we look forward to receiving your valuable feedback.

Sincerely,

The authors of Submission6907

Weakness1: Many thanks for your comments! OGL is involved in a hyperparameter $d$ in $G_{dim}\in \mathbb{R}^{h \times d}$, which is the column dimension of the gradient space, i.e., the number of the gradient vectors. However, the parameter $d$ is self-adjusted with the optimization process. Specifically, it is known that a space can be spanned by the maximally linear independent set, and PCA used in this study is to find the independent set of the gradient space. Once the independent set is found, $d$ here is determined since it is set to the number of vectors in the maximally linear independent set. Accordingly, we did not perform the parameter analysis of the proposed method.

Weakness2: Many thanks for your valuable feedback on the assumptions made in the theoretical proofs.

In the proof of lemma 1, there is a remainder term (i.e.,$R_1(w)$) of Taylor expansion of the loss function, namely, the infinitesimal of the first order. In practice, we ignored this term for theoretical proof and drew a conclusion that the update of weights along the orthogonal direction of the gradient of this operation will slightly change the accurancy of the trained architecture. However, we must admit that ignoring $R_1(w)$ will impact the accuracy of the trained architecture to some extent, but the impact is tiny. Accordingly, we have emphasized the conclusion in the manuscript that the OGL guided training paradigm enables the training of the current architecture to largely eliminate the impact to the performance of all previously trained architectures.

Dear Reviewer,

We would like to express our sincere gratitude for taking the time to review our paper and providing valuable feedback. We appreciate your expertise and insights, which are significant in enhancing the quality of our work.

We are eagerly awaiting your response to our rebuttal, as your comments and suggestions are crucial to the further development of our research. We understand that your time is precious, and we respect your commitment to this process.

In our rebuttal, we have thoroughly addressed the issues raised and provided comprehensive discussions and revisions. If there is any additional information you require or further clarification needed, please do not hesitate to reach out to us. We are more than willing to explain in any way possible.

Once again, we appreciate your dedication and effort in reviewing our paper. Your prompt attention to our rebuttal would be highly appreciated, as it greatly contributes to the timely progress of our research.

Thank you for your consideration, and we look forward to receiving your valuable feedback.

Sincerely,

The authors of Submission6907

Weakness3: Yes. We totally agree with your opinion and thanks for your comments. Theoretically, our method is more competitive by using a larger search space than a smaller one. Specifically, more candidate architectures will be sampled from a larger search space to train the supernet to get high performance, leading to more coupling candidate architectures. Therefore, the multi-model forgetting issue is more likely to occur. Hence, our method is more competitive by alleviating the issue by using a larger search space than a smaller one.

Here, we in this study did not use a large search space and aim to get a fair comparison with the up-to-date methods in handling the multi-model forgetting issue, where most of them use small search space. However, we will experimentally investigate the performance of our method by using a larger search space to evaluate the comprehensive performance of our method.

Weakness4: Many thanks and the differences between OGL and baseline NAS are as follows:

The difference results from the multi-model forgetting issue in the baseline NAS. The key of the baseline NAS and other one-shot NAS methods is weight sharing, where the weights of all candidate architectures directly inherit from a supernet without training from scratch. However, it may introduce multi-model forgetting. During the training of a supernet, a number of architectures are sequentially sampled from the supernet and trained independently. Once the architectures have partially overlapped structures, the weights of these overlapped structures of the previously well-trained architecture will be overwritten by the weights of the newly sampled architectures. In this way, the performance of the previously well-trained architecture may be decreased. Therefore, we proposed a strategy called OGL to solve the multi-model forgetting exists in baseline NAS and other one-shot NAS methods.

The difference between OGL and baseline NAS is on the weight update. OGL firstly detects the structures of current architecture whether they are ever sampled or not. If not, then the weights of the architecture are updated with back-propagation algorithm (e.g., SGD) and a pre-constructed gradient space is updated by the gradient direction of the structure. If yes, then the weights of the overlapped structures of the current architecture are updated in the orthogonal direction to the gradient space of all previously trained architectures. Following the OGL guided training paradigm, the training of the current architecture will largely eliminate the influence to the performance of all previously trained architectures, which has been proved in Lemma 1. In other words, the multi-model forgetting issue is largely alleviated.

Weakness5: Many thanks for your insightful comments, and we will explore the generality of our method on other architecture search domains. It will be great interesting to extend OGL to other architecture search if the previously-trained and newly-sampled architectures have overlapped structures during the training.

Weakness1: Thanks for your constructive comments. We provide with the convergence analysis of the update of the weights as follows:

Theorem 1 : Given a $l$-smooth and convex loss function $L(w)$, $w^*$ and $w_0$ are the optimal and initial weights of $L(w)$, respectively. If we let the learning rate $\eta = 1/l$, then we have:

$$L(w_t) - L(w^*) \leq \frac{2l}{t} \left\lVert w_0 - w^* \right\rVert_F^2,$$

where $w_t$ is the weights of architecture after $t$-th training.

According to Theorem 1, the OGL has a convergence rate of $O(1/t)$. The main proof of Theorem 1 is as follows:

Proof. The update of the weights of architecture $w$ can be represented as follows:

$$q(w_t) = \arg\min_{w \in Q} (L(w_t) + \langle L^{'}(w_t), w - w_t \rangle + \frac{\beta}{2}\left\lVert w_t - w \right\rVert_F^2)$$ $$w_{t+1} = w_t - \eta\beta(w_t - q(w_t)),$$

where $\eta$ and $\beta$ are two hyperparameters.

Let $Q$ is a closed convex set, $w^+ \in Q$ and $\beta \geq l$. We denote $Q_w = q(w^+)$ and $g_Q = g_Q(w^+) = \beta(w^+ - q(w^+))$, then we have:

$$\langle L^{'}(w^+) - g_Q, w - Q_w \rangle = \langle L^{'}(w^+), w - Q_w \rangle - \langle g_Q, w - Q_w \rangle \geq 0.$$

And combined with the property of convex function, we have:

$$L(w) \geq L(Q_w) + \frac{1}{2\beta}\left\lVert g_Q \right\rVert_F^2 + \langle g_Q, w - w^+ \rangle.$$

Let $\beta = l$, $w = w^+ = w_t$, we have:

$$L(w_t) \geq L(w_{t+1}) + \frac{1}{2l}\left\lVert g_Q(w_t) \right\rVert_F^2,$$

where $g_Q(w_t) = \beta(w_t - q(w_t))$.

Let $\beta = l$, $w = w^*$, $w^+ = w_t$, we have:

$$L(w^*) \geq L(w^*) + \frac{1}{2l}\left\lVert g_Q(w_t) \right\rVert_F^2 - \langle g_Q(w_t), w^* - w^t \rangle.$$

We denote $r_t = \left\lVert w_t - w^* \right\rVert_F$ and $g_{Q,t} = g_Q(w_t)$, then if $\eta \leq \frac{1}{\beta}$ we have:

$$r_{t+1}^2 \leq r_t^2 + \eta (\eta - \frac{1}{\beta}) \left\lVert g_{Q,t} \right\rVert_F^2 \leq r_t^2 \leq \ldots \leq r_0^2.$$

We denote $\Delta_t = L(w_t) - L(w^*)$, and $\Delta_{t+1} \leq \Delta_t$, we have:

$$\frac{1}{\Delta_{t+1}} \geq \frac{1}{\Delta_{t}} + \frac{1}{2l} \frac{1}{r_0^2} \frac{\Delta_{t}}{\Delta_{t+1}} \geq \frac{1}{\Delta_t} + \frac{1}{2l} \frac{1}{r_0^2} \geq \ldots \geq \frac{1}{\Delta_0} + \frac{1}{2l} \frac{1}{r_0^2}.$$

Then we have:

$$\Delta_t = \frac{2l (L(w_0) - L(w^*)) \left\lVert w_0 - w^* \right\rVert_F^2}{2l \left\lVert w_0 - w^* \right\rVert_F^2 + t (L(w_0) - L(w^*))}.$$

Based on the property of $l$-smooth function, we have:

$$L(w_0) \leq L(w^*) + \langle L^{'}(w^*), w_0 - w^* \rangle + \frac{l}{2} \left\lVert w_0 - w^* \right\rVert_F^2.$$

Based on the inequation above, we have:

$$L(w_t) - L(w^*) \leq \frac{2l \left\lVert w_0 - w^* \right\rVert_F^2}{2l \frac{\left\lVert w_0 - w^* \right\rVert_F^2}{L(w_0) - L(w^*)} + t} \leq \frac{2l}{t} \left\lVert w_0 - w^* \right\rVert_F^2.$$

Thus the Theorem 1 is proven.

The details of the proof of Theorem 1 is provided in the section 1.2 of the Supplementary material.

Weakness2: Sorry for the unclear statement and we detailed the update of the gradient space as follows:

1. Initialization of the gradient spaces: We firstly design a gradient space $G$ for each operation to save the gradient vectors of corresponding operation, then initialize each gradient space as the identity matrix $I$ (i.e., $G = I$);
2. Training of architectures: During the process of supernet training, an architecture is sampled in each supernet training epoch, and then the weights of the architecture is updated through OGL;
3. Calculation of the gradient vectors: We calculate the gradient of the weights for each operation in the supernet after the update of the architecture, and then obtain the gradient vectors of each operation (i.e., $g_1, g_2, ..., g_n$ where $n$ is the number of gradient vectors);
4. Concatenation of gradient vectors: We concatenate the gradient vectors $g_1, g_2, ..., g_n$ to the gradient space $G$ (i.e., $G\leftarrow [G, g_1, g_2, ..., g_n]$);
5. Dimension reduction of gradient space through PCA: We extract a set of base vectors of each gradient space by PCA (i.e., $G\in \mathbb{R}^{h \times n} \rightarrow G_{dim}\in \mathbb{R}^{h \times d}$, where $h$ and $d$ are the dimension of the gradient space and the number of base vectors, respectively).

About the hyperparameters. OGL is involved in a hyperparameter $d$ in $G_{dim}\in \mathbb{R}^{h \times d}$, which is the column dimension of the gradient space, i.e., the number of the gradient vectors. However, the parameter $d$ is self-adjusted with the optimization process. Specifically, it is known that a space can be spanned by the maximally linear independent set, and PCA used in this study is to find the independent set of the gradient space. Once the independent set is found, $d$ here is determined since it is set to the number of vectors in the maximally linear independent set. Accordingly, we did not perform the parameter analysis of the proposed method.

Dear Reviewer,

We would like to express our sincere gratitude for taking the time to review our paper and providing valuable feedback. We appreciate your expertise and insights, which are significant in enhancing the quality of our work.

We are eagerly awaiting your response to our rebuttal, as your comments and suggestions are crucial to the further development of our research. We understand that your time is precious, and we respect your commitment to this process.

In our rebuttal, we have thoroughly addressed the issues raised and provided comprehensive discussions and revisions. If there is any additional information you require or further clarification needed, please do not hesitate to reach out to us. We are more than willing to explain in any way possible.

Once again, we appreciate your dedication and effort in reviewing our paper. Your prompt attention to our rebuttal would be highly appreciated, as it greatly contributes to the timely progress of our research.

Thank you for your consideration, and we look forward to receiving your valuable feedback.

Sincerely,

The authors of Submission6907