PaperlayerView exact revision on arXiv

Source-linked AI summary

LP-NAS: Linear Programming-based Neural Architecture Search

Abhishek Shukla, Ankur Sinha, Faiz Hamid

arXiv:2608.14472v1cs.LGcs.AI

TL;DR

Differentiable NAS needs efficient ways to optimize continuous architecture spaces while preserving model optimality. LP-NAS uses linear programming to compute architecture updates, outperforming DARTS and remaining competitive in transferability to ImageNet.

  • Problem

    Existing differentiable NAS methods optimize continuous architectures, but preserving model optimality during architecture updates remains a research challenge.

  • Method

    LP-NAS formulates a linear program using validation gradients and training-loss Hessian information to jointly update architectures and model parameters while maintaining lower-level optimality.

  • Results

    LP-NAS surpasses DARTS on CIFAR experiments, outperforms several DARTS variants under time constraints, and remains competitive when architectures transfer to ImageNet.

  • Takeaways & Limitations

    LP-NAS provides an effective architecture-search framework for continuous spaces, with stronger reported performance than DARTS and competitive transferability to ImageNet.

  • Takeaways & Limitations

    LP-NAS requires Hessian computation and linear-program solving, so the authors use reduced and L-BFGS-approximated second-order information to address computational challenges.

Abstract

from arXiv · show

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.

1 Introduction

LP-NAS frames differentiable NAS as a linear-programming approach that uses validation gradients and lower-level Hessian information to improve architecture updates while preserving model optimality. Its efficient variants and LP-DARTS instantiations are reported to accelerate convergence, outperform standard DARTS, and transfer across benchmark datasets.

  • Motivation: NAS is formulated as a bilevel optimization problem in which architecture selection is the outer problem and weight training is the inner problem.The formulation uses validation loss and training loss as the upper- and lower-level objectives, respectively.
  • Motivation: Reinforcement-learning and evolutionary NAS methods require approximately three orders of magnitude more GPU days than gradient-based methods.Their higher cost stems from exploring discrete architectural spaces and treating the objective as a black box.
  • LP-NAS: LP-NAS formulates a linear program from lower-level Hessian information and upper-level validation gradients to compute architecture descent directions within the lower-level optimal valley.The method is designed to improve validation performance while preserving model optimality.
  • LP-NAS: LP-NAS maintains lower-level optimality while jointly updating architecture and model parameters, enabling convergence toward parameters with superior validation or test performance.This behavior contrasts with updates that may reach a lower-level local maximum or a nonoptimal bilevel architecture.
  • Efficient variants: S-LP-NAS and R-LP-NAS are computationally efficient variants that accelerate convergence and improve validation performance during early architecture-search stages.The variants differ in their model-parameter selection strategies.
  • Empirical validation: LP-DARTS consistently outperforms standard DARTS during architecture search and evaluation on CIFAR-10 and CIFAR-100, while comparisons with P-DARTS, PC-DARTS, and STO-DARTS and ImageNet experiments assess effectiveness and transferability.LP-DARTS is LP-NAS applied to the DARTS search space.

2 Preliminaries

This section introduces approximate hypergradients for bilevel NAS and develops an LP-based descent direction that improves validation performance while preserving lower-level optimality. It also states propositions guaranteeing parameter optimality preservation and non-decreasing validation performance under the HLS update.

  • Hypergradient-Based Bilevel Optimization: The hypergradient is the validation-loss gradient with respect to architecture parameters, accounting for model weights after one training-loss descent step.Setting ξ = 0 gives a first-order approximation; ξ ≠ 0 adds a second-order mixed-Hessian correction.
  • LP-Based Descent Direction: Solving the LP produces an upper-level descent direction that maintains lower-level optimality conditions during simultaneous architecture and weight updates.The LP constraints enforce orthogonality to the relevant Hessian structure, so infinitesimal movement along the direction preserves lower-level optimality.
  • Theoretical Guarantees: Proposition 2.1 guarantees that initially lower-level-optimal model parameters remain optimal after the proposed HLS update.The guarantee assumes the model parameters are initially optimal for the given architecture parameters.
  • Theoretical Guarantees: Proposition 2.2 states that HLS improves validation performance in most cases and leaves it unchanged in the worst case.The LP’s optimal objective value is always ≤0, and positive step sizes move along a validation-improving direction.

