Towards Theoretically Grounded Evolutionary Learning

Chao QianIJCAI 2022 · OpenReview

Abstract

Evolutionary Algorithms (EAs) have long been valued for their empirical success in solving complex, non-differentiable, and noisy optimization problems. However, their heuristic nature has often led to criticism regarding a lack of theoretical rigor. This paper reviews the recent shift toward theoretically grounded evolutionary learning, highlighting new mathematical tools and algorithms that provide provable performance guarantees. We discuss analysis methodologies such as drift and switch analysis, the strategic use of Pareto optimization, and the development of algorithms like POSS that match optimal approximation ratios for NP-hard tasks.

1. Introduction

Optimization in machine learning frequently involves "mathematically ugly" functions—those that are non-differentiable, noisy, or dynamic. While gradient-based methods often struggle in these environments, Evolutionary Algorithms (EAs) thrive by mimicking natural selection. Despite their practical utility, the machine learning community has historically been hesitant to adopt EAs due to a perceived lack of theoretical support. This work bridges the gap between empirical success and mathematical proof, summarizing the methodologies used to analyze EA runtime and the creation of algorithms with solid theoretical foundations.

2. Methodological Pillars

The transition toward grounded evolutionary learning rests on three primary pillars:

2.1 Analysis Methodologies

To establish time complexity bounds for EAs, researchers employ several sophisticated tools:

  • Fitness Level Partitioning: Dividing the search space into hierarchical levels to calculate the expected time to reach the next improvement.
  • Drift Analysis: A technique for measuring the expected progress toward an optimal solution in each iteration.
  • Switch Analysis: A novel method that derives tighter complexity bounds by comparing a complex EA process to a simpler reference process.

2.2 Pareto Optimization

A significant theoretical advancement is the use of multi-objective optimization to solve single-objective problems. By transforming a constrained problem into a bi-objective one (e.g., balancing the objective function against constraint violations), EAs can navigate through infeasible regions of the search space, often finding global optima faster than single-objective approaches.

2.3 Algorithmic Innovations: POSS

The Pareto Optimization for Subset Selection (POSS) algorithm exemplifies this grounded approach. POSS uses bi-objective search to address NP-hard selection problems, such as sparse regression and ensemble pruning. It maintains a set of non-dominated solutions, iteratively improving them through mutation and selection.

The POSS (Pareto Optimization for Subset Selection) algorithm, which utilizes bi-objective search to solve subset selection problems with theoretical guarantees.

3. Key Insights and Results

Theoretical analysis has yielded several counter-intuitive insights. For instance, adding a second objective can simplify a problem rather than complicate it. Furthermore, implementing "threshold selection" in noisy environments—where a new solution is only accepted if it exceeds a margin—can reduce runtime from exponential to polynomial.

Key results include:

  • Improved Complexity: Switch analysis has improved runtime bounds for multi-objective problems from $O(n^{m+1})$ to $O(n^m)$.
  • Optimal Approximations: POSS achieves a $(1 - 1/e)$ approximation ratio for monotone submodular functions, matching the theoretical limit for polynomial-time algorithms.
  • Robustness: The PONSS variant maintains strong performance in noisy environments, outperforming traditional greedy algorithms.
  • Dynamic Adaptation: Research proves that EAs can maintain their approximation guarantees even when problem constraints (like a budget $k$) change over time.

4. Conclusion and Future Directions

While theoretical grounding has advanced significantly, challenges remain in making these analysis tools accessible to non-experts. Future research aims to develop EAs that surpass current theoretical limits of greedy methods and to improve computational efficiency through hybridization with gradient-based techniques or surrogate modeling.

Summary updated

BibTeX
@inproceedings{qian2022towards,
  author = {Chao Qian},
  title = {{Towards Theoretically Grounded Evolutionary Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=oB8yO90j1sQ},
}
Figure