BGADAM: Boosting based Genetic-Evolutionary ADAM for Neural Network Optimization

Jiyang Bai, Yuxiang Ren, Jiawei Zhang

TL;DR

This paper introduces BGADAM, a novel optimization algorithm that combines ADAM, genetic algorithms, and a boosting strategy to overcome the common issue of deep learning models getting stuck in local optima. By using boosting to diversify the training of individual models, BGADAM enhances the effectiveness of genetic algorithms in finding better solutions.

What Problem Does This Paper Address?

Deep neural networks have achieved remarkable success, but their training is often hampered by non-convex loss functions. Standard gradient descent-based optimizers like ADAM, while fast, can easily converge to suboptimal "local optima" instead of the desired "global optima." Existing approaches that combine genetic algorithms with multiple learners (like GADAM) aim to address this by using genetic operators to "jump out" of local minima. However, if these multiple learners converge to very similar local optima, the genetic algorithm's effectiveness is diminished, leading to a "local sticking" problem. This paper tackles this limitation by proposing a method to ensure that the individual learners within the optimization process diverge more, thereby making the genetic algorithm more potent.

Methods

The core innovation is the Boosting based Genetic-Evolutionary ADAM (BGADAM) algorithm. It operates in generations, with each generation involving several key steps:

  1. Boosting based ADAM Training: Instead of training all input models on the same data, BGADAM employs a boosting strategy. This involves dynamically re-weighting the training data for each of the 'g' input models. Models that misclassify certain data points are given more emphasis in subsequent training rounds, encouraging them to learn from their mistakes and diverge from each other. This process uses the ADAM optimizer for efficient training of individual models.
  2. Parent Model Selection: After training, models are evaluated based on their performance (loss on a validation set). Models with better performance are more likely to be selected as "parents" for the next stage.
  3. Genetic Algorithm Operations (Crossover & Mutation): Selected parent models undergo genetic operations. Crossover combines variables from parent models, with a bias towards retaining variables from better-performing parents. Mutation introduces small random changes to variables, further aiding in exploration. These operations create "child" models.
  4. New Generation Selection: The best models from both the trained input models and the newly generated child models are selected to form the next generation. This iterative process continues for a predefined number of generations (K).

The boosting strategy is crucial here, as it ensures that the input models are trained on different data distributions, leading them to converge to potentially different local optima. This diversity is what makes the subsequent genetic algorithm operations more effective at finding superior solutions.

Datasets

The paper evaluates BGADAM on the following standard datasets:

  • ORL Dataset: A dataset of face images.
  • MNIST Dataset: A dataset of handwritten digits.
  • CIFAR-10 Dataset: A dataset of small color images.

Key Insights and Ideas

  • Boosting for Divergence: The key insight is that simply having multiple learners isn't enough; they need to diverge. Boosting is an effective mechanism to achieve this by creating distinct training distributions for each learner.
  • Overcoming "Local Sticking": BGADAM directly addresses the "local sticking" problem where similar parent models in a genetic algorithm lead to meaningless offspring. By ensuring parent models are more diverse, the genetic algorithm has a higher chance of exploring different regions of the loss landscape.
  • Synergy of ADAM, GA, and Boosting: The algorithm effectively combines the fast convergence of ADAM, the exploration capabilities of genetic algorithms, and the diversity-inducing power of boosting.
  • Theoretical Guarantees: The paper provides theoretical analysis suggesting that BGADAM can guarantee learning effectiveness and convergence.

Key Results

  • Improved Performance: BGADAM consistently outperforms baseline methods like GADAM, ADAM, RMSProp, and AdaGrad across the tested datasets.
  • Higher Accuracy: BGADAM achieves the best prediction accuracy on most datasets, notably outperforming others on CIFAR-10.
  • Lower Loss: BGADAM significantly reduces test loss, often by nearly 50% compared to GADAM and ADAM, and is substantially better than RMSProp and AdaGrad. For example, on CIFAR-10, BGADAM's test loss is half that of GADAM.
  • Convergence: The algorithm demonstrates convergence within a finite number of generations, with test loss decreasing and accuracy increasing as the number of generations (K) increases.

Limitations and Future Work

  • Hyper-parameter Sensitivity: The paper acknowledges that the performance of BGADAM is influenced by hyper-parameters like 'g' (number of input models) and 'K' (number of generations). While analysis is provided, further exploration of optimal settings for various tasks might be beneficial.
  • Computational Cost: While BGADAM aims for better solutions, it involves multiple generations and multiple models per generation, potentially increasing computational cost compared to simpler optimizers like ADAM. The paper mentions setting training iterations in each generation to match ADAM's total iterations to mitigate this.
  • Future Work: The paper's conclusion suggests that BGADAM outperforms previous methods, especially for deep neural networks, implying that its application to a wider range of complex models and tasks would be a natural next step.

Summary updated

Abstract

For various optimization methods, gradient descent-based algorithms can achieve outstanding performance and have been widely used in various tasks. Among those commonly used algorithms, ADAM owns many advantages such as fast convergence with both the momentum term and the adaptive learning rate. However, since the loss functions of most deep neural networks are non-convex, ADAM also shares the drawback of getting stuck in local optima easily. To resolve such a problem, the idea of combining genetic algorithm with base learners is introduced to rediscover the best solutions. Nonetheless, from our analysis, the idea of combining genetic algorithm with a batch of base learners still has its shortcomings. The effectiveness of genetic algorithm can hardly be guaranteed if the unit models converge to close or the same solutions. To resolve this problem and further maximize the advantages of genetic algorithm with base learners, we propose to implement the boosting strategy for input model training, which can subsequently improve the effectiveness of genetic algorithm. In this paper, we introduce a novel optimization algorithm, namely Boosting based Genetic ADAM (BGADAM). With both theoretic analysis and empirical experiments, we will show that adding the boosting strategy into the BGADAM model can help models jump out the local optima and converge to better solutions.
BibTeX
@inproceedings{bai2021bgadam,
  author = {Jiyang Bai and Yuxiang Ren and Jiawei Zhang},
  title = {{BGADAM: Boosting based Genetic-Evolutionary ADAM for Neural Network Optimization}},
  booktitle = {IJCNN},
  year = {2021},
  url = {https://openreview.net/forum?id=UDBPwVmore6},
}
Figure