Optimizing Neural Networks with Gradient Lexicase Selection
Authors: Li Ding
Lee Spector
Venue: ICLR 2022 Poster (2022)
Keywords: deep learning
lexicase selection
optimization
evolutionary algorithms

Abstract: One potential drawback of using aggregated performance measurement in machine learning is that models may learn to accept higher errors on some training cases as compromises for lower errors on others, with the lower errors actually being instances of overfitting. This can lead both to stagnation at local optima and to poor generalization. Lexicase selection is an uncompromising method developed in evolutionary computation, which selects models on the basis of sequences of individual training case errors instead of using aggregated metrics such as loss and accuracy. In this paper, we investigate how the general idea of lexicase selection can fit into the context of deep learning to improve generalization. We propose Gradient Lexicase Selection, an optimization framework that combines gradient descent and lexicase selection in an evolutionary fashion. Experimental results show that the proposed method improves the generalization performance of various popular deep neural network architectures on three image classification benchmarks. Qualitative analysis also indicates that our method helps the networks learn more diverse representations.

Published as a conference paper at ICLR 2022
OPTIMIZING NEURAL NETWORKS WITH GRADIENT LEXICASE SELECTION
Li Ding
Lee Spector
University of Massachusetts Amherst 1 Lgdingumasee edu
Amherst College
University of Massachusetts Amherst Ispectore amherst..
ABSTRACT
One potential drawback of using aggregated performance measurement in ma- chine learning that models may learn to accept higher errors on some training cases compromises for lower errors others, with the lower emrors actually being instances of overfitting. This can lead both to stagnation at local optima and poor generalization. Lexicase selection is uncompromising method devel- oped in evolutionary computation, which selects models on the basis of sequences of individual training case errors instead of using aggregated metries such loss and accuracy. In this paper, we investigate how the general idea of lexicase se- lection can fit into the context of deep learning improve generalization. We propose Gradient Lexicase Selection, an optimization framework that combines gradient descent and lexicase selection an evolutionary fashion. Experimental results show that the proposed method improves the generalization performance of various popular deep neural network architectures on three image classifica- tion benchmarks. Qualitative analysis also indicates that our method helps the networks learn more diverse representations.
INTRODUCTION
Modern data-driven learning algorithms, in general, define an optimization objective, e.g., fitness function for parent selection in genetic algorithms (Holland, 1992) or loss function for gradi- ent descent in deep learning (LeCun et al., 2015), which computes the aggregate performance on the training data to guide the optimization process. Taking the image classification problem as an example, most recent approaches use Cross-Entropp loss with gradient descent (Bottou 2010) and backpropagation (Rumelhart et al. 1985) to train deep neural networks (DNNs) batches of training images. Despite the success that advanced DNNs can reach human-level performance on the image recognition task (Russakovsky et al. 2015), one potential drawback for such aggregated performance measurement is that the model may learn to seek "compromises" during the learning procedure, e-g., optimizing model weights to intentionally keep some errors in order gain higher likelihood on correct predictions. To give an example, consider a situation that may happen during the training phase image classification for a batch 10 images: of them correctly predicted with high probabilities, but one is wrong. The aggregated loss may produce gradients that guide the model weights to compromise the wrong case for higher probabilities on other cases, which may lead to the optimization process getting stuck at local optima.
We refer to problems for which such compromises are undesirable as uncompromising prob- lems (Helmuth et al. (2014), that is, as problems for which it is not acceptable for solution to perform sub-optimally on any one of the cases in exchange for better performance on others. In deep learning, in order to improve the generalization (Zhang et al. 2017) of DNNs, it is important to maintain the diversity and generality of the representations contributed by every training case.
From the literature, uncompromising problems have been recently explored in genetic programming (GP) and genetic algorithms (GAs) for tasks such as program synthesis. Among many methods that aim to mitigate this problem, lexicase selection (Helmuth al.) 2014 Spector, 2012) has been shown to outperform many other methods (Fieldsend & Moraglio 2015) Galvan- et al. 2013
Krawiec & Liskowski 2015) in number of applications and benchmarks (Helmuth & Spector

---

Published as a conference paper at ICLR 2022
2013
Helmuth & Kelly| 2021). Instead of using an aggregated fitness function for parent selec- tion, lexicase selection gradually eliminates candidates as proceeds to look at how the population fares at each data point in the shuffled training dataset, in which way it can bolster the diversity and generality in populations. Recent works also show that lexicase selection can be used in rule-based learning systems (Aenugu & Spector 2019), symbolic regression (La Cava et al. 2016), constraint satisfaction problems (Metevier et al., 2019), machine learning (La Cava & Moore 2020b a), and evolutionary robotics (Huizinga & Clune 2018 La Cava & Moore 2018
improve model gen- eralization, especially in situations of diverse and unbalanced data. It is reasonable to suspect that for many deep learning problems such as image classification, due to natural variances in real-world data collection, lexicase selection is likely to help improve the generalization of models.
In this work, we aim to explore the application of lexicase selection in the task of optimizing deep neural networks. Taking advantage of the commonly-used gradient descent and backpropagation methods, we introduce Gradient Lexicase Selection, an optimization framework for training deep neural networks that not only benefit from the efficiency of gradient-based learning but also im- proves the generalization of the networks using the outline of lexicase selection method in an evo- lutionary fashion. We test the proposed method on the basic image classification task on three benchmark datasets (CIFAR- 10 (Krizhevsky et al., 2009). CIFAR-100 (Krizhevsky et al.j 2009), and SVHN (Netzer al., 201T)). Experimental results show that gradient lexicase selection man- ages to improve the performance of the DNNs consistently across six different popular architectures
(VGG (Simonyan & Zisserman 2015). ResNet (He al. 2016). DenseNet (Huang et al. 2017). MobileNetV2 (Sandler et al., (2018). SENet (Hu et al., 2018). 8). EfficientNet (Tan & Lej 2019)). In addition, we perform further ablation studies to analyze the effectiveness and robustness of the pro- posed method from various perspectives. We first introduce variants to our method by using random selection and tournament selection, in order to validate the contribution of each component in the framework. We also investigate the trade-offs between exploration and exploitation by analyzing the effects of changing population size and momentum. Finally, the qualitative analysis shows that our algorithm can produce better representation diversity, which is advantageous to the generalization of DNNs.
2 BACKGROUND AND RELATED WORK
Preliminaries of Lexicase Selection
Lexicase selection is initially proposed as a parent selection method in oopulation-based stochastic search algorithms such as genetic programming (Helmuth et al., 2014, Spector 2012). Follow-up work has shown that lexicase selection can effectively improve behavioral diversity and the overall performance and on a variety of genetic programming problems (Helmuth et al. 2016 Helmuth & Spector 2015 Helmuth et al. 2014 Liskowski et al. 2015). The key idea in lexicase selection is that each selection event considers a randomly shuffled sequence of training cases. As a result, lexicase selection sometimes selects specialist individuals that perform poorly on average but perform better than many individuals on one or more other cases. A more detailed description of lexicase selection is appended in Sec. A
Unlike methods such as tournament selection that use a single fitness value and thus tend to always select generalist individuals that have good average performance, lexicase selection does not base selection on an aggregated measure of performance. Such a difference allows lexicase selection to maintain higher population diversity by prioritizing different parts of the dataset during each selection event through the ordering of the cases. It has been shown empiricaly on a number of program synthesis benchmark problems that lexicase selection substantially outperforms standard tournament selection and typically maintains higher levels of diversity (Helmuth et al. 2016).
In a more general context, lexicase selection can be used in any case where selection proce- dure occurs with regard to performance assessment of multiple candidates with set of train- ing cases. Recent work also explores the usage of lexicase selection rule-based learning sys- tems (Aenugu& & Spector 2019), symbolic regression (La Cava et al. 2016), constraint satisfaction problems (Metevier et al.) 2019), machine learning (La Cava & Moore, 2020b a). and evolutionary robotics (Huizinga& & Clune 2018 La Cava & Moore 2018). In this work, we aim to explore the effectiveness of lexicase selection in the context of deep learning optimization from the perspective of improving the diversity of gradient-based representation learning for better generalization. While
2

