Department of Computer Science Fall 2023 Darrell Whitley Charles Anderson
Nikhil Krishnaswamy Michael Kirby Copyright by Timothy J. Whitaker 2023
All Rights Reserved

# Subnetwork Ensembles

Timothy J. Whitaker<EMAIL_ADDRESS>
###### Abstract

Neural network ensembles have been effectively used to improve generalization
by combining the predictions of multiple independently trained models.
However, the growing scale and complexity of deep neural networks have led to
these methods becoming prohibitively expensive and time consuming to
implement. Low-cost ensemble methods have become increasingly important as
they can alleviate the need to train multiple models from scratch while
retaining the generalization benefits that traditional ensemble learning
methods afford. This dissertation introduces and formalizes a low-cost
framework for constructing Subnetwork Ensembles, where a collection of child
networks are formed by sampling, perturbing, and optimizing subnetworks from a
trained parent model. We explore several distinct methodologies for generating
child networks and we evaluate their efficacy through a variety of ablation
studies and established benchmarks. Our findings reveal that this approach can
greatly improve training efficiency, parametric utilization, and
generalization performance while minimizing computational cost. Subnetwork
Ensembles offer a compelling framework for exploring how we can build better
systems by leveraging the unrealized potential of deep neural networks.

###### Acknowledgements.

I would like to start by thanking my advisor Dr. Darrell Whitley for his
mentorship and guidance. It’s been an honor and a privilege to work together
for the last several years. Thank you for taking a chance on me and for
pushing me to become a better research scientist. Thank you to the members of
my dissertation committee: Dr. Chuck Anderson, Dr. Nikhil Krishnaswamy, and
Dr. Michael Kirby. I am so grateful to have been able to learn from each of
you. Your classes have been an integral part of this research and I appreciate
the feedback, advice, and guidance that you’ve offered along the way. I am
appreciative of financial support from The Computer Science Department at
Colorado State University (Artificial Intelligence and Evolutionary
Computation Fellowship) and The National Science Foundation (Grant
IIS-1908866). I am thankful for my family and friends who have stood by me
throughout this journey. A special thanks to my mom and dad, Sandy and Brian,
for their unwavering support and unconditional love. I am eternally grateful
for the sacrifices you have made to give me the opportunity to be where I am
today. You’ve set an example for what one can accomplish with hard work,
determination and the courage to pursue your dreams. Shout out to my brother,
Dylan, and my best friend, Kyler, for always having my back. Thank you for
giving me perspective and focus when I needed it most. Thank you to my
extended family and in-laws for their encouragement and continued interest in
my work. It has meant a lot to know I have so many loved ones rooting for me.
Last but not least, my deepest gratitude is reserved for my wife, Alyssa. I
feel so blessed to have you in my life. You were the inspiration for taking on
this endeavor and you were the foundation upon which it was all built. You’ve
been there to celebrate my triumphs and you’ve been there to help me overcome
insurmountable challenges. You’ve been my constant source of strength and my
guiding light when all seemed dark. Thank you for always believing in me. I
could not have done this without you. Dedication DEDICATION For Alyssa
In this grand cosmic ensemble, it is my deepest joy to share this time and
space with you.

###### Contents

  1. 1 Introduction
    1. 1.1 Overview
    2. 1.2 Challenges
    3. 1.3 Contributions
  2. 2 Background
    1. 2.1 Neuroscience
    2. 2.2 Artificial Neural Networks
      1. 2.2.1 Optimization
      2. 2.2.2 Architecture
      3. 2.2.3 Subnetworks
    3. 2.3 Ensemble Learning
      1. 2.3.1 Low-Cost Ensemble Methods
  3. 3 Theoretical Framework
    1. 3.1 Introduction
    2. 3.2 Formalization
      1. 3.2.1 Subnetwork Sampling
      2. 3.2.2 Neural Partitioning
      3. 3.2.3 Perturbative Processes
      4. 3.2.4 Network Optimization
      5. 3.2.5 Ensemble Predictions
      6. 3.2.6 Evaluation Metrics
  4. 4 Noisy Subnetwork Ensembles
    1. 4.1 Introduction
    2. 4.2 Implementation
      1. 4.2.1 Trust-Region Search
      2. 4.2.2 Mirrored and Partitioned Noise
    3. 4.3 Experiments
      1. 4.3.1 Decision Boundaries
      2. 4.3.2 Ablations
      3. 4.3.3 Benchmarks
    4. 4.4 Discussion
  5. 5 Sparse Subnetwork Ensembles
    1. 5.1 Introduction
    2. 5.2 Implementation
    3. 5.3 Experiments
      1. 5.3.1 Ablations
      2. 5.3.2 Landscapes
      3. 5.3.3 Benchmarks
    4. 5.4 Discussion
  6. 6 Stochastic Subnetwork Ensembles
    1. 6.1 Introduction
    2. 6.2 Implementation
      1. 6.2.1 Random Annealing
      2. 6.2.2 Temperature Annealing
    3. 6.3 Experiments
      1. 6.3.1 Ablations
      2. 6.3.2 Benchmarks
    4. 6.4 Discussion
  7. 7 Diversity Analysis
    1. 7.1 Introduction
    2. 7.2 Output Diversity
      1. 7.2.1 Prediction Clusters
    3. 7.3 Interpretable Diversity
      1. 7.3.1 Perceptual Hashing
    4. 7.4 Experiments
    5. 7.5 Discussion
  8. 8 Conclusions
    1. 8.1 Summary
    2. 8.2 Discussion

###### List of Tables

  1. 2.1 A collection of popular activation functions used in neural networks. Logistic Sigmoids and Hyperbolic Tangents have long been the standard for shallow multilayer perceptrons thanks to their smooth differentiable qualities. Deep neural networks have primarily moved towards rectifiers as their unbounded nature helps preserve gradient flow over many layers.
  2. 2.2 A generalized overview of the benefits and drawbacks of various low-cost ensemble learning strategies. Specific methods within each category may differ significantly in regards to their strengths or weaknesses. All categories are relatively and subjectively graded according to the primary idea behind their cost reduction, where a dash represents baseline performance, a single checkmark corresponds to relatively good performance, and two checkmarks corresponds to best performance.
  3. 4.1 Results for sparse mutation ensembles on ImageNet with a wide variety of models. Mutation sparsity and strength are determined from a small hyperparameter grid search. Accuracy (Acc), Negative Log Likelihood (NLL), and expected calibration error (ECE) are reported for the parent and the ensemble. Metrics prepended with $e$ refer to ensemble results. $\Delta$Acc is the change in accuracy between the parent and the ensemble, $\sigma$ is the mutation strength, and $\overline{KL}$ is the average output divergence between the mutated models and the parent models. 16 models are generated and the 8 most accurate candidates on a validation set are used together as an ensemble.
  4. 4.2 Proximal Policy Optimization hyperparameters and evaluation results over 10 episodes.
  5. 5.1 Accuracy of various methods for the small training budget benchmark experiment. All ensembles contain 8 models and are trained for a total of 16 epochs. Dropout rate is 50%, Bootstrap Aggregation is trained on 90% subsets.
  6. 5.2 Results for ensembles of WideResNet-28-10 models on both CIFAR-10 and CIFAR-100. Methods with ∗ denote results obtained from [62, 107]. Best low-cost ensemble results are bold. cAcc, cNLL, and cECE correspond to corrupted test sets.
  7. 5.3 Results for Sparse Subnetwork Ensembles on CIFAR-10 with different child network partition sizes. The parent network is trained for 140 epochs. 6 children are then created through neural partitioning and each is trained for an additional 10 epochs. Total Params counts all parameters in the ensemble.
  8. 6.1 Comparison between various baseline approaches when used with random/magnitude pruning on CIFAR-100. We report the best accuracy for each method at various levels of target sparsity when tuned with both a constant learning rate and a one-cycle learning rate schedule. Our annealing strategies consistently outperform established one-shot and iterative pruning methods.
  9. 6.2 Results for ensembles of WideResNet-28-10 models on both CIFAR-10 and CIFAR-100. Methods with ∗ denote results obtained from [62, 107]. Best low-cost ensemble results are bold. cAcc, cNLL, and cECE correspond to corrupted test sets.
  10. 7.1 Average prediction disagreement ratio and KL divergence between ensemble members for several benchmark methods on CIFAR-10 with WideResNet-28x10. Results reported from [107, 62, 161]

###### List of Figures

  1. 2.1 A diagram of the McCulloch and Pitts computational model of a neuron used in the Perceptron. The neuron computes a weighted sum of the inputs and then passes the output through a binary step function for classification.
  2. 2.2 Visualizations of how convolutional layers operate on input images. Each convolutional filter in a layer scans over the input image according to a stride length. The middle image displays how a 7x7 filter with a stride of 7 applies to the input image. The right most image displays a 7x7 filter with overlap using a stride of 2.
  3. 3.1 A visualization of child networks formed through three distinct methodologies that we investigate in Chapters 4, 5, and 6. Noisy Subnetwork Ensembles perturb subnetworks with noise. Sparse Subnetwork Ensembles prune subnetworks from the parent. Stochastic Subnetwork Ensembles use probability scores to determine active parameters on every pass through the network.
  4. 4.1 Neuroevolution excels at fine tuning fully-trained networks that get stuck in flat loss basins. The left graph displays a typical SGD training trajectory where models tend to converge to the edges of flat optima [78]. The middle graph displays white dots as child networks that are generated from sparse mutations. The right graph shows the final ensemble consisting of top candidates selected from evaluation on a separate validation set. A key insight to the success of gradient-free methods for fine tuning is that the loss landscapes of test distributions rarely match the training distribution exactly. Ensembling over wide areas of good validation performance is key to improving generalization.
  5. 4.2 The images above detail decision boundaries for a trained three layer multilayer perceptron after being perturbed with various mutations. With dense perturbations, there is a comparatively small window between a functional decision boundary and complete performance collapse. As mutations become more sparse, the model is better able to retain its behavior while the strength of parameter mutation increases.
  6. 4.3 Results of mutation ablations for a trained WideResNet-28x10 model on CIFAR-10. Lines of different colors correspond to the percentage of sparsity for the mutations. The top left graph reports the average KL divergence as a result of mutation strength. The top right graph explores the relationship between KL divergence and accuracy. The bottom left reports the accuracy of an an ensemble evaluated with majority vote predictions. The bottom right reports accuracy of an ensemble evaluated with averaged predictions.
  7. 4.4 Training graphs on all 16 environments in the ProcGen benchmark. Orange lines correspond to single model evaluations and blue lines correspond to noisy subnetwork ensembles.
  8. 5.1 A diagram explaining network partitions in Sparse Subnetwork Ensembles. The parent network is optimized and settles into some optima. Child networks are created via neural partitioning. That is, two sparse children each inherit a different set of parameters from the parent. The optimization landscapes for each child are diverse, yet they converge quickly due to inheritance from a fully trained parent.
  9. 5.2 A convolutional parent network filter split into two partitioned child filters. The child networks learn diverse feature representations due to the geometric constraints of their unique topologies.
  10. 5.3 An example of the one-cycle learning rate and momentum schedule we use to fine-tune the child networks in Sparse Subnetwork Ensembles.
  11. 5.4 Ablations over pruning sparsity and structure for various model sizes. Each graph reports performance for an ensemble containing 8 models. The left figure reports the effect that pruning sparsity has on models of different sizes. The right figure displays the efficacy of neuron and connection pruning for LeNet-L.
  12. 5.5 Ablations exploring the effect of ensemble size and various ensemble pruning/tuning strategies. The left graph displays the results for ever increasing ensemble sizes spawned from a single parent network. The right figure contains results for various configurations of random pruning and neural partitioning with constant rate fine tuning and one-cycle fine tuning.
  13. 5.6 Exploring the early training efficiency of Sparse Subnetwork Ensembles with Mothernets and Dropout. The left figure compares Mothernets on the MNIST dataset with a multilayer perceptron. The right figure compares Dropout on CIFAR-10 with LeNet-L.
  14. 5.7 Visualizations of the loss landscapes of a ResNet-56 model as it undergoes pruning and tuning. The first column is the landscape of the fully trained parent model. The middle figure is the landscape of the model after removing 50% of the parameters. The final figure is the landscape of the pruned model after three additional epochs of fine tuning.
  15. 6.1 Ablations exploring how the initial temperature and the number of annealing epochs affect convergence behavior.
  16. 6.2 Ablations over the number of annealing epochs for random annealing vs temperature annealing and temperature annealing vs iterative pruning.
  17. 6.3 The rightmost graph displays the best performing annealing configuration for each sparsity and plots it against the one-shot pruning baseline. Stochastic annealing outperformed the other methods for each sparsity, with more drastic improvements appearing in extremely sparse networks.
  18. 7.1 Pairwise correlation heatmaps for ResNet-18 on CIFAR-10. (R/NP) denotes random pruning/neural partitioning. (BAG) denotes bootstrap aggregation.
  19. 7.2 T-SNE cluster representations of CIFAR-10 and WideResNet-28x10. The first row is the representation of classes in CIFAR-10 that each of our models produce. The second row displays the results of our model predictions and the final row displays the incorrect predictions.
  20. 7.3 Feature visualizations of a random selection of neurons in child networks from a Snapshot Ensemble and a Sparse Subnetwork Ensemble. Values reported are the mean hash distances between the two child networks over all 1024 visualizations in the final convolutional layer. Higher values represent greater distance and more diversity between representations. The sparsity from Subnetwork Ensembles results in more diverse feature representations than two subsequent checkpoints in Snapshot Ensembles.
  21. 7.4 Mean distances between Snapshot Ensemble and Sparse Subnetwork Ensemble saliency maps for all 50,000 samples in the ILSVRC2012 ImageNet validation set. The visualization includes SmoothGrad saliency maps for a shared parent network, two snapshot ensemble checkpoints, and two sparse subnetwork children. The visualization is an example of how saliency maps can be useful with ambiguous input as both snapshot checkpoints focus on the dog while the subnetworks split their attention between the dog and the cat. The diversity encouraged by sparse network structures help to reduce bias present in the parent network.

