# NDARTS: A Differentiable Architecture Search Based on the Neumann Series
## 2 Methods
### DARTS Optimization Algorithm Based on Neumann Series Approximation (NDARTS)
#### 2.2.2 Proof  
We provide some necessary assumptions that are relatively easy to satisfy before proving the convergence of NDARTS:  
(1) The function \(\omega:\alpha\longrightarrow\omega(\alpha)\) is Lipschitz continuous and has a Lipschitz constant \(L_{\omega}>0\) and \(L_{\
abla_{a}\omega}>0\). (2) \(||\
abla_{\omega a}^{2}L_{1}||\) is bounded, that is, there exists \(C_{L_{1}^{\omega a}}>0\) that can make \(||\
abla_{\omega a}^{2}L_{1}||<C_{L_{1}^{\omega a}}\). (3) For any \(\omega\) and \(\alpha\), \(L_{2}(\omega,\cdot)\) and \(L_{2}(\cdot,\alpha)\) are bounded and Lipschitz continuous, and have Lipschitz constant \(L_{2}^{\omega}>0\), \(L_{2}^{\alpha}>0\). (4) For any \(\omega\) and \(\alpha\), \(\
abla_{\omega}L_{2}(\omega,\cdot)\) and \(\
abla_{a}L_{2}(\cdot,\alpha)\) are Lipschitz continuous and have Lipschitz constant \(L_{2}^{\
abla\omega}>0\), \(L_{2}^{\
abla\alpha}>0\) related to \(\omega\), \(\alpha\). **Theorem 1**. : _When \(\gamma_{a_{i}}\) satisfy \(\sum\limits_{i=1}^{\infty}\gamma_{a_{i}}=\infty\), \(\sum\limits_{i=1}^{\infty}\gamma_{a_{i}}^{2}<\infty\), the algorithm is converges on expectations:_  
\[\lim\limits_{m\rightarrow\infty}E\big{[}\
abla_{a}L_{2}^{\prime}(\omega( \alpha_{m}),\alpha_{m})\big{]}=0, \tag{9}\]  
_where \(\alpha_{m}\) and \(\gamma_{a_{m}}\) are the architecture parameters and the learning rate of architecture parameters founded during the m-th iteration, respectively._  
We first prove two lemmas:  
**Lemma 1**. : _Assuming \(L_{1}\) is quadratic differentiable and \(\mu\)-strongly convex for parameter \(\omega\), that the difference of the approximate value \(\
abla_{a}L_{2}^{\prime}\) and \(\
abla_{a}L_{2}\) in DARTS is satisfy:_  
\[||\
abla_{a}L_{2}-\
abla_{a}L_{2}^{\prime}||\leqslant C_{L_{1}^{\omega a}}C_ {L_{2}^{\omega}}\frac{1}{\mu}(1-\gamma\mu)^{K+1}. \tag{10}\]  
**Lemma 2**. : _Assuming assumptions (1)-(4) are satisfied, the function \(L_{2}:\alpha\longrightarrow L_{2}(\omega(\alpha),\alpha)\) is differentiable and has a Lipschitz constant \(L_{\
abla_{a}L_{2}}=L_{2}^{\
abla_{a}}+L_{2}^{\
abla_{\omega}}L_{\omega}^{2} +L_{2}^{\omega}L_{\
abla_{a}\omega}\)._  
Proof of Lemma 1.: Since  
\[\
abla_{a}L_{2}=\frac{\partial L_{2}}{\partial\alpha}-\gamma\frac{\partial L_{2 }}{\partial\omega}\sum\limits_{j=0}^{\infty}(I-\gamma\frac{\partial^{2}L_{1}}{ \partial\omega\partial\omega})^{j}\frac{\partial^{2}L_{1}}{\partial\alpha \partial\omega}, \tag{11}\]\[\
abla_{a}L_{2}^{\prime}=\frac{\partial L_{2}}{\partial\alpha}-\gamma\frac{ \partial L_{2}}{\partial\omega}\sum_{j=0}^{K}(I-\gamma\frac{\partial^{2}L_{1}} {\partial\omega\partial\omega})^{j}\frac{\partial^{2}L_{1}}{\partial\alpha \partial\omega}, \tag{12}\]  
thus,  
\[\
abla_{a}L_{2}-\
abla_{a}L_{2}^{\prime}=\gamma\frac{\partial L_{2}}{\partial \omega}\sum_{j=K+1}^{\infty}(I-\gamma\frac{\partial^{2}L_{1}}{\partial\omega \partial\omega})^{j}\frac{\partial^{2}L_{1}}{\partial\omega\partial\omega}. \tag{13}\]  
Since \(L_{1}\) is \(\mu\)-strongly convex and \(\gamma\mu I\leqslant\gamma\frac{\partial^{2}L_{1}}{\partial\omega\partial \omega}\leqslant I\), thus  
\[\sum_{j=K+1}^{\infty}(I-\gamma\frac{\partial^{2}L_{1}}{\partial\omega\partial \omega})^{j}\leqslant\sum_{j=K+1}^{\infty}(I-\gamma\mu I)^{j}, \tag{14}\]  
the sum of the right-hand series,  
\[\sum_{j=K+1}^{\infty}(I-\gamma\frac{\partial^{2}L_{1}}{\partial\omega\partial \omega})^{j}\leqslant\frac{1}{\gamma\mu}(I-\gamma\mu I)^{K}. \tag{15}\]  
And, as \(\frac{\partial L_{2}}{\partial\omega}\) and \(\frac{\partial^{2}L_{1}}{\partial\alpha\partial\omega}\) are bounded, so there exist a constant \(C_{L_{1}^{\omega\omega}}\) and \(C_{L_{2}^{\omega}}\), subject to  
\[||\
abla_{a}L_{2}-\
abla_{a}L_{2}^{\prime}||\leqslant C_{L_{1}^{\omega\omega }}C_{L_{2}^{\omega}}\frac{1}{\mu}(1-\gamma\mu)^{K}. \tag{16}\]  
\(\square\)  
**Proof of Lemma 2. **  
\[