---

Published as a conference paper at ICLR 2022
there are also other parent selection methods (Fieldsend & Moraglio 2015 Galvan Lopez et al. 2013 Krawiec & Liskowski] 2015) that have been proposed to achieve similar goals, in this work focus on investigating the usage of lexicase selection in deep learning. Further discussion of comparisons between lexicase selection to other selection methods are out of the scope of this work.
Galvan-Lopez
Deep Neuroevolution and Population-based Optimization
While backpropagation (Rumelhart et al. 1985) with gradient descent has been the most successful method in training DNNs with fixed-topology in the past few decades (LeCun et al. (013)). there also attempts to train DNNS through evolutionary algorithms (EAs). [ucch et al. (2017) proposed a gradient-free method to evolve the network weights by using a simple genetic algorithm, and was able to evolve a relatively deep network (with 4 million parameters) and demonstrated competitive results on several reinforcement learning benchmark problems. [Jaderberg al. (2017) proposed nopulation-based training to optimize both model and the hyperparameters. [Cui et al. 2018) pro- posed to alternate between the SGD step and evolution step improve the average fitness of the population. Ding & Spector (202)) demonstrate the usage of selection-inspires methods as regular- ization DNNs. The most relevant recent work is Pawelczyk al. (2018), which did a pilot study on combining simple GA schema with gradient-based learning, where gradient training is used as part of the mutation process. Although the method was tested only on one dataset, the results were encouraging and offered some insights lowing this trend, this paper aims to explore a more efficient evolutionary framework that takes advantage of both SGD and lexicase selection, improve the network generalization by treating image recognition as an uncompromising problem.
deeper combination of GAs and gradient learning. Fol-
From broader perspective that is also closely related to this work, there has been surge of in- terest in methods for Neural Architecture Search (NAS) (Elsken et al. 22019) where evolutionary algorithms gain high popularity. A majority of methods (Floreano et al. 20088] Liu al., 2017 Mikkulainen et al. 2019 Real et al., 2019 2017, Stanley & Mükkkulainen 2002 Xie & Yuille 2017) use EA to search neural network topologies and use backpropagation to optimize network weights and some others (Stanley & Miikkulainen 2002) use EA to co-evolve topologies along with weights. While our method can easily extended to the NAS problem, this work focuses on training various fixed-topology networks in order to make fair comparisons to show the significance of using lexicase selection to improve model generalization.
3 GRADIENT LEXICASE SELECTION
Our goal is to integrate lexicase selection to improve the generalization of DNNs, while at the same time to the greatest extent keep the efficiency of the popular gradient-based learning. We propose Gradient Lexicase Selection as an optimization framework to combine the strength of these two methods, The algorithm is outlined in Alg. [ An overview of the algorithm is also depicted in Fig. The proposed algorithm has two main components, Subset Gradient Descent (SubGD) and Lexicase Selection, which we describe in details in this section as follows.
3.1 EVOLUTION WITH SUBSET GRADIENT DESCENT (SUBGD)
First, we introduce the general evolutionary framework that uses a combination of stochastic gra- dient descent and evolution. Given the network topology, we first initialize all the parameters Wo as the initial parent weights. For each generation, given a population size of we gener- ate p instances of the model as p offspring with the same weights as the parent weights, namely, 17(0) = (1)1) lexicase selection to select the parent for the next generation.
()(r-) Wo- We then perform mutation on these offspring and use
For each generation, have p instances of the model starting with the exact same weights. In- stead of random mutations such as adding gaussian noise as commonly used in neuroevolution, we propose a gradient-based mutation method called subset gradient descent (SubGD).
Given the whole training dataset Strain, we divided it into p subsets with random sampling, as ((0) (()) Srain Stasn -s We then train each model instance accordingly one of the subsets using the normal mini-bate batch stochastic gradient descent. The mutation is done when all the training data is consumed, which is one epoch in traditional deep learning.
3

---

Published as a conference paper at ICLR 2022
randomly shuffled training cases
candidate DNNs
n1. 72. ng. n4. n5
t
t
t
n₂: n2. n4
t2
t2
22
SubGD
n2: n4
t3
t
f3
n2
selected parent for the next generation
f
fs
parent DNN
Lexicase Selection
Figure 1: Overview of the proposed gradient lexicase selection. Given the parent model, we first generate candidates by running subset gradient descent (SubGD), then perform lexicase selection by assessing candidates on each individual case to obtain the parent model for the next generation.
There are several advantages of the proposed mutation method. First, since all the offspring are trained with different non-overlapping training samples, they are likely to evolve diversely, espe- cially when data augmentation is also included. Secondly, each off-spring is trained using gradient descent, meaning they will be optimized efficiently towards the objective, comparing to random mutation methods such as gaussian noise. Thirdly, if implemented with distributed training, all the offisring can be trained simultancously to further reduce computation time. In general, the subset gradient descent aims to find a balance between exploration and exploitation during the evolution process for more efficient optimization.
3.2 LEXICASE SELECTION FOR DNNS
After mutation, the offspring become candidates and we use lexicase selection to select a parent from them for the next generation. First, randomly shuffled sequence of training data points (without data augmentation) is used for selection. Starting from the first training sample, we evaluate all the candidates on each case individually and remove the candidate from the selection pool does not make the correct prediction. This process is repeated until if 1) there is only candidate left, which will be selected as the parent for the next generation, or 2) all the training samples are exhausted and more than one candidates survive, in which case randomly pick candidate from the selection pool.
For the selection process, do not hold out another validation set because 1) if we choose to a validation set, the validation set should have an adequate size in order to ensure its diversity and generality, which means the training set will be noticeably smaller, and thus the training performance is likely to degrade; 2) since each model instance only gets access to part of the (augmented) training data, the selection performed on the original training data is still effective, since the exact same data was never used in the mutation (training).
An important feature of lexicase selection that it treats all the cases equally and thus there is no way to modify its selection pressure. The motivation behind lexicase selection is to allow the survival of those models which may not perform best overall but were able to solve the given testing cases. Such model is likely to learn essential feature representations that allow it make correct predictions on specific cases where all others fail. By letting lexicase selection guide the training process, the neural network potentially learn more diverse representations that finally contribute to better generalization.
To better accommodate the situation of training deep models large-scale datasets, also make some slight modifications to the original lexicase selection algorithm in regard to the tie situations, ie. when all the remaining candidates fail make the correct prediction on one case. The original
4

