Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds

• URL: http://arxiv.org/abs/2511.07125v1
• Date: Mon, 10 Nov 2025 14:11:07 GMT
• Title: Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds
• Authors: Andre Opris,
• Abstract summary: We prove tight runtime bounds for NSGA-III on the bi-objective OneMinMax ($2$-OMM) problem.<n>This is the first proven lower runtime bound for NSGA-III on a classical benchmark problem.<n>We also improve the best known upper bound of NSGA-III on the $m$-objective OneMinMax problem.
• Score: 5.482532589225553
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Evolutionary algorithms are widely used for solving multi-objective optimization problems. A prominent example is NSGA-III, which is particularly well suited for solving problems involving more than three objectives, distinguishing it from the classical NSGA-II. Despite its empirical success, the theoretical understanding of NSGA III remains very limited, especially with respect to runtime analysis. A central open problem concerns its population dynamics, which involve controlling the maximum number of individuals sharing the same fitness value during the exploration process. In this paper, we make a significant step towards such an understanding by proving tight runtime bounds for NSGA-III on the bi-objective OneMinMax ($2$-OMM) problem. Firstly, we prove that NSGA-III requires $\Omega(n^2 \log(n) / \mu)$ generations in expectation to optimize $2$-OMM assuming the population size $\mu$ satisfies $n+1 \leq \mu =O(\log(n)^c(n+1))$ where $n$ denotes the problem size and $c<1$ is a constant. Apart from~\cite{opris2025multimodal}, this is the first proven lower runtime bound for NSGA-III on a classical benchmark problem. Complementing this, we secondly improve the best known upper bound of NSGA-III on the $m$-objective OneMinMax problem ($m$-OMM) of $O(n \log(n))$ generations by a factor of $\mu /(2n/m + 1)^{m/2}$ for a constant number $m$ of objectives and population size $(2n/m + 1)^{m/2} \leq \mu \in O(\sqrt{\log(n)} (2n/m + 1)^{m/2})$. This yields tight runtime bounds in the case $m = 2$, and the surprising result that NSGA-III beats NSGA-II by a factor of $\mu/n$ in the expected runtime.

Related papers

• Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer [21.23874800091344]
  We show that the SPEA2 has very different population dynamics than the NSGA-II.<n>We show that the best runtime guarantee of $O(nk)$ is not only achieved for $mu = Theta+1n)$ and $lambda = O(nk)$ but for arbitrary $mu, lambda = O(nk)$.
  arXiv  Detail & Related papers  (2025-11-10T14:43:02Z)
• Graph Random Features for Scalable Gaussian Processes [52.89901965157282]
  We study the application of graph random features (GRFs) to scalable Gaussian processes on discrete input spaces.<n>We prove that (under mild assumptions) Bayesian inference with GRFs enjoys $O(N3/2)$ time complexity with respect to the number of nodes $N$, compared to $O(N3)$ for exact kernels.
  arXiv  Detail & Related papers  (2025-09-03T20:13:23Z)
• Speeding Up the NSGA-II via Dynamic Population Sizes [24.440172242035228]
  We propose the dynamic NSGA-II (dNSGA-II), which is based on the popular NSGA-II and features a non-static population size.<n>We prove that the dNSGA-II with parameters $mu geq 4(n + 1)$ and $tau geq frac25650 e n$ computes the full front of the scOneMinMax benchmark of size.<n>For an optimal choice of $mu$ and $tau$, the resulting $O(n log(n
  arXiv  Detail & Related papers  (2025-09-01T19:45:17Z)
• A First Runtime Analysis of NSGA-III on a Many-Objective Multimodal Problem: Provable Exponential Speedup via Stochastic Population Update [1.223779595809275]
  NSGA-III is a prominent algorithm in evolutionary many-objective optimization.<n>This paper conducts a rigorous runtime analysis of NSGA-III on the many-objective $OJZJfull$ benchmark.<n>We show that NSGA-III is faster than NSGA-II by a factor of $mu/nd/2$ for some $mu in omega(nd/2ln)$.
  arXiv  Detail & Related papers  (2025-05-02T13:26:05Z)
• Speeding Up the NSGA-II With a Simple Tie-Breaking Rule [9.044970217182117]
  We analyze a simple tie-breaking rule in the selection of the next population.<n>We prove the effectiveness of our benchmarks on the classic OneMinMax, LeadingOnesZero, and OneJumpJump benchmarks.<n>For the bi-objective problems, we show runtime guarantees that do not increase when moderately increasing the population size over the minimum size.
  arXiv  Detail & Related papers  (2024-12-16T16:15:37Z)
• Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
  We give a new algorithm for decomposing an $n_times n times n_3$ tensor as the sum of a minimal number of rank-1 terms.<n>We show that an even more general class of degree-$d$s cannot surpass rank $Cn$ for a constant $C = C(d)$.
  arXiv  Detail & Related papers  (2024-11-21T17:41:09Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III) [9.853329403413701]
  The Non-dominated Sorting Genetic Algorithm II (NSGA-II) is the most prominent multi-objective evolutionary algorithm for real-world applications. We provide the first mathematical runtime analysis of the NSGA-III, a refinement of the NSGA-II aimed at better handling more than two objectives.
  arXiv  Detail & Related papers  (2022-11-15T15:10:36Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds [10.107150356618588]
  We prove that the NSGA-II with suitable population size needs $Omega(Nnlog n)$ function evaluations. For the computation of the crowding distance contributions of the two objectives, we even obtain a runtime estimate that is tight including the leading constant.
  arXiv  Detail & Related papers  (2022-09-28T10:11:20Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
  We show a proof of convergence between the Adam Adagrad and $O(d(N)/st)$ algorithms. Adam converges with the same convergence $O(d(N)/st)$ when used with the default parameters.
  arXiv  Detail & Related papers  (2020-03-05T01:56:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.