Deep Neural Networks with Multi-Branch Architectures Are Less Non-Convex

Abstract

Several recently proposed architectures of neural networks such as ResNeXt, Inception, Xception, SqueezeNet and Wide ResNet are based on the designing idea of having multiple branches and have demonstrated improved performance in many applications. We show that one cause for such success is due to the fact that the multi-branch architecture is less non-convex in terms of duality gap. The duality gap measures the degree of intrinsic non-convexity of an optimization problem: smaller gap in relative value implies lower degree of intrinsic non-convexity. The challenge is to quantitatively measure the duality gap of highly non-convex problems such as deep neural networks. In this work, we provide strong guarantees of this quantity for two classes of network architectures. For the neural networks with arbitrary activation functions, multi-branch architecture and a variant of hinge loss, we show that the duality gap of both population and empirical risks shrinks to zero as the number of branches increases. This result sheds light on better understanding the power of over-parametrization where increasing the network width tends to make the loss surface less non-convex. For the neural networks with linear activation function and ${\ell }_2$ loss, we show that the duality gap of empirical risk is zero. Our two results work for arbitrary depths and adversarial data, while the analytical techniques might be of independent interest to non-convex optimization more broadly. Experiments on both synthetic and real-world datasets validate our results.

arXiv comment26 pages, 6 figures, 3 tables; v2 fixes some typos. arXiv admin note: text overlap with arXiv:1712.08559 by other authors

References in corpus (26)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <0.5MB model size
• Wide Residual Networks
• Understanding deep learning requires rethinking generalization
• Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
• The Loss Surfaces of Multilayer Networks
• Visualizing the Loss Landscape of Neural Nets
• Residual Networks Behave Like Ensembles of Relatively Shallow Networks
• Shake-Shake regularization
• How to Escape Saddle Points Efficiently
• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
• Path-SGD: Path-Normalized Optimization in Deep Neural Networks
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• Learning One-hidden-layer Neural Networks with Landscape Design
• Efficient approaches for escaping higher order saddle points in non-convex optimization
• Mathematics of Deep Learning
• Depth Creates No Bad Local Minima
• Diverse Neural Network Learns True Target Functions
• Failures of Gradient-Based Deep Learning
• Complex-Valued Autoencoders
• Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
• The Multilinear Structure of ReLU Networks
• An Approximate Shapley-Folkman Theorem

Cited by in corpus (7)

• Theoretically Principled Trade-off between Robustness and Accuracy
• On the loss landscape of a class of deep neural networks with no bad local valleys
• Elimination of All Bad Local Minima in Deep Learning
• Stackelberg GAN: Towards Provable Minimax Equilibrium via Multi-Generator Architectures
• On Connected Sublevel Sets in Deep Learning
• McKernel: A Library for Approximate Kernel Expansions in Log-linear Time
• Towards Lightweight Controllable Audio Synthesis with Conditional Implicit Neural Representations