---

Published as a conference paper at ICLR 2022
Algorithm 1: Gradient Lexicase Selection
Data:
data the whole training dataset
candidates set of instances of the DNN model initialized with the same
parameters
Result:
an optimized DNN model
// training epochs for epoch = 1: : K do
subsets p equal-size subsets obtained through random sampling from the
entire data without replacement
Use gradient descent and backpropagation optimize each of the p candidates on each of the subsets respectively
cases + randomly shuffled sequence of data be used in lexicase selection
parent t None
for case cases do Evaluate all the candidates
on case.
the subset of the current candi dates that have exactly
best performance on case
if candi dates contains only one single candidate then
pa rent &- candidate
break
end end
if parent is None then parent <- a randomly selected individual in candidates end
candidated f- set p instances of the DNN model copied with the same end
parameters parent
return parent
lexicase selection lets all the candidates survive because they all have the same "best" performance, which is failure. However, in the early stages of DNN training, while all the candidates are unable predict correctly on any case, the original lexicase selection will proceed evaluate them until someone happens to get correct prediction by chance, which is inefficient especially on large datasets. So we modify the algorithm randomly select candidate from the remaining candidates they all fail. The modification improves the efficiency of early-stage training and has not shown any noticeable effect on the final model performance.
4 EXPERIMENTAL RESULTS
The proposed Gradient Lexicase Selection is tested on the task of image classification, which is one of the most common benchmark problems in computer vision and deep learning in general. We implement the algorithm on six popular DNN architectures (VGG (Simonyan & Zisserman, 2015), ResNet (He et al. 2016). DenseNet (Huang et al. 2017), MobileNetV2 (Sandler er al.) (018)), SENet (Hu et al. 2018), EfficientNet (Tan & Le 2019)). To show the significance our method, also implement the original momentum-SOOl training baselines for all the architectures.
Three benchmark datasets (CIFAR-I0 (Krizhevsky et al.) 2009), CIFAR-100 (Krizhevsky et al. 2009), and SVHN (Netzer et al., 2011)) are used for evaluation. These datasets comprise 32 x 32 pixel real-world RGB images of common objects (CIFAR-10. CIFAR-100) and street scene digits the test set after the training process finished. Note that for illustration purposes, we only use the training dataset of SVHN without the large extra set, the results not comparable other work.
(SVHN). The training is done using the training set only and evaluate the methods
5

---

