# Generalization Properties of NAS under Activation and Skip Connection Search

arXiv: https://arxiv.org/abs/2209.07238 · HTML: https://mlsanity.com/paper/2209.07238/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 52 of its 87 references that are in the map.
- First posted on arXiv 15 Sep 2022.

## Builds on (most cited first, 30 of 52)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks](https://mlsanity.com/paper/1905.11946/) (2019)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [Learning Transferable Architectures for Scalable Image Recognition](https://mlsanity.com/paper/1707.07012/) (2017)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [FBNet: Hardware-Aware Efficient ConvNet Design via Differentiable Neural Architecture Search](https://mlsanity.com/paper/1812.03443/) (2018)
- [NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search](https://mlsanity.com/paper/2001.00326/) (2020)
- [A Downsampled Variant of ImageNet as an Alternative to the CIFAR datasets](https://mlsanity.com/paper/1707.08819/) (2017)
- [NAS-Bench-101: Towards Reproducible Neural Architecture Search](https://mlsanity.com/paper/1902.09635/) (2019)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [PC-DARTS: Partial Channel Connections for Memory-Efficient Architecture Search](https://mlsanity.com/paper/1907.05737/) (2019)
- [Auto-DeepLab: Hierarchical Neural Architecture Search for Semantic Image Segmentation](https://mlsanity.com/paper/1901.02985/) (2019)
- [Random Search and Reproducibility for Neural Architecture Search](https://mlsanity.com/paper/1902.07638/) (2019)
- [A Comprehensive Survey of Neural Architecture Search: Challenges and Solutions](https://mlsanity.com/paper/2006.02903/) (2020)
- [Neural Architecture Search without Training](https://mlsanity.com/paper/2006.04647/) (2020)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [Hierarchical Representations for Efficient Architecture Search](https://mlsanity.com/paper/1711.00436/) (2017)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective](https://mlsanity.com/paper/2102.11535/) (2021)
- [NATS-Bench: Benchmarking NAS Algorithms for Architecture Topology and Size](https://mlsanity.com/paper/2009.00437/) (2020)

## Built on by (most cited first, 14 of 14)

- [On the Convergence of Encoder-only Shallow Transformers](https://mlsanity.com/paper/2311.01575/) (2023)
- [Benign Overfitting in Deep Neural Networks under Lazy Training](https://mlsanity.com/paper/2305.19377/) (2023)
- [Hadamard product in deep learning: Introduction, Advances and Challenges](https://mlsanity.com/paper/2504.13112/) (2025)
- [Robust NAS under adversarial training: benchmark, theory, and beyond](https://mlsanity.com/paper/2403.13134/) (2024)
- [LayerNAS: Neural Architecture Search in Polynomial Complexity](https://mlsanity.com/paper/2304.11517/) (2023)
- [On the Generalization Capability of Temporal Graph Learning Algorithms: Theoretical Insights and a Simpler Method](https://mlsanity.com/paper/2402.16387/) (2024)
- [Generalization of Scaled Deep ResNets in the Mean-Field Regime](https://mlsanity.com/paper/2403.09889/) (2024)
- [The effect of Leaky ReLUs on the training and generalization of overparameterized networks](https://mlsanity.com/paper/2402.11942/) (2024)
- [DiffoRA: Enabling Parameter-Efficient Fine-Tuning via Differential Module Selection](https://mlsanity.com/paper/2502.08905/) (2025)
- [Dextr: Zero-Shot Neural Architecture Search with Singular Value Decomposition and Extrinsic Curvature](https://mlsanity.com/paper/2508.12977/) (2025)
- [Neural Tangent Kernels Motivate Graph Neural Networks with Cross-Covariance Graphs](https://mlsanity.com/paper/2310.10791/) (2023)
- [ActNAS : Generating Efficient YOLO Models using Activation NAS](https://mlsanity.com/paper/2410.10887/) (2024)
- [Is Supervised Learning Really That Different from Unsupervised?](https://mlsanity.com/paper/2505.11006/) (2025)
- [Zero-shot Quantum Neural Architecture Search](https://mlsanity.com/paper/2605.27410/) (2026)

## Abstract (arXiv)

Neural Architecture Search (NAS) has fostered the automatic discovery of state-of-the-art neural architectures. Despite the progress achieved with NAS, so far there is little attention to theoretical guarantees on NAS. In this work, we study the generalization properties of NAS under a unifying framework enabling (deep) layer skip connection search and activation function search. To this end, we derive the lower (and upper) bounds of the minimum eigenvalue of the Neural Tangent Kernel (NTK) under the (in)finite-width regime using a certain search space including mixed activation functions, fully connected, and residual neural networks. We use the minimum eigenvalue to establish generalization error bounds of NAS in the stochastic gradient descent training. Importantly, we theoretically and experimentally show how the derived results can guide NAS to select the top-performing architectures, even in the case without training, leading to a train-free algorithm based on our theory. Accordingly, our numerical validation shed light on the design of computationally efficient methods for NAS. Our analysis is non-trivial due to the coupling of various architectures and activation functions under the unifying framework and has its own interest in providing the lower bound of the minimum eigenvalue of NTK in deep learning theory.