Neural Networks Should Be Wide Enough to Learn Disconnected Decision Regions

Quynh Nguyen, Mahesh Chandra Mukkamala, Matthias Hein

Abstract

In the recent literature the important role of depth in deep learning has been emphasized. In this paper we argue that sufficient width of a feedforward network is equally important by answering the simple question under which conditions the decision regions of a neural network are connected. It turns out that for a class of activation functions including leaky ReLU, neural networks having a pyramidal structure, that is no layer has more hidden units than the input dimension, produce necessarily connected decision regions. This implies that a sufficiently wide hidden layer is necessary to guarantee that the network can produce disconnected decision regions. We discuss the implications of this result for the construction of neural networks, in particular the relation to the problem of adversarial manipulation of classifiers.

Introduction

While deep learning research often focuses on the benefits of depth for expressive power, this paper demonstrates that width is equally critical for a network's topological flexibility. A fundamental requirement for many classification tasks is the ability to separate a single class into multiple disconnected "islands" in the input space—for instance, when a single category like "dogs" exists in several distinct clusters. We investigate the architectural conditions under which a neural network is topologically constrained to produce only connected decision regions, a limitation that can severely hamper generalization and increase vulnerability to adversarial attacks.

Theoretical Framework: The Pyramidal Constraint

The core of our analysis focuses on "pyramidal" networks, defined as feedforward architectures where the width of every hidden layer $n_i$ is less than or equal to the input dimension $d$.

We examine activation functions that are continuous and strictly monotonically increasing, such as Leaky ReLU, ELU, Softplus, and Sigmoid. The central result, Theorem 3.10, proves that for pyramidal networks using these activations, every decision region must be an open connected set.

Illustration of the pre-image mapping $f^{-1}(S)$ showing how connectivity is preserved through narrow layers.

The proof utilizes the concept of pre-images to show that if one starts with a connected region at the output layer and moves backward through layers that are no wider than the input, the connectivity of that region cannot be "broken." Essentially, narrow layers act as continuous deformations that lack the "room" to snip or tear regions apart.

Empirical Evidence: 2D Toy Datasets and MNIST

To illustrate these constraints, we employed synthetic 2D datasets and modified MNIST tasks.

2D Toy Datasets

In binary classification tasks in $\mathbb{R}^2$ where one class is split into two disconnected clusters, we observed a sharp performance threshold. A network with width $n_1=2$ (equal to the input dimension $d=2$) was mathematically forced to produce connected regions, often resulting in a simple linear-like separator that failed to capture the data's multi-modal nature. However, adding just one more neuron ($n_1=3$, or $d+1$) provided the necessary topological freedom to perfectly separate the disconnected clusters.

A 2D binary classification task (left) and the resulting decision regions (right). Narrow networks are constrained by the topology of the input space.

Rotated MNIST

We further validated this on a high-dimensional task using rotated MNIST digits. By selecting specific rotation ranges, we created a dataset where a single class is physically disconnected in pixel space. Narrow networks (width $\le 784$) were forced to create a "bridge" of high-confidence predictions between these separate clusters. These bridges often contain images that look like other classes (e.g., a "4") but are classified with 99% confidence as the target class (e.g., a "1"), highlighting a significant source of adversarial vulnerability.

Key Insights

  • The $d+1$ Threshold: The results are "tight"; while width $d$ is restrictive, width $d+1$ is often sufficient to break connectivity constraints.
  • Activation Nuance: Standard ReLU can sometimes bypass these constraints because its "flat" region ($x < 0$) allows it to zero out parts of the space. However, Leaky ReLU, which avoids dead neurons, is strictly bound by the pyramidal constraint in narrow networks.
  • Adversarial Implications: Topological "stiffness" forces networks to build high-confidence bridges through regions of space that should belong to other classes, creating natural targets for adversarial manipulation.

Conclusion

This work establishes that sufficient width—specifically exceeding the input dimension—is a necessary condition for neural networks to learn complex, disconnected decision regions. While depth adds expressive power, width provides the topological "room" required to model multi-modal data distributions accurately and robustly. Future work remains to extend these deep network proofs to a broader range of bounded activation functions like Sigmoid and ELU.

Summary updated

Abstract

In the recent literature the important role of depth in deep learning has been emphasized. In this paper we argue that sufficient width of a feedforward network is equally important by answering the simple question under which conditions the decision regions of a neural network are connected. It turns out that for a class of activation functions including leaky ReLU, neural networks having a pyramidal structure, that is no layer has more hidden units than the input dimension, produce necessarily connected decision regions. This implies that a sufficiently wide hidden layer is necessary to guarantee that the network can produce disconnected decision regions. We discuss the implications of this result for the construction of neural networks, in particular the relation to the problem of adversarial manipulation of classifiers.
BibTeX
@inproceedings{nguyen2018neural,
  author = {Quynh Nguyen and Mahesh Chandra Mukkamala and Matthias Hein},
  title = {{Neural Networks Should Be Wide Enough to Learn Disconnected Decision Regions}},
  booktitle = {International Conference on Machine Learning},
  year = {2018},
  url = {https://openreview.net/forum?id=ryEmQh-uZS},
}
Figure