Published as a conference paper at ICLR 2022
Table I: Image classification results. We report the mean percentage accuracy (acc.) with standard deviation (std.) obtained by running the same experiment with three different random seeds. The last column (acc. 7) calculates the difference of accuracy by using our method compared to bascline, where positive numbers indicate improvement.
Baseline
Lexicase
Dataset
Architecture
acc.
std.
acc.
std.
acc. f
VGG16
92.85
0.10
93.40
0.13
0.55
ResNet18
94.82
0.10
95.35
0.06
0.53
ResNet50
94.63
0.46
94.98
0.18
0.34
CIFAR-10
DenseNet121
95.06
0.31
95.38
0.04
0.32
MobileNetV2
94.37
0.19
93.97
0.12
-0.39
SENet1 8
94.69
0.14
95.37
0.23
0.68
EfficientNeiBO
92.60
0.18
93.00
0.22
0.40
VGG16
72.09
0.52
72.53
0.20
0.44
ResNet18
76.33
0.29
76.68
0.40
0.35
ResNet50
76.82
0.96
77.44
0.25
0.63
CIFAR-100
DenseNet121
78.72
0.82
79.08
0.26
0.36
MobileNetV2
75.87
0.28
75.57
0.30
-0.30
SENet18
76.97
0.06
77.22
0.29
0.25
EfficientNetB00
71.03
0.86
71.36
0.87
0.33
VGG16
96.27
0.06
96.29
0.08
0.02
ResNet18
96.43
0.14
96.62
0.08
0.19
ResNet550
96.69
0.21
96.74
0.07
0.04
SVHN
DenseNet121
96.82
0.16
96.87
0.03
0.05
MobileNetV2
96.23
0.13
96.26
0.07
0.03
SENe118
96.62
0.19
96.59
0.11
-0.03
EfficientNeiBO
96.14
0.12
95.94
0.10
-0.20
4.1 IMAGE CLASSIHICATION RESULTS
The image classification results shown in Tab. [ We report the mean percentage accuracy (acc.) with standard deviation (std.) obtained by running the same experiment with three different random seeds. The last column (acc. 1) calculates the difference of accuracy by using method compared to baseline, where positive numbers indicate improvement. We can first see that by using method, most of the architectures show significant improvement easier SVHN dataset, we can still observe moderate and consistent improvement. To show the robustness of our algorithm, we use the same population size of 4 for lexicase in all the experiments, meaning the performance may be further improved if extra tuning is performed. The ablation study on the effect of population size is described later in See 5.1
the testing result. On the
Beyond those improvements, we also find that among all the architectures, our method surprisingly fails improve MobileNetV2 on both CIFAR- 10 and CIFAR-100. The main difference between MobileNetV2 and other architectures is that it is highly optimized architecture with over order of magnitude less parameters compared to other architectures. Sandler al. (2018) stated that they tailor the architecture to different performance points, which can be adjusted depending eccuracy/performande trade-of. As result, it is likely that the accuracy is restricted by the model size. and even with better training strategies the performance is not going to improve. Such results indicate that our method may not work directly with architectures that have been optimized by using other training methods. But for other general architectures method work directly out-of- the-box without further tuning.
desired
4.2 COMPARING DIFFERENT SELECTION METHODS
The proposed method has two major components, SubGD and Lexicase Selection. To further val- idate the contribution of each component, we introduce other selection methods for compari-

---

Published as a conference paper at ICLR 2022
Table 2: Comparing gradient lexicase selection to other selection methods on CIFAR-10. We report the mean percentage accuracy (acc.) with standard deviation (std.) obtained by running the same experiment with three different random seeds.
SGD
Random
Tournament
Lexicase
Architecture
std.
acc.
std.
std.
acc.
std.
VGG16
92.85
0.10
92.97
0.15
93.12
0.12
93.40
0.13
ResNet18
94.82
0.10
94.99
0.12
94.90
0.14
95.35
0.06
ResNet50
94.63
0.46
94.75
0.13
94.77
0.04
94.98
0.18
DenseNet12 21
95.06
0.31
95.13
0.04
95.12
0.02
95,38
0.04
MobileNetV2
94.37
0.19
94.02
0.14
93.91
0.09
93.97
0.12
8
94.69
0.14
95.04
0.15
95.01
0.23
95.37
0.23
EfficientNeiBO
92.60
0.18
92.77
0.11
92.83
0.12
93.00
0.22
son: random selection and tournament selection (Miller et al. 1995). Using the same evolutionary framework with SubGD, random selection simply selects random offssring for each generation, and tournament selection uses the average accuracy as the fitness function for selection, which an aggregated metric oppose to lexicase selection. The results are shown in Tab,
We can observe that both random selection and tournament selection perform slightly better than the SGD baseline in most cases, but the proposed gradient lexicase selection is consistently better than both methods with a significant margin. Random selection can be viewed as a baseline method that uses SGD with the same amount of computation as gradient lexicase selection, which indicates that the proposed method outperforms SGD even at the same level of computation. Tournament selection one of the most commonly used selection method in evolutionary algorithms, which select parents based on an aggregated fitness evaluation. As the performance of tournament selection is similar to random selection, indicating that the mechanism of lexicase selection has the major contribution to the improvement.
ABLATION STUDIES
In this section, we design several ablation studies to further analyze and validate the effectiveness of the proposed method. Unless specifically mentioned, all the implementation details follow the same practices in Sec.
5.1 POPULATION SIZE
Population size is an essential hyperparameter for evolutionary algorithms. In this work, the pop- ulation size of DNNs has more constraints such as computation cost and total GPU memory, so has to be much smaller comparing
those for classic GP problems. We test lexicase gradient
lection with population sizes of 2, 4, 6, 8. For illustration purposes, two architectures (VGG16 and ResNet18) are evaluated on the CIFAR-10 10 dataset. The results are shown Tab.
First, we can see that lexicase is relatively robust to different population size p. Under all the pop- ulation size configurations lexicase manages to outperform baseline significantly. Since there have not been trend of increased accuracy with larger population size, the generalization performance does not seem to increase with a larger population. This observation aligns well with the behavior of lexicase selection in GP problems (Helmuth et al., 2018 La Cava et al. 2019), where there seems to be an optimal population size through the trade-off between exploration and exploitation.
For our method, having a larger population size not only adds more offspring for each generation, but also reduces the size of each subset used for training each offspring by SubGD, In either way, the exploration is reduced and the exploitation is increased. There is conflict between the two effects, so we do not control the size of each subset when increasing the population size. the population gets too large, the individuals may evolve different-enough behaviors from each other, and thus the diversity of population may become lower. In general, we find that with relatively small population size,
get good results for gradient lexicase selection.

---

Published as a conference paper at ICLR 2022
Table 3: Comparing different population sizes CIFAR-10. Lexicase is relatively robust dif- ferent population size p. and it manages to outperform baseline with all the configurations in this experiment. The generalization performance does not seem to increase with larger population size.
Lexicase with population size
Architecture
Baseline
p 2
p 4
p
p 8
VGG16
92.85
93.61
93.40
93.92
93.37
ResNet18
94.82
95.50
95.35
95.27
95.38
Table Comparing different momentum configurations on CIFAR-I0. Resetting momentum after each selection event avoids too much aggregation of gradients, which results in higher diversity of offspring and thus better generalization performance.
Lexicase with different momentum options
Architecture
Baseline
No Momentum
Reset Momentum
Inherit Momentum
VGG16
92.85
92.95
93.40
93.13
ResNet18
94.82
94.77
95.35
95.23
5.2 MOMENTUM
In deep learning, SGD with momentum (Sutskever al.) 2013 Liu et al., 2020) has been of the most widely adopted methods for training DNNs. Momentum accelerates gradient descent by accumulating velocity vector in directions persistent reduction in the objective across iterations. This accumulating behavior actually interferes with the proposed gradient lexicase selection algo- rithm, because model instances in the population get different gradient updates, and thus will have different momentum parameters.
To solve this issue, we propose three options: 1) No Momentum: do not use momentum all; 2) Reset Momentum: use high momentum rate and re-initialize the momentum parameters every epoch for each model instance; 3) Inherit Momentum: when selecting the parent model, also copy the momentum parameters along with the model parameters to all the instances in the next generation. For this study, we also test two architectures (VGGI6 and ResNet18) with population size on the CIFAR-10 10 dataset. The results are shown in Tab.
The key idea of lexicase selection is to select parent by using a sequence of training cases that are pri- oritized lexicographically for each generation. In this way, the population maintain a high level of diversity. On the other hand, momentum tends to find an aggregated direction of gradient update accumulated through time. From the results, we can see that the Reset Momentum option works the best, indicating that if we inherit momentum, will influence the mutation over generations and thus the selection strength of lexicase will be negatively affected. By resetting momentum each epoch, only the mutation in the current generation is accelerated by using momentum SGD, which results in higher diversity of offspring. In general, the momentum options can also be viewed as different trade-offs of exploration and exploitation.
5.3 REPRESENTATION DIVERSITY
While quantitative results have shown that the proposed method manages to improve the gener- alization of DNNs, we would like to further investigate the reasons behind this in order to better understand the behavior of the algorithm. One hypothesis is that since lexicase selection is able to increase the diversity and generality of the population in GP, it may as well help DNNs learn more diverse representations, which improves the overall model generalization. To validate this, we ana- lyze and compare the feature representations lexicase selection. We take the first 100 samples from the CIFAR-10 test set and use global max pooling to obtaín the channel- wise activations conv 4x and conv 5x layers (as defined He et al. (0166)). Fig. shows the results.
ResNet-18 18 trained using normal SGD and gradient
8

