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

Hongyang Zhang, Junru Shao, Ruslan SalakhutdinovAISTATS 2019 · OpenReview

Abstract

Modern neural network architectures like ResNeXt, Inception, and Wide ResNet rely on multi-branch designs to achieve state-of-the-art performance. This paper provides a theoretical foundation for their success, demonstrating that increasing the number of branches makes the optimization landscape "intrinsically less non-convex." By employing the duality gap as a metric and leveraging the Shapley-Folkman Lemma, the authors prove that multi-branching effectively "convexifies" the loss surface, leading to a zero duality gap in deep linear networks and a rapidly shrinking gap in non-linear ones.

Introduction

Training deep neural networks is fundamentally a non-convex optimization challenge. While local search algorithms like stochastic gradient descent (SGD) are effective in practice, the presence of local minima and saddle points often complicates the search for a global optimum. Recent architectural trends have moved toward "wider" networks with multiple parallel paths, or branches. This paper investigates whether this specific design choice fundamentally alters the difficulty of the optimization problem, asking if branching changes the "degree of non-convexity" of the loss surface.

The Multi-Branch Architecture

The core idea analyzed is a network that splits into $I$ parallel sub-networks before merging at an output layer. This structure is common in modern architectures but its optimization properties were previously poorly understood.

Diagram of a multi-branch neural network architecture.

The authors analyze this structure using the duality gap—the difference between the solution to a primal (original) non-convex problem and its dual (convex relaxation). In optimization theory, a smaller duality gap indicates a problem that is "closer" to being convex and thus more amenable to standard optimization techniques.

Theoretical Framework: The Shapley-Folkman Lemma

The researchers utilize the Shapley-Folkman Lemma, a geometric result stating that the Minkowski sum of many non-convex sets tends toward convexity. The authors apply this to the "augmented epigraph" of the network's loss function. By treating the output of each branch as a component of a sum, they show that as the number of branches $I$ grows, the "non-convexity" of individual branches is effectively "averaged out."

For non-linear networks using a $\tau$-hinge loss, the authors prove that the normalized duality gap decreases at a rate of $2/I$. Remarkably, for deep linear networks of arbitrary depth with specific regularization, they establish strong duality, meaning the duality gap is exactly zero. This is a rare property in non-convex optimization and suggests that for certain architectures, the non-convex training problem can be mapped directly to an equivalent convex one.

Empirical Results and Landscape Visualization

The theoretical predictions are supported by empirical visualizations of the loss landscape. As the number of branches $I$ increases, the surface transforms from a jagged, multi-modal landscape into a smooth, bowl-shaped convex-like surface.

Loss landscape visualizations for varying numbers of branches (I).

Experiments on synthetic and real-world datasets (MNIST, CIFAR-10) confirm that this "convexification" leads to higher optimization success rates. For instance, in experiments on synthetic data, increasing the number of hidden neurons (effectively widening the branches) increased the "hitting rate"—the frequency of SGD finding the global minimum—from 21% to 75%.

Conclusion and Limitations

This work offers a rigorous explanation for the efficacy of multi-branch architectures. By quantifying non-convexity through the duality gap, it shows that branching serves as a powerful "convexifier."

However, some limitations remain. The proof for non-linear networks requires a margin parameter $\tau$ to be sufficiently large. Additionally, while the paper explains why these networks are easier to train, it does not directly address how this convexification affects generalization to new data. Future research may extend these proofs to more standard losses like cross-entropy and further explore the relationship between optimization ease and final model accuracy.

Summary updated

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 demo...
BibTeX
@inproceedings{zhang2019deep,
  author = {Hongyang Zhang and Junru Shao and Ruslan Salakhutdinov},
  title = {{Deep Neural Networks with Multi-Branch Architectures Are Intrinsically Less Non-Convex}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=CSj1wIjdaI},
}
Figure