Titolo della tesi: Pruning by Optimization: Selecting Optimal Sub-Networks in Neural Architecture Search
Neural Architecture Search (NAS) automates neural network design by formulating it as an op- timization problem over a space of candidate architectures. Among NAS methods, Differentiable Architecture Search (DARTS) has become a reference framework. It represents the search space as a Directed Acyclic Graph (DAG) whose edges carry candidate operators, and assigns to each edge a scalar architecture weight that quantifies the relevance of its operator in the network. All candidate architectures are then encoded into a single over-parameterised super-network in which network weights and architecture parameters are trained jointly via block gradient descent. Once trained, a discrete sub-network is extracted by retaining, in each group of parallel edges, only the operator whose architecture parameter is the largest. While the training phase has received exten- sive attention, this final pruning step, despite fully determining the deployed architecture, is still performed by a greedy magnitude-based heuristic that ignores cross-edge dependencies, provides no control over the topology or efficiency of the extracted model, and offers no mechanism to address the well-known performance collapse induced by non-parametric operators. This thesis develops a combinatorial-optimisation approach to sub-network extraction. The pruning step is reformulated as a Binary Quadratic Programming (BQP) problem over binary node and edge selection variables, with a second-order Taylor expansion of the validation loss as the objective and a family of linear constraints encoding connectivity, edge cardinality, and hardware-aware bounds on Floating Point Operations per Second (FLOPS), memory, and parameters. The quadratic term is handled through standard Hessian-approximation techniques to keep the formulation tractable on realistic search spaces. Under additional structural assumptions, the problem reduces to a Con- vex Quadratic Shortest Path Problem (QSPP) on a DAG, for which a custom branch-and-bound algorithm is developed and implemented in the zcqsp library. The full pipeline is implemented in hephaestus, a task-agnostic NAS framework that accepts any search space expressible as a multi- DAG, any operator set, and any input modality. The proposed approach is validated on two standard image classification benchmarks and a real- world robotics application. On CIFAR-10, the pruned sub-networks match the test accuracy of magnitude-based DARTS with less than half the parameters, and outperform it at comparable model size. On Tiny ImageNet, the gap is more pronounced, with the BQP-pruned networks out- performing DARTS by a wide margin at all parameter budgets considered. On synthetic instances of the Convex QSPP, the custom branch-and-bound is faster than both leading commercial and open-source solvers across all problem sizes considered, while attaining the same solution quality. Finally, the framework is applied to person detection from 2D Light Detection and Ranging (LiDAR) scans in the context of the REXASI-PRO autonomous wheelchair project, demonstrating that the approach generalises beyond image classification to a different task, without any modification to the pipeline.