Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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.
main_review: The paper is very well-written, flows smoothly and is a pleasure to read. The ideas are well articulated and clear.

The 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.

The 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.

On 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.

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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: [Strengths]
- This paper is well-written. The proposed algorithm is easy to follow.
- The experimental results show that the proposed gradient lexicase selection improves the CNN performance.

[Weaknesses]
- 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.
    1. The algorithm using random selection for the parent selection in Algorithm 1 instead of the gradient lexicase selection
    1. The algorithm using aggregated loss for the parent selection in Algorithm 1 instead of the gradient lexicase selection
- As the proposed method maintains a population of deep neural networks, the memory consumption is higher than single training.
- It would be better if tasks other than image classification were examined to show the generalization of the proposed method.

[Comments]
- 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.
- 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.
    - Xiaodong Cui, Wei Zhang, Zoltán Tüske, and Michael Picheny, "Evolutionary stochastic gradient descent for optimization of deep neural networks," NeurIPS 2018
    - Max Jaderberg, et al., "Population Based Training of Neural Networks," arXiv:1711.09846
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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. 

The 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.

Despite 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:

- 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. 

- 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.

- 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).

Although 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).

++UPDATED SCORE 29TH NOV++
After 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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

Experiments 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.

Some 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?

The 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?

summary_of_the_review: 1. Please justify where the proposed training strategy is more useful than ensemble models as they have similar complexity.
2. Please include experiments that justify the reason of the performance improvement (see above).
3. 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)
3. Algorithm 1 seems not quite helpful in this paper. Please consider to remove it and make more discussion to justify the claims.
review_title: null

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)