3 Methodology

LP-NAS applies a linear-programming descent update to continuous differentiable search spaces while alternating architecture and model-parameter optimization. To make this practical for deep networks, it uses reduced Hessians with either specific or random parameter selection and has polynomial computational scaling.

  • Continuous search space: LP-NAS requires continuous hyperparameters, which differentiable search spaces such as DARTS obtain by SoftMax-relaxing categorical operation choices.This continuous relaxation enables the LP to perform efficient hyperlocal architecture search.
  • LP-NAS algorithm: Each LP-NAS iteration approximates the Hessian, computes validation gradients, solves an LP for a descent direction, updates architecture and model parameters, and reoptimizes model weights.The lower-level optimization uses a warm start from the updated parameters, and the final architecture is derived from learned architecture parameters.
  • Reduced Hessian: LP-NAS reduces memory and computation by retaining all p architecture parameters but using only κq selected model parameters, where κ ≪1, to construct the reduced LP.The validation gradient is restricted to the same selected model parameters, preserving essential second-order information while avoiding the full model Hessian.
  • Parameter-selection strategies: S-LP-NAS deterministically selects the model-parameter tensor with the largest Gradient Norm Per Parameter, using every parameter in that tensor for reduced-Hessian computation.GNPP is based on the normalized magnitude of the training-loss gradient.
  • Parameter-selection strategies: R-LP-NAS randomly selects one or more parameter tensors within a predefined reduced-Hessian size limit, varying tensors across iterations to diversify update opportunities.The strategy uses all parameters belonging to the selected tensors.
  • Computational complexity: The method scales quadratically with the number of optimization variables and linearly with effective data processed per iteration, with LP solving and lower-level training as dominant costs.All components are polynomial in problem size and involve no exponential or combinatorial operations.

4 Experimental Results

Experiments on CIFAR-10 and CIFAR-100 show that LP-DARTS variants converge faster and outperform standard DARTS during architecture search and evaluation. Under time-constrained transfer experiments, LP-DARTS also performs competitively on ImageNet, while its LP-based bilevel updates preserve lower-level training optimality.

  • Architecture search: LP-DARTS was compared with DARTS through three random-seed runs on CIFAR-10 and CIFAR-100, tracking validation accuracy, loss, and runtime during architecture search.The experiments used CNN classifiers and recorded mean and standard deviation for validation accuracy and runtime.
  • Architecture search: Both LP-DARTS variants achieved faster convergence and higher validation performance than DARTS during the early architecture-search iterations.The performance trends were illustrated in Figure 2, with summarized results reported in Table 1.
  • CIFAR evaluation: Architectures searched by both LP-DARTS variants significantly outperformed DARTS in overall evaluation results and used fewer parameters.The searched cells were evaluated by constructing larger models and training them on the full CIFAR datasets.
  • CIFAR evaluation: Neither LP-DARTS variant showed definitive overall superiority, although S-LP-DARTS produced better best architectures than R-LP-DARTS on both datasets.The overall comparison is reported separately from the best-architecture results.
  • ImageNet transferability: LP-DARTS achieved superior CIFAR-10 performance to several DARTS variants under time-constrained settings and remained competitive when the architectures were transferred to ImageNet.DARTS and LP-DARTS used a controlled comparable CPU search budget, with architectures selected before full convergence.
  • Optimization mechanism: The LP formulation jointly updates architecture variables and network weights while explicitly enforcing lower-level optimality at each architecture update.This mechanism captures the coupling between the upper-level validation objective and lower-level training problem.

5 Conclusion · Appendix