---

Published as a conference paper at ICLR 2022
Deseline Lexicase
Deseline texicase
104
10a
frequency
Frequency
102
10a
101
10a
10a
0
5
ResNet-18 conv_4x activations
ResNet-18 conv_5x activations
Figure 2: Comparing representation diversity of normal SGD (Baseline in red) and gradient lexicase selection (lexicase blue). The flatter distribution shows that our method produces more diverse representations.
We can observe that method produces flatter distribution of activations with less frequency on Os and more frequency on other values. Joffe Szegedy (2013); Wu & He (2018) shows that normalized distribution of layer activations during training, and thus improves the training efficiency and model generalization. Similarly, our method manages learn more diverse representations by incorporating lexicase selection into the training framework, which advantageous to the generalization of DNNs.
help reduce the internal covariate shift of DNNs
CONCLUSION AND FUTURE WORK
In this work, efficient adaption of lexicase selection in the task of optimizing deep neural networks explored. We propose gradient lexicase selection, an evolutionary algorithm that incorporates lexicase selection with stochastic gradient descent to help DNNs learn more diverse representa- tions for better generalization. Experimental results show that the proposed method can improve the performance of several popular DNN architectures Several ablation studies further validate the robustness and advantages of our method from different perspectives. More specifically, investigate the trade-offs between exploration and exploitation by analyzing the effects of population size and momentum. We also show that our algorithm can produce better representation diversity, which is advantageous the generalization of DNNs.
benchmark image classification datasets.
The goal of our method is to improve the generalization performance rather than speed up the opti- mization. Our method is potentially valuable many real-world problems, especially those safety- critical applications like autonomous vehicles, where higher cost of computation during training is acceptable for better generalization performance. There also several factors consider regard- ing the computation cost: 1) our method expects parallel training of model instances, so the optimal training time can be reduced naive SGD training with modern cloud computing facilities; 2) we have shown that with relatively small population sizes (4x naive SGD), our method can already achieve significantly better performance; 3) with the same amount of computation, the naive method (random selection baseline in See 4.2) can not achieve the same performance ours.
There are several limitations of our work. As described Sec. 4.1 the current gradient lexicase selection method may not work with architectures that have been highly optimized, indicating potential correlation between network architecture and lexicase selection. For future directions, we look forward to explorations on how lexicase selection be used in optimizing neural architectures along with the parameters, and the integration lexicase selection neural architecture search in general.

---

Experiment configurations and Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This material is based upon work supported by the National Science Foundation under Grant No. 1617087. Any opinions, findings, and conclusions recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the National Science Foundation.
This work was performed part using high performance computing equipment obtained under grant from the Collaborative R&D Fund managed by the Massachusetts Technology Collaborative.
The authors would like to thank Ryan Boldi, Edward Pantridge, Thomas Helmuth, and Anil Saini for their valuable comments and helpful suggestions.
REPRODUCIBILITY STATEMENT
We submit our source code as the supplementary material for the review process, which can be used to reproduce the experimental results in this work. We also release our source code on Github: https: / /gipps://githbb com/ BaanngGrraieent-eeee implementation details are described in Sec. B
REFERENCES
Sneha Aenugu and Lee Spector. Lexicase selection in learning classifier systems. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 356-364, 2019.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT pp. 177-186. Springer, 2010.
Xiaodong Cui, Wei Zhang, Zoltán Tüske, and Michael Picheny. Evolutionary stochastic gradient descent for optimization of deep neural networks. Advances in Neural Information Processing Systems, 31, 2018.
Li Ding and Lee Spector. Evolving neural selection with adaptive regularization. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 1717-1725, 2021.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey, The Journal of Machine Learning Research, 20(1):1997-2011 2019.
Jonathan Fieldsend and Alberto Moraglio. Strength through diversity: Disaggregation and multi- objectivisation approaches for genetic programming. In Proceedings of the 2015 Annual Confer- ence on Genetic and Evolutionary Computation, pp. 1031-1038, 2015.
Dario Floreano, Peter Dürr, and Claudio Mattiussi. Neuroevolution: from architectures to learning. Evolutionary intelligence, 1(1):47-62, 2008
Edgar Galvan-Lopez, Brendan Cody-Kenny, Leonardo Trujillo, and Ahmed Kattan. Using semantics in the selection mechanism in genetic programming: simple method for promoting semantic diversity. In 2013 IEEE Congress Evolutionary Computation, pp. 2972-2979. IEEE, 2013.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Thomas Helmuth and Peter Kelly. Psb2: the second program synthesis benchmark suite. In Pro- ceedings of the Genetic and Evolutionary Computation Conference, pp. 785-794, 2021.
Thomas Helmuth and Lee Spector. General program synthesis benchmark suite. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 1039-1046, 2015.
Thomas Helmuth, Lee Spector, and James Matheson. Solving uncompromising problems with lex- icase selection. IEEE Transactions on Evolutionary Computation, 19(5):630-643, 2014.
Thomas Helmuth, Nicholas Freitag McPhee, and Lee Spector. Lexicase selection for program syn-
thesis: a diversity analysis. In Genetic Programming Theory and Practice XIII, pp. 151-167. Springer, 2016.
10

---