##  Chapter 1 Introduction

###  1.1 Overview

Ensemble Learning has long been an active area of research in machine learning
as it is one of the most reliable, powerful, and flexible techniques for
improving the predictive power of machine learning systems. [58, 89]. Rather
than training a single model to make predictions, ensemble methods instead
train several models and use them in combination with one another in order to
make predictions. Combining the outputs of several models allows for ensembles
to improve generalization by leveraging the complementary strengths and
weaknesses of its members [29]. The principles behind ensemble learning
algorithms are general and have been used with many types of parametric models
(e.g. decision trees, support vector machines, neural networks) [10, 33, 11].
Recent research has shown that ensembles of deep neural networks in particular
are especially effective, often being implemented as a part of winning
solutions in high profile machine learning competitions [118, 21, 182, 134,
77, 132, 40].

Improvements in network architecture and training methodologies have led to a
large increase in both model size and predictive power. Networks with billions
of parameters are becoming increasingly commonplace as overparameterization is
shown to be effective for improved training dynamics. However, the resource
intensive nature of these large models brings about important challenges
related to computational requirements, memory constraints, and energy
efficiency. As deep neural networks continue to grow in both scale and
complexity, the cost associated with traditional ensemble learning techniques
quickly becomes untenable. The development of low-cost ensemble methods have
become increasingly important as they offer the opportunity to significantly
reduce computational costs while retaining the generalization benefits that
full size ensembles afford.

Meanwhile, pruning has emerged as a critical avenue of research for reducing
the size of deep neural networks. Large numbers of parameters can be removed
from previously trained models with little discernible loss in predictive
power after a few epochs of continued training [6, 44]. Saliency metrics are
often used to select the most unnecessary parameters to remove in order to
produce the most accurate subnetwork [99, 149, 44]. However, there is no
single magic subnetwork that works best for every situation [166, 20]. A
sufficiently overparameterized network contains vast numbers of equally
capable subnetworks and even random sampling has been shown to result in
highly accurate subnetworks at moderate levels of sparsity [30, 108].

In light of these observations, we introduce a novel low-cost ensemble
learning framework that involves the dynamic generation of a collection of
child networks spawned through the random sampling of subnetworks in a trained
parent model. This research introduces and formalizes this process of
constructing Subnetwork Ensembles with the goal of exploring how we can
improve the training efficiency, parametric utilization, and generalization of
deep ensembles while minimizing computational cost.

###  1.2 Challenges

The benefits of improved generalization have been well established in ensemble
learning literature as performance has been shown to increase with larger
numbers of both accurate and diverse members [29]. Diversity is an important
concept that pertains to the correlation of predictions made by individual
models in an ensemble [13, 154, 92]. If each model in the ensemble makes the
same predictions or learns the same feature representations, then there is
little benefit to be gained by combining their outputs.

Traditional ensemble methods encouraged diversity by training large
collections of fast and simple classifiers on different subsets of the feature
space [10, 33, 67]. However, these dataset splitting techniques do not work
well with deep neural networks due to their data hungry nature. Deep neural
network ensembles are more commonly trained on the entire dataset, instead
relying on random weight initialization, heterogeneous network architectures
and stochastic ordering of training samples to encourage diversity.

Diversity is an especially important consideration for low-cost ensemble
learning methods as they typically alleviate the need to train multiple deep
neural networks from scratch by sharing network structure, gradient
information, or learned parameters among ensemble members. This sharing of
information invariably increases correlation and reduces diversity, which can
have a significant negative impact on generalization [13, 92, 154].

Low-Cost ensemble methods often struggle to balance this trade-off between
member diversity, member accuracy and ensemble size. Prioritizing one aspect
often comes at the expense of another when working with a fixed compute
budget. Low-cost methods can also lack algorithmic flexibility as they
typically require particular training procedures or specialized network
architectures to construct ensemble members [71, 51, 101, 159]. This can make
it challenging to adapt these ensembles to accommodate evolving problem
spaces.

Subnetwork Ensembles alleviate many of the challenges that typically plague
competing methods. Our approach builds on the idea that we can train a single
parent network and spawn diverse child networks by sampling, perturbing, and
optimizing unique subnetworks from the parent. The decoupled nature between
the parent and child networks allow for highly flexible implementations. The
parent network can use any standard training procedure or network architecture
without modification. This offers an opportunity to leverage pre-trained
models which is becoming more valuable as networks continue to scale in size
and cost. This also enables the ability to generate new child networks
dynamically, which can lead to larger and more robust ensembles than are
typically seen with deep neural networks. Child networks can be generated and
optimized in parallel which allows for wide scaling as independent members
don’t rely on the weights of other child networks in the ensemble. Using
sparse subnetworks allows for the potential to greatly reduce computational
complexity while maintaining accuracy. The investigation of Subnetwork
Ensembles could prove to be an important avenue of research for not only
improving the efficiency and generalization of low-cost ensemble methods, but
also for advancing the theoretical underpinnings of neural computation.

###  1.3 Contributions

This work introduces, generalizes and formalizes the process of constructing,
training, and evaluating Subnetwork Ensembles. We explore several approaches
for generating child networks through noise perturbations, network pruning,
and stochastic masking. We conduct a thorough and in depth evaluation of these
methods across a number of benchmark tasks and with a wide variety of deep
neural network architectures.

Chapter 2 introduces relevant background information and related work grounded
in the foundations of modern deep learning. We explore how this work relates
to the natural structures observed in biological neural networks. We discuss
the state of deep neural network architectures and optimization methods. We
also discuss traditional ensemble learning techniques and conduct a literature
review of recent low-cost deep neural network ensemble methods.

Chapter 3 introduces the theoretical framework and formalizes Subnetwork
Ensembling at a high level. We provide a mathematical overview of this
approach and discuss various hyperparameters that govern how Subnetwork
Ensembles could be formulated through different sampling, perturbation, and
optimization methodologies. We introduce Neural Partitioning as a novel
technique for encouraging diversity by dividing the parent network into
independent partitions such that sets of child networks are formed with no
inherited parameter overlap.

Chapter 4 introduces Noisy Subnetwork Ensembles, where child networks are
generated by applying noise perturbations to subnetworks. We connect the ideas
behind this approach to popular neuroevolutionary methods that use dense
mutations and model selection strategies to generate populations of child
networks. We conduct several ablation studies exploring the impact of noisy
subnetwork mutations on network behavior. We introduce a grid search algorithm
for finding good perturbation hyperparameters by using trust region
constraints, which limits divergence in the output space as a result of
perturbation [129]. We evaluate Noisy Subnetwork Ensembles with many different
deep neural network architectures on the difficult ImageNet dataset and we
explore how this technique can be used on difficult reinforcement learning
tasks with the ProcGen benchmark [28, 23].

Chapter 5 introduces Sparse Subnetwork Ensembles, where we generate child
networks by pruning randomly sampled subnetworks from the trained parent
network. We explore the efficacy of Neural Partitioning and demonstrate how it
can reduce variance and improve performance by creating sets of child networks
with opposing topologies. We illustrate how sparse child networks can be tuned
to encourage diversity by using a phasic learning rate schedule that uses
large learning rates to move child networks further apart in weight space
before converging to local optima with small learning rates [138, 70]. We
conduct several other ablations exploring the impact of pruning structure,
pruning severity, ensemble size, and tuning procedure. We benchmark Sparse
Subnetwork Ensembles against several state of the art low-cost and traditional
ensemble methods on both in-distribution and out-of-distribution datasets,
where we find that our approach proves to be more accurate and more robust
than traditional ensemble methods that require up to 4x more training compute,
all while using fewer parameters.

Chapter 6 introduces Stochastic Subnetwork Ensembles, which extends work in
the previous chapter with a novel approach to representing subnetworks with
probabilistic masks. Rather than pruning all the parameters in one-shot,
instead each parameter is assigned a probability score that determines whether
the connection will be retained on any forward pass. These probabilities are
then annealed over several epochs such that the target subnetwork slowly
reveals itself over time. Diversity is encouraged by assigning different
probability distributions to different child networks. The inclusion of extra
dimensionality in the early phases of tuning can help to provide smooth
optimization of the target subnetwork. This proves to be highly effective
technique for extremely sparse (98%) and moderately sparse (50%) subnetworks,
outperforming established one-shot and iterative pruning strategies.

Chapter 7 includes an in depth analysis of diversity in Sparse Subnetwork
Ensembles. We include a standard evaluation of pairwise output diversity
metrics and compare those to other benchmark ensemble algorithms. We
additionally introduce a new approach to analyzing diversity by leveraging
interpretability and visualization methods. We discuss how feature
visualization and saliency maps can be used to qualitatively compare the
differences between knowledge representations among sibling child networks in
an ensemble. This allows us to meaningfully explore how and why diversity
develops and contributes to robust performance. We introduce several
perceptual hashing algorithms used to measure the distances between feature
visualizations, improving on the typically noisy results seen with common
image difference metrics like the squared error or cosine similarity. We
conduct a large scale evaluation of this interpretable approach with both
Sparse Subnetwork Ensembles and a benchmark temporal ensemble method called
Snapshot Ensembles. We find that Sparse Subnetwork Ensembles produce
significantly more diversity in both the feature space and output space among
child networks while maintaining better accuracy.

Chapter 8 wraps up with a summary of the ideas, experiments, and observations
found through this research. We discuss of how the Subnetwork Ensemble
framework fits into the current landscape of ensemble methods for deep neural
networks. We include our thoughts on the broader impacts and potential
limitations that this work may have in other domains, and we explore several
promising avenues and ideas for furthering this research in the future.

##  Chapter 2 Background

###  2.1 Neuroscience

Biological neural networks are far larger and more complex than the artificial
neural networks used in machine learning research. Even the largest artificial
neural networks pale in comparison to the human brain, which is a vast and
complex web of interconnected subsystems containing over 86 billion neurons
and 100 trillion synaptic connections [32]. Individual neurons within this
framework tend to be very noisy, which makes it difficult to understand the
relation between neuronal activity and behavior. A new conceptual paradigm is
reframing how we view neuronal activity by instead exploring how groups of
structurally connected neurons form the functional building blocks of the
brain [15]. The organizational structure of these interconnected subsystems
appears to play an important role for both energy efficiency and the emergence
of complex, resilient, and adaptable learning behavior.

These structures emerge from an early process in brain development that
involves a massive proliferation of neurons and synaptic connections followed
by a widespread pruning of billions and trillions of those neurons and
connections respectively. Neuronal proliferation creates an environment in
which neurons and connections compete for resources. Neuronal apoptosis
results in widespread neural cell death, resulting in a highly specialized
structure consisting of many sparsely connected neuronal groups. These
neuronal groups form the primary repertoire from which the rest of brain
development occurs [36]. This overgrowth and subsequent pruning maximizes
memory performance under metabolic energy constraints [18]. Additionally, this
connective structure allows for information to be encoded in a sparse and
distributed manner which optimizes a tradeoff between energy expenditure and
expressivity [1, 54].

Several other important processes rely on the flexibility and resilience of
these sparse subnetwork structures to encourage healthy brain function [139].
Neuroplasticity serves as a fundamental mechanism for learning and memory that
relies on reorganizing synaptic connections in response to stimulus [26].
Long-term depression and long-term potentiation facilitate this process by
strengthening or weakening the synaptic connections between neurons [76, 152].
Sparse subnetwork structures also provide a protective framework for
mitigating the consequences of cellular damage or neurodegeneration. Synaptic
Stripping is one such process where immunocompetent cells called microglia
constantly scan the brain and selectively remove dysfunctional synapses from
injured neurons [82, 136]. This is critical for preventing cascading failures
that could result from synaptic dysfunction.

###  2.2 Artificial Neural Networks

The origins of artificial neural network research can be traced back to the
work of Warren McCulloch and Walter Pitts in 1943, who proposed a mathematical
model of a biological neuron based on the all-or-nothing character of nervous
activity [117]. This simplified computational model casts the neuron as a
binary threshold unit that computes a weighted sum of its inputs to produce an
output. Frank Rosenblatt later expanded on this work by developing the first
single layer artificial neural network, consisting of McCulloch and Pitts
neurons, called the Perceptron [125]. While the Perceptron was limited to
modeling simple linearly separable functions, it was groundbreaking work that
introduced adaptability to neural models through learning algorithms [115].

The transition to multilayer perceptrons greatly expanded the learning
capabilities of neural networks [68]. Networks would now be organized into
several successive layers, each consisting of multiple neurons with weighted
connections to neurons in adjacent layers. The output of a neuron is computed
by taking the weighted sum of all the inputs into the neuron and passing it
through some non-linear activation function. Table 2.1 includes a small sample
of some of the most popular activation functions used in neural networks over
time.

$x_{2}$$x_{1}$$x_{0}$⋮$x_{n}$$\sum$$w_{2}$$w_{1}$$w_{0}$⋮$w_{n}$inputsweightsactivation Figure 2.1: A diagram of the McCulloch and Pitts computational model of a neuron used in the Perceptron. The neuron computes a weighted sum of the inputs and then passes the output through a binary step function for classification. Table 2.1: A collection of popular activation functions used in neural networks. Logistic Sigmoids and Hyperbolic Tangents have long been the standard for shallow multilayer perceptrons thanks to their smooth differentiable qualities. Deep neural networks have primarily moved towards rectifiers as their unbounded nature helps preserve gradient flow over many layers. Name |  Function ($\sigma(x)$) |  Derivative ($\sigma^{\prime}(x)$) | Graph
---|---|---|---
Logistic |  $\displaystyle\frac{1}{1+e^{-x}}$ |  $\sigma(x)(1-\sigma(x))$ |
Hyperbolic Tangent |  $\displaystyle\frac{e^{x}-e^{-x}}{e^{x}+e^{-x}}$ |  $1-\sigma(x)^{2}$ |
Binary Step |  $\begin{cases}0&~{}\text{if}~{}x<0\\\ 1&~{}\text{if}~{}x\geq 0\end{cases}$ |  0 |
Rectified Linear Unit |  $\begin{cases}0&~{}\text{if}~{}x<0\\\ x&~{}\text{if}~{}x\geq 0\end{cases}$ |  $\begin{cases}0&~{}\text{if}~{}x<0\\\ 1&~{}\text{if}~{}x\geq 0\end{cases}$ |