LP-NAS performs architecture search within a bilevel framework by solving an LP each iteration for a validation-loss descent direction while preserving training-loss optimality. Reduced Hessian and LP formulations address computational challenges, and experiments report stronger results than DARTS and several variants.

  • 5 Conclusion: LP-NAS performs architecture search within the bilevel optimization framework.The method solves an LP at each iteration to obtain an architecture descent direction.
  • 5 Conclusion: Each iteration solves an LP that descends validation loss while keeping training loss optimal.The LP computes the descent direction under the training-loss optimality requirement.
  • 5 Conclusion: Applied to CNNs in DSS, LP-NAS discovers cell architectures with superior performance to DARTS.The conclusion reports that LP-NAS surpasses DARTS in the DSS search space.
  • 5 Conclusion: LP-NAS also outperforms several DARTS variants in time-constrained experiments.The supplied passage states this comparative result without specifying the variants or numerical values.
  • 5 Conclusion: Computational challenges center on Hessian calculation and LP solving.These are identified as key challenges for LP-NAS.
  • Appendix: Reduced Hessians, L-BFGS approximation, and reduced LPs address LP-NAS’s computational challenges.The method uses limited second-order information from the lower-level problem.
  • Appendix: Limited lower-level second-order information still yields better losses and accuracies than standard DARTS across the experiments.The passage attributes this result to the method quickly leading to improved losses and accuracies.

A DARTS

DARTS introduced an efficient, competitive NAS approach in a continuous search space, prompting extensions that improve computational efficiency, stability, and architecture search. Its collapse phenomenon, caused by overfitting and excessive skip-connects, motivated early stopping in DARTS+.

  • A DARTS: DARTS provides a highly efficient and competitive NAS approach operating in a continuous search space.It was introduced as an alternative to reinforcement-learning- and evolutionary-computation-based methods.
  • A DARTS: P-DARTS improves DARTS through search-space approximation and regularization techniques that address computational challenges and enhance search stability.Att-DARTS extends the framework by incorporating attention modules into the architecture search process.
  • A DARTS: DARTS can collapse through excessive skip-connects over many search epochs because of one-shot-model overfitting, diminishing performance.DARTS+ addresses this challenge with early stopping when two or more skip-connects appear in a normal cell.

B LP for HLS

The section derives an LP-based architecture direction by combining a validation-loss descent condition with preservation of lower-level training-loss optimality. Under differentiability and existence assumptions, the resulting SOCP is relaxed into a usable LP.

  • Assumptions: The derivation assumes a lower-level solution exists for every hyperparameter set, with validation loss once differentiable and training loss twice differentiable.
  • Validation-loss descent: A direction improves validation loss precisely when its inner product with the upper-level validation-loss gradient is negative.The direction uses components [dA, dW]ᵀ and a positive step-size t.
  • Lower-level optimality: The architecture direction must preserve lower-level optimality as hyperparameters change, requiring dW to minimize training loss for the selected dA.
  • Quadratic approximation: A quadratic training-loss approximation uses the Hessian with respect to hyperparameters and model parameters; at lower-level optimality, the linear terms vanish.The resulting unconstrained problem yields first-order optimality conditions by differentiating with respect to dW.
  • Optimization formulation: The steepest unit descent direction subject to lower-level optimality is formulated as an SOCP and relaxed into a usable LP.

C Proof of Proposition 1

The proof rewrites the LP constraints and Taylor expansion through relationships between dA, dW, and Hessian blocks. It then uses a Schur-complement argument to show the updated Hessian is positive semidefinite, confining the HLS to the lower-level optimality region.

  • The proof begins by expressing the LP’s affine constraints using the cited equations.
  • Writing dW in terms of dA and Hessian matrices enables the subsequent reformulation of the Taylor expansion.
  • Assuming the pseudo-inverse of H21, the proof expresses dA in terms of dW before substituting it into the Taylor expansion.
  • The updated second-order gradient yields a new Hessian whose relevant block is characterized through the Schur complement of H22.
  • If the original Hessian is positive semidefinite, the Schur complement argument confirms that the new Hessian H′′ is also positive semidefinite.
  • The positive semidefiniteness of H′′ establishes that the HLS is confined to the lower-level optimality region.

D Proof of Proposition 2 · E Reduced Hessian Formulation for Memory and Computational Efficiency · F Mathematical Formulation of Model Parameter Selection