Published as a conference paper at ICLR 2022
Thomas Helmuth, Nicholas Freitag McPhee, and Lee Spector. Program synthesis using uniform mutation by addition and deletion. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1 1127-1134, 2018.
John Holland. Genetic algorithms. Scientific american, 267(():66-73, 1992.
Jie Hu, Li Shen, and Gang Sun. Squeere-and-excitttin networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7132-7141, 2018.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 17700-4703 2017.
Joost Huizinga and Jeff Clune. Evolving multimodal robot behavior via many stepping stones with the combinatorial multi-objective evolutionary algorithm. arXiv preprint arXiv:1807.03392, 2018.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference machine learning, pp. 448-456. PMLR, 2015.
Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech M Czarneck,, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning. Karen Simonyan, et al. Population based train- ing of neural networks. arXiv preprint arXiv:1711.098.0 2017.
Krzysztof Krawiec and Pawel Liskowski. Automatic derivation of search objectives for test-based genetic programming. European Conference on Genetic Progrumming, pp. 53-65. Springer, 2015.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Tech. Report, 2009.
William La Cava and Jason Moore. Behavioral search drivers and the role of elitism in soft robotics. In ALIFE 2018: The 2018 Conference on Artificial Life. pp. 206-213. MIT Press, 2018.
William La Cava and Jason H Moore. Genetic programming approaches to learning fair classifiers. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pp. 967-975, 2020a.
William La Cava and Jason H Moore. Learning feature spaces for regression with genetic program- ming. Genetic Programming and Evolvable Machines, 21(3):433-455 467, 2020b.
William La Cava, Lee Spector, and Kourosh Danai. Epsilon-lexicase selection for regression. In Proceedings of the Genetic and Evolutionary Computation Conference 2016, pp. 741-748, 2016.
William La Cava, Thomas Helmuth, Lee Spector, and Jason H Moore. A probabilistic and multi- objective analysis of lexicase selection and s-lexicase selection. Evolutionary Computation, 27 (3)37774402, 2019.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521((553):436 444, 2015.
Pawel Liskowski, Krzysztof Krawiec, Thomas Helmuth, and Lee Spector. Comparison of semantic- aware selection methods in genetic programming. Proceedings of the Companion Publication of the 2015 Annual Conference Genetic and Evolutionary Computation, pp. 1301-1307, 2015.
Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu. Hier- archical representations for efficient architecture search. arXiv preprint arXiv: 000466 2017.
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. arXiv preprint arXiv:2007.07989 2020.
Ilya Loshchilov and Frank Hutter. SGDR: stochastic gradient descent with warm restarts. In 5th International Conference Learning Representations (ICIR), 2017.
11

---

Published as a conference paper at ICLR 2022
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. International Conference on Learning Representations, 2018.
Blossom Metevier, Anil Kumar Saini, and Lee Spector. Lexicase selection beyond genetic program- ming. In Genetic Programming Theory and Practice XVI, pp. 123-136. Springer, 2019.
Risto Mikkullanenn, Jason Liang, Elliot Meyerson, Aditya Rawal, Daniel Fink, Olivier Francon, Bala Raju, Hormoz Shahrzad, Arshak Navruzyan, Nigel Duffy, et al. Evolving deep neural net- works. In Artificial intelligence in the age of neural nefworks and brain computing, pp. 293-312. Elsevier, 2019.
Brad I. Miller, David E Goldberg, et al. Genetic algorithms, tournament selection, and the effects of noise. Complex systems, 93):193-212, 1995.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. NeurlPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
Krzysztof Pawelczyk, Michal Kawulok, and Jakub Nalepa. Genetically-rrained deep neural net- works. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 63-64, 2018.
Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoc V Le, and Alexey Kurakin. Large-scale evolution of image classifiers. In International Conference on Machine Learning, pp. 2902-2911. 1. PMLR, 2017.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V Le. Regularized evolution for image classifier architecture search. In Proceedings of the aaai conference on artificial intelligence, volume 33, pp. 4780-4789, 2019.
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning internal representations by error propagation. Technical report, California Univ San Diego La Jolla Inst for Cognitive Science, 1985.
Olga Russakovsky, Jia Deng. Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-25) 2015.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang- Chihh Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 4510-4520, 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. International Conference on Learning Representations, 2015.
Lee Spector. Assessment of problem modality by differential performance of lexicase selection in genetic programming: a preliminary report. In Proceedings of the 14th annual conference companion Genetic and evolutionary computation, pp. 401-408, 2012.
Kenneth Stanley and Risto Miikkulainen. Evolving neural networks through augmenting topolo- gies. Evolutionary computation, 10(2)99--277, 2002.
Felipe Petroski Such, Vashisht Madhavan, Edoardo Conti, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Deep neurocvolution: Genetic algorithms deep neural networks for reinforcement learning. arXiv preprint arXiv:1712.06558 2017.
competitive alternative for training
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initial- ization and momentum in deep learning. In International conference on machine learning. pp. 1139-1147. PMLR, 2013.
Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural net- works. In International Conference on Machine Learning, pp. 6105-6114, PMLR, 2019.
12

---

Published as a conference paper at ICLR 2022
Ashia C Wilson, Rebecca Roelofs, Mitchell Stem, Nathan Srebro, and Benjamin Recht. The
marginal value of adaptive gradient methods in machine learning. Proceedings of the 31st International Conference Neural Information Processing Systems, pp. 4151-4161, 2017.
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference on
computer vision (ECCV), pp. 3-19, 2018.
Lingxi Xie and Alan Yuille. Genetic enn. In Proceedings of the IEEE international conference on computer vision, pp. 1379-1388, 2017.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference Learning Representations (ICLR), 2017.
13

---