####  2.2.1 Optimization

Learning happens by adjusting the weights of the neural network to minimize
error over a set of training samples. The error is described with a loss
function that serves to measure the differences between model predictions and
the true target values. The loss function can vary according to the task and
training procedure. The mean squared error (MSE) and the mean absolute error
(MAE) are both popular measures for regression tasks, where the goal is to
predict a single scalar value.

$\displaystyle MSE$ $\displaystyle=\frac{1}{N}\sum_{i=1}^{N}(Y-\hat{Y})^{2}$
(2.1) $\displaystyle MAE$ $\displaystyle=\frac{1}{N}\sum_{i=1}^{N}|Y-\hat{Y}|$
(2.2)

Different loss functions may result in different optimization behavior
according to their mathematical properties. For example, the mean squared
error will tend to magnify the penalty for outliers compared to the mean
absolute error. Regularization and penalty terms, such as weight decay, are
often included in these loss functions to encourage optimization with respect
to additional constraints [179].

The cross entropy loss (CE) is commonly used for classification tasks.
Consider a dataset with samples that belong to one of $C$ potential classes.
The target label for each sample is encoded into a $C$-dimensional one-hot
vector where each element in the vector has a value of 0 except for the
correct class which has a value of 1. Neural networks are configured to output
a $C$-dimensional vector where each dimension corresponds to the likelihood of
that particular class being predicted. The outputs of the network are
normalized and converted into a probability distribution by using the softmax
function. The error is then determined by measuring the log likelihood between
the predicted probability distribution $\hat{Y}$ and the true distribution
$Y$.

$CE=-\sum_{i=1}^{C}Y_{i}\ log(\hat{Y}_{i})$ (2.3)

Optimization is guided by algorithms that iteratively adjust the weights
throughout training. Supervised deep learning tasks overwhelmingly use
variations of gradient descent [126]. Data is fed through the network, the
error is calculated according to the loss function, and updates are made by
adjusting the weights according to a learning rate $\eta$ with respect to the
gradient of the loss $\nabla F(x)$.

$w_{t+1}=w_{t}-\eta\nabla F(x)$ (2.4)

The advent of the backpropagation algorithm provided an efficient method for
calculating the gradient of neural networks by employing chain rule calculus
layer by layer from the output to the input [160]. Consider the simple network
in Figure 2.1 that contains a single neuron and a set of weights $W$. The
output of the neuron $O$, feeds into an activation function with an output
$A$. The derivative of the error $E$ with respect to particular weight
$W_{i}$, can be described by a chain of partial derivatives backpropagating
through the network.

$\frac{\partial E}{\partial W_{i}}=\frac{\partial E}{\partial A}\frac{\partial
A}{\partial O}\frac{\partial O}{\partial W_{i}}$ (2.5)

Classical gradient descent computes the gradient with respect to all samples
in the training set for each weight update. While this approach leads directly
to the optima of the loss function, it is computationally expensive for large
datasets. Stochastic Gradient Descent instead updates the weights for every
training sample individually. This approach is more efficient but adds
variance as the gradient for each individual sample will not necessarily be in
the direction of the true gradient of the training set. Minibatch Gradient
Descent is most often used in deep learning, where the gradient is calculated
over small subsets of the training data. This approach is more computationally
efficient than full gradient descent while being less noisy than stochastic
gradient descent [126].

Second order and derivative free methods have also been explored for
optimizing neural networks. Second order approaches like Newton’s method and
the conjugate gradient use curvature information through second order
derivatives to achieve faster convergence [4]. However, the computational cost
of these methods with deep neural networks can make them impractical for
large-scale problems [9]. Derivative free methods like evolutionary strategies
and particle swarm optimization eschew gradient information and require only
some objective fitness measure. These approaches excel on tasks where the
gradient is non-differentiable, unavailable, or unreliable. However, these
methods tend to be sample inefficient on supervised learning tasks compared to
gradient methods [168].

Adaptive optimizers like Adagrad, Adadelta, and Adam use running statistics of
previous gradients to scale the learning rates for each parameter [85, 177,
34]. This results in very fast convergence, however the solutions found by
these methods tend to generalize worse than those trained with stochastic
gradient descent [165]. While these alternatives are effective in certain
contexts, stochastic gradient descent is the most popular optimization
algorithm used in deep learning for its reliability, simplicity, and
generality.

####  2.2.2 Architecture

Recent advancements in neural network architectures have led to breakthrough
results across a wide variety of machine learning tasks. Many of these have
been driven by the multilayer perceptron’s notoriously poor performance with
high dimensional image data. These networks do not inherently account for
spatial hierarchies as the input is flattened into a large one dimensional
vector where each input neuron corresponds to a single feature. As a
consequence, these networks are incredibly prone to overfitting noisy pixel
level details and even small images lead to an explosion in the number of
trainable weights.

Convolutional layers were introduced to mitigate these problems by drawing
inspiration from the biological network structures found in animal visual
cortexes [46]. These layers scan the input through a convolution operation,
using a set of filters to produce feature maps that capture spatial
relationships between neighboring pixels. Each filter uses the same shared
window of weights for the entire input which drastically reduces the number of
parameters required. These layers enabled much deeper networks that are able
to capture complex hierarchical features without overfitting.

Figure 2.2: Visualizations of how convolutional layers operate on input
images. Each convolutional filter in a layer scans over the input image
according to a stride length. The middle image displays how a 7x7 filter with
a stride of 7 applies to the input image. The right most image displays a 7x7
filter with overlap using a stride of 2.

Convolutional networks have continued to establish state of the art results on
many benchmarks, spurred by the introduction of MNIST and the five layer LeNet
in 1989 [98]. Improvements have been progressive in the following years and
limited mostly by the computational limitations of hardware at the time.
Notable architectures include the eight layer AlexNet, which kickstarted the
deep learning revolution by winning the ImageNet competition in 2012, and the
sixteen layer VGG model that won the ImageNet localization challenge in 2014
[86, 133]. However, the use of deeper neural networks presented optimization
challenges in the form of vanishing gradients [121]. This happens because
backpropagation involves the repeated multiplication of partial derivatives
through each layer from the output back to the input. If these derivative are
small, then the repeated multiplication can cause the gradient to diminish
quickly such that weight updates in the early layers approach zero. This is
exacerbated by sigmoidal activation functions that saturate as their inputs
become larger.

Residual Networks have since mitigated this problem by introducing skip
connections between blocks of convolutional layers [63]. These connections
bypass one or more layers by performing identity mapping where the input to a
block is summed with the output of the layers being bypassed. This reframes
the underlying mapping $H(x)$ for a group of layers to a residual mapping
$F(x)=H(x)-x$, creating shortcuts that allow gradients to propagate more
effectively throughout the network. Residual connections have enabled the
effective training of substantially deeper networks while also exhibiting
better convergence behavior during training, usually requiring fewer epochs to
reach a stable and more accurate solution.

Vision Transformers have recently emerged as a powerful alternative to
convolutional networks [31]. Unlike convolutional layers that use small
kernels to capture local features, self-attention mechanisms in Vision
Transformers allow for global interactions where pixels or image patches are
weighted in relation to every other pixel or image patch. This approach offers
the potential for better capturing spatial hierarchies, however it can be
computationally expensive and require much more training data to avoid
overfitting. Despite the promising results for Vision Transformers on massive
datasets, deep residual convolutional networks are the de facto standard for
computer vision tasks as they continue to achieve state-of-the-art results on
many benchmarks.

####  2.2.3 Subnetworks

There has been a long history investigating the role of sparse subnetwork
structures in deep learning research. Drawing inspiration from the high degree
of sparsity observed in biological neural networks, these structures offer
significant potential for improving parametric efficiency, inference speed,
memory requirements, and generalization.

A large body of research has emerged to explore how network pruning can find
accurate subnetworks within deep neural networks by selectively removing
unimportant weights [6]. These methods offer significant potential for
reducing computational complexity as a large number of parameters can be
removed from a trained network while maintaining high performance after a
small amount of continued training [6]. Many techniques have been introduced
to select unnecessary weights by using importance measures like weight
magnitude, gradient saliency, connection sensitivity, and synaptic flow [99,
100, 149]. While these methods can find extremely sparse subnetworks that
achieve high accuracy, even random pruning has been shown to result in
accurate subnetworks up to moderate levels of sparsity [108, 104].

Sparse subnetwork structures are also implicitly leveraged in several
important algorithmic advancements in deep learning. The rectified linear unit
(ReLU), defined as $f(x)=max(0,x)$, has gained widespread adoption as an
activation function in deep neural networks. The activation patterns of ReLU
neurons exhibit high levels of sparsity which are thought to improve the
separability of high dimensional data [54]. Certain regularization methods
leverage sparsity in parameter space in order to reduce overfitting and
prevent feature reuse. Dropout, DropConnect, and Stochastic Depth Networks are
the most popular examples where random neurons, connections, or layers are
masked on each forward pass through the network [140, 156, 73]. Other
effective regularization techniques include L1 and L2 weight decay penalties
that aim to penalize large weights and push unimportant ones towards zero
during training [88]. Weight decay can help to prevent overfitting, identify
important features, and compress model sizes by learning sparse structures
[112].

Other promising areas of neural network research aim to leverage the unique
qualities of sparse networks to explore new models of neural computation.
Spiking neural networks use biologically inspired action potentials over time
where neurons only activate if a threshold is crossed [52, 150]. These models
hold potential for significantly faster inference and reduced energy
consumption for resource constrained environments. Echo State Networks and
Liquid State Machines use recurrent reservoirs of sparsely connected neurons
with fixed weights that have been proven to be particularly effective for
dynamic time series modeling [79, 113]. Neuroevolutionary algorithms often
evolve sparse network architecture along with the weights, excelling on tasks
where gradient information is noisy or unavailable [41, 141, 48]. Super
Networks are a theorized concept about how giant networks of the future will
be too big to be trained by any one system, and instead portions of the
network will need to be trained in a distributed manner by isolating sparse
pathways [39].

###  2.3 Ensemble Learning

Many supervised learning algorithms can be described as search algorithms in a
hypothesis space, where the goal is to train a set of model parameters to some
candidate solution that best fits the target distribution [7]. These
hypothesis spaces are very large and complex in deep learning which makes
finding the global optimum very difficult. In practice, there are often many
local optima that are good enough, however each will invariably have its own
set of inherent biases [22]. Ensemble learning tries to remedy this problem by
training several models that each converge to different local optima that are
then combined together to form a better overall hypothesis.

This approach to improving generalization error is often explained in ensemble
literature with an example of the bias-variance decomposition of the mean
squared error (MSE) [122, 154, 13]. Given a model prediction $\hat{y}$ and a
true target value from an unknown test distribution $y$, the mean squared
error is defined to be the expectation of the squared distance between the
models predictions and the true target distribution. Bias is the difference
between the expectation of the model and the true targets and variance is the
squared difference between the models predictions and its mean.

$\displaystyle bias=E[\hat{y}]-y$ (2.6) $\displaystyle
var=E[(\hat{y}-E[\hat{y}])^{2}]$ (2.7) $\displaystyle
MSE=E[(\hat{y}-y)^{2}]=(E[\hat{y}]-y)^{2}+E[(\hat{y}-E[\hat{y}])^{2}]$ (2.8)
$\displaystyle MSE=bias^{2}+var$ (2.9)

Given an ensemble of $M$ equally weighted estimators, the decomposition can be
further extended to produce the bias-variance-covariance decomposition [13].

$\displaystyle\overline{bias}=\frac{1}{M}\sum_{i}(E[\hat{y}_{i}]-y)$ (2.10)
$\displaystyle\overline{var}=\frac{1}{M}\sum_{i}E[(\hat{y}_{i}-E[\hat{y}_{i}])^{2}]$
(2.11) $\displaystyle\overline{covar}=\frac{1}{M(M-1)}\sum_{i}\sum_{j\neq
i}E[(\hat{y}_{i}-E[\hat{y}_{i}])(\hat{y}_{j}-E[\hat{y}_{j}])]$ (2.12)
$\displaystyle
MSE=\overline{bias^{2}}+\frac{1}{M}\overline{var}+(1-\frac{1}{M})\overline{covar}$
(2.13)

Generalization error for single models relies upon the optimization of both
bias and variance, where the tuning of a model towards high bias can cause it
to miss important features and the tuning of a model toward high variance can
cause it to be highly sensitive to noise. When the decomposition is extended
to an ensemble, the generalization performance additionally depends on the
covariance between models. Ideally, ensemble methods that promote diversity
will be able to reduce covariance without increasing the bias or variance of
individual models [154, 13].

Diversity is primarily encouraged through variation of the training data,
network architecture, or training procedure for each ensemble member. Several
of the most popular traditional ensemble methods predate the deep learning
revolution and instead use simple and fast classifiers (e.g. decision trees,
support vector machines, logistic regression, etc.) to produce large numbers
of models optimized on different variations of the training data [128].
Bootstrap Aggregation does this by training each model on a random subset of
the training data with replacement [10]. The Random Subspace Method instead
trains each model on a random subset of features for each training sample
[67]. Boosting strategically samples subsets of data to train models in
sequence, where each subsequent model is trained to correct the mistakes of
its predecessors [33, 45, 19, 81].

