Paper deep dive
LP-NAS: Linear Programming-based Neural Architecture Search
Abhishek Shukla, Ankur Sinha, Faiz Hamid
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Neural Architecture Search (NAS) aims to automate neural network architecture design, reducing reliance on human expertise. Among the various NAS methods, differentiable NAS has gained prominence due to its efficiency and accuracy compared to conventional NAS approaches. Since differentiable NAS relaxes the architecture search space into a continuous domain, it is possible to apply principles from continuous optimization to NAS. In this paper, we propose Linear Programming-based NAS (LP-NAS), a mathematical programming-based framework for differentiable NAS that is applicable to a wide range of continuous search spaces. LP-NAS formulates a linear program (LP) using the validation-loss gradient and the training-loss Hessian to compute an architecture update direction that improves generalization while preserving the optimality of the model parameters. By following this LP-derived descent direction, LP-NAS efficiently navigates the architecture search space, leading to faster and more effective architecture optimization. We introduce two computationally efficient variants of LP-NAS, namely S-LP-NAS and R-LP-NAS. Applying LP-NAS to the Differentiable Architecture Search (DARTS) search space results in two algorithmic variants, S-LP-DARTS and R-LP-DARTS. Both variants achieve faster convergence and significantly higher validation performance during the early search iterations than the standard DARTS algorithm. Extensive experiments on CIFAR-10 and CIFAR-100 show that LP-DARTS outperforms standard DARTS in both the architecture search and evaluation phases. Additionally, we compare our approach with several DARTS variants (P-DARTS, PC-DARTS, and STO-DARTS) on the CIFAR-10 dataset and demonstrate its effectiveness. Furthermore, we validate the transferability of the discovered architectures through experiments on the ImageNet dataset.
Tags
Links
- Source: https://arxiv.org/abs/2608.14472v1
- Canonical: https://arxiv.org/abs/2608.14472v1
Trouble viewing inline? Open PDF directly →
Full Text
73,990 characters extracted from source content.
Expand or collapse full text
LP-NAS: Linear Programming-based Neural Architecture Search Abhishek Shukla Ankur Sinha Faiz Hamid 1Department of Management Sciences, IIT Kanpur, India abhiskl@iitk.ac.in, fhamid@iitk.ac.in 2Krishnamurthy Tandon School of AI, IIM Ahmedabad, India asinha@iima.ac.in Abstract Neural Architecture Search (NAS) aims to automate neural network architecture design, reducing reliance on human expertise. Among the various NAS methods, differentiable NAS has gained prominence due to its efficiency and accuracy compared to conventional NAS approaches. Since differentiable NAS relaxes the architecture search space into a continuous domain, it is possible to apply principles from continuous optimization to NAS. In this paper, we propose Linear Programming-based NAS (LP-NAS), a mathematical programming-based framework for differentiable NAS that is applicable to a wide range of continuous search spaces. LP-NAS formulates a linear program (LP) using the validation-loss gradient and the training-loss Hessian to compute an architecture update direction that improves generalization while preserving the optimality of the model parameters. By following this LP-derived descent direction, LP-NAS efficiently navigates the architecture search space, leading to faster and more effective architecture optimization. We introduce two computationally efficient variants of LP-NAS, namely S-LP-NAS and R-LP-NAS. Applying LP-NAS to the Differentiable Architecture Search (DARTS) search space results in two algorithmic variants, S-LP-DARTS and R-LP-DARTS. Both variants achieve faster convergence and significantly higher validation performance during the early search iterations than the standard DARTS algorithm. Extensive experiments on CIFAR-10 and CIFAR-100 show that LP-DARTS outperforms standard DARTS in both the architecture search and evaluation phases. Additionally, we compare our approach with several DARTS variants (P-DARTS, PC-DARTS, and STO-DARTS) on the CIFAR-10 dataset and demonstrate its effectiveness. Furthermore, we validate the transferability of the discovered architectures through experiments on the ImageNet dataset. Keywords: Deep learning, Neural architecture search, Bilevel optimization, Linear programming. 1 Introduction Artificial Neural Networks (ANNs) are machine learning models designed to process data in a manner inspired by the human brain. ANNs are characterized by architecture parameters (hyperparameters) which are not learned from the training data but are instead set prior to training. Hyperparameter Optimization (HPO) is a technique aimed at determining the optimal values of the hyperparameters for machine learning models. Traditionally, expert knowledge was essential in designing neural network architectures. However, with advances in artificial intelligence, engineers and scientists are increasingly focused on automating the neural network design process. This emerging area of research, referred to as Neural Architecture Search (NAS), a sub-field of HPO and Automated Machine Learning (AutoML), aims to facilitate the automated development of neural network architectures for specific requirements. Mathematically, NAS and other HPO problems, as formalized in [9, 29], are bilevel optimization problems [35, 27], in which an outer (leader) problem selects the architecture and an inner (follower) problem trains the corresponding weights, as shown in Formulation (1). These problems are typically solved under the optimistic bilevel assumption. In this formulation, ℒvL_v and ℒtL_t represent the validation loss and the training loss functions. The lower-level variable (W) corresponds to the neural network’s weights and biases, while the upper-level variable (A) denotes the architecture parameters. When considering NAS as a bilevel optimization problem, it is noteworthy that the dimensionality of W significantly exceeds that of A. minA _A ℒv(A,W^) _v(A, W) (1) st. . W^∈argminW∈ℒt(A,W) W∈ _W∈ WL_t(A,W) A∈ A∈ A NAS gained significant attention following the publication of the research paper [49]. Since then, this domain has experienced substantial growth, evidenced by the proliferation of related publications in recent years [41]. Architectures designed through NAS have demonstrated exceptional performance across diverse application areas, such as medical imaging [43, 40, 39], language modeling [30], translation [7], smart city applications [16], image classification and object detection [51], and semantic segmentation [19]. In many instances, NAS-designed architectures have outperformed those crafted by human experts. Advancements in automated neural network design have democratized the architecture design process, reducing the need for specialized knowledge. Current progress in NAS demonstrates its potential to revolutionize various application domains and research fields [22]. Due to the combinatorial nature and NP-hard complexity of NAS, solving this problem is computationally challenging and time-intensive. Specifically, Reinforcement Learning (RL) [49] and Evolutionary Computation (EC) [21]-based algorithms require approximately three orders of magnitude more GPU days than gradient-based methods [20] due to the exploration of discrete architectural spaces and treating the objective function as a black box rather than a functional form. In contrast, gradient-based NAS approaches lack such intricacies. Since NAS emerged, various benchmarks have been developed to assess and compare new NAS methods. Differentiable Architecture Search (DARTS) has emerged as one of the most widely adopted benchmarks in the NAS field. The DARTS algorithm pioneered the use of gradient-based optimization techniques within NAS. Following its introduction, several variants of DARTS have been developed to improve particular aspects of the original method. Some of them are given in Appendix A. The continuous advancements and broad usage of DARTS highlight its importance and substantial influence within the NAS field. Although these methods have significantly improved DARTS in terms of search efficiency, robustness, and optimization stability, they primarily focus on modifying the search strategy, search space, or regularization techniques. Comparatively less attention has been devoted to exploiting the mathematical structure of the underlying bilevel optimization problem, despite DARTS being naturally formulated as one. One of the early works to model HPO as a bilevel optimization problem is [1], which has inspired various studies [32, 34, 33, 25, 10]. Beyond NAS, more recently, the mathematical structure of bilevel optimization-based regularization problems has also been exploited for overfitting control in large language models, including transformer architectures, as demonstrated in [31]. The current work builds on this line of research by exploiting the mathematical properties of continuous hyperparameter optimization through its bilevel formulation. Figure 1: Optimization paths of a first-order method and our proposed approach. We propose a novel NAS approach based on linear programming within the differentiable framework. Our method leverages the Hessian information from the lower-level optimization, together with the validation gradient from the upper-level, to formulate a Linear Program (LP) that computes a descent direction for the upper-level while ensuring that the architecture search is performed within the optimal valley of the lower-level problem. This approach, referred to as LP-NAS (an amalgamation of the LP-based bilevel descent method and differentiable NAS), distinguishes itself by maintaining model optimality throughout the architecture update process, unlike many existing NAS and HPO algorithms, which assume model optimality solely from the condition that the gradient of the training loss with respect to the model parameters is zero. While a zero gradient is a necessary condition, they are not sufficient for optimality. In contrast, our method ensures lower-level optimality while updating the architecture parameters and model parameters along the descent direction, providing a robust approach to optimization and effectively minimizing validation loss. Figure 1 illustrates the issue of relying on the first-order lower-level optimality conditions alone and then optimizing the architecture parameters. To begin with, let the optimal model parameters corresponding to the initial architecture A1A^1 be known. Changing the architecture parameters (e.g., from A2A^2 to A3A^3) across iterations, while ensuring first-order optimality at the lower-level, may result in updated weights corresponding to A3A^3 that do not sufficiently satisfy the lower-level minimization condition. Consequently, although the upper-level objective (validation loss) may improve, the minimization of the lower-level training loss is not guaranteed. This imbalance can lead to overfitting on the validation loss while disregarding the sufficient minimization conditions for the training loss. A common approach to mitigate this issue is to re-solve the lower-level problem with a fixed A3A^3, as done by many optimization methods. However, this approach can still pose challenges because the optimization begins from a state where the gradient is nearly zero. In such scenarios, the solution may be at a saddle point or even a local maximum of the lower-level problem while still achieving a relatively low validation loss. The final architecture (say A4A^4) may also not be optimal for the bilevel program. In contrast, the proposed method ensures that lower-level optimality is maintained while updating both architecture and model parameters along the descent direction, as illustrated in Figure 1. This allows for efficient convergence to model and architecture parameters that yield superior performance on validation/test datasets. In a nutshell, the key contributions of our work are: 1. Linear pogramming-based hyperlocal search: This approach leverages second-order information to compute architecture updates that improve validation performance while preserving model optimality. 2. Efficient variants for faster convergence: We propose two computationally efficient variants of LP-NAS, namely S-LP-NAS and R-LP-NAS, which differ in their model parameter selection strategies. Both variants accelerate convergence and improve validation performance during the early stages of the architecture search process. 3. Superior performance on benchmark datasets: Extensive experiments on the CIFAR-10 and CIFAR-100 datasets demonstrate that LP-DARTS, an instance of LP-NAS for the DARTS search space (DSS), consistently outperforms standard DARTS during both the architecture search and evaluation phases, resulting in superior architectures. 4. Comparison with DARTS variants and transferability: We perform a comprehensive comparison with several DARTS variants (P-DARTS, PC-DARTS, and STO-DARTS) on the CIFAR-10 dataset, demonstrating the effectiveness of LP-DARTS, and validate the transferability of the discovered architectures through experiments on the ImageNet dataset. The paper is organized as follows. Section 2 covers the foundational concepts and background necessary for the development of the LP-NAS algorithm. Section 3 introduces the proposed LP-NAS approach in detail. In Section 4, we present the experimental results for architecture optimization on the CIFAR-10 and CIFAR-100 datasets and compare the performance of LP-DARTS with that of the original DARTS algorithm. We also compare the architectures obtained in this work with those reported in the literature on the CIFAR-10 dataset. Furthermore, we evaluate the transferability of the architectures obtained on CIFAR-10 to the ImageNet dataset and discuss the insights gained from the experimental results. Finally, Section 5 offers concluding remarks, outlines the challenges and limitations encountered during the architecture search process, and suggests potential directions for future research. 2 Preliminaries In this section, we discuss the hypergradient-based approach for bilevel optimization and lay the foundation for developing the LP-NAS algorithm. 2.1 Hypergradient The gradient of the upper-level objective (validation loss) with respect to the upper-level decision variable A is called the hypergradient. One of the most well-known optimization methods for NAS is based on an approximate hypergradient [12]. This hypergradient is used to update the architecture parameters to improve validation performance while accounting for the model weights obtained after one step of gradient descent on the training loss. The hypergradient is approximated as: ∇Aℒv(A,W^)≈∇Aℒv(A,W−ξ∇Wℒt(A,W)), _AL_v(A, W)≈ _AL_v (A,W-ξ _WL_t(A,W) ), where ξ is a small learning rate used for one-step unrolled optimization of the model training problem. Setting ξ=0ξ=0 yields a first-order approximation, while ξ≠0ξ≠ 0 introduces a second-order correction: ∇Aℒv(A,W^)≈∇Aℒv(A,W′)−ξ∇A,W2ℒt(A,W)∇W′ℒv(A,W′), _AL_v(A, W)≈ _AL_v(A,W )-ξ∇^2_A,WL_t(A,W) _W L_v(A,W ), (2) with W′=W−ξ∇Wℒt(A,W)W =W-ξ _WL_t(A,W). The second term captures the interaction between the architecture parameters and the network weights through the mixed Hessian of the training loss, thereby accounting for their influence on the approximate hypergradient. This term can be efficiently approximated using finite-difference schemes. For further details on DARTS, see [20]. 2.2 Hyperlocal Search using LP To address the bilevel optimization problem described in Formulation (1), it is required to compute the descent direction/gradient of the upper-level objective. This is achieved by formulating and solving an LP, giving a descent direction for the upper-level objective that ensures the maintenance of lower-level optimality conditions when upper-level and lower-level variables are updated along this direction (Proposition 2.1). This descent direction facilitates efficient exploration of the continuous hyperparameters and simultaneously updates model parameters. We refer to this search using LP as Hyperlocal Search (HLS). The LP for HLS is given as follows, which is a relaxed formulation of the original Second-Order Cone Program (SOCP) (see Appendix B for the derivation), whose optimal solution gives the steepest descent direction. mindA,dW _d_A,d_W ⟨[∇Aℒv(A0,W0)∇Wℒv(A0,W0)],[dAdW]⟩ bmatrix _AL_v(A^0,W^0)\\ _WL_v(A^0,W^0) bmatrix, bmatrixd_A\\ d_W bmatrix (3) subject to: to: [H21H22][dAdW]=0 bmatrixH_21&H_22 bmatrix bmatrixd_A\\ d_W bmatrix=0 −1≤dA≤1 -1≤ d_A≤ 1 It is noteworthy that the set of linear constraints in the LP ensures that [dA,dW]T[d_A,d_W]^T is orthogonal to [Hij]i=p+1,j=1i=p+q,j=p+q[H_ij]_i=p+1,j=1^i=p+q,j=p+q.11 1 With some abuse of terminology, we refer to the rectangular matrix, [Hij]i=p+1,j=1i=p+q,j=p+q[H_ij]_i=p+1,j=1^i=p+q,j=p+q, as the Hessian matrix. ∇(A,W)2ℒt(A0,W0)=[Hij]i=1,j=1i=p+q,j=p+q=[[Hij]i=1,j=1i=p,j=p[Hij]i=1,j=p+1i=p,j=p+q[Hij]i=p+1,j=1i=p+q,j=p[Hij]i=p+1,j=p+1i=p+q,j=p+q]=[H11H12H21H22] _(A,W)^2L_t(A^0,W^0)= bmatrixH_ij bmatrix_i=1,j=1^i=p+q,j=p+q= bmatrix[H_ij]_i=1,j=1^i=p,j=p&[H_ij]_i=1,j=p+1^i=p,j=p+q\\ [H_ij]_i=p+1,j=1^i=p+q,j=p&[H_ij]_i=p+1,j=p+1^i=p+q,j=p+q bmatrix= bmatrixH_11&H_12\\ H_21&H_22 bmatrix This means that any infinitesimal change in (A0,W0)(A^0,W^0) along this direction will continue to guarantee lower-level optimality. Solving the LP (3) we obtain a descent direction (dA∗,dW∗d_A^*,d_W^*), which provides models with different architectures, ℳ(A0+tdA∗,W0+tdW∗)M(A^0+td_A^*,W^0+td_W^*), when t is varied. With t>0t>0, one moves along the direction that improves validation loss (optimal objective value for the linear programming problem is always ≤0≤ 0 as proved in the Proposition 2.2). Proposition 2.1. (Preservation of Lower-Level Optimality after the HLS update). Let the model parameters (W0)(W^0) be initially optimal at the lower-level for given architecture parameters (A0)(A^0). If the HLS is performed using the proposed linear program, the model parameters continue to remain optimal after the HLS update. (proof in Appendix C.) Proposition 2.2. (Validation Performance Improvement via HLS). The HLS results to an improvement in validation performance in most cases, and in the worst case, leaves it unchanged. (proof in Appendix D.) 3 Methodology To utilize the LP devised in (3), the hyperparameters considered must be continuous. As previously explained, differentiable search spaces, such as that of DARTS, employ a continuous relaxation of the categorical operation choices on each edge by applying the SoftMax function over all candidate operations, thereby transforming the discrete search space into a continuous one. Therefore, the devised LP can be employed to conduct HLS, enabling efficient exploration of the architecture and model parameters. Once the descent direction (dA∗,dW∗d_A^*,d_W^*) is obtained by solving the LP, we simultaneously update the hyperparameters and model parameters by a step size (t)(t) in the descent direction. We provide the details of a basic version of the proposed method, LP-NAS, in Algorithm 1. Algorithm 1 LP-NAS 1: Set iteration count k=0k=0, initialize architecture parameters A0A^0 randomly and create the neural network using this architecture. 2: Lower-level optimization: Solve for W0W^0 for the given A0A^0, i.e. W0=argminW∈ℒt(A0,W)W^0= argmin _W∈ WL_t(A^0,W) 3: while k<kmaxk<k^max do 4: Hessian approximation: Use an efficient approximation approach to get the approximation of the Hessian matrix [Hijk]i=p+1,j=1i=p+q,j=p+q[H_ij^k]_i=p+1,j=1^i=p+q,j=p+q at (Ak,Wk)(A^k,W^k). 5: Validation gradient: Calculate the validation gradient: [∇Aℒv(Ak,Wk),∇Wℒv(Ak,Wk)]T[ _AL_v(A^k,W^k), _WL_v(A^k,W^k)]^T. 6: LP formulation and solution: Formulate and solve the LP to get the descent direction (dAk∗,dWk∗d_A^k^*,d_W^k^*). 7: Hyperlocal search: Update the architecture and the model parameters along the descent direction, (Ak+1,Vk+1) (A^k+1,V^k+1) ←(Ak,Wk)+t(dAk∗,dWk∗) ←(A^k,W^k)+t(d_A^k^*,d_W^k^*) 8: Lower-level optimization: Solve for Wk+1W^k+1 for the given Ak+1A^k+1 with a warm start from Vk+1V^k+1. Wk+1=argminW∈ℒt(Ak+1,W) W^k+1= argmin _W∈ WL_t(A^k+1,W) 9: Increment iteration count: k←k+1k← k+1 10: end while 11: Get the final architecture from the learned architecture parameters. 3.1 Improving Memory and Computational Efficiency A direct implementation of the proposed LP formulation is computationally impractical for modern deep neural networks because the number of model parameters is typically several orders of magnitude larger than the number of architecture parameters, i.e., p≪qp q. Consequently, computing and storing the Hessian with respect to all model parameters incurs prohibitive memory and computational costs. To address this challenge, LP-NAS computes a reduced Hessian by retaining all architecture parameters while considering only a small subset of the model parameters. Specifically, all p architecture parameters and only κqκ q selected model parameters (κ≪1κ 1) are used to construct the LP. Accordingly, the validation gradient is also computed only for these selected parameters, resulting in a reduced LP that is significantly more memory- and compute-efficient while preserving the essential second-order information required for optimization. The detailed formulation, computational complexity, and memory analysis of the reduced Hessian are provided in Appendix E. The following section describes the strategies used to select the subset of model parameters employed in the reduced Hessian computation. 3.2 Model Parameter Selection for Reduced Hessian Computation To compute the reduced Hessian matrix efficiently, LP-NAS computes the Hessian with respect to only a subset of the model parameters. We propose two parameter-selection strategies for selecting κqκ q parameters from the total of q model parameters. Specific parameter selection (S-LP-NAS). This strategy selects the model parameter tensor that is expected to have the greatest influence on the optimization process. The selection is based on the normalized magnitude of the training-loss gradient, referred to as the Gradient Norm Per Parameter (GNPP). The tensor with the largest GNPP value is selected, and all parameters within that tensor are used for reduced Hessian computation. Since this strategy deterministically selects a specific tensor, the resulting algorithm is referred to as S-LP-NAS, where S denotes specific. Random parameter selection (R-LP-NAS). As an alternative, we randomly select one or more model parameter tensors whose sizes satisfy a predefined upper bound on the reduced Hessian size. The reduced Hessian is then computed using all parameters belonging to the selected tensors. By varying the selected tensors across iterations, this strategy provides diverse update opportunities for different parts of the network. The corresponding algorithm is referred to as R-LP-NAS, where R denotes random. The mathematical formulation of both parameter-selection strategies is provided in Appendix F. 3.3 Time Complexity In Algorithm 1, let kmaxk^max denote the number of outer iterations in the bilevel optimization framework. Each outer iteration consists of three main components: (i) an L-BFGS-based Hessian approximation with memory size m, (i) an LP-based architecture update, and (i) lower-level model optimization. Let p denote the number of architecture parameters and κqκ q the number of selected model parameters. Define the total number of optimization variables as n=p+κqn=p+κ q. Further, let EDE_D denote the number of training samples processed per outer iteration with batch size B, and let CPC_P represent the cost of a single forward–backward pass. The overall simplified complexity can be given as follows (see Appendix G for details). O(kmax[n2+EDBCP]).O\! (k^max [n^2+ E_DBC_P ] ). (4) This shows that the algorithm scales quadratically with the number of optimization variables and linearly with the effective data processed per iteration. All components are polynomial in problem size, and no exponential or combinatorial operations are involved, making the method computationally tractable for practical NAS settings. In practice, the dominant costs arise from the LP solve and the lower-level training. 4 Experimental Results In this section, we perform architecture searches using the two LP-DARTS approaches and compare their performance with DARTS. The loss and accuracy during the bilevel search are recorded for comparison purposes. The experiments utilized Convolutional Neural Network (CNN) for multi-class classification on the CIFAR-10 and CIFAR-100 datasets. Each dataset consists of 50,000 training and 10,000 test images, all in RGB format at 32×3232× 32 pixels. CIFAR-10 contains 10 classes, while CIFAR-100 has 100 classes. All experiments were conducted on a high-memory HPC node featuring Intel Xeon Platinum 8268 processor (2.9 GHz, 48 cores) with 768 GB DDR4 RAM, and a 480 GB SSD. Despite the processor’s multi-core capability, we restricted all executions to a single core for a fair comparison. After conducting the architecture search experiments, we evaluated the resulting architectures on their respective datasets. To evaluate the transferability and generalization capability of the searched architectures, architectures obtained from architecture search on CIFAR-10 were also evaluated on the ImageNet32 dataset. The ImageNet32 dataset used here is a downsampled version of the ILSVRC 2012 ImageNet classification dataset, comprising 1,281,167 training images and 50,000 validation images, uniformly resized to 32×3232× 32 pixels in RGB format. It includes 1,000 object classes, preserving the fine-grained classification challenge of the original ImageNet while maintaining computational tractability. The architecture search and evaluation results are detailed as follows. 4.1 Architecture Search The experimental configuration followed the guidelines from the original DARTS study [20]. For all algorithms (DARTS, S-LP-DARTS and R-LP-DARTS), the search for optimal cells was conducted with a batch size of 96, splitting the dataset into equal-sized training and validation sets. The architecture consisted of 8 cells: 6 normal cells and 2 reduction cells. The two reduction cells were positioned at 1/3 and 2/3 distances deep in the network. All operations in the normal cells were performed with stride 1, while stride 2 was used in the reduction cells to downsample the feature maps by half. The operation set O considered in this work is the same as that used in DARTS article [20]. We employed stochastic gradient descent (SGD) with momentum to optimize the model parameters. The initial learning rate was set to 2.5×10−22.5× 10^-2, momentum to 0.9, and weight decay to 3.0×10−43.0× 10^-4, with a cosine annealing schedule to gradually reduce the learning rate to 2.5×10−52.5× 10^-5. Architecture search using LP-DARTS used a constant step size of 2.75×10−32.75× 10^-3 for HLS across all epochs. We performed two architecture updates per epoch in all our architecture search experiments while optimizing architecture using LP-DARTS. This required the computation of the reduced Hessian matrix, reduced validation gradient, and the subsequent formulation and solution of the reduced LP (3) for each update. We utilized three random mini-batches from the training and validation sets to approximate the reduced Hessian and compute the reduced validation gradient. In R-LP-DARTS, the size of each selected model parameter tensor was limited to 1025 (ϰCIFAR−10≈0.053%,ϰCIFAR−100≈0.052%)( _CIFAR-10≈ 0.053\%, _CIFAR-100≈ 0.052\%) and we used only one model parameter tensor for HLS. To solve the LP formulations during optimization, we used the IBM CPLEX solver via the DOcplex Python API. Since CPLEX predominantly requires CPU resources, S-LP-DARTS and R-LP-DARTS necessitated the execution on a CPU. To ensure a fair comparison, DARTS was also run on the CPU. Table 1: Performance metrics of NAS methods on CIFAR-10 and CIFAR-100. NAS Alg. CIFAR-10 CIFAR-100 Val. Acc. (%) Search Cost (CPU hours) Val. Acc. (%) Search Cost (CPU hours) DARTS 81.93±0.3181.93± 0.31 26.30±0.5626.30± 0.56 49.69±0.8649.69± 0.86 26.12±0.4026.12± 0.40 S-LP-DARTS 84.94±0.3184.94± 0.31 25.30±0.2225.30± 0.22 55.51±0.3955.51± 0.39 25.84±0.6625.84± 0.66 R-LP-DARTS 84.96±0.4784.96 0.47 26.11±0.4226.11± 0.42 55.78±0.9255.78 0.92 25.40±0.2325.40± 0.23 (a) CIFAR-10 (b) CIFAR-100 Figure 2: Architecture search performance plots of the algorithms for three independent runs on the CIFAR-10 and CIFAR-100 datasets. S-LP-DARTS and R-LP-DARTS algorithms were executed three times on the CIFAR-10 and CIFAR-100 datasets, each with a different random seed. For comparison, the DARTS algorithm was also run three times using different random seeds. The performance trends observed during architecture optimization are illustrated in Figure 2. The summarized results, including mean and standard deviation of validation accuracy and runtime, are presented in Table 1. As shown in Figure 2, both LP-DARTS approaches achieve improvements in validation accuracy much faster than DARTS. In all experiments, the proposed LP-DARTS approach outperforms DARTS in terms of validation accuracy. 4.2 Architecture Evaluation We evaluate the searched architectures in two phases: the best architecture selection phase and the best architecture evaluation phase. The optimal normal and reduction cells are derived based on the highest validation accuracy achieved during the architecture search process. Once these optimal cells are identified, a larger model is constructed by stacking 20 optimal cells sequentially, with two reduction cells placed at 1/3 and 2/3 depths in the network (similar to the model considered for architecture search). The initial number of channels is increased from 16 to 32 to enhance the model’s capacity. To improve generalization, a path dropout rate of 0.2 is applied, along with auxiliary towers weighted at 0.4 and cutout data augmentation. All other hyperparameters remain unchanged from those used during the architecture search. The larger models, built using the optimal cells found through the architecture search on CIFAR-10 and CIFAR-100, are trained from scratch on their respective full training datasets and evaluated on their respective test sets. For the selection of the best architectures, the architectures derived from three architecture search experiments were trained for approximately 12 hours with a batch size of 576 and subsequently evaluated on the test datasets. The results, summarized in Table 2, consistently demonstrate the superior performance of the proposed method. Notably, models constructed using architectures searched by the two versions of LP-DARTS also exhibit significantly fewer parameters compared to those obtained with DARTS, as evidenced in Table 2. To illustrate the performance of the architectures in the evaluation phase, the test accuracy is plotted in Figure 3. Additionally, the visual representations of the best architectures (that is, yellow points in Figure 3) are provided in Appendix H. To further verify the performance of the architectures, we once again train the model parameters for each of architectures (yellow points in Figure 3) for an extended period of time (that is 20 hours) and evaluate the models once again on the test dataset. The results of this final evaluation are presented in Table 3. The training and validation performance of the models corresponding to the best architectures are presented in Figure 3. Table 2: Evaluation metrics for the architectures on CIFAR-10 and CIFAR-100. NAS Alg. CIFAR-10 CIFAR-100 Test Acc. (%) Eval. Cost (CPU hours) Params (M) Test Acc. (%) Eval. Cost (CPU hours) Params (M) DARTS 70.83±2.0970.83± 2.09 11.55±0.4811.55± 0.48 3.40±0.103.40± 0.10 23.84±9.4823.84± 9.48 11.85±0.4411.85± 0.44 3.64±0.123.64± 0.12 S-LP-DARTS 89.04±1.2689.04± 1.26 11.43±0.2411.43± 0.24 1.41±0.221.41± 0.22 63.94±3.6163.94 3.61 11.78±0.1811.78± 0.18 1.59±0.231.59± 0.23 R-LP-DARTS 89.87±0.8289.87 0.82 12.08±0.1812.08± 0.18 1.66±0.281.66± 0.28 58.92±4.5658.92± 4.56 12.02±0.3012.02± 0.30 1.75±0.411.75± 0.41 (a) Architecture Selection (b) Architecture Evaluation Figure 3: (a) Matrix plots illustrating architecture selection for the CIFAR-10 and CIFAR-100 datasets. (b) Training and validation performance of the best architectures on the CIFAR-10 and CIFAR-100 datasets. Table 3: Evaluation metrics for the best architectures on CIFAR-10 and CIFAR-100. Method CIFAR-10 CIFAR-100 Test Acc. (%) Eval. Cost (CPU hours) Params (M) Test Acc. (%) Eval. Cost (CPU hours) Params (M) DARTS 82.57 19.66 3.38 49.86 19.85 3.50 S-LP-DARTS 92.56 19.91 1.66 68.50 20.04 1.33 R-LP-DARTS 92.55 19.72 1.36 65.58 19.59 1.36 While both variants of LP-DARTS significantly outperformed DARTS in the overall evaluation results, the experimental findings did not indicate a definitive superiority between the two variants of LP-DARTS, as illustrated in Figure 3. However, the best architectures discovered by S-LP-DARTS achieved superior performance compared to those identified by R-LP-DARTS across both datasets, as presented in Table 3. 4.3 Architecture Transferability To evaluate the transferability of the learned architectures, we assess models on ImageNet using architectures obtained from CIFAR-10 via several NAS methods, including DARTS, LP-DARTS, P-DARTS, PC-DARTS, and STO-DARTS. Each model comprises 14 cells, with reduction cells placed at one-third and two-thirds of the total depth, and an initial channel size of 48. All models are trained from scratch on ImageNet for approximately 100 hours using a batch size of 576, an initial learning rate of 0.1, and a decay factor of 0.97, closely following the original DARTS evaluation protocol. The performance of these models is summarized in Table 4. The results indicate that LP-DARTS achieves competitive transferability performance from CIFAR-10 to ImageNet while maintaining the lowest model complexity among the considered methods. Notably, the architectures for DARTS and LP-DARTS are obtained under a controlled and comparable search budget, with all computations performed on CPUs. These architectures are selected during the early stages of the search process-well before full convergence-to reflect a realistic, resource-constrained setting. In contrast, the architectures for P-DARTS, PC-DARTS, and STO-DARTS variants are adopted from their original works [6, 44, 4], where the search is carried out to convergence using significantly greater computational resources, typically on GPUs. This distinction underscores the efficiency and practical viability of LP-DARTS in identifying high-quality, transferable architectures under limited computational budgets. Overall, despite operating under comparable or more restrictive search and evaluation conditions, LP-DARTS achieves competitive test performance with highest parameter efficiency, demonstrating their effectiveness in discovering competitive and transferable architectures. Table 4: Evaluation metrics for the best architectures on CIFAR-10 and their transferability on ImageNet under time-constrained settings. Method CIFAR-10 ImageNet Test Acc. (%) Eval. Cost (CPU hours) Params (M) Top-1 (5) Acc. (%) Eval. Cost (CPU hours) Params (M) DARTS 82.57 19.66 3.38 39.09 (64.10) 99.36 5.81 P-DARTS 90.23 21.67 2.74 44.60 (69.38) 98.96 4.94 PC-DARTS 89.10 20.84 2.90 42.40 (67.39) 101.53 5.27 STO-DARTSv1 89.04 19.79 2.20 42.72 (67.78) 101.52 4.15 STO-DARTSv2 87.89 20.85 3.06 42.89 (68.05) 102.32 5.37 LP-DARTS (ours) 92.56 19.91 1.66 42.50 (67.55) 99.32 3.46 4.4 Analysis and Discussion The comparative results summarized from the NAS literature [50, 26, 28, 20, 44, 3, 42, 36, 37, 2, 5, 11, 6, 4] (Appendix I) reveal several noteworthy trends. Early NAS methods such as NASNet and AmoebaNet, which rely on RL or evolutionary strategies, achieve strong accuracy but demand thousands of GPU-days due to discrete search and full training of candidate architectures. The introduction of differentiable NAS methods such as DARTS and PC-DARTS marked a breakthrough in efficiency, reducing computational cost by three orders of magnitude while maintaining competitive accuracy. Hardware-aware designs such as ProxylessNAS, FBNet, and MnasNet further refined this efficiency by explicitly incorporating latency constraints during search, making them viable for mobile and embedded systems. Meta-learning approaches, such as Once-for-All and Autoformer, illustrate a shift toward scalable and adaptive NAS frameworks that can generalize across architectures and modalities. Once-for-All introduces elastic supernetworks, allowing the reuse of pre-trained subnetworks across multiple deployment scenarios, while Autoformer demonstrates that NAS principles extend beyond CNNs to transformer-based architectures. Collectively, these methods highlight an ongoing trend toward generalizable and hardware-efficient NAS. Table 4 shows that LP-DARTS achieves superior performance compared to several DARTS variants under the time-constrained experimental settings on CIFAR-10, and remains competitive in the architecture transferability evaluation on ImageNet. This is particularly noteworthy given that the architectures for P-DARTS, PC-DARTS, and STO-DARTS are adopted from their original studies, where extensive experimentation and greater computational resources were used to identify optimal configurations. Furthermore, LP-DARTS attains the lowest model complexity among the considered methods. The superior performance of the proposed method arises from the inherent strength of its bilevel optimization framework. Unlike conventional DARTS variants, which approximate the hypergradient using only partial information, our LP formulation explicitly enforces lower-level optimality at each update. In particular, the solution of the LP provides a coupled direction (dA∗,dW∗)(d_A ,d_W ), where dA∗d_A denotes the descent direction for the architecture variables and dW∗d_W represents the consistent adjustment of network weights that preserves training optimality. This joint update mechanism effectively captures the interdependence between the upper-level validation objective and the lower-level training problem, thereby avoiding the instability that often limits DARTS-style methods, which do not ensure the optimality of the model parameters after architecture updates. Also, it can be easily shown that the original SOCP, which computes the steepest descent direction through its closed-form solution, yields the same direction for the architecture parameters as hypergradient-based methods [13]. Notably, exact hypergradient computation requires the inversion of the training-loss Hessian, whereas the proposed LP-based NAS framework operates directly on the Hessian, thereby avoiding this computationally expensive operation. More importantly, the proposed formulation is not restricted to the classical DARTS search space and is broadly applicable to a wide range of differentiable NAS settings, making it relevant to expert system applications based on deep learning. 5 Conclusion In this paper, we have introduced LP-NAS, an approach for architecture search within the bilevel optimization framework. The approach requires an LP to be solved in each iteration to obtain a descent direction for validation loss while ensuring that the training loss remains optimal. Applied to CNNs in DSS, LP-NAS surpasses the performance of DARTS, discovering cell architectures that lead to superior results. It also outperforms several DARTS variants under time-constrained experimental settings on the CIFAR-10 dataset while remaining competitive in architecture transferability to the ImageNet dataset. A key challenge in LP-NAS lies in the calculation of the Hessian matrix and solving the LP. To cater to the computational issues associated with these challenges we use a reduced Hessian, approximate it using L-BFGS, and formulate a reduced LP. The use of limited second-order information from the lower-level is still advantageous as the method quickly leads to better losses and accuracies in all our experiments as compared to the standard DARTS algorithm. The proposed LP based approach can be integrated with any architecture search problem with continuous architecture and model parameters. Interesting future research can be performed on appropriate choice of model parameters for the formulation of the reduced Hessian such that maximum amount of second-order information is extracted. Additionally, approximate Hessians with special structures, such as, block diagonal, block angular, block triangular, staircase, and bordered angular, can be formulated for faster solution of the LP. The results are promising and we believe it has the potential to open a new line of research on solving architecture search problems using bilevel methods by utilizing second-order information. Acknowledgments The authors gratefully acknowledge the High Performance Computing (HPC) facility at the Indian Institute of Technology (IIT) Kanpur (PARAM Sanganak) for providing the resources that enabled the smooth execution of the experiments in this work. References [1] K. P. Bennett, G. Kunapuli, J. Hu, and J. Pang (2008) Bilevel optimization and machine learning. In IEEE world congress on computational intelligence, p. 25–47. Cited by: §1. [2] H. Cai, C. Gan, T. Wang, Z. Zhang, and S. Han (2019) Once-for-all: train one network and specialize it for efficient deployment. arXiv preprint arXiv:1908.09791. Cited by: Table 5, Appendix I, §4.4. [3] H. Cai, L. Zhu, and S. Han (2018) Proxylessnas: direct neural architecture search on target task and hardware. arXiv preprint arXiv:1812.00332. Cited by: Table 5, Appendix I, §4.4. [4] Z. Cai, L. Chen, T. Ling, and H. Liu (2024) STO-DARTS: stochastic bilevel optimization for differentiable neural architecture search. IEEE Transactions on Emerging Topics in Computational Intelligence. Cited by: Appendix A, Appendix I, §4.3, §4.4. [5] M. Chen, H. Peng, J. Fu, and H. Ling (2021) Autoformer: searching transformers for visual recognition. In Proceedings of the IEEE/CVF international conference on computer vision, p. 12270–12280. Cited by: Table 5, Appendix I, §4.4. [6] X. Chen, L. Xie, J. Wu, and Q. Tian (2019) Progressive differentiable architecture search: bridging the depth gap between search and evaluation. arXiv preprint arXiv:1904.12760. Cited by: Appendix A, Appendix I, §4.3, §4.4. [7] K. T. Chitty-Venkata, M. Emani, V. Vishwanath, and A. K. Somani (2022) Neural architecture search for transformers: a survey. IEEE access 10, p. 108374–108412. Cited by: §1. [8] X. Chu, T. Zhou, B. Zhang, and J. Li (2020) Fair DARTS: eliminating unfair advantages in differentiable architecture search. In Computer Vision – ECCV 2020, Cham, p. 465–480. External Links: ISBN 978-3-030-58555-6 Cited by: Appendix A. [9] T. Elsken, J. H. Metzen, and F. Hutter (2019) Neural architecture search: a survey. Journal of Machine Learning Research 20 (55), p. 1–21. Cited by: §1. [10] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil (2018) Bilevel programming for hyperparameter optimization and meta-learning. In International conference on machine learning, p. 1568–1577. Cited by: §1. [11] Y. Gao, H. Yang, P. Zhang, C. Zhou, and Y. Hu (2019) Graphnas: graph neural architecture search with reinforcement learning. arXiv preprint arXiv:1904.09981. Cited by: Table 5, Appendix I, §4.4. [12] T. Giovannelli, G. D. Kent, and L. N. Vicente (2021) Inexact bilevel stochastic gradient methods for constrained and unconstrained lower-level problems. arXiv preprint arXiv:2110.00604. Cited by: §2.1. [13] T. Giovannelli, G. D. Kent, and L. N. Vicente (2025) Inexact bilevel stochastic gradient methods for constrained and unconstrained lower-level problems. Journal of Global Optimization 92 (3), p. 569–614. Cited by: §4.4. [14] B. Guo, S. He, M. Shi, K. Yu, J. Chen, and X. Shen (2024) Semantic-DARTS: elevating semantic learning for mobile differentiable architecture search. IEEE Internet of Things Journal. Cited by: Appendix A. [15] J. Li, Y. Wang, Y. Wang, R. Yu, and X. Wang (2024) HN-DARTS: hybrid network differentiable architecture search for industrial scenarios. In Pacific Rim International Conference on Artificial Intelligence, p. 322–327. Cited by: Appendix A. [16] T. Li, J. Zhang, K. Bao, Y. Liang, Y. Li, and Y. Zheng (2020) AutoST: efficient neural architecture search for spatio-temporal prediction. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, p. 794–802. Cited by: §1. [17] Z. Li, Y. Xu, P. Ying, H. Chen, R. Sun, and X. Xu (2024) LMD-DARTS: low-memory, densely connected, differentiable architecture search. Electronics 13 (14), p. 2743. Cited by: Appendix A. [18] H. Liang, S. Zhang, J. Sun, X. He, W. Huang, K. Zhuang, and Z. Li (2019) DARTS+: improved differentiable architecture search with early stopping. arXiv preprint arXiv:1909.06035. Cited by: Appendix A. [19] C. Liu, L. Chen, F. Schroff, H. Adam, W. Hua, A. L. Yuille, and L. Fei-Fei (2019) Auto-DeepLab: hierarchical neural architecture search for semantic image segmentation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, p. 82–92. Cited by: §1. [20] H. Liu, K. Simonyan, and Y. Yang (2019) DARTS: differentiable architecture search. In International Conference on Learning Representations (ICLR), Cited by: Appendix A, Table 5, Appendix I, §1, §2.1, §4.1, §4.4. [21] Y. Liu, Y. Sun, B. Xue, M. Zhang, G. G. Yen, and K. C. Tan (2021) A survey on evolutionary neural architecture search. IEEE transactions on neural networks and learning systems 34 (2), p. 550–570. Cited by: §1. [22] F. Meng, C. Wang, and A. Brown (2024) Evolution and efficiency in neural architecture search: bridging the gap between expert design and automated optimization. arXiv preprint arXiv:2403.17012. Cited by: §1. [23] J. Mun, S. Ha, and J. Lee (2023) DE-DARTS: neural architecture search with dynamic exploration. ICT Express 9 (3), p. 379–384. Cited by: Appendix A. [24] K. Nakai, T. Matsubara, and K. Uehara (2020) Att-DARTS: differentiable neural architecture search for attention. In 2020 International Joint Conference on Neural Networks (IJCNN), p. 1–8. Cited by: Appendix A. [25] T. Okuno, A. Takeda, A. Kawana, and M. Watanabe (2021) On lp-hyperparameter learning via bilevel nonsmooth optimization. Journal of Machine Learning Research 22 (245), p. 1–47. Cited by: §1. [26] H. Pham, M. Guan, B. Zoph, Q. Le, and J. Dean (2018) Efficient neural architecture search via parameters sharing. In International conference on machine learning, p. 4095–4104. Cited by: Table 5, Appendix I, §4.4. [27] D. Pujara and A. Sinha (2025) A review of bilevel optimization: methods, emerging applications, and recent advancements. arXiv preprint arXiv:2511.03448. Cited by: §1. [28] E. Real, A. Aggarwal, Y. Huang, and Q. V. Le (2019) Regularized evolution for image classifier architecture search. In Proceedings of the aaai conference on artificial intelligence, Vol. 33, p. 4780–4789. Cited by: Table 5, Appendix I, §4.4. [29] P. Ren, Y. Xiao, X. Chang, P. Huang, Z. Li, X. Chen, and X. Wang (2021) A comprehensive survey of neural architecture search: challenges and solutions. ACM Computing Surveys (CSUR) 54 (4), p. 1–34. Cited by: §1. [30] A. Sarah, S. N. Sridhar, M. Szankin, and S. Sundaresan (2024) LLaMA-NAS: efficient neural architecture search for large language models. arXiv preprint arXiv:2405.18377. Cited by: §1. [31] A. Shukla, A. Khanna, A. Sinha, and F. Hamid (2026) LiFT: local search via linear programming for overfitting-controlled transformers. arXiv preprint arXiv:2606.16243. Cited by: §1. [32] A. Shukla, A. Sinha, and F. Hamid (2026) Bilevel optimization for neural architecture search. arXiv preprint arXiv:2606.29582. Cited by: §1. [33] A. Sinha, T. Khandait, and R. Mohanty (2024) A gradient-based bilevel optimization approach for tuning regularization hyperparameters. Optimization Letters 18 (6), p. 1383–1404. Cited by: §1. [34] A. Sinha and S. Gunwal (2025) A linear programming-based hyper local search for tuning hyperparameters. Operations Research Letters 61, p. 107287. Cited by: §1. [35] A. Sinha, P. Malo, and K. Deb (2017) A review on bilevel optimization: from classical to evolutionary approaches and applications. IEEE transactions on evolutionary computation 22 (2), p. 276–295. Cited by: §1. [36] M. Tan, B. Chen, R. Pang, V. Vasudevan, M. Sandler, A. Howard, and Q. V. Le (2019) Mnasnet: platform-aware neural architecture search for mobile. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, p. 2820–2828. Cited by: Table 5, Appendix I, §4.4. [37] M. Tan and Q. Le (2019) Efficientnet: rethinking model scaling for convolutional neural networks. In International conference on machine learning, p. 6105–6114. Cited by: Table 5, Appendix I, §4.4. [38] B. Wang, Y. Zhong, and Y. Liu (2026) Zen-DARTS: mitigating performance collapse with synflow metric regularization and improved architecture parameter initialization. In ICASSP 2026-2026 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), p. 1591–1595. Cited by: Appendix A. [39] Y. Wang, L. Zhen, J. Zhang, M. Li, L. Zhang, Z. Wang, Y. Feng, Y. Xue, X. Wang, Z. Chen, et al. (2024) MedNAS: multi-scale training-free neural architecture search for medical image analysis. IEEE Transactions on Evolutionary Computation. Cited by: §1. [40] Y. Weng, T. Zhou, Y. Li, and X. Qiu (2019) NAS-Unet: neural architecture search for medical image segmentation. IEEE access 7, p. 44247–44257. Cited by: §1. [41] C. White, M. Safari, R. Sukthanker, B. Ru, T. Elsken, A. Zela, D. Dey, and F. Hutter (2023) Neural architecture search: insights from 1000 papers. arXiv preprint arXiv:2301.08727. Cited by: §1. [42] B. Wu, X. Dai, P. Zhang, Y. Wang, F. Sun, Y. Wu, Y. Tian, P. Vajda, Y. Jia, and K. Keutzer (2019) Fbnet: hardware-aware efficient convnet design via differentiable neural architecture search. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, p. 10734–10742. Cited by: Table 5, Appendix I, §4.4. [43] L. Xie, E. Lomurno, M. Gambella, D. Ardagna, M. Roveri, M. Matteucci, and Q. Shi (2024) A lightweight neural architecture search model for medical image classification. arXiv preprint arXiv:2405.03462. Cited by: §1. [44] Y. Xu, L. Xie, X. Zhang, X. Chen, G. Qi, Q. Tian, and H. Xiong (2019) PC-DARTS: partial channel connections for memory-efficient architecture search. arXiv preprint arXiv:1907.05737. Cited by: Appendix A, Table 5, Appendix I, §4.3, §4.4. [45] L. Yang, Z. Zheng, Y. Han, S. Song, G. Huang, and F. Li (2024) OStr-DARTS: differentiable neural architecture search based on operation strength. IEEE Transactions on Cybernetics. Cited by: Appendix A. [46] A. Zela, T. Elsken, T. Saikia, Y. Marrakchi, T. Brox, and F. Hutter (2019) Understanding and robustifying differentiable architecture search. arXiv preprint arXiv:1909.09656. Cited by: Appendix A. [47] H. Zhang, K. Hao, L. Gao, X. Tang, and B. Wei (2023) Enhanced gradient for differentiable architecture search. IEEE Transactions on Neural Networks and Learning Systems. Cited by: Appendix A. [48] H. Zhu, X. Jin, H. Liao, Y. Xiang, M. A. El-Yacoubi, and H. Qin (2024) Relax DARTS: relaxing the constraints of differentiable architecture search for eye movement recognition. arXiv preprint arXiv:2409.11652. Cited by: Appendix A. [49] B. Zoph and Q. V. Le (2017) Neural architecture search with reinforcement learning. In Proceedings of the International Conference on Learning Representations (ICLR), Cited by: §1, §1. [50] B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le (2018) Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, p. 8697–8710. Cited by: Table 5, Appendix I, §4.4. [51] B. Zoph, V. Vasudevan, J. Shlens, and Q. Le (2017) AutoML for large scale image classification and object detection. Google AI Blog 2 (2017). Cited by: §1. Appendix Appendix A DARTS The DARTS method, introduced in [20], presented a highly efficient and competitive NAS approach compared to RL- and EC-based methods, functioning within a continuous search space. Building on DARTS, Progressive Differentiable Architecture Search (P-DARTS) was developed by [6], which addressed computational challenges and enhanced search stability through search space approximation and regularization techniques. To further improve the robustness of DARTS, [46] proposed Robustness of Differentiable Architecture Search (R-DARTS), which systematically investigated architectural spaces and regularization strategies. In [44], the authors introduced an innovative method known as Partially-Connected Differentiable Architecture Search (PC-DARTS) with the obvious goal of improving the efficiency and stability of NAS. Another extension, Att-DARTS [24], incorporated attention modules into the DARTS framework to further enhance the architecture search process. The manifestation of the collapse phenomenon in DARTS, characterized by an excessive occurrence of skip-connects over an extensive number of search epochs due to overfitting of the one-shot model, resulted in diminished performance. This challenge was effectively addressed by introducing early stopping criteria in DARTS+ [18], where DARTS stops when two or more skip-connects appear in a normal cell or when the architecture parameter ranking remains stable for a predefined number of epochs. Fair DARTS [8] was introduced to tackle issues of collapse observed in the DARTS algorithm due to unfair advantages in exclusive competition among candidate operations during the search process. DE-DARTS developed by [23] addressed the challenges of gradient-based NAS by proposing a novel approach that incorporated Dynamic Attention Networks (DANs). More recently, EG-DARTS [47] used a multi-objective evolution-based approach, combining gradient optimization with evolutionary strategies to improve DARTS’ search effectiveness. Additional advancements have been made with methods like Relax-DARTS [48], STO-DARTS [4], OSTR-DARTS [45], semantic DARTS [14], LMD-DARTS [17], HN-DARTS [15], and ZEN-DARTS [38], among others, highlighting continued innovation within the DARTS framework. Appendix B LP for HLS Assuming that for any given set of hyperparameters, a solution to the lower-level problem always exists. Additionally, it is required that the validation loss function be at least once differentiable and the training loss function be at least twice differentiable. By writing the linear Taylor’s approximation of the validation loss function around the point (A0,W0)(A^0,W^0), we obtain the following expansion: ℒv(A0+tdA,W0+tdW)= _v(A^0+td_A,W^0+td_W)= ℒv(A0,W0)+t⟨∇Aℒv(A0,W0),dA⟩ _v(A^0,W^0)+t _AL_v(A^0,W^0),d_A +t⟨∇Wℒv(A0,W0),dW⟩ +t _WL_v(A^0,W^0),d_W where t is the step-size greater than zero and [dA,dW]T[d_A,d_W]^T is a direction vector. ℒv(A0+tdA,W0+tdW)−ℒv(A0,W0)= _v(A^0+td_A,W^0+td_W)-L_v(A^0,W^0)= t⟨[∇Aℒv(A0,W0)∇Wℒv(A0,W0)],[dAdW]⟩ t bmatrix _AL_v(A^0,W^0)\\ _WL_v(A^0,W^0) bmatrix, bmatrixd_A\\ d_W bmatrix From the above equation, it can be concluded that the direction vector is a descent direction (validation loss improves) if and only if the inner product of the gradient of the upper-level objective function with the direction vector is negative. This can be mathematically expressed as ⟨[∇Aℒv(A0,W0)∇Wℒv(A0,W0)],[dAdW]⟩<0 bmatrix _AL_v(A^0,W^0)\\ _WL_v(A^0,W^0) bmatrix, bmatrixd_A\\ d_W bmatrix <0 where ∇Aℒv _AL_v and ∇Wℒv _WL_v represent the gradients of the validation loss function with respect to A and W respectively. Moreover, this descent direction must ensure that the lower-level problem remains optimal as the upper-level variable A changes along the direction dAd_A. This imposes the condition dW∈argmindWℒt(A0+tdA,W0+tdW)d_W∈ _d_WL_t(A^0+td_A,W^0+td_W) (5) which ensures that dWd_W is the direction minimizing the lower-level objective with respect to W, given the change in A along the direction dAd_A. By writing the quadratic approximation of the lower-level objective around the point (A0,W0)(A^0,W^0), we obtain the following expansion: ℒt(A0+tdA,W0+tdW)= _t(A^0+td_A,W^0+td_W)= (6) ℒt(A0,W0)+t⟨∇Aℒt(A0,W0),dA⟩ _t(A^0,W^0)+t _AL_t(A^0,W^0),d_A +t⟨∇Wℒt(A0,W0),dW⟩ +t _WL_t(A^0,W^0),d_W +12t2⟨[dAdW],∇(A,W)2ℒt(A0,W0)[dAdW]⟩ + 12t^2 bmatrixd_A\\ d_W bmatrix, _(A,W)^2L_t(A^0,W^0) bmatrixd_A\\ d_W bmatrix where ∇(A,W)2ℒt(A0,W0) _(A,W)^2L_t(A^0,W^0) denotes the Hessian matrix of the training loss function (ℒt)(L_t) with respect to A and W, evaluated at (A0,W0)(A^0,W^0). At the optimal solution of the lower-level objective, the second and third terms vanish. Ignoring the constant first term, the lower-level problem (5) reduces to the following optimization problem: dW∈argmindW⟨[dAdW],∇(A,W)2ℒt(A0,W0)[dAdW]⟩d_W∈ _d_W bmatrixd_A\\ d_W bmatrix, _(A,W)^2L_t(A^0,W^0) bmatrixd_A\\ d_W bmatrix (7) Let p and q denote the number of hyperparameters and model parameters, respectively. The Hessian matrix of the training loss can be expressed as follows: [Hij]i=1,j=1i=p+q,j=p+q=∇(A,W)2ℒt(A0,W0) bmatrixH_ij bmatrix_i=1,j=1^i=p+q,j=p+q= _(A,W)^2L_t(A^0,W^0) (8) Let [Hij]i=1,j=1i=p+q,j=p+q bmatrixH_ij bmatrix_i=1,j=1^i=p+q,j=p+q =[[Hij]i=1,j=1i=p,j=p[Hij]i=1,j=p+1i=p,j=p+q[Hij]i=p+1,j=1i=p+q,j=p[Hij]i=p+1,j=p+1i=p+q,j=p+q] = bmatrix[H_ij]_i=1,j=1^i=p,j=p&[H_ij]_i=1,j=p+1^i=p,j=p+q\\ [H_ij]_i=p+1,j=1^i=p+q,j=p&[H_ij]_i=p+1,j=p+1^i=p+q,j=p+q bmatrix (9) =[H11H12H21H22] = bmatrixH_11&H_12\\ H_21&H_22 bmatrix Since the problem (7) is an unconstrained optimization problem, the first-order optimality conditions can be derived by taking the gradient of the objective function with respect to dWd_W and setting it equal to zero, which reduces to: [H21H22][dAdW]=0 bmatrixH_21&H_22 bmatrix bmatrixd_A\\ d_W bmatrix=0 (10) Ensuring the lower-level optimality conditions, if we aim to find the unit vector with the steepest descent direction for validation loss, it leads to solving the following SOCP problem: mindA,dW _d_A,d_W ⟨[∇Aℒv(A0,W0)∇Wℒv(A0,W0)],[dAdW]⟩ bmatrix _AL_v(A^0,W^0)\\ _WL_v(A^0,W^0) bmatrix, bmatrixd_A\\ d_W bmatrix (11) subject to: to: [H21H22][dAdW]=0 bmatrixH_21&H_22 bmatrix bmatrixd_A\\ d_W bmatrix=0 ‖dA‖2≤1 \|d_A\|_2≤ 1 This SOCP problem can be relaxed to the following usable LP to give a descent direction: mindA,dW _d_A,d_W ⟨[∇Aℒv(A0,W0)∇Wℒv(A0,W0)],[dAdW]⟩ bmatrix _AL_v(A^0,W^0)\\ _WL_v(A^0,W^0) bmatrix, bmatrixd_A\\ d_W bmatrix (12) subject to: to: [H21H22][dAdW]=0 bmatrixH_21&H_22 bmatrix bmatrixd_A\\ d_W bmatrix=0 −1≤dA≤1 -1≤ d_A≤ 1 Appendix C Proof of Proposition 1 Proof. The affine (linear) constraints of the LP can be written as: H21dA+H22dW=0 H_21d_A+H_22d_W=0 (13) From equations (6), (8) and (9), we have ℒt(A0+tdA,W0+tdW)= _t(A^0+td_A,W^0+td_W)= (14) ℒt(A0,W0)+t⟨∇Aℒt(A0,W0),dA⟩ _t(A^0,W^0)+t _AL_t(A^0,W^0),d_A +t⟨∇Wℒt(A0,W0),dW⟩ +t _WL_t(A^0,W^0),d_W +12t2⟨[dAdW],[H11H12H21H22][dAdW]⟩ + 12t^2 bmatrixd_A\\ d_W bmatrix, bmatrixH_11&H_12\\ H_21&H_22 bmatrix bmatrixd_A\\ d_W bmatrix From equations (13) and (14) ℒt(A0+tdA,W0+tdW)= _t(A^0+td_A,W^0+td_W)= (15) ℒt(A0,W0)+t⟨∇Aℒt(A0,W0),dA⟩ _t(A^0,W^0)+t _AL_t(A^0,W^0),d_A +t⟨∇Wℒt(A0,W0),dW⟩ +t _WL_t(A^0,W^0),d_W +12t2⟨dA,H11dA+H12dW⟩ + 12t^2 d_A,H_11d_A+H_12d_W Writing dWd_W in terms of dAd_A and Hessian matrices using equation (13) dW=−H22−1H21dAd_W=-H_22^-1H_21d_A (16) Building upon Equations (15) and (16) ℒt(A0+tdA,W0+tdW)= _t(A^0+td_A,W^0+td_W)= (17) ℒt(A0,W0)+t⟨∇Aℒt(A0,W0),dA⟩ _t(A^0,W^0)+t _AL_t(A^0,W^0),d_A +t⟨∇Wℒt(A0,W0),dW⟩ +t _WL_t(A^0,W^0),d_W +t2⟨dA,(H11−H12H22−1H21)dA⟩ +t^2 d_A,(H_11-H_12H_22^-1H_21)d_A Assuming the pseudo-inverse of H21H_21, denoted as H21†H_21 , we can express dAd_A in terms of dWd_W as dA=−H21†H22dWd_A=-H_21 H_22d_W (18) Substituting dAd_A from Equation (18) into Equation (17), we rewrite the Taylor’s expansion in terms of dWd_W ℒt(A0+tdA,W0+tdW)= _t(A^0+td_A,W^0+td_W)= ℒt(A0,W0)+t⟨∇Aℒt(A0,W0),−H21†H22dW⟩ _t(A^0,W^0)+t _AL_t(A^0,W^0),-H_21 H_22d_W +t⟨∇Wℒt(A0,W0),dW⟩ +t _WL_t(A^0,W^0),d_W +t2⟨H21†H22dW,(H11−H12H22−1H12T)H21†H22dW⟩ +t^2 H_21 H_22d_W,(H_11-H_12H_22^-1H_12^T)H_21 H_22d_W The second-order gradient with respect to the updated model parameters, (W0+tdW)(W^0+td_W), yields the new Hessian matrix H′=(H21†H22)T(H11−H12H22−1H12T)H21†H22H =(H_21 H_22)^T(H_11-H_12H_22^-1H_12^T)H_21 H_22 where S=H11−H12H22−1H12TS=H_11-H_12H_22^-1H_12^T represents the Schur complement of H22H_22 in the original Hessian matrix [Hij]i=1,j=1i=p+q,j=p+q bmatrixH_ij bmatrix_i=1,j=1^i=p+q,j=p+q. If the original Hessian matrix is positive semidefinite (PSD), its Schur complement S is also guaranteed to be PSD. H′H will be PSD if for all vectors z∈ℝqz ^q, zTH′z≥0z^TH z≥ 0. To verify the positive semidefiniteness of H′H , we consider an arbitrary vector y∈ℝqy ^q yTH′y=yT((H21†H22)TS(H21†H22))y^TH y=y^T ((H_21 H_22)^TS(H_21 H_22) )y Let v=H21†H22yv=H_21 H_22y, then yTH′y=vTSvy^TH y=v^TSv. Since S is PSD, it follows that vTSv≥0v^TSv≥ 0 for all v∈ℝpv ^p. Thus, yTH′y≥0∀y∈ℝqy^TH y≥ 0 ∀ y ^q which confirms that H′H is PSD. In conclusion, the new Hessian matrix H′H being PSD establishes that the HLS is confined to the lower-level optimality region. ∎ Appendix D Proof of Proposition 2 Proof. To establish that the optimal objective value is always non-positive, we construct a feasible solution and evaluate its objective value. Feasibility of (dA,dW)=(0,0)(d_A,d_W)=(0,0): Choosing dA=0d_A=0 and dW=0d_W=0, the affine constraints of the devised LP are trivially satisfied H21(0)+H22(0)=0 H_21(0)+H_22(0)=0 Additionally, the box constraints hold as −1≤0≤1 -1≤ 0≤ 1 Objective Function Evaluation: At (dA,dW)=(0,0)(d_A,d_W)=(0,0), the objective function evaluates to ⟨[∇Aℒv(A0,W0)∇Wℒv(A0,W0)],[00]⟩=0 bmatrix _AL_v(A^0,W^0)\\ _WL_v(A^0,W^0) bmatrix, bmatrix0\\ 0 bmatrix =0 Since the problem is of minimization type, the optimal objective value satisfies ⟨[∇Aℒv(A0,W0)∇Wℒv(A0,W0)],[dA∗dW∗]⟩≤0 bmatrix _AL_v(A^0,W^0)\\ _WL_v(A^0,W^0) bmatrix, bmatrixd_A^*\\ d_W^* bmatrix ≤ 0 Thus, the validation performance improves in most cases, and in the worst case, leaves it unchanged. ∎ Appendix E Reduced Hessian Formulation for Memory and Computational Efficiency In deep learning, the model architecture is characterized by architecture parameters and model parameters. The architecture parameters typically have a much smaller dimension than the model parameters, i.e., p≪qp q, whereas the number of model parameters can range from millions to billions. Consequently, formulating the LP presents a significant computational challenge due to the size of the Hessian matrix. For a model with p architecture parameters and q model parameters, the complete Hessian of the training loss has dimension (p+q)×(p+q)(p+q)×(p+q). Since the lower-level optimization is performed only with respect to the model parameters, only the submatrix of size q×(p+q)q×(p+q) is required by the proposed LP. For convenience, we continue to refer to this rectangular submatrix as the Hessian matrix throughout the paper. The memory required to store this matrix is substantial. For example, a model with approximately two million parameters requires nearly 29.829.8 TB of memory to store the Hessian in double precision. Furthermore, the computational complexity of explicit Hessian computation is O(n2)O(n^2), making it prohibitively expensive for modern deep neural networks. To overcome these limitations, we compute second-order derivatives only for a subset of the model parameters, denoted by w⊂Ww⊂ W. Specifically, all p architecture parameters together with only κqκ q model parameters are retained, where κ≪1κ 1. The resulting reduced Hessian, [Hij′]i=p+1,j=1i=p+κq,j=p+κq,[H _ij]_i=p+1,\;j=1^\,i=p+κ q,\;j=p+κ q, has dimension κq×(p+κq).κ q×(p+κ q). Similarly, the validation gradient is computed only with respect to the retained parameters, i.e. [∇Aℒv(A,W),∇wℒv(A,W)]T,[ _AL_v(A,W),\; _wL_v(A,W)]^T, which we refer to as the reduced validation gradient. These quantities are then used to formulate a reduced LP that can be solved efficiently. Finally, we employ the L-BFGS algorithm to approximate the reduced Hessian. L-BFGS requires only O(mn)O(mn) computation per iteration, where m denotes the memory parameter (the number of stored correction pairs) and n is the parameter dimension. Consequently, the proposed formulation achieves substantial reductions in both memory consumption and computational time, at the cost of utilizing only partial second-order information from the lower-level problem. Appendix F Mathematical Formulation of Model Parameter Selection This section presents the mathematical formulation of the two model parameter selection strategies used for reduced Hessian computation in LP-NAS. In deep learning models, model parameters are typically represented as multi-dimensional tensors. In our experimental configurations, which employ a convolutional neural network (CNN), most parameters are structured as four-dimensional tensors. Let the ithi^th model parameter tensor be denoted by iW_i, with NiN_i dimensions such that i∈ℝd1i×d2i×⋯×dNii,W_i ^d_1^i× d_2^i×·s× d_N_i^i, where djid_j^i denotes the size of the jthj^th dimension. Specific parameter selection (S-LP-NAS). Following the lower-level optimization, the gradients of the training loss with respect to all model parameters are available. These gradients are used to compute the Gradient Norm Per Parameter (GNPP), GNPPi=‖∇iℒt(A0,W0)‖2∏j=1Nidji.GNPP_i= \| _W_iL_t(A^0,W^0)\|_2 _j=1^N_id_j^i. (19) The model parameter tensor is selected according to i∗=argmaxiGNPPi,i^*= _iGNPP_i, (20) and the number of selected parameters is κq=∏j=1Ni∗dji∗.κ q= _j=1^N_i^*d_j^\,i^*. (21) This criterion favors parameter tensors exhibiting large training-loss gradients while maintaining a relatively small tensor size. Random parameter selection (R-LP-NAS). Alternatively, a subset of parameter tensors is selected uniformly at random from the set of valid candidate tensors satisfying a prescribed size constraint. Let =i|∏j=1Nidji≤ϰq,C= \i\, |\, _j=1^N_id_j^i≤ q \, (22) where ϰq q denotes the maximum allowable number of parameters for reduced Hessian computation. A subset of n tensors is sampled as I=ij∣ij∼Uniform(),j=1,…,n,I= \i_j i_j (C),\;j=1,…,n \, (23) and the total number of selected parameters is κq=∑i∈I∏j=1Nidji.κ q= _i∈ I _j=1^N_id_j^i. (24) Since different parameter tensors are selected across iterations, this strategy enables diverse Hessian approximations and provides update opportunities for different regions of the network. Appendix G Time Complexity The computational cost of each outer iteration is summarized as follows: 1. Hessian approximation (L-BFGS): O(mn)O(mn) 2. Validation gradient and parameter update: O(n)O(n) 3. LP formulation and solution: The LP involves n variables, κqκ q linear equality constraints, and p box constraints. While the worst-case complexity of generic LP solvers is O(n3)O(n^3), the practical cost in our setting is significantly lower due to the small value of κ and the structured nature of the constraint matrix (primarily linear orthogonality constraints). Empirically, the solve time is well approximated by O(n2)O(n^2). 4. Lower-level weight optimization: Processing EDE_D samples with batch size B requires O(EDBCP)O\! ( E_DBC_P ). Aggregating these components over kmaxk^max outer iterations, the total time complexity is: O(kmax[mn+n+n2+EDBCP]).O\! (k^max [mn+n+n^2+ E_DBC_P ] ). (25) Since typically m≪nm n (e.g., m≈15m≈ 15 and n≈103n≈ 10^3 in our experiments), the linear term mnmn is dominated by the quadratic term n2n^2. Therefore, the overall complexity can be simplified as: O(kmax[n2+EDBCP]).O\! (k^max [n^2+ E_DBC_P ] ). (26) Appendix H Optimal Normal and Reduction Cells The optimal normal and reduction cells discovered by the NAS methods for the CIFAR-10 and CIFAR-100 datasets are shown in Figures 4 and 5, respectively. Figure 4: Optimal normal and reduction cells searched on CIFAR-10 dataset. Figure 5: Optimal normal and reduction cells searched on CIFAR-100 dataset. Appendix I Comparative Results NAS has evolved into one of the most dynamic subfields in deep learning, with a diverse set of methodologies demonstrating competitive results across benchmark datasets such as CIFAR-10, CIFAR-100, ImageNet, and more recently, large-scale transformer and graph domains. To provide a unified perspective on performance trends, this section consolidates results from key NAS algorithms, highlighting accuracy, parameter efficiency, and computational requirements. The data presented are drawn from original studies and comparative analysis in the NAS literature [50, 26, 28, 20, 44, 3, 42, 36, 37, 2, 5, 11, 6, 4]. Table 5 summarizes representative NAS methods spanning RL, EC, differentiable optimization, and meta-learning paradigms. Each approach is evaluated based on Top-1 accuracy, parameter count, and computational cost (architecture search time) measured in GPU days. The results clearly show the efficiency gains achieved by differentiable NAS and one-shot frameworks compared to earlier black-box methods. Table 5: Comparative performance of representative NAS methods on CIFAR-10 and ImageNet benchmarks. Method Search Type Search Space Dataset Top-1 Acc. (%) Params (M) GPU Days NASNet-A [50] RL-based Cell-based CIFAR-10 (ImageNet) 97.35 (74.0) 3.3 (5.3) 2000 ENAS [26] RL (Weight Sharing) Cell-based CIFAR-10 97.11 4.6 0.5 AmoebaNet-A [28] Evolutionary Cell-based CIFAR-10 (ImageNet) 96.66 (74.5) 3.2 (5.1) 3150 DARTS [20] Differentiable Continuous CIFAR-10 (ImageNet) 97.24 (73.3) 3.3 (4.7) 4 PC-DARTS [44] Differentiable Continuous CIFAR-10 (ImageNet) 97.43 (74.9) 3.6 (5.3) 0.1 ProxylessNAS [3] Differentiable Hardware-aware CIFAR-10 (ImageNet) 97.92 (75.1) 5.7 (7.1) 4 FBNet [42] Differentiable Hardware-aware ImageNet 74.9 5.5 9 MnasNet [36] RL + Hardware Mobile Search ImageNet 75.2 3.9 4.5 EfficientNet-B0 [37] Compound Scaling Platform-aware ImageNet 76.3 5.3 - Once-for-All [2] One-shot (Meta) Elastic Supernet ImageNet 76.9 7.7 1.7 Autoformer [5] Differentiable Transformer ImageNet 82.4 54.0 - GraphNAS [11] RL-based Graph Neural Nets Cora (Citeseer) 84.2 (73.1) - -