Published as a conference paper at ICLR 2022
A LEXICASE SELECTION
Lexicase selection is a parent selection method population- based stochastic search algorithms
such genetic programming (Helmuth al. 2014 Spector 2012). The lexicase selection algorithm outlined in Alg. 2
Algorithm 2: Lexicase selection to select one parent program in genetic programming
Data:
cases randomly shuffled sequence of data samples to be used selection
candidates: the entire population of programs
Result:
an individual program to be used as parent
for case in cases do candidates the subset of the current candidates that have exactly best performance on case if candidates contains only one single candidate then return candi date end end
return randomly selected candi date in candidates
The key idea of lexicase selection is that each selection event considers randomly shuffled sequence of training cases. With the specific ordering, only individuals whose error minimal among all the already-cone already-considered cases are allowed to survive. Moving forward through the sequence of cases, the selection is done when there is only one candidate left or until all the training cases have been gone through, in which case select randomly from the remaining candidates.
Since the ordering of training cases is randomized for each selection event, every training case gets the opportunity to be prioritized when being put at the beginning of the sequence. As a result, lex- icase selection sometimes selects specialist individuals that perform poorly on average but perform better than many individuals
more other cases.
B IMPLEMENTATION DETAILS
Each network architecture with baseline SGD training and its corresponding counterpart with gra- dient lexicase selection are trained with identical experimental schemes. We use SGD with momen- tum instead of the popular adaptive methods (such as Adam) because, despite the popularity of those recent works (Luo et al.) 2018: Wilson al., 2017) observe that the solutions found by those methods actually generalize worse (often significantly worse) than SGD. We did experi- ments with Adam and tuned the learning rate for several trials, but the results are significantly worse than the SGD counterpart. This work focuses more on the generalization performance rather than the training speed, so we follow the common practice to use SGD with momentum for both baseline training and SubGD. However, it is very likely that some most recent optimization methods, such as Luo et al. (2018), can achieve faster training as well as the same generalization performance as SGD.
methods,
We follow standard practices and perform data augmentation with random cropping with padding and perform random horizontal flipping during the training phase (no augmentation is used during selection phase). The input images are normalized through mean RGB-channel subtraction for all the phases. For both baseline and lexicase,
SGD with momentum of 0.9. For lexicase, use the Reset Momentum option that re- initiializze the momentum parameters for each epoch, which is explained in detail later in Sec. 5.2
The batch size is set to 128 for CIFAR-10 and 64 for CIFAR- 100 and SVHN. The initial learning rate is set to 0.1 and tuned by using Cosine Annealing (Loshchilov & Hutter 2017)
14

---

Published as a conference paper at ICLR 2022
We set the total number of epochs 200 for baseline training and as 100(p+1) for gradient lexicase selection, where p is the size of population. For each epoch in lexicase, the mutation only uses 1/p of the training data to train each model instance, lexicase training similar to baseline training to ensure convergence.
keep the total iterations of weight update of
15