Traditional ensemble methods are well founded mathematically by leveraging
large numbers of diverse models to overcome weak base classifiers. However,
this approach is ill-suited to the computationally intensive nature of deep
neural networks, which tend to be data hungry and require large numbers of
training samples. These methods instead focus on training fewer models for
longer periods, aiming to achieve high individual accuracy. Data variation
techniques that reduce the size of the training set for each member tend to
result in lower individual accuracy and worse ensemble performance overall
[95]. Deep ensembles instead rely mostly on variations to network architecture
(e.g. weight initializations, layer configurations, etc.) and training
procedure (e.g. optimizer hyperparameters, loss functions, stochastic order of
training samples, etc.) to induce diversity for each member [95, 42, 58, 109].

####  2.3.1 Low-Cost Ensemble Methods

Efficient ensemble algorithms have become increasingly important as they hold
the potential to significantly reduce the computational cost associated with
traditional ensemble learning, while retaining many generalization benefits
that ensemble learning affords. Several methods have been introduced that we
broadly categorize as pseudo-ensembles, temporal ensembles, or evolutionary
ensembles. Pseudo-ensembles train several models under the guise of a single
monolithic architecture. Temporal ensembles encompass methods that save
snapshots or checkpoints of a single model throughout training. Evolutionary
ensembles leverage biologically inspired concepts like mutation,
recombination, and selection to spawn new child networks. While these methods
vary in their approach to reducing cost, the primary idea behind each is to
share either network structure, gradient information, or learned parameters
among ensemble members. Table 2.2 provides a broad overview on the relative
benefits and drawbacks of each type of method across a number of categories:
training cost, inference cost, storage cost, member diversity, and ensemble
size.

Table 2.2: A generalized overview of the benefits and drawbacks of various low-cost ensemble learning strategies. Specific methods within each category may differ significantly in regards to their strengths or weaknesses. All categories are relatively and subjectively graded according to the primary idea behind their cost reduction, where a dash represents baseline performance, a single checkmark corresponds to relatively good performance, and two checkmarks corresponds to best performance. Method | Training | Inference | Storage | Diversity | Ensemble Size
---|---|---|---|---|---
Pseudo | ✓ | ✓✓ | ✓✓ | - | -
Temporal | ✓✓ | - | - | ✓ | ✓
Evolutionary | ✓ | - | - | ✓✓ | ✓✓

##### Pseudo-Ensembles

Pseudo-ensembles encompass a variety of methods that implicitly train
ensembles as if they were a part of a single architecture [2]. These methods
typically exploit variations of computational paths within the model to
simulate the existence of multiple submodels. Pseudo-Ensembles also tend to
share parameters among members, distinguishing these methods from other
ensembles where independent members are created and trained separately.

Dropout is the canonical example of a pseudo-ensemble where neurons are
randomly masked during training on each forward pass [140]. This technique
effectively trains a unique subnetwork, or ensemble member, for each batch of
training data. Dropout is deactivated during inference so that the entire
network is utilized, which results in a computation where each of the
subnetworks are implicitly ensembled together. Several variants of Dropout
have since been introduced that mask different network structures. DropConnect
masks individual connections rather than neurons [156]. Spatial Dropout masks
feature maps in convolutional layers rather than neurons [153]. Stochastic
Depth Networks mask entire layers of deep residual networks [74]. Since these
techniques mask large parts of the network during training, significantly more
forward passes are needed to fully train a network. Given enough training
time, the resulting networks tend to converge to more robust optima than
standard deep neural networks.

Some pseudo-ensemble methods explicitly encode relationships into the network
architecture design. TreeNets are built on this idea where the network
architecture splits into several independent branches that each have their own
output head [101]. The early layers in the network serve as generalized
feature extractors, while the independent branches learn specialized
representations. During training, the shared layers accumulate the gradients
from each independent branch and during testing, each path from input to one
of the outputs can be treated as an independent ensemble member. Multiple-
Input Multiple-Output architectures extend the ideas introduced with TreeNets
to also incorporate independent input branches. Each input head is fed
different samples and each of the output heads is trained to predict the
corresponding input [62]. During inference, the same input is fed to all of
the branches and the resulting outputs are ensembled together.

BatchEnsembles utilize parameter sharing by decomposing weight matrices into
an element wise product between a single shared set of base weights and
member-specific rank-1 matrices [159]. During training, the shared weights
capture features that are common across all ensemble members while the member-
specific weights can specialize. The rank-1 matrices for each ensemble member
is represented with two single column vectors, which significantly reduces the
storage cost compared to storing full rank weight matrices. Additionally, the
element wise product is much cheaper computationally than matrix
multiplication which results in little computational overhead compared to
inference with a single network.

Knowledge Distillation was introduced to alleviate the inference and storage
costs of ensembles and large networks. This approach is based on the idea that
you can transfer the knowledge learned from a large network to a small network
by training the small network using the predictions of a trained large
network, instead of the raw training labels. This enables the small network to
learn features that would be hard to disentangle if trained from scratch. This
can be done in the context of ensemble learning by training a single network
on the predictions made by a fully trained ensemble. The single network then
approximates the behavior of the ensemble without needing to store and test
all of the models separately [66].

Stochastic Weight Averaging is a recent optimization technique where the
weights of a model are averaged over several states taken from the final
training epochs [78]. This approach effectively integrates several local
optima into a composite model with implicit pseudo-ensemble like inference.
Model Soups operate on a similar principle and have recently shown state-of-
the-art performance on large image classification benchmarks. Instead of
taking the final epoch checkpoints of a single model, Model Soups average the
weights of several independent models that are derived from the same pre-
trained network but are each fine tuned with different hyperparameters [167].

Pseudo-ensembles are much more memory efficient than other low-cost ensemble
methods as members are embedded within a single network structure. These
techniques are generally very fast at performing inference, as forward passes
do not need to be independently computed for each ensemble member. This makes
these techniques highly valuable for environments where memory and inference
cost is prioritized, like in embedded systems or edge computing. However,
pseudo-ensembles do tend to need more training epochs to converge and the
resulting models are less diverse than other ensemble methods, as large parts
of the network structure are shared.

##### Temporal Ensembles

Temporal ensembles are built on the idea that ensemble members can be created
by selecting and saving checkpoints over a single network’s training
trajectory [145]. These approaches capitalize on the variability of model
weights as they converge to several distinct optima throughout training.
Temporal methods primarily differ in how they determine which checkpoints to
save and how to encourage the model to converge to diverse and accurate
optima.

Fast Committee Learning pioneered this concept by selecting time slices at
even intervals throughout training [145]. Horizontal Voting Ensembles were
later introduced that saved a contiguous number of states from every epoch
taken late in the training phase [170]. This sacrifices diversity for member
accuracy as contiguous checkpoints tend to be highly correlated, while
checkpoints taken early in training will be much less accurate.

Snapshot Ensembles introduced a highly effective technique for manipulating
the learning rate schedule by alternating between large and small values over
predetermined cycles [71]. The large rates encourage the model to move further
in parameter space before converging to local optima with small learning
rates. The model is saved at the end of each cycle before repeating, striking
a nice balance between member diversity and accuracy. Fast Geometric Ensembles
extend the algorithm introduced in Snapshot Ensembles by analyzing the loss
surfaces found between the local optima saved at the end of each Snapshot
checkpoint [51]. The landscape analysis revealed that these local optima tend
to be connected by high accuracy pathways. Fast Geometric Ensembles leverage
these high accuracy pathways by saving model states along them. Interpolating
the weights between these optima allows for much larger ensemble sizes as they
are not constrained by the cycle length used in Snapshot Ensembles.

FreeTickets is a recent method that combines ideas from sparse neural network
training and temporal ensemble learning [107]. This approach uses a dynamic
sparse training algorithm that isolates a unique sparse subnetwork at each
cycle which is then optimized with a cyclic learning rate schedule. At the end
of every optimization cycle, the sparse model state is saved before updating
connectivity for the next cycle. The unique topological structure of each
member encourages greater diversity between members, however training sparse
subnetworks from scratch tends to result in slower convergence.

Temporal Ensembles tend to be very computationally efficient for training as
these algorithms save model states over a typical network training trajectory.
The performance of these temporal ensembles often compete with traditional
dense ensembles at a significant fraction of the compute cost. Inference and
storage is more expensive than pseudo-ensembles since each ensemble member
needs to be evaluated independently. Temporal ensembles also tend to have
smaller ensemble sizes than evolutionary ensembles as member generation is
dependent on training budget and the predetermined approach for selecting
checkpoints. The members of certain temporal ensembles can struggle with
diversity or accuracy as model checkpoints taken later in the training process
tend to be highly correlated while earlier checkpoints tend to be less
accurate.

##### Evolutionary Ensembles

Evolutionary methods utilize concepts inspired by biological evolution like
natural selection, mutation, and recombination to optimize populations over
time [162]. These approaches have traditionally been concerned with single
hypothesis testing, where optimization is geared towards selecting a single
network with the best generalization performance from a population. However,
several researchers have noted the natural connection between evolutionary
populations and ensemble learning [47, 110, 172].

Evolution Strategies represent a popular subclass of evolutionary methods that
describe a family of algorithms that generate child networks by selecting
elite candidate models according to their fitness rankings and mutating them
with noise perturbations [5]. These approaches are known to excel with wide
scaling as candidate members can be cheaply generated and quickly evaluated in
parallel [127].

Several variations of evolution strategies have been introduced that alter the
ways that child networks are created. Natural Evolution Strategies generates
new populations according to a weighted average over the previous population
distribution [164]. This approach approximates a natural gradient as models
are weighted according to their fitness such that mutations encourage models
to move in the direction of previously successful models. Covariance Matrix
Adaptation Evolution Strategies improves on evolution strategies by tracking
dependencies between member parameters with a pairwise covariance matrix. The
standard deviation can then control for the overall scale of the distribution,
greatly improving exploration [59, 60]. However, despite the exploratory power
of this approach, constructing the pairwise covariance matrix is
computationally expensive and impractical for large networks.

Evolutionary algorithms are also commonly employed to evolve the topology of
the network along with the weights. Neuroevolution of Augmenting Topologies is
perhaps the most well known approach where networks are incrementally evolved
from simple minimalist structures to more complex ones [141]. This approach
also incorporates concepts like speciation to maintain a diverse population of
network architectures with the goal of preventing premature convergence to
suboptimal solutions. Weight Agnostic Neural Networks employ a similar
approach, however the weights between neurons remain fixed. [49]. The focus
then becomes entirely on evolving the architecture, where this approach
interestingly found that network topology alone can encode solutions to
complex reinforcement learning tasks.

Neuroevolutionary methods have primarily seen success with tasks that can be
solved by relatively small networks, as these methods tend to be sample
inefficient when scaling to larger models [50]. As a result, hybrid
gradient/evolutionary methods have grown in popularity for deep neural
networks as gradient optimization can be used to rapidly train the model while
evolutionary processes can be used to improve exploration [27]. Evolutionary
Ensembles with Negative Correlation Learning is a recent example of this
hybrid methodology where gradient based optimization is applied to each member
at each evolutionary generation. Multiple independent networks are trained
simultaneously with the inclusion of a correlation penalty error term to
encourage diversity. At each generation, the fittest individuals are selected
as parents for the next generation, and child networks are spawned with
normally distributed weight perturbations [110]. MotherNets is another method
where a small base network is trained and used as a source to hatch larger
child networks, where additional neurons and layers are added around the core
network. The weights of the child networks are adjusted using function
preserving network morphisms, in order to ensure that the added layers and
neurons do not catastrophically affect the functionality of the core network.
Diversity is encouraged through heterogenous network architectures where each
child is optimized with different topological configurations [158].

These evolutionary approaches to optimization have several advantages over
gradient based methods that are typically used in deep learning. They are
inherently scalable as population members can be evaluated independently and
they excel at exploring landscapes where gradient information is noisy, flat,
or unavailable [127]. These low-cost evolutionary methods offer a unique
advantage over other approaches in that it is generally cheap to generate new
ensemble members. Once a parent network is trained, child networks tend to
converge quickly while maintaining diversity in the parameter space. The
decoupled nature of child generation and parent training enables more
flexibility as large ensembles can be generated dynamically and pre-trained
models could be used to save significant amounts of compute.

##### Discussion

Ensemble learning has long been known to be an effective and powerful way to
improve performance and these low-cost methods have introduced ways to share
information between members that can significantly reduce computational cost.
While there is no established taxonomy for low-cost methods in the literature,
we note several commonalities where they can be organized under the categories
of pseudo, temporal, and evolutionary ensembles. With fixed training budgets
and competing research objectives, these approaches often struggle to balance
several tradeoffs relating to member accuracy, member diversity, training
cost, inference cost, and storage cost. These methods can suffer from
restrictive algorithms that require special network structures or training
procedures, which can make it difficult to utilize off the shelf models. It
can also be costly to generate and train new ensemble members which results in
smaller ensemble sizes that can limit generalization potential. These are
increasingly important properties for ensemble methods as deep neural networks
continue to grow in size. To address these multifaceted challenges, we aim to
introduce a framework that allows for flexibility in its implementation while
also optimizing these tradeoffs to produce accurate, robust, and efficient
ensembles.

##  Chapter 3 Theoretical Framework

###  3.1 Introduction

We introduce Subnetwork Ensembles as an efficient low-cost approach to
creating ensembles of deep neural networks. The goal with this research is to
develop a generalized framework for describing a process where a large parent
network is trained to convergence and then used to generate child networks
through a perturbative process applied to randomly sampled subnetworks in the
parent model. The spawned child networks can then be further optimized or
tuned in order to recover the lost accuracy as a result of the perturbations.

The perturbative process, subnetwork sampling method, and tuning procedure
used to create child networks can take many forms. We explore several
approaches in Chapters 4, 5, and 6 called Noisy Subnetwork Ensembles, Sparse
Subnetwork Ensembles, and Stochastic Subnetwork Ensembles respectively. Noisy
Subnetwork Ensembles apply noise mutations to modify the weights of sampled
subnetworks. Sparse Subnetwork Ensembles prune the weights of sampled
subnetworks to create sparse child networks. Stochastic Subnetwork Ensembles
uses probability distributions and Bernoulli realizations to create children
with stochastic properties. Figure 3.1 provides a visualization of child
networks formed through these three methodologies.

