Spurious Local Minima Provably Exist for Deep CNNs: Theory and Application

In this article, we prove that a general family of spurious local minima exist in the loss landscape of deep convolutional neural networks (CNNs) with strictly convex loss functions and ReLU activations. Our construction of spurious local minima is general and applies to CNNs with arbitrary architectures. We construct a local minimum $\theta $ at first, and then construct another point $\theta ^{\prime } $ in parameter space with the same empirical risk as $\theta $ . Data samples are split into some groups such that each group behaves differently under the perturbation around $\theta ^{\prime } $ to produce a lower empirical risk. We tackle the challenges caused by convolutional layers in the construction. We show that a differentiation of data samples is always possible somewhere in the feature maps, and despite network parameters being tied in each feature map, our perturbation scheme only affects the output of a single or a few neurons for a group of data samples. We then give an example of nontrivial spurious local minimum in which multiple activation patterns are explicitly constructed. Finally, based on our construction of spurious local minima, we design a deterministic optimization method to escape local minima that is applicable to CNNs, ResNets, MLPs, and transformers. Experimental results on CIFAR-10, CIFAR-100, and ImageNet-1k datasets verify our theoretical findings and show that our optimization method outperforms SGD or Adam in accuracy (by 0.27% on average) consistently on all these architectures and datasets.