Reviews:
[{"review_id": "hmuHeznfY5l", "reviewer": "Reviewer_U4uc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The training strategy presented in this paper appears expensive in terms of 1) holding multiple copies of the models at all times and 2) looping over permutations of test points for searching the best candidates. That means training this model is as expensive as training multiple independent models. Especially, when the author stated that the proposed method needs to train 200(p+1) epochs, which is slower than training a single model (even with the same number of instance iterations). Compared to the <<1% accuracy improvements, I am curious why people want to use this approach. With the same complexity, one can use the ensemble method to achieve better performance, calibration~(uncertainty estimation), etc.\n\nExperiments also seem to be missing some critical components. For example, since the training strategy optimally searches candidates among the many in the same generation, the entire training process treats data inequivalently. The experiments should show the skewness of data used in the final training model to show the strength of the proposed work. By comparing a model that is directly trained on the weighted data points (weights are from the proposed approach), we can see if the data point's weighting is the reason for the better performance (order independent). This experiment is to identify the real reason for the better model performance. This is just one experiment I can quickly think of, and I think the authors should consider including something like this to enhance their claim.\n\nSome experiment conclusions are not quite convincing—for example, Table 2. I am not sure if the population size P is indeed helpful in this case since the population size difference does not significantly impact the results. What can I learn from this?\n\nThe experiments only showed accuracy as the metric. There are two concerns here. 1) Even for accuracy, the proposed method (with the significant sacrifice on training complexity), in some cases, performs poorly compared to the baseline. 2) The proposed method is very greedy. Does it affect the model's calibration? E.g. predicted likelihood mismatch data distribution a lot? What is the overall loss comparison on the validation set?\n", "summary_of_the_paper": "This paper presents a neural network training strategy that leverages lexicase selection and evolutionary algorithms. Specifically, the training strategy involves two layers of loops to iteratively update model&select candidates, which searches the best optimization direction through greedy search. Experiments are conducted on two image datasets and show the proposed training strategy allows the learned model to reach better performance (accuracy). Further experiments investigate how hyperparameters would impact the final performance.", "summary_of_the_review": "1. Please justify where the proposed training strategy is more useful than ensemble models as they have similar complexity.\n2. Please include experiments that justify the reason of the performance improvement (see above).\n3. Please add comparison between ensemble model and the proposed method in terms of both accuracy and other metrics (Expected Calibration Error, Cross-entropy Loss, etc)\n3. Algorithm 1 seems not quite helpful in this paper. Please consider to remove it and make more discussion to justify the claims.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "JgRxAAB_rN_", "reviewer": "Reviewer_bGuc", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very well-written, flows smoothly and is a pleasure to read. The ideas are well articulated and clear.\n\nThe lexicase selection method proposed in the paper seems analogous to ES methods where an area around the current solution is explored and then a selection step leverages the information received from this exploration step to improve the existing solution. The distinctive part here is the use of bagged sub-gradients instead of random mutation operators and distributed selection instead of a centralized one with an aggregate metric. Including ES-based baselines (such as CMA-ES or a more performant variant) would strengthen the claims of the paper.\n\nThe baseline uses a standard sgd method with momentum. How does the performance compare against a more modern optimizer? For instance, Adam is often preferred over sgd + momentum as it is simple and tends to find the global optima with good regularity. A comparison integrating Adam would answer questions on how fundamental the merits of the proposed lexicase selection method are? And could it translate across varying choices of optimizers to help practitioners.\n\nOn the relationship between population size and performance, should this design choice be informed by the amount of training data available? Since the population bags the data to train, a larger population can mean less data per sub-gradient step. I presume this could affect the exploration/exploitation tradeoff quite noticeably. It would be great if the authors could discuss this in more detail and suggest/provide more insight into how this tradeoff could be balanced without relying on parameter tuning.\n", "summary_of_the_paper": "The paper applies lexicase selection towards training deep neural networks using a hybrid evolutionary-gradient descent optimization method. The mutation operator is replaced by sub-gradient descent on bagged data and lexicase selection is used as the selection procedure in the evolutionary framework. Results in a variety of benchmark image classification tasks demonstrate that the proposed method can improve upon standard stochastic gradient descent methods.", "summary_of_the_review": "The paper presents an interesting evolutionary framework, where mutation is replaced by bagged sub-gradient descent and lexicase selection is used to refresh the population. The proposed method builds on ideas of lexicase selection from related domains and applies it successfully to train deep neural networks on benchmark image classification tasks demonstrating improved performance. The work is novel and potentially valuable to the community.   ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "JMmW6r66j-L", "reviewer": "Reviewer_Fzye", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and organized. The language is clear at all times, and the proposed method is explained well enough. The literature review is comprehensive and in place. \n\nThe only significant drawback in editing style of the draft is the way algorithms are presented. Both algorithms 1 and 2, rely on _while True do_ control flow blocks, along their corresponding _if ... then break_ cases, which makes the algorithms unorthodox in their presentation, and difficult to understand and analyze.\n\nDespite all above, the major flaw of the paper are the empirical assessment and obtained results, that in my opinion, render this work unsuitable for acceptance. I will detail my specific concerns:\n\n- The performance gains observed in the experimental results are simply too marginal. It's been argued that major forums such as ICLR should move away from works that represent marginal improvements over baseline or state of the art methods, and instead favor innovative approaches, or methods that significantly outclass existing research. \n\n- The results might be even deceptive. Authors never explicitly state that baseline SGD was given the same computational resources (CPU threads-GPU cores-exec. time) than that of their method. They hint at the idea by mentioning that some actions were taken in order to guarantee \"same number of evaluations\", but that is not enough to consider it a fair comparison. The computational resources should be the same (CPUorGPU-time)- because if that is not the case, and with such marginal improvements, it could be the case that by simply running SGD a few more epochs, their proposed approach could be left behind.\n\n- One part of their proposed approach, the lexicase evaluation, worries me because it seems to be a choke point for the algorithm running time, that could leave their method in serious disadvantage against SGD. Hardware has moved towards SIMD architectures, which has allowed us to harness the power of algorithms such as SGD, and even population-based method to certain extent; however, their approach would require a MISD architecture to be efficiently implemented, which is, to my knowledge, nonexistent, (or at least not mainstream).\n\nAlthough the proposed approach seems interesting enough, it is simply no attractive enough to switch from SGD. My suggestion for the authors is to search for cases where their method can excel and surpass most other baselines. Exactly as they hinted at the beginning of their paper, perhaps scenarios where data is scarce or incomplete, could be a better test ground for their proposed method. Or simply go directly for NAS and other problems where SGD is known to fail, (e.g. heterogeneous networks).\n\n++UPDATED SCORE 29TH NOV++\nAfter authors replies and improved version of the paper, I raise my score. I think the proposed approach is very interesting; the empirical assessment looks more like something of a work in progress, but authors definitively seem to be on to something.", "summary_of_the_paper": "Authors propose a method to optimize deep networks through a combination of gradient descent and a population-based mechanism. In particular, authors propose an adaptation of \"lexicase\" selection, an exotic selection mechanism proposed in evolutionary computation, in order to be used in the context of deep learning and deep networks optimization. In gross terms, _lexicase selection_ consists of picking individuals for surviving and/or as parents for generating offspring, based on their performance test-case instance-wise, rather than based on some aggregated metric such as MSE or loss, as usually done. Authors provide results from a extensive battery of tests where they compare the performance of their method, against that of regular SGD, optimizing several well-know deep architectures in a set of commonly used too benchmark datasets.", "summary_of_the_review": "The performance improvements over baseline methods are too marginal, nor the method is novel enough, for the work to be considered above acceptance threshold. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9l1Y_mVXk2-", "reviewer": "Reviewer_ezPJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[Strengths]\n- This paper is well-written. The proposed algorithm is easy to follow.\n- The experimental results show that the proposed gradient lexicase selection improves the CNN performance.\n\n[Weaknesses]\n- The reviewer suspects whether the performance improvement is really caused by the gradient lexicase selection. The proposed method modifies the overall procedure of network training to inject the concept of \"population\" into deep neural network training. That is, several networks are trained in parallel by using different portions of datasets in one epoch. After the lexicase selection, $p-1$ candidate networks are discarded. Therefore, we cannot exclude that the reason for the performance improvement by the proposed method is caused by such parallel training. In summary, the reviewer thinks that the following baseline algorithms should be considered to highlight the effectiveness of the gradient lexicase selection.\n    1. The algorithm using random selection for the parent selection in Algorithm 1 instead of the gradient lexicase selection\n    1. The algorithm using aggregated loss for the parent selection in Algorithm 1 instead of the gradient lexicase selection\n- As the proposed method maintains a population of deep neural networks, the memory consumption is higher than single training.\n- It would be better if tasks other than image classification were examined to show the generalization of the proposed method.\n\n[Comments]\n- The actual computational times of the proposed method and naive CNN training should be reported. It seems that the computational cost of the proposed method is about $p$ times higher than that of naive training because the authors set the number of training epochs to $200(p + 1)$. The authors should consider the comparison under the same computational cost for a fair comparison.\n- The proposed method maintains several deep neural networks in training. The population-based training (e.g., the following literature) may be related to this paper.\n    - Xiaodong Cui, Wei Zhang, Zoltán Tüske, and Michael Picheny, \"Evolutionary stochastic gradient descent for optimization of deep neural networks,\" NeurIPS 2018\n    - Max Jaderberg, et al., \"Population Based Training of Neural Networks,\" arXiv:1711.09846", "summary_of_the_paper": "This paper extends the lexicase selection developed in the genetic programming community to apply the idea of lexicase selection to deep neural network training. In the proposed gradient lexicase selection, a parent network is selected based on the lexicase selection from several candidate networks trained using different subsets of the dataset. The authors apply the proposed method to several well-known convolutional neural networks (CNN) and show that the gradient lexicase selection can improve the performance of trained models.", "summary_of_the_review": "This paper is easy to follow. However, the current experimental evaluation is insufficient to clearly show the effectiveness of the gradient lexicase selection.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose bringing lexicase selection from evolutionary computation and applying it to the optimisation of gradient descent. This is done by training a set of p networks and using their performance to select this set of p networks as training progresses on random subsets of the training data.
The reviewers felt, and I agree, that the paper was well written and its method now well described. Concerns raised during review include: additional computational cost, novelty, and marginal performance improvements. Nonetheless after discussion, while the computational cost is indeed higher, it is a novel application, and the reviewers were all in agreement with acceptance after further discussion around experiments.
Decision: Accept (Poster)