Figure 3.1: A visualization of child networks formed through three distinct
methodologies that we investigate in Chapters 4, 5, and 6. Noisy Subnetwork
Ensembles perturb subnetworks with noise. Sparse Subnetwork Ensembles prune
subnetworks from the parent. Stochastic Subnetwork Ensembles use probability
scores to determine active parameters on every pass through the network.

Subnetwork Ensembles are motivated by several principles observed in deep
learning optimization research. Using a large parent network enables improved
training dynamics and better convergence efficiency. Smaller networks trained
from scratch often fail to achieve the same performance [106, 148, 65]. Large
parent networks are extremely overparameterized and there’s a notion that
trained models contain large amounts of redundancy [6, 108]. Creating children
from the subspaces of parent networks leverages unrealized capacity to improve
parametric utilization. Spawned child networks inherit optimized parameters
that enable convergence to new local optima quickly. This property has long
been observed in both pruning and transfer learning literature [6, 183, 174].
Perturbing different subspaces of the parent network encourages diverse
representations among child networks. This is especially true for sparse
subnetworks where altered network topologies impact the underlying
optimization landscape [142].

This approach also offers several unique advantages over competing low-cost
ensemble methods. Since the parent and child network procedures are completely
decoupled, any parent network architecture or optimization algorithm can be
used. Modern deep learning best practices (dropout, normalization layers,
weight decay, adaptive optimizers, data augmentations, learning rate
schedules, etc.) can be used to maximize performance of the parent [90]. This
also opens the door to leveraging open source pre-trained models, which is an
increasingly valuable area of research as models and datasets continue to grow
in size. It is also relatively fast and cheap to generate and train new child
networks. This allows for the ability to dynamically grow ensemble sizes as
needed, which can be very useful for some types of tasks where the problem
space grows [16, 157]. This also allows for wide scaling as child networks can
be generated and trained in parallel, avoiding the limitations of low-cost
ensemble methods that are restricted to taking models along a sequential
training trajectory [71, 51, 94]. Sparse Subnetwork Ensembles that leverage
pruning mechanisms result in much smaller ensembles that significantly reduces
memory requirements.

###  3.2 Formalization

Consider a parent neural network $F$ parameterized with a set of weights
$\theta$ optimized via some standard training procedure. We create an ensemble
$E$ consisting of $k$ child networks, where each child network $f_{i}$ has
weights $\hat{\theta}_{i}$ obtained through a perturbative process $\xi$
applied to a subset of weights from the parent network determined using a
stochastic sampling process $\phi$.

$\displaystyle E$ $\displaystyle=\\{f_{1},f_{2},...,f_{k}\\}$ (3.1)
$\displaystyle f_{i}(x;\hat{\theta}_{i})$ $\displaystyle=F(x;\theta;\xi,\phi)$
(3.2)

The generality of this approach offers a lot of freedom for deciding how
Subnetwork Ensembles are formed. The perturbative and subnetwork sampling
processes used to create child networks can take arbitrary forms which can be
useful for tailoring this algorithm to a wide variety of tasks. Any network
architecture can be used with this approach, however it is important to note
that the parent network does serve a foundational role in ensemble
performance, such that the parent network should be both accurate and have
sufficient capacity to enable the creation of high performing children.

####  3.2.1 Subnetwork Sampling

Subnetworks are represented with binary bit mask matrices with the same
dimensions of the weight matrices for each layer in the parent network.
Consider a weight matrix $W\in\mathbb{R}^{m\times n}$ representing the weights
of a particular layer in a neural network. We generate a matrix
$M\in\\{0,1\\}^{m\times n}$, using a stochastic process $\phi$, with the same
dimensions as W. The elements of M are binary values, where $M_{ij}=1$ if the
corresponding weight $W_{ij}$ is retained, and $M_{ij}=0$ if the weight is
masked. The subnetwork weights $\hat{W}$ can then be computed by taking the
element-wise (Hadamard) product of W and M.

$\displaystyle M$ $\displaystyle\sim\phi^{m\times n}$ (3.3)
$\displaystyle\hat{W}$ $\displaystyle=W\circ M$ (3.4)

The topology of the subnetwork can be further described by the granularity in
which parameters are masked. This granularity can be unstructured or
structured, where the former refers to weight-level or connection-level
pruning and the latter refers to neuron-level, channel-level, or layer-level
pruning. Unstructured pruning tends to result in networks with better
predictive capacity while structured pruning results in better computational
efficiency. Removing entire rows, columns, or blocks from a network is more
easily leveraged by hardware optimizations [6, 102]. However, emerging
hardware technology offers a promising future for exploiting unstructured
sparse computation [120, 56, 17, 37].

$(\hat{W}_{uns},\
\hat{W}_{str})=\left(\begin{bmatrix}w_{11}&w_{12}&0&w_{14}\\\ 0&w_{22}&0&0\\\
w_{31}&0&0&w_{34}\\\ 0&0&w_{43}&w_{44}\end{bmatrix}\begin{matrix}\\\ \\\ \\\
,\end{matrix}\begin{bmatrix}w_{11}&w_{12}&w_{13}&w_{14}\\\ 0&0&0&0\\\
w_{31}&w_{32}&w_{33}&w_{34}\\\ 0&0&0&0\end{bmatrix}\right)$ (3.5)

It’s important to also consider the distribution of masked weights throughout
non-homogenous networks. It’s common for layer configurations in deep neural
networks to vary significantly in size. Severe pruning of small layers may
result in bottlenecks that restrict gradient flow. The distribution of masked
weights can be controlled with global and local masking methods. Global
methods are applied uniformly across the entire network while local methods
are applied independently within each layer or sub-region. Global methods tend
to result in higher compression rates as more parameters from the larger
layers are removed whereas local methods offer more fine-grained control and
reduced variance.

####  3.2.2 Neural Partitioning

The transformation of unique subnetworks among child networks is critical at
encouraging diverse behavior. However, the random nature of subnetwork
sampling can be a large source of variance when constructing child networks.
It is prudent to reduce the amount of overlap between the subnetworks
inherited by the parent in order produce less correlated models. We introduce
Neural Partitioning as an effective tool for achieving variance reduction by
dividing neural networks into sets of opposed child networks.

These ideas are inspired by antirandom testing and antithetic sampling [114,
169, 57]. This is also known as mirrored sampling in evolutionary communities,
where whenever a random vector $v=\\{x_{1},...,x_{n}\\}$ is generated, another
vector is generated with the opposite signs
$v^{\prime}=\\{-x_{1},...,-x_{n}\\}$ [12]. Antithetic sampling takes advantage
of the fact that the variance of dependent random variables depends on the
covariance between them.

$\displaystyle var(X)$ $\displaystyle=E[(X-E[X])^{2}]$ (3.6) $\displaystyle
var(X+Y)$ $\displaystyle=E[((X+Y)-E[(X+Y)])^{2}]$ (3.7)
$\displaystyle=E[(X-E[X])^{2}]+E[(Y-E[Y])^{2}]+E[2(X-E[X])(Y-E[Y])]$ (3.8)
$\displaystyle=var(X)+var(Y)+2cov(X,Y)$ (3.9)

If X and Y are independent, then the variance of the sum of them is equal to
the sum of each. However, if we sample Y such that it’s dependent on X, then
the variance is reduced if the covariance between them is negative.

With Neural Partitioning, we can leverage this idea by generating groups of
subnetworks such that the inherited parameters are antithetical and form a
disjoint union over the parameters of the parent network. Consider a weight
matrix $W\in\mathbb{R}^{m\times n}$ for a particular layer in a network.
Consider a mask $M\in\\{0,1\\}^{m\times n}$ that has been generated via some
subnetwork sampling process. The corresponding subnetwork mask with no
parameter overlap, also called the anti-mask $M^{\prime}$, is one in which the
polarity of all of the mask bits are flipped $M^{\prime}=1-M$.

$(M,\ M^{\prime})=\left(\begin{bmatrix}1&1&0&1\\\ 0&1&0&0\\\ 1&0&0&1\\\
0&0&1&1\end{bmatrix}\begin{matrix}\\\ \\\ \\\
,\end{matrix}\begin{bmatrix}0&0&1&0\\\ 1&0&1&1\\\ 0&1&1&0\\\
1&1&0&0\end{bmatrix}\right)$ (3.10)

For large networks, this idea can be extended to partition the parameter space
into $k$ sibling subnetworks with a sparsity level of $1-\frac{1}{k}$.
However, creating too many partitions can lead to increasingly sparse
subnetworks that exhibit bottleneck effects. This can reduce information flow
throughout the network and adversely affect both model performance and
training efficiency.

$(M_{1},\ M_{2},\ M_{3})=\left(\begin{bmatrix}0&1&0&1\\\ 0&1&0&0\\\ 1&0&0&0\\\
0&0&1&1\end{bmatrix}\begin{matrix}\\\ \\\ \\\
,\end{matrix}\begin{bmatrix}0&0&1&0\\\ 1&0&0&1\\\ 0&0&1&0\\\
1&0&0&0\end{bmatrix}\begin{matrix}\\\ \\\ \\\
,\end{matrix}\begin{bmatrix}1&0&0&0\\\ 0&0&1&0\\\ 0&1&0&1\\\
0&1&0&0\end{bmatrix}\right)$ (3.11)

$(M_{1},\ M_{2},\ M_{3})=\left(\begin{bmatrix}0&1&0&1\\\ 0&1&0&0\\\ 1&0&0&0\\\
0&0&1&1\end{bmatrix}\begin{matrix}\\\ \\\ \\\
,\end{matrix}\begin{bmatrix}0&0&1&0\\\ 1&0&0&1\\\ 0&0&1&0\\\
1&0&0&0\end{bmatrix}\begin{matrix}\\\ \\\ \\\
,\end{matrix}\begin{bmatrix}1&0&0&0\\\ 0&0&1&0\\\ 0&1&0&1\\\
0&1&0&0\end{bmatrix}\right)$ (3.12)

The goal of Neural Partitioning is to generate subnetwork masks that maximize
the Cartesian distance between them. For an ensemble of $k$ subnetwork masks
$E=\\{M_{1},M_{2},...M_{k}\\}$, we wish to maximize the total pairwise
distance between all ensemble subnetworks. Consider the masks for weight
matrices flattened into vectors $A=\\{a_{1},...,a_{N}\\}$ and
$B=\\{b_{1},...,b_{N}\\}$. The Cartesian distance ($CD$) and total Cartesian
distance ($TD$) for an ensemble can be described with:

$\displaystyle CD(A,B)$ $\displaystyle=\sqrt{|a_{1}-b_{1}|+...+|a_{N}-b_{N}|}$
(3.13) $\displaystyle TD$
$\displaystyle=\sum_{i=1}^{k}\sum_{j=1}^{k}CD(M_{i},M_{j})$ (3.14)

####  3.2.3 Perturbative Processes

There are a wide variety of ways for defining and applying a perturbative
process to a parent network in order to generate child networks. The choice of
perturbation mechanism can influence distinct aspects of ensemble performance.
We explore three methodologies in Chapters 4, 5, and 6 that have various
levels of regularization effects and computational requirements.

In chapter 4, we explore how child networks can be created simply by
perturbing subnetwork weights with random noise. Consider a noise matrix
$N\in\mathbb{R}^{m\times n}$, with the same dimensions of the corresponding
layer’s weight matrix, generated with random values drawn from a Gaussian
distribution $\mathcal{N}(\mu,\sigma^{2})$. Assume that a bit mask
$M\in\\{0,1\\}^{m\times n}$ was generated with a sampling process $\phi$ to
determine the subnetwork that the perturbations should apply to. The perturbed
weights $\hat{W}$ are then computed by adding the masked noise values to the
original weights $W$.

$\displaystyle M$ $\displaystyle\sim\phi^{m\times n}$ (3.15) $\displaystyle N$
$\displaystyle\sim\mathcal{N}(\mu,\sigma^{2})^{m\times n}$ (3.16)
$\displaystyle\hat{W}$ $\displaystyle=W+(N\circ M)$ (3.17)

In chapter 5, we prune subnetwork weights to create sparse topological
structures. The perturbation can be described as setting certain parameters
indicated by the subnetwork mask to zero and freezing them so that no further
weight updates affect them during optimization. This form of perturbation
offers a stronger regularization effect than those created with noise
perturbations. However, the child networks need to be optimized further to
recover the accuracy lost via pruning.

$\hat{W}=\begin{bmatrix}w_{11}&w_{12}&0&w_{14}\\\ 0&w_{22}&0&0\\\
w_{31}&0&0&w_{34}\\\ 0&0&w_{43}&w_{44}\end{bmatrix}$ (3.18)

In chapter 6, we explore how stochasticity can be injected into the
perturbation process by leveraging probability matrices that determine how
likely it is that a given parameter is retained. Consider a subnetwork mask M
generated from a random sampling process $\phi$. The mask is then used as a
foundation for a function $\psi(M)$ to construct a probability matrix
$P\in[0,1]^{m\times n}$ where each value corresponds to the probability that a
parameter is retained or masked. The subnetwork mask is determined on every
forward pass through a Bernoulli realization of the probability matrix. We
further experiment with annealing the probability matrix over time such that
the subnetwork mask evolves to become deterministic throughout training.

$\displaystyle M$ $\displaystyle\sim\phi^{m\times n}$ (3.19) $\displaystyle P$
$\displaystyle\sim\psi(M)^{m\times n}$ (3.20) $\displaystyle\hat{W}$
$\displaystyle=W\circ Bernoulli(P)$ (3.21)

####  3.2.4 Network Optimization