The proof establishes a non-positive optimal LP objective, so the validation performance improves in most cases and never worsens in the worst case. Reduced Hessian computation addresses prohibitive full-Hessian costs through parameter subsampling, L-BFGS approximation, and specific or random tensor selection strategies.

  • D Proof of Proposition 2: Consequently, the validation performance improves in most cases and remains unchanged in the worst case.This follows from the non-positive optimal objective value in the minimization problem.
  • D Proof of Proposition 2: The zero direction (d_A, d_W) = (0, 0) satisfies the LP’s affine and box constraints and provides a feasible reference solution.Evaluating the objective at this feasible point establishes the non-positive optimal objective bound.
  • E Reduced Hessian Formulation for Memory and Computational Efficiency: Because p ≪ q and q can reach millions or billions, the complete training-loss Hessian creates a major computational challenge.The full Hessian has dimension (p + q) × (p + q), although the LP requires only a q × (p + q) submatrix.
  • E Reduced Hessian Formulation for Memory and Computational Efficiency: Nearly 29.8 TB of double-precision memory is required for the Hessian of a model with approximately two million parameters, while explicit computation has O(n^2) complexity.These costs make explicit Hessian computation prohibitively expensive for modern deep neural networks.
  • E Reduced Hessian Formulation for Memory and Computational Efficiency: The reduced formulation retains all p architecture parameters and only κq model parameters, then uses reduced Hessian and validation-gradient quantities to construct an efficient reduced LP.This approach uses partial second-order information from the lower-level problem.
  • E Reduced Hessian Formulation for Memory and Computational Efficiency: L-BFGS approximates the reduced Hessian with O(mn) computation per iteration, reducing memory and computational time.Here, m is the number of stored correction pairs and n is the parameter dimension.
  • F Mathematical Formulation of Model Parameter Selection: Specific parameter selection computes Gradient Norm Per Parameter from training-loss gradients and favors tensors with large gradients and relatively small sizes.The selected tensor count is constrained by the reduced-Hessian parameter budget.
  • F Mathematical Formulation of Model Parameter Selection: Random parameter selection uniformly samples valid candidate tensors under a prescribed size constraint, varying selections across iterations to diversify Hessian approximations.This provides update opportunities for different regions of the network.

G Time Complexity

LP-NAS’s outer-iteration cost combines Hessian approximation, gradient and parameter updates, LP solving, and lower-level weight optimization. In the reported setting, the quadratic LP-solve term dominates the linear mn term, yielding an overall quadratic simplification.

  • Hessian approximation with L-BFGS costs O(mn), while validation-gradient computation and parameter updates cost O(n).
  • The LP uses n variables, κq equality constraints, and p box constraints; although generic solvers have O(n3) worst-case complexity, empirical solve time is approximately O(n2).The lower practical cost is attributed to small κ and a structured constraint matrix dominated by linear orthogonality constraints.
  • Lower-level weight optimization processes ED samples with batch size B, contributing the stated ED-dependent cost.
  • Across kmax outer iterations, the listed complexity terms are mn + n + n2 + ED.
  • Because m ≪n, with m ≈15 and n ≈103 in the experiments, mn is dominated by n2 and overall complexity simplifies accordingly.

H Optimal Normal and Reduction Cells

The paper presents the optimal normal and reduction cells discovered by NAS methods for CIFAR-10 and CIFAR-100. These architectures are shown in Figures 4 and 5, respectively.

  • H Optimal Normal and Reduction Cells: Optimal normal and reduction cells for CIFAR-10 and CIFAR-100 are presented as the architectures discovered by the NAS methods.The paper directs readers to Figures 4 and 5 for these cells, respectively.
  • H Optimal Normal and Reduction Cells: Figure 5 shows the optimal normal and reduction cells searched on the CIFAR-100 dataset.The figure caption identifies these as the CIFAR-100 search results.
  • H Optimal Normal and Reduction Cells: Figure 4 shows the optimal normal and reduction cells searched on the CIFAR-10 dataset.The figure caption identifies these as the CIFAR-10 search results.

I Comparative Results

The section compares representative NAS methods using accuracy, parameter efficiency, and computational requirements across CIFAR-10 and ImageNet benchmarks.

  • Comparative performance: The comparative analysis considers accuracy, parameter efficiency, and computational requirements.These criteria are presented as a unified perspective on NAS performance.
  • Comparative performance: The comparison consolidates performance trends among representative NAS methods on CIFAR-10 and ImageNet.The section frames these benchmarks as part of NAS evaluation across established datasets.
Loading 2608.14472v1…