Hot of the Press: A First Runtime Analysis of NSGA-III on a Many-Objective Multimodal Problem: Provable Exponential Speedup via Stochastic Population Update

Abstract

The NSGA-III is a prominent algorithm in evolutionary many-objective optimization. It is well-suited for optimizing functions with more than three objectives, setting it apart from the classic NSGA-II. However, theoretical insights about NSGA-III are still in its early development. This paper addresses this point and conducts a rigorous runtime analysis of NSGA-III on the many-objective OneJumpZeroJump benchmark (OJZJ for short), providing runtime bounds where the number of objectives is constant. We show that NSGA-III finds the Pareto front of OJZJ in time O(nk+d/2 +μn ln(n)) where n is the problem size, d is the number of objectives, k is the gap size, a problem specific parameter, if its population size μ ∈ 2O(n) is at least (2n/d + 1)d/2. Notably, NSGA-III is faster than NSGA-II by a factor of μ/nd/2 for some μ ∈ ω(nd/2). We also show that a stochastic population update, proposed by Bian et al. [1], provably guarantees a speedup of order Θ((k/b)k-1) in the runtime where b > 0 is a constant. Besides [15], this is the first rigorous runtime analysis of NSGA-III on OJZJ. Proving these bounds requires a much deeper understanding of the population dynamics of NSGA-III than previous papers achieved. This Hot-off-the-Press paper summarises the work Andre Opris. 2025. A First Runtime Analysis of NSGA-III on a Many-Objective Multimodal Problem: Provable Exponential Speedup via Stochastic Population Update. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, Article No.: 990, Pages 8903 - 8911, 2025 [9].