Once we have a collection of child networks, they can be further optimized to
recover lost accuracy as a result of the perturbative processes. The fine
tuning procedure generally consists of continued training of each child
network independently. Since the child networks inherit parameters from a
fully trained parent, they tend to converge in relatively few epochs.
Moreover, unique topological transformations as a result of pruning or
stochastic masking can promote convergence to diverse local optima.
Neuroevolutionary methods that leverage fitness evaluations and model
selection strategies can also be used as a form of ensemble optimization.
Ultimately, the goal is to construct an ensemble that minimizes the expected
loss $\mathcal{L}(\hat{y},y)$ of the averaged predictions $\bar{f}(x)$ for
each $(x,y)$ pair over the dataset $d_{xy}$.

$\text{minimize}\underset{(x,y)\sim
d_{xy}}{\mathbb{E}}\mathcal{L}(\bar{f}(x),y)$ (3.22)

####  3.2.5 Ensemble Predictions

There are several approaches for combining model predictions in the ensemble.
The two most popular methods include majority vote and weighted model
averaging, where voting methods operate on the predicted class labels and
averaging methods take the weighted mean of the output distributions of each
member [43, 35, 93].

$\displaystyle\bar{f}_{\text{vote}}(x)$
$\displaystyle=\text{mode}\\{\text{argmax}(f_{i}(x)):i\in 1,2,...,k\\}$ (3.23)
$\displaystyle\bar{f}_{\text{avg}}(x)$
$\displaystyle=\text{argmax}\left(\frac{1}{k}\sum_{i=1}^{k}w_{i}f_{i}(x)\right)$
(3.24)

While majority vote has a long history with traditional ensemble methods,
averaged predictions have become the standardized approach for ensembles of
deep neural networks. Throughout this research, we consider ensemble
predictions given by the mean of equally weighted ensemble members.
Perturbations can result in networks that produce outputs of very different
magnitudes. In order to prevent the outsized influence by specific models, the
raw output logits of each model are normalized by a softmax function before
averaging. This is typically done in classification tasks to convert outputs
into probability distributions.

$softmax(x_{i})=\frac{e^{x_{i}}}{\sum_{j}e^{x_{j}}}$ (3.25)

####  3.2.6 Evaluation Metrics

The bulk of our benchmark experiments in the following chapters focus on
typical image classification tasks. In these contexts we report standardized
metrics including the accuracy, negative log likelihood, and expected
calibration error of ensemble predictions on holdout test sets [91]. Accuracy
reports the fraction of correct predictions (Eqn. 3.15). Negative Log
Likelihood is a common loss function used for classification tasks in deep
learning that measures the difference between predicted probability
distributions and true output distributions (Eqn. 3.16). Expected Calibration
Error is used for uncertainty estimation to measure how well a model’s
estimated probabilities match the true observed probabilities of its
predictions (Eqn. 3.17). This involves splitting the data into several bins
and taking the average difference between the accuracy and confidence of the
predictions within each bin.

$\displaystyle Acc$ $\displaystyle=\frac{1}{N}\sum_{i=1}^{N}1(argmax\
\bar{f}(x_{i})\equiv argmax\ y_{i})$ (3.26) $\displaystyle NLL$
$\displaystyle=-\frac{1}{N}\sum_{i=1}^{N}\sum_{c=1}^{C}y_{i,c}\
log(\bar{f}(x_{i})_{c})$ (3.27) $\displaystyle ECE$
$\displaystyle=\sum_{i=1}^{B}\frac{|B_{i}|}{N}\left|(acc(B_{i})-conf(B_{i})\right|$
(3.28)

where $\bar{f}(x)$ represents the prediction made by the ensemble, $y$
represents the correct output for input $x$, $N$ is the total number of test
samples, $|B_{i}|$ is the number of predictions in the bin, $acc(B_{i})$ is
the accuracy of the predictions made in the bin and $conf(B_{i})$ is the
average confidence of model predictions in the bin.

##  Chapter 4 Noisy Subnetwork Ensembles

###  4.1 Introduction

Figure 4.1: Neuroevolution excels at fine tuning fully-trained networks that
get stuck in flat loss basins. The left graph displays a typical SGD training
trajectory where models tend to converge to the edges of flat optima [78]. The
middle graph displays white dots as child networks that are generated from
sparse mutations. The right graph shows the final ensemble consisting of top
candidates selected from evaluation on a separate validation set. A key
insight to the success of gradient-free methods for fine tuning is that the
loss landscapes of test distributions rarely match the training distribution
exactly. Ensembling over wide areas of good validation performance is key to
improving generalization.

Neuroevolution is an area of machine learning research that aims to combine
evolutionary algorithms and neural networks by using biologically inspired
concepts like natural selection, mutation, and reproduction [3, 163, 162]. A
core component of evolution strategies involves the generation of child
networks by applying noise perturbations to one or more parent networks [5].
However, as neural networks continue to grow in size, the effect of noise
perturbations on network behavior becomes increasingly pronounced.

There is often a critical region of mutation where weak perturbations fail to
provide any diversity while strong perturbations lead to complete performance
collapse. The optimal mutation window can be vanishingly small with modern
deep neural networks that contain millions or billions of parameters. Due to
the difficulty in mutating these large models, neuroevolutionary methods have
primarily seen success with tasks that can be solved by relatively small
networks [50]. One approach to alleviating this challenge with large models is
to implement sparse mutations, where only a small subset of parameters are
modified. This can widen the critical mutation window which allows models to
handle stronger perturbations before succumbing to performance collapse. While
sparse mutations have long been used in other areas of evolutionary and
genetic programming, they have rarely been explored with evolution strategies
using deep neural networks [5, 59, 83].

These observations of neuroevolutionary methods connect naturally to our work
with Subnetwork Ensembles. In this chapter, we introduce a formulation that we
call Noisy Subnetwork Ensembles where child networks are generated through
noise perturbations applied to random subnetworks in a large, pre-trained
parent network. Generating child networks in this manner can alleviate the
problems with sample inefficiency that typically plague neuroevolutionary
methods. Since child networks retain their network structure and are only
perturbed by noise, we eschew continued training of the children and instead
implement a standard evolutionary model selection strategy, where we evaluate
a large population of models and form the ensemble with those that perform
best on a small validation set.

We conduct several ablation studies and visualizations designed to gain
insight into the effect that mutation strength and sparsity have on network
behavior. We evaluate Noisy Subnetwork Ensembles on the benchmark
reinforcement learning environment ProcGen as well as the large scale ImageNet
classification task [23, 86]. We observe reliable and consistent
generalization improvements with over a dozen different deep neural network
architectures on several difficult tasks. This approach is flexible and
strikes a nice balance with computational cost as these ensembles can improve
performance over fully trained parent networks with no additional training
required.

###  4.2 Implementation

Noisy Subnetwork Ensembles begin with the standard training of a large parent
network $F$, parameterized with weights $\theta$. We then spawn $k$ child
networks by copying and perturbing a subset of the weights. The binary
subnetwork mask $M\in\\{0,1\\}$ is generated for each layer with the same
dimensions as the layer weights $W$. The mask can be determined according to
any random process $\phi$ for a given sparsity target $\rho$. In our
implementation, we use a layerwise unstructured approach where we randomly
assign the value for each parameter in the mask by sampling a Bernoulli
distribution with probability $\rho$, where a successful trial denotes that
the parameter will be retained. We also generate a noise matrix $N$ with the
same dimensions as the weight matrix according to some given random
distribution. We use a Gaussian distribution with tunable parameters for the
mean $\mu$ and variance $\sigma^{2}$. The sparse mutation for each layer is
created by taking the Hadamard product $\circ$ of the subnetwork mask $M$ with
the noise matrix $N$.

$\displaystyle M$ $\displaystyle\sim Bernoulli(\rho)$ (4.1) $\displaystyle N$
$\displaystyle\sim\mathcal{N}(\mu,\sigma^{2})$ (4.2) $\displaystyle\hat{W}$
$\displaystyle=W+(N\circ M)$ (4.3)

####  4.2.1 Trust-Region Search

It is important to determine appropriate values for both the mean $\mu$ and
variance $\sigma^{2}$ of the noise distribution as well as the amount of
sparsity $\rho$ in the subnetwork mask. This can be challenging to determine
before hand due to differences between the size and complexity of datasets,
model architectures, optimization hyperparameters, etc.

We implement a grid search over a small validation set, where we measure the
average differences between the outputs of a network before and after
mutations are applied. Ensuring that the outputs of the network diverge within
some bound is referred to as trust region optimization in machine learning
contexts [25]. This is a popular technique in reinforcement learning
algorithms as they promote stable policy updates in environments where too
large of a change may lead to performance collapse such that the model will
struggle to recover [129, 130].

A standard approach for establishing the trust region would be to measure the
squared difference between output predictions before and after mutation. Given
a network $F$ that is parameterized by $\theta$ with $C$ outputs and a network
that is perturbed with a noise mutation $\gamma$, the mean squared difference
over a set of $N$ total input samples $X$ can be described as:

$MSE=\frac{1}{N}\sum_{n=1}^{N}\sum_{c=1}^{C}(F(X_{n};\theta)_{c}-F(X_{n};\theta+\gamma)_{c})^{2}$
(4.4)

However, since classification networks are trained with cross entropy loss,
where outputs are treated as probability distributions, the mean squared error
may not be the best fit for approximating the effect of that perturbation as
it can be prone to increased variance. Instead, it is more common to describe
the difference between output distributions with the Kullback-Leibler
Divergence, also known as relative entropy. This allows for a stable measure
of comparison that works regardless of network architecture or noise
distribution.

$KL=\frac{1}{N}\sum_{n=1}^{N}\sum_{c=1}^{C}F(X_{n};\theta)_{c}\log\left(\frac{F(X_{n};\theta)_{c}}{F(X_{n};\theta+\gamma)_{c}}\right)$
(4.5)

A grid search algorithm can then be implemented to try out several values for
the mutation strength and sparsity parameters in order to target a divergence
score that represents the boundary of a trust region. One nice property
revealed in our experiments is that there is a roughly linear relationship
between KL divergence and accuracy degradation in trained models. This insight
can be used to tweak mutation parameters according to problem complexity,
ensemble size, or parameter sensitivity where a larger KL target can allow for
stronger mutations and better exploration at the cost of potentially less
accurate candidate models.

Input: N, the number of candidate models

Input: K, the number of ensemble members

Input: ($X_{train},X_{val},X_{test}$), the training, validation, and test data

Input: $\eta$, the optimizer hyperparameters

Input: $\Delta$, trust region boundary target

Input: $\phi(\rho)$, the subnetwork sampling process with target sparsity
$\rho$

$O=sgd(\eta)$

$F=initialize()$

$F.w=train(F,O,X_{train})$

$\rho,\mu,\sigma^{2}=trustRegionSearch(F,\ X_{val},\ \Delta)$

$candidates=[]$

for  _i in 1 to N_ do

$f_{i}=initialize()$

$f_{i}.w=F.w$

for  _$j$ in $f_{i}.layers$_ do

$M\sim\phi(\rho)^{f_{i,j}.w}$

$N\sim\mathcal{N}(\mu,\sigma^{2})^{f_{i,j}.w}$

$f_{i,j}.w=F_{i,j}.w+(N\circ M)$

end for

$fitness=evaluate(f_{i},X_{val})$

$candidates\leftarrow(f_{i},fitness)$

end for

$ensemble=select(candidates,K)$

for  _$(x,y)$ in $X_{test}$_ do

$outputs=[F(x)$]

for  _c in ensemble_ do

$outputs\leftarrow c(x)$

end for

$predictions=softmax(mean(outputs))$

$loss=nll(predictions,y)$

$accuracy=acc(predictions,y)$

end for

Algorithm 1 Noisy Subnetwork Ensembles

####  4.2.2 Mirrored and Partitioned Noise

Using the above techniques, we can then generate a collection of child
networks with subnetworks perturbed according to parameters found through this
trust region grid search. Neural Partitioning and Antithetical Sampling can
also be leveraged when generating child networks [12]. A single generated
subnetwork mask $M$ and noise matrix $N$ can be used to generate four child
networks $\hat{W}_{i}$ perturbed in opposite directions and subspaces,
resulting in reduced variance and a balanced exploration of the parameter
space.

$\displaystyle M$ $\displaystyle\sim\text{Bernoulli}(\rho)$ (4.6)
$\displaystyle N$ $\displaystyle\sim\mathcal{N}(\mu,\sigma^{2})$ (4.7)
$\displaystyle\hat{W}_{1}$ $\displaystyle=W+(N\circ M)$ (4.8)
$\displaystyle\hat{W}_{2}$ $\displaystyle=W+(N\circ(1-M))$ (4.9)
$\displaystyle\hat{W}_{3}$ $\displaystyle=W-(N\circ M)$ (4.10)
$\displaystyle\hat{W}_{4}$ $\displaystyle=W-(N\circ(1-M))$ (4.11)

We can gain further improvements (without conducting any additional
optimization) by implementing a model selection process. For each candidate
child network in the population, we evaluate its performance on a holdout
validation set where the accuracy is recorded as a measure of its fitness. The
top $k$ models with the best performance will then be selected to become
members of the final ensemble.

###  4.3 Experiments

####  4.3.1 Decision Boundaries

Figure 4.2: The images above detail decision boundaries for a trained three
layer multilayer perceptron after being perturbed with various mutations. With
dense perturbations, there is a comparatively small window between a
functional decision boundary and complete performance collapse. As mutations
become more sparse, the model is better able to retain its behavior while the
strength of parameter mutation increases.

We begin by exploring the interplay between mutation sparsity and mutation
strength by visualizing how changing these values affects network predictions.
We use a simple three layer fully connected multilayer perceptron that
contains 64 neurons in each layer. We train this model on a binary interleaved
spiral dataset that contains 2500 sample (x, y) points. We train for 10 epochs
using the Adam optimizer [85] with a learning rate $0.001$ and use this
trained model as the starting point for all mutations.

We then perturb the model with mutations sampled from a Gaussian Distribution
$N\sim\mathcal{N}(0,\sigma^{2})$ applied to random subnetworks with varying
levels of sparsity. The subnetwork masks are generated in a layerwise
unstructured fashion by sampling $M\sim Bernoulli(\rho)$ where $\rho$
corresponds to the sparse probability. We evaluate several values for the
variance of the noise perturbation $\sigma\in[0.05,0.25]$ and for subnetwork
sparsities $\rho\in[0.0,0.9]$.

Using the perturbed models, we make predictions on a holdout test set
containing 250 samples. In figure 4.2, we display a grid of the decision
boundaries of these perturbed models on the test set as we ablate between
mutation strength and sparsity. When mutations are dense, we see a very quick
collapse of performance for small perturbations. The window for optimal dense
mutation is quite small even for this toy network and simple dataset. When
mutations become more sparse, the model is able to maintain good
classification boundaries while displaying small variations of prediction
diversity. This kind of behavior is desirable for neuroevolutionary
populations as ensemble learning research has shown that ensembles perform
better with large numbers of both accurate and diverse members [8].

####  4.3.2 Ablations

Next, we aim to explore whether the intuitions about how mutations affect
predictions translate to a much larger convolutional network on benchmark
computer vision datasets. For this experiment, we conduct ablations on the
CIFAR-10 and CIFAR-100 datasets [86]. These are popular benchmark datasets and
their use is widespread in computer vision research. They each contain 50,000
training and 10,000 test samples of colored 32x32 pixel images. CIFAR-10
contains samples belonging to one of 10 classes while CIFAR-100 contains
samples belonging to one of 100 classes. We use a WideResNet-28x10 model for
our parent network, which is a highly accurate network architecture that
contains $\sim 36M$ parameters. This network is a variant on the popular
ResNet that decreases the depth and increases the width of each convolutional
layer [175].

We implement a standard training algorithm for this type of model where we
train for 100 epochs using Stochastic Gradient Descent with momentum [144]. A
stepwise learning rate decay is used where an inital value of 0.1 decays to
0.01 after 50% of training and decays again to 0.001 for the final 10% of
training. We use standard data augmentation schemes for CIFAR that includes a
random crop and random horizontal flip along with mean standard normalization.
We split the test set in half in order to construct a validation set used for
model selection.

Figure 4.3: Results of mutation ablations for a trained WideResNet-28x10 model
on CIFAR-10. Lines of different colors correspond to the percentage of
sparsity for the mutations. The top left graph reports the average KL
divergence as a result of mutation strength. The top right graph explores the
relationship between KL divergence and accuracy. The bottom left reports the
accuracy of an an ensemble evaluated with majority vote predictions. The
bottom right reports accuracy of an ensemble evaluated with averaged
predictions.

The parent networks achieve an accuracy of approximately 96% on CIFAR-10 and
approximately 80% on CIFAR-100. Using these saved models as parent networks,
we then perturb the models with varying amounts of mutation strengths,
$\sigma\in(0.0,0.05]$, and sparsities, $\rho\in[0.01,0.99]$, and we evaluate
their performance on the test sets. Figure 4.3 displays the results of these
experiments where we start by measuring the effect that mutations have on KL
Divergence. Predictably, we see that KL divergence quickly increases as the
density and strength of mutations increase. The rapid increase in KL
divergence for dense perturbations illustrates how quickly performance
collapses between very small changes in mutation strength. We also observe an
interesting linear relationship between KL divergence and model accuracy.

We then implement Noisy Subnetwork Ensembles where a population of 16 models
are created by perturbing the parent model according to a given mutation
strength and sparsity. The top 4 models with the best accuracy on the
validation set are then selected. We report the accuracy on the test set with
this ensemble when predictions are decided via majority vote and averaged
output distributions. The averaged predictions approach is much more
consistent than majority vote, which display large amounts of variance as
mutations become stronger. The accuracy of both combination methods are
comparable with no noticeable difference at low levels of mutation. In
settings with strong mutations, the averaged predictions model exhibits more
robust behavior and better accuracy than majority vote. The point where the
mutation started to negatively impact member accuracy corresponds to an
observed KL divergence approximately between 0.02 to 0.05.

####  4.3.3 Benchmarks

##### ImageNet

We then explore our approach on the difficult benchmark computer vision
dataset, ImageNet [87, 28]. ImageNet is a large scale collection of images
that have been hand labelled for use in machine learning tasks and is
organized according to the wordnet dataset hierarchy. Over 14 million images
and 20,000 labels have been collected in total. We use the 2012 ImageNet
collection which consists of a training set of 1.2 million images and a
validation set of 50,000 images, each belonging to one of 1000 categories.
Images have varying sizes and aspect ratios and consist of both colored and
grayscale photos. Images are normalized with mean standard normalization and
we implement standard data augmentations which consists of resizing to 256x256
pixels and center cropping to 224x224 pixels.

We evaluate our approach with ten popular deep neural network architectures of
varying sizes and generalization capacities in order to demonstrate the
generality of this approach across different contexts [86, 72, 146, 69, 63,
171, 180, 75, 133, 175]. All networks are pretrained and available from the
torchvision repository [123].

We break the ImageNet competition test collection (ILSVRC 2012) of 50,000
images into a 80/20 split between test and and validation sets that now each
contain 40,000 and 10,000 samples respectively. All fitness evaluations and
model selections use the validation set and all reported results are evaluated
on the holdout test set. We report accuracy, negative log likelihood, and
expected calibration error for the parent network and the ensemble [91]. We
ran each model twice and report the best results.

Table 4.1: Results for sparse mutation ensembles on ImageNet with a wide variety of models. Mutation sparsity and strength are determined from a small hyperparameter grid search. Accuracy (Acc), Negative Log Likelihood (NLL), and expected calibration error (ECE) are reported for the parent and the ensemble. Metrics prepended with $e$ refer to ensemble results. $\Delta$Acc is the change in accuracy between the parent and the ensemble, $\sigma$ is the mutation strength, and $\overline{KL}$ is the average output divergence between the mutated models and the parent models. 16 models are generated and the 8 most accurate candidates on a validation set are used together as an ensemble. Model |  Acc $\uparrow$ |  NLL $\downarrow$ |  ECE $\downarrow$ |  eAcc $\uparrow$ |  eNLL $\downarrow$ |  eECE $\downarrow$ |  $\Delta$Acc $\uparrow$ | Parameters | $\sigma$ | $\overline{KL}$
---|---|---|---|---|---|---|---|---|---|---
AlexNet | 56.46 | 1.904 | 0.021 | 56.52 | 1.903 | 0.019 | 0.06 | 61.1M | 0.0025 | 0.046
DenseNet-121 | 74.43 | 1.014 | 0.024 | 74.68 | 1.004 | 0.021 | 0.25 | 8.0M | 0.0012 | 0.040
Inception-V3 | 69.57 | 1.819 | 0.184 | 69.98 | 1.681 | 0.169 | 0.41 | 27.2M | 0.0007 | 0.049
MobileNet-V2 | 72.12 | 1.136 | 0.072 | 72.14 | 1.132 | 0.024 | 0.02 | 3.5M | 0.0010 | 0.045
ResNet-18 | 69.76 | 1.247 | 0.026 | 69.93 | 1.238 | 0.022 | 0.17 | 11.7M | 0.0020 | 0.046
ResNext-50 | 77.64 | 0.945 | 0.065 | 77.72 | 0.929 | 0.059 | 0.08 | 25.0M | 0.0012 | 0.051
ShuffleNet-V2 | 69.51 | 1.354 | 0.072 | 69.57 | 1.351 | 0.071 | 0.06 | 2.3M | 0.0020 | 0.052
SqueezeNet | 58.10 | 1.852 | 0.017 | 58.14 | 1.852 | 0.017 | 0.04 | 1.2M | 0.0020 | 0.026
VGG-16 | 71.62 | 1.140 | 0.027 | 71.64 | 1.138 | 0.028 | 0.02 | 138.4M | 0.0025 | 0.048
WideResNet-50 | 78.47 | 0.879 | 0.054 | 78.60 | 0.852 | 0.038 | 0.13 | 68.9M | 0.0015 | 0.049

We conduct a hyperparameter grid search in order to find appropriate mutation
strengths for each model. Using a separate holdout dataset of 1000 samples we
measure the average KL Divergence and accuracy while we ablate mutation
strength $\sigma\in[0.001,0.015]$ with a mutation sparsity of 0.5. We then
choose both a mutation strength that maximizes accuracy while targeting a KL
Divergence of approximately 0.02 which was found empirically to be a safe
range for mutation where the the accuracy of candidate models is balanced with
exploration. We then construct a population of 16 models with neural
partitioning and mirrored sampling. We first generate a random noise mutation
sampled from a Gaussian distribution modified with mutation strength. We
construct a mirrored version of this random vector by flipping the signs of
each value. We then use neural partitioning to generate two opposed
unstructured subnetwork masks each with 50% sparsity Each child network is
then evaluated on a validation set and the top 8 candidates with the best
accuracy are selected. We evaluate the top 8 candidates and combine their
output predictions together to report the ensemble accuracy, negative log
likelihood and expected calibration error.

Table 4.1 contains both the parent results and the ensemble results. We see
consistent improvement in all metrics for each model with Noisy Subnetwork
Ensembles. While the difference between generalization performance is very
small in many cases, it is notable that convergence is stable and appears to
be monotonic with optimal mutation hyperparameters. However, there’s a
question as to how much potential is able to be squeezed out of these fully
trained networks without any further optimization to the child networks. There
is no accepted method for determining the theoretical ceiling of
generalization capacity for complex network architectures. These small
improvements may be considered significant in some contexts where an
improvement of 0.5% accuracy on a dataset of 50,000 images corresponds to 250
more correct predictions.

##### Procgen

Figure 4.4: Training graphs on all 16 environments in the ProcGen benchmark.
Orange lines correspond to single model evaluations and blue lines correspond
to noisy subnetwork ensembles.

Table 4.2: Proximal Policy Optimization hyperparameters and evaluation results
over 10 episodes.

Parameter | Value
---|---
$\gamma$ | 0.999
$\lambda$ | 0.95
Epochs/rollout | 3
Timesteps/rollout | 256
Minibatches | 8
Batch size | 2048
Entropy Bonus | 0.01
Target KL | 0.01
Clip Range | 0.2
Framestack | 2
Normalization | Reward
Learning Rate | 5e-4
Workers | 1
Envs/worker | 64
Total Timesteps | 10m
Network | Impala
Block Config | $[32,64,128]$

Environment | Baseline | Noisy Subnetworks | $\sigma$
---|---|---|---
Bigfish | $13.7\pm 5.47$ | $25.9\pm 5.59$ | 0.06
Bossfight | $9.1\pm 1.93$ | $12.4\pm 0.32$ | 0.05
Caveflyer | $3.9\pm 1.53$ | $7.3\pm 1.32$ | 0.07
Chaser | $2.3\pm 0.22$ | $3.7\pm 1.0$ | 0.01
Climber | $5.1\pm 1.61$ | $7.0\pm 1.75$ | 0.01
Coinrun | $8.0\pm 1.26$ | $7.0\pm 1.44$ | 0.06
Dodgeball | $0.8\pm 0.51$ | $2.0\pm 0.56$ | 0.05
Fruitbot | $30.2\pm 3.16$ | $32.4\pm 0.69$ | 0.04
Heist | $3.0\pm 1.54$ | $4.0\pm 1.55$ | 0.10
Jumper | $6.0\pm 1.55$ | $7.0\pm 1.45$ | 0.02
Leaper | $6.0\pm 1.55$ | $9.0\pm 0.94$ | 0.01
Maze | $6.0\pm 1.54$ | $5.0\pm 1.58$ | 0.04
Miner | $7.4\pm 1.78$ | $4.7\pm 1.74$ | 0.09
Ninja | $5.0\pm 1.58$ | $7.0\pm 1.45$ | 0.01
Plunder | $10.6\pm 3.02$ | $13.6\pm 2.97$ | 0.06
Starpilot | $20.1\pm 5.42$ | $39.1\pm 6.85$ | 0.01
Mean | $8.58\pm 1.86$ | $11.69\pm 2.74$ | $0.04\pm 0.01$

We additionally explore the efficacy of Noisy Subnetwork Ensembles on the
difficult Procgen reinforcement learning benchmark [23]. Procgen consists of
16 unique game environments that use procedural generation to produce distinct
and diverse levels for every run. The observation space for all environments
are 64x64x3 RGB images and the action space consists of 15 discrete options
that correspond to behavior within the game (e.g. left, right, jump, shoot).
Procgen can generate endless numbers of unique levels which allows for a more
robust evaluation of generalization, which has previously been challenging to
evaluate in other reinforcement learning benchmarks [178].

We use the Proximal Policy Optimization algorithm to train our models [130].
This is one of the most popular and reliable baseline algorithms in deep
reinforcement learning. Proximal Policy Optimization updates policies by
taking the largest step possible to improve performance while satisfying a
constraint on how close new and old policies can be. The motivation is to
avoid a common failure point in reinforcement learning where too significant
of a change in policy can result in catastrophic performance collapse.

We train an Impala Convolutional Neural Network for 10 million time steps on
each environment [38]. The Impala architecture is a benchmark residual
convolutional network for reinforcement learning tasks that contains 15 layers
and approximately 1.6 million parameters. On evaluation rollouts, we create a
Noisy Subnetwork Ensemble consisting of 8 models where a random selection of
20% of the weights are perturbed by sampling from a Gaussian distribution with
mutation strength scaled by $\sigma\in[0.01,0.10]$. Perturbations are applied
in a layerwise unstructured fashion. Actions are chosen by averaging the
softmax outputs of the ensemble members.

Figure 4.4 and Table 4.2 includes evaluation graphs and final results on each
environment for both Noisy Subnetwork Ensembles as well as the single parent
model. All results are reported as the mean and standard deviation over 10
runs. Noisy Subnetwork Ensembles improved results in most environments with a
few exceptions, potentially due to the relation between ensembles and
probabilistic actions. Proximal Policy Optimization is a stochastic algorithm
that chooses actions according to a probability distribution. When combining
the predictions of child networks, the output distribution tends to magnify
the most likely action. This can be detrimental in environments where
stochasticity is helpful for encouraging exploration as the deterministic
choice may lead to situations where an agent gets stuck in a state where it is
unable to recover.

###  4.4 Discussion

We introduce Noisy Subnetwork Ensembles as a formulation of Subnetwork
Ensembles where child networks are generated by perturbing sampled subspaces
of a parent network with random noise mutations. This proves to be an
effective approach to alleviating the challenges of mutating deep neural
networks in evolution strategies. Subnetwork perturbations widen the critical
mutation window which allows for stronger mutations and more diversity before
succumbing to performance collapse. We explore how these subnetwork mutations
reduce variance and we show how a model selection strategy can further improve
performance in these ensembles.

We conduct several ablation studies in order to explore the interplay between
sparsity and mutation strength on network behavior. We conduct a decision
boundary experiment where visualizations are created that show the predictions
of a model on a binary classification dataset. After being perturbed with
dense mutations, the model sees a rapid decline in performance while sparsity
significantly helps in maintaining accurate predictions. We then explore how
these insights translate to a wide residual network on CIFAR where we explore
parameter sensitivity and differences between averaged weights and averaged
predictions for various levels of mutation strength and sparsity. Our findings
reaffirm the idea that subnetwork mutations produce accurate models more
reliably than dense mutations.

We then introduce two large scale benchmark evaluations of Noisy Subnetwork
Ensembles on ImageNet and Procgen, with a wide variety of deep neural network
architectures. We use a trained parent network to generate child networks with
noise perturbation hyperparameters found through a short grid search
algorithm. We observe a small yet reliable improvement in generalization for
every model on ImageNet and for most environments on Procgen. This formulation
of Noisy Subnetwork Ensembles offers an intriguing computational tradeoff as
child networks can be quickly generated to obtain small generalization
improvements, without requiring any additional training.

##  Chapter 5 Sparse Subnetwork Ensembles

###  5.1 Introduction

Figure 5.1: A diagram explaining network partitions in Sparse Subnetwork
Ensembles. The parent network is optimized and settles into some optima. Child
networks are created via neural partitioning. That is, two sparse children
each inherit a different set of parameters from the parent. The optimization
landscapes for each child are diverse, yet they converge quickly due to
inheritance from a fully trained parent.

Noisy Subnetwork Ensembles were introduced as a no-cost formulation of
Subnetwork Ensembles where child networks are generated through subnetwork
perturbations and ensembled together without applying any additional training.
The combination of these perturbed models was shown to reliably improve
generalization performance on holdout data, however the differences were
relatively small. Without further optimization of the child networks, there is
a limited potential for improving the predictive capacity of each child
network. Additionally, continued training of the child networks in Noisy
Subnetwork Ensembles would naturally lead to convergence towards highly
correlated areas of the optimization landscape as they share the vast majority
of their parameters and network structure. This lack of diversity can limit
performance and lead to less robust ensembles.

We extend this work by introducing Sparse Subnetwork Ensembles, a formulation
of Subnetwork Ensembles where child networks are created through the pruning
of subnetworks in a trained parent network. The sparse child networks are then
subsequently trained for a small number of epochs in order to recover the lost
accuracy from pruning. The unique network topology of each child encourages
convergence to unique and diverse minima, resulting in more robust ensembles.
We also explore several methods for improving diversity among child networks,
including Neural Partitioning for generating children with mirrored network
structures, and a cyclic learning rate schedule that alternates between large
and small values to promote more exploration in weight space before converging
[138].

This approach is highly flexible and offers several unique benefits over other
low-cost ensemble methods. Like Noisy Subnetwork Ensembles, additional child
networks can be dynamically generated with little additional computation.
Generating ensemble members through pruning results in much smaller networks
that significantly reduce memory usage and computational cost during forward
passes. This approach attempts to strike the optimal balance between
leveraging the improved training dynamics associated with using a large parent
network, while also creating accurate and diverse child networks that converge
quickly to good optima.

We compare Sparse Subnetwork Ensembles to several popular state-of-the-art
ensemble learning algorithms with benchmark deep neural network architectures
and datasets. We conduct hyperparameter ablation studies with child sparsity,
pruning structures, tuning schedules, and ensemble sizes of up to 128 members.
We demonstrate that Sparse Subnetwork Ensembles are both highly efficient,
accurate, and robust with both small and large training budgets.

###  5.2 Implementation

Sparse Subnetwork Ensembles begin with the standard training of a large parent
network $F$, parameterized with weights $\theta$. Given a fixed training
budget, it can be difficult to determine the appropriate amount of time to
allot for training the parent as model architecture, dataset complexity, total
training budget, ensemble size, and inference compute limitations can all have
a strong impact on performance for different ensemble configurations. As a
general guideline, our large scale image classification experiments with Wide
Resnets suggest a 70/30 split between parent/children training time for a
budget of 200 epochs.

We then spawn $k$ child networks by copying the parent and pruning a subset of
the weights. The binary subnetwork mask $M\in\\{0,1\\}$ is generated for each
layer with the same dimensions as the layer weights $W$. The values for each
parameter in the mask is determined by sampling a Bernoulli distribution with
probability $\rho$, where a successful trial denotes that the parameter will
be retained. We also explore an implementation where the mask is determined by
sampling such that neurons are masked rather than individual connections. The
sparse subnetwork is created by taking the Hadamard product $\circ$ of the
mask $M$ with the weights $W$ at each layer.

We additionally implement Neural Partitioning when constructing child networks
of 50% sparsity. In this case, whenever we generate a child network, we
construct the anti-random subnetwork by flipping the polarity of the bits in
the subnetwork mask of the original child. This can be repeated $n$ times to
create an ensemble of size $2n$. The weights for each child network $\hat{W}$
and it’s anti-random complement $\hat{W^{\prime}}$ can be described with.

$\displaystyle M$ $\displaystyle\sim Bernoulli(\rho)$ (5.1)
$\displaystyle\hat{W}$ $\displaystyle=W\circ M$ (5.2)
$\displaystyle\hat{W^{\prime}}$ $\displaystyle=W\circ(1-M)$ (5.3)

This works best with a child sparsity target of 50% such that the size of all
the child networks in the ensemble are roughly equivalent. Given a large
enough parent network, the children can be partitioned to greater degrees
(e.g. three child networks that inherit 33% of the parent’s parameters each).
However, children with higher sparsity may require more training time to
achieve similar performance.

Given the high dimensionality of deep neural networks, the probability that
any two child networks will end up with similar topologies is small since the
number of unique graph structures in random and complex graphs grow
exponentially with the number of nodes [61]. The unique network topology of
each child encourages optimization of diverse feature representations which
helps to produce more robust ensembles. Figure 5.2 illustrates how pruning
convolutional filters applies unique geometric constraints which inherently
forces the production of diverse feature maps.

Figure 5.2: A convolutional parent network filter split into two partitioned
child filters. The child networks learn diverse feature representations due to
the geometric constraints of their unique topologies.

Input: N, the number of ensemble members

Input: ($X_{train},X_{test}$), the training and test data

Input: ($t_{parent},t_{child}$), the number of parent and child epochs to
train for

Input: ($\eta_{parent},\eta_{child}$), the parent and child optimizer
hyperparameters

Input: $\phi(\rho)$, the subnetwork sampling process with target sparsity
$\rho$

$O=sgd(\eta_{parent})$

$F=initialize()$

$F.w=train(F,O,X_{train},t_{parent})$

$ensemble=[]$

for  _i in 1 to $N$_ do

$f_{i}=initialize()$

$f_{i}.w=F.w$

for  _$j$ in $f_{i}.layers$_ do

$M\sim\phi(\rho)^{f_{i,j}.w}$

$f_{i,j}.w\leftarrow f_{i,j}.w\circ M$

end for

$O=sgd(\eta_{child})$

$f_{i}.w=train(f_{i},O,X_{train},t_{child})$

$ensemble\leftarrow f_{i}$

end for

for  _$(x,y)$ in $X_{test}$_ do

$outputs=[F(x)$]

for  _c in ensemble_ do

$outputs\leftarrow c(x)$

end for

$predictions=softmax(mean(outputs))$

$loss=nll(predictions,y)$

$accuracy=acc(predictions,y)$

end for

Algorithm 2 Sparse Subnetwork Ensembles

Each child network is then tuned for a small number of epochs. Since each
child inherits its parameters from an accurate parent, the convergence to good
solutions often occurs after a relatively small number of epochs [6]. There
are several tunable hyperparameters related to optimization that influence the
performance of the fine tuning phase. These include the number of epochs,
learning rate schedule, batch size, weight decay, and data augmentation
strategies. These optimization hyperparameters are generally kept consistent
with those used for training the parent network [124]. Parent networks are
typically trained with a learning rate schedule that starts with a large value
and slowly decays to a small value over time. The most common method for
tuning subnetworks in pruning literature is to use a small constant learning
rate that is consistent with the final phase of training the parent. However,
recent work has found that mimicking the decaying schedules used for the
parent network can be highly effective for tuning subnetworks [124, 96].

We experiment with a learning rate schedule called the one-cycle policy, which
has been shown to be highly effective for rapidly training deep neural
networks from scratch [138]. The one-cycle policy consists of a warm-up, cool-
down, and annihilation phase, which alters the learning rate during training
for each batch of data. The warm up phase begins with a small learning rate
that ramps up to a large maximum rate. The cool-down phase gradually decays
the maximum rate to a minimum rate that is lower than the initial learning
rate. The annihilation phase takes place in the very final stages of training
where the learning rate is decayed to 0.

The one-cycle policy is highly effective at encouraging diversity among child
networks as the large learning rates enable each child to move greater
distances away from the initial weights before converging to optima. This idea
has been shown to be effective in other successful low-cost ensemble methods
and is the primary insight underlying several popular temporal ensemble
methods such as Snapshot Ensembles and Fast Geometric Ensembles [71, 51].

The original introduction of the one-cycle policy utilized linear annealing to
modify the learning rates. However, cosine annealing tends to be more popular
in subsequent implementations. In our experiments we use a revised one-cycle
schedule that disregards the annihilation phase and uses only the warm-up and
cool-down. Additionally, we use the inverse of the one-cycle policy for
momentum when tuning with stochastic gradient descent [144]. Both of these
modifications have been shown empirically in unpublished work to perform
better than the original implementations [70].

The value for the learning rate $\eta$ at iteration $t$, where $\eta_{init}$
is the initial learning rate value, $\eta_{max}$ is the maximium value,
$\eta_{min}$ is the minimum value and $T$ is the total number of iterations
can be described as:

$\displaystyle\eta_{warm}(t)$
$\displaystyle=\eta_{init}+\frac{1}{2}(\eta_{max}-\eta_{init})\left(1-cos\left(\frac{\pi
t}{T}\right)\right)$ (5.4) $\displaystyle\eta_{cool}(t)$
$\displaystyle=\eta_{min}+\frac{1}{2}(\eta_{max}-\eta_{min})\left(1+cos\left(\frac{\pi
t}{T}\right)\right)$ (5.5)

Figure 5.3: An example of the one-cycle learning rate and momentum schedule we
use to fine-tune the child networks in Sparse Subnetwork Ensembles.

###  5.3 Experiments

####  5.3.1 Ablations

We explore the impact of several hyperparameters that govern how sparse
Subnetwork Ensembles are created and optimized. We use three different
variations of the LeNet-5 model architecture where we vary the number of
neurons in each hidden layer to produce a small, medium and large model that
we call LeNet-S (253,290 parameters), LeNet-M (1,007,306 parameters), and
LeNet-L (4,017,546 parameters). All ablation experiments use the Adam
optimizer with a learning rate of $0.001$ and the benchmark CIFAR-10 and
CIFAR-100 datasets, which consist of 60,000 small natural colored images of
32x32 pixels in size. Those 60,000 images are split up into 50,000 training
images and 10,000 testing images. CIFAR-10 samples from 10 classes of images,
while CIFAR-100 samples from 100 classes of images.

Our first ablation aims to evaluate the effect that the amount of sparsity in
the child networks has on both the size of the parent model and the resulting
ensemble performance. We train each parent model (LeNet-S, LeNet-M, and
LeNet-L) for 10 epochs. An ensemble of 8 sparse subnetwork children are
created for each parent by pruning to ablated target sparsity values
$s\in[0.1,0.9]$, and subsequently tuned for an additional 3 epochs. Larger
models are shown to have more capacity for pruning and learning more
efficiently. Ensemble accuracy improves up to a critical region as child
networks become more sparse without needing any additional epochs of training.
More sparsity in the child networks can yield greater ensemble performance
which may suggest better diversity.

Next we explore how structured (neuron-level) and unstructured (connection-
level) pruning methods affect ensemble performance at different levels of
child network sparsity. We first train the LeNet-L parent network for 10
epochs. An ensemble of 8 children is created where each is pruned using either
structured or unstructured pruning to ablated target sparsity levels
$s\in[0.1,0.9]$, and tuned for an additional 3 epochs. Connection pruning
performs much better at higher levels of sparsity compared to neuron pruning.
However, we see little difference in performance for child network sparsities
up to 50%.

Figure 5.4: Ablations over pruning sparsity and structure for various model
sizes. Each graph reports performance for an ensemble containing 8 models. The
left figure reports the effect that pruning sparsity has on models of
different sizes. The right figure displays the efficacy of neuron and
connection pruning for LeNet-L.

One of the unique advantages of Subnetwork Ensembles is that it is relatively
cheap to dynamically generate additional ensemble members. We explore this by
taking the LeNet-M network and producing up to 128 candidate member networks.
We start by training the parent network for 10 epochs. Child networks are
created through unstructured pruning with a sparsity target of $0.5$. Each
child is tuned for one additional epoch. We evaluate ensemble performance over
10 runs as we increase the size of the ensemble from 4 to 128. Larger
ensembles offer great potential for improved generalization as we see
monotonically improved accuracy with reduced variance as the number of
ensemble members increases.

We then aim to evaluate the efficacy of neural partitioning and the one-cycle