Why Popular MOEAs Are Popular: Proven Advantages in Approximating the Pareto Front
Authors: Mingfeng Li
Qiang Zhang
Weijie Zheng
Benjamin Doerr
Venue: NeurIPS 2025 poster ()
Keywords: Evolutionary Computation; Runtime Modeling
Primary area: theory

Abstract: Recent breakthroughs in the analysis of multi-objective evolutionary algorithms (MOEAs) are mathematical runtime analyses of those algorithms which are intensively used in practice. So far, most of these results show the same performance as previously known for simpler algorithms like the GSEMO. The few results indicating advantages of the popular MOEAs share the same shortages: They only consider the problem of computing the full Pareto front, sometimes of algorithms enriched with newly invented mechanisms, and this on newly designed benchmarks. In this work, we overcome these shortcomings by analyzing how  existing popular MOEAs approximate the Pareto front of the established LargeFront benchmark. We prove that several popular MOEAs, including NSGA-II (with current crowding distance), NSGA-III, SMS-EMOA, and SPEA2, only need an expected time of $O(n^2 \log n)$ fitness evaluations to compute an additive $\varepsilon$-approximation of the Pareto front of the LargeFront benchmark. This contrasts with the already proven exponential runtime (with high probability) of the GSEMO on the same task. Our result is the first mathematical runtime analysis showing and explaining the superiority of popular MOEAs over simple ones like the GSEMO for the central task of computing good approximations to the Pareto front.

Why Popular MOEAs Are Popular: Proven Advantages in Approximating the Pareto Front
Mingfeng Li Qiang Zhang': Weijie Zh Benjamin Doerr
School of Computer Science and Technology.
State Key Laboratory of Smart Farm Technologies and Systems, International Research Institute for Artificial Intelligence.
Harbin Institute of Technology. Shenzhen, China
Pengcheegg Laboratory. Shenzhen, China
Laboratoire d' I'Informaiquue (LIX), CNRS, École Polytechnique,
Institut Polytechnique de Paris, Palaiseau, France
limingfeng @ stu hiu.hit.dduenn zhengweijie hit.edu.cn, doerr@ lix poltechniquue
Abstract
Recent breakthroughs in the analysis of multi multi-objectiiv evolutionary algorithms (MOEAs) mathematical runtime analyses of those algorithms which are inten- sively used in practice. So far, most of these results show the same performance previously known for simpler algorithms like the GSEMO. The few results indicating advantages of the popular MOEAs share the same shortages: They only consider the problem of computing the full Pareto front, sometimes of algorithms enriched with newly invented mechanisms, and this on newly designed benchmarks. In this work, we overcome these shortcomings by analyzing how existing popular MOEAS approximate the Pareto front of the established LARGEFRONT bench- mark. We prove that several popular MOEAs, including NSGA-II (with current crowding distance), NSGA-III, SMS-EMOA, and SPEA2, only need an expected time of O(n² log n) fitness evaluations to compute an additive e-approximation of the Pareto front of the LARGEF RONT benchmark. This contrasts with the already proven exponential runtime (with high probability) the GSEMO on the same task. Our result is the first mathematical runtime analysis showing and explaining the superiority of popular MOEAs over simple ones like the GSEMO for the central task of computing good approximations to the Pareto front.
Introduction
Mathematical runtime analyses of the evolutionary algorithms are usually challenging. Early theoretical results for multi-objective evolutionary algorithms (MOEAs) O2 LTZ04 fo- cused on the simple algorithms like the (G)SEMO, which use only dominance for the sur- vival selection. Recent breakthroughs like the runtime analysis the most widely used MOEA, (ZLD22 ZD23), have triggered a new era in the theory of MOEAS. Other algorithms that intensively used in practice, like the NSGA-III DIE, SMS-EMOA [BNE077, and SPEA2 (LTOT, were theoretically analyzed soon there- after WD23 BZLQ23 RBLQ24). letting the theory of these popular MOEAs quickly become
NSGA-II [DAMM2)] successfully conducted
hot topic BQ22 DQ23a DOSS23b BZLQ23] DDHW23 WD23 ZD24b ZLDD24 DZL+24
ZD24a ODNS24 RBLQ24 DIK25 DZD25 LZD25]
Equal Contribution. sooneinn author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Interestingly, despite the rapid progress in the analysis of practical MOEAs, only very few results have demonstrated theoretical advantages of popular MOEAs over simpler algorithms. Dang et al. DOSS23a introduced the drastic Bernoulli noise model, and showed that the GSEMO fails badly on every Bernoulli-noisy fitness function, while the NSGA-II can cover the whole Pareto front of the Bernoulli-noisy LOTZ problem in polynomial time. Dang et al. [DS24] proved that three popular MOEAs, namely NSGA-II, NSGA-III and MMS-EMOA, enhanced with a mild diversity mechanism (avoiding genotype duplication), require (n log n) expected fitness evaluations to cover the whole Pareto front of their newly designed ONETRAPZEROTRAL problem, which only has two extremal points as the whole Pareto front. In contrast, the simpler algorithm GSEMO requires least n" fitness evaluations in expectation. The very recent work [DO225] constructed an artificial problem with small Pareto set where almost all pairs of search points are incomparable, also with only two points in the whole Pareto front, and proved that any black-box MOEA using only dominance- selection and bit-value-invariint variation operators takes exponential time with high probability, while three popular MOEAs, namely NSGA-II, NSGA-III, and SMS-EMOA, efficiently cover the Pareto front in expected quadratic time.
The above results [DOSS23 DOS24 DOS25 indicating advantages of popular MOEAs share the same shortages. They consider the performance for the problem of computing the full Pareto front, (of some algorithms enriched with newly invented mechanisms), and this on newly designed benchmarks. In practice, one cannot know the Pareto front beforehand. The newly invented mechanisms newly designed benchmarks place the question on the generality of tailored results. Till now, it is still not convincingly proved in theory why popular MOEAs popular in practice.
Our contributions: This work undertakes an attempt to overcome these shortages by analyzing how several popular MOEAs (NSGA-II, NSGA-III, EMS-EMOA, and SPEA2) approximate the Pareto front of the LARGEFRONT', benchmark (denoted by LF)) proposed in [HN09]. Note that we do not consider MOEA/D here, since it is structurally very different from the domination-based algorithms analyzed in this work and poses additional challenges due to its decomposition mechanism. We prove that, for LF with problem size n, these four popular MOEAS achieve an additive e-approximation of LF', better in an expected number of O( logn) fitness evaluations (see Theorems 9 12 14 and existing result from [N009 showed that the GSEMO fails to accomplic issh this task in expected polynomial time (see Theorem 5. We also provide a general theorem showing an expected runtime of (un log n) fitness evaluations for finding an additive e-approximation of LF for any MOEA with population size at most fa satisfying a general property of the selection of the next population (see Theorem 7 Compared with the GSEMO, which only applies the dominance criterion for survival selection, these popular MOEAs additionally use a criterion to increase the diversity of the survive individuals in the next population. This will result in a better approximation when the number of Pareto front points is large. This provides the first mathematical runtime analysis showing the superiority of popular MOEAs over simpler ones like the GSEMO for the central task of computing good approximations to the Pareto front.
16. In contrast,
The rest of the paper is organized as follows. Section 2 defines the approximation measure and the known LARGEFRONT, benchmark. Section 3 presents a general approximation theorem, and Section 4 applies it to establish runtime guarantees for NSGA-II, NSGA-IIII SMS-EMOA, and SPEA2 for computing good approximations. Section concludes our paper.
2 Preliminaries
2.1 Additive E-Approximation
We first recall some basic definitions for the maximization of a bi-objective problem f= (f1, fe) Ω 2 defined on the search space Ω. For x, E Q. say that weakly dominates y. written as x = y. (x) 2 fy( and that f2(x) Z f2(y), and x dominates y. written as x > y. if in addition at least one inequality is strict. A solution E Ω is a Pareto optimum if no other solution dominates it. The Pareto set consists of all Pareto optima. The set of corresponding objective values is called the Pareto front.
When the Pareto front is excessively large or infinite, covering the whole Pareto front is infeasible and a good approximation of the Pareto front becomes natural goal. There are multiple approximation measures, such as e-dominance [TDZ402, generational distances [VVL98 BT03| CCRS04, hyper-
volume indicator (ZT98) maximal empty interval size [DD25) Here we adhere to the original
2

---

LARGEFRONT,, work [HN09], and use additive e-approximation (see Definition to evaluate how well of points approximates the Pareto front. It is built on the additive e-dominance, first defined in [ that relaxes the usual dominance relation by allowing an additive slack in each objective.
Definition (LTTDZ0)). A set of objective vectors T is an additive e-approxination of f {0, 13. + Tm if and only if for each objective vector
f((0,1}"). there exists at least one objective vector u E T that additively E-dominates where an objective vector u is said to additively 8-dominate (written as u Ze U) if and only if us + 2 vs for all E ml....,m.
2.2 The LargeF ront Benchmark
LARGEFRONT, is a benchmark proposed in HNOS and HNO9]. exists in two variants, LF. [NN08] and LF' [HN09]. Different from existing benchmarks for theoretical analysis, like
COCZ [TZZ4] LOTZ LTZ04), ONEMINMAX [LLO OJZJ [DZ21] which have the polynomial Pareto fronts, for both variants the Pareto fronts have exponential size (see Lemma 3 Since LF shows more similarity to the arguably most popular ONEMINMax benchmark, this paper will only discuss this variant. We hope that our findings will inspire analyses of MOEAs the other variant L.g. Following is the definition of LF".
Definition 2 (HNO9)). Letn N be even and The function LF((2) {0, 13 2 is defined by
LF2,, (FF
(2/x'11
+ (2
2 (V
minfl='11, [a'lo] 2 vn.
LF" (x)) =
12/="11-E
otherwise
(2/x²lo n/2 BV (x"))
minf[='1,, |a' 2 vn
LF" (x))
1/
otherwise.
where x' and x" are the prefix and suffix of length n2/2 of x, 1-11 and lo denote the number of ones and the number of zeros in this bitstring respectively, and (V 10, - R is defined by
(v) = Σm 2n' -y,, computing the decimal value of the n' nit binary number y.
An illustration of this function is given in Figure 1
1bii do
1)
le BA wnn
17
lef BVTe
Rvie 16 -
36
32
Mi of De =T
Iej =0.==
28
24
8
15)
lul Jeff
4-
0-
12
20 (F'c(())
24
36
Figure 1: Objective space LF. for 1 and n 36.
As stated in HN09) bitstrings are Pareto optimal. Since any two solutions x and y such that x" # y have different objective values, the size of the Pareto front grows exponentially with the

---

problem size n. The following lemma collects the results of the Pareto set and the Pareto front w.r.t.
LF.. Note that we use the notation of [a..b] := {a, a .,...,b) for $ and a, b E Z.
Lemma 3 ((HN99) ) The Pareto set of LF is S* -1011%² that is, every bitstring of length is Pureto optimal. The Pareto front is F {((2k 222n/2 (n 2k + 2-n/222nn/2 a))=) k E m2..m/2), E [0..2"/2 1]}, where = 0 for k < vn or k > n/2 vn, and for vn S k S n/2 vn, ranges over all integers in [0..2n/² - 1}.
The following lemma from [HN09] gives necessary and sufficient condition for a set to be an additive E-approximation w.r.t. LF"
Lemma 4 ((HNO9). set is an additive E-approximation of LF and only if for each l {0. n/2) there exists solution x E with |<'] k.
As common in the evolutionary computation theory community DN201, by runtime we usually mean the number of fitmess evaluations to reach specific goal. Horoba and Neumann [HN09 proved that the GSEMO fails to achieve an additive e-approximation of LF, in polynomial runtime.
ZYQ19
Theorem ((HN09)). The runtime until the GSEMO has achieved an additive s-approximation of LF is 20(x with probability 1 2 2-1((
As stated above, in this work, we aim to analyze the runtime of popular MOEAs achieve an additive e-approximation of LF...
3 General Approximation Theorem
Before proving runtime results specific to a popular MOEA, this section will formulate general theorem asserting a runtime guarantee (to reach an additive s-approximation w.r.t. LF") ) for general MOEA framework. It will be then used prove runtime guarantees of popular MOEAs in next section. We believe that it will be useful also for future research on LF Algorithm states the general MOEA framework regarded in this section. The population (the set of solutions) IS initialized uniformly at random. In each generation, the algorithm chooses the mating population, generates offspring individuals, and then uses survival selection to determine the next population. We note that this framework with À = 1, Pe = O, random parent selection, bit-wise mutation, and dominance only survival selection gives the GSEMO. The setting of PP)). the survival selection of non- non-dominated sorting and crowding distance gives the NSGA-II. The NSGA- corresponds to Prl, survival selection by non-dominated sorting and reference point mechanism. The setting of A l the survival selection of non-dominated sorting and hypervolume contribution indicator gives the SMS-EMOA. The SPEA2 fits this framework by maintaining a fixed population size, generating À offspring per iteration, and employing strength-and-densitt estimation for survival selection.
Algorithm 1: A general MOEA framework
Initialize Po uniformly at random;
2 for ( /= 2, do
Choose À individuals from P. to form the mating population P/; Generate the offspring population Q, with individuals from P. via applying crossover
(with crossover rate pc) and mutation;
Select the next population Pt+1 from R₁ = P. U Q via a specific survival selection;
We define the following property for the survival selection that will be used for our general theorem. Definition (Property A). An MOEA, or more specifically its survival selection procedure, satisfies Property A on LF', if whenever some time the combined population Re = P. U Q₂ contains with |x' 1= = k; the next population P.41 contains a with ly'l1 = k, where (y') is the first half sub-bite bitstriisiig of x (y).
Property ensures that once value of l 1-bits the first half of bitstring discovered, will never be lost. Together with Lemma 4 we bound the expected number of fitness evaluations to achieve an

---

additive e-approximation of LF, by O(pn log n) in the following theorem. Due to the space limit, we omit all our proofs here. They can be found the extended of this paper on the arviv preprint server.
Theorem 7. Let the crossover rate Pe [0, 1). Let l be upper bound the size of parent population P with > n/2, Let X be the size of offspring population Q with À = O(u). Consider using Algorithm 1 with random selection, one-bit mutation or bit-wise mutation generate P', and survival selection with Property A, to optimize LF Then the expected number of fitness evaluations for achieving an additive E e-approximation is (wnlog n).
Approximation Guarantees for Popular MOEAs
Based on the general approximation theorem (Theorem / in the previous section, this section will prove (n² log n.) expected runtimes for obtaining an additive e-approximation w.r.t. LF', for four widely used MOEAs, namely NSGA-II, NSGA-IIII SMS- AAS-EMOA, and SPEA2, all by majorly proving that these popular MOEAs satisfy Property A.
4.1 NSGA-II Using the Current Crowding Distance
The Non-dominated Sorting Genetic Algorithm II (NSGA-II [DAM022 ), is the most widely used MOEA in practice. As stated in the Section Zheng et al. ZLD22 Z conducted the first mathematical runtime analysis of the NSGA-II, inspiring a series of follow-up studies. Among them, only Zheng and Doerr DD22 AD25 analyzed how the NSGA-II approximates the Pareto front. These works suggest that the original NSGA-II has difficulties computing good approximation. In contrast, they also proved that simple modification. like using the current crowding distance in the survival selection [KD or steady-state mode (DNLA09, will result in near-ideal approximation of the Pareto front for the ONEMINMAX benchmark. Since the proofs are quite similar for these two variants, this work will only discuss the NSGA-II with the current crowding distance. We conjecture similar results for the steady-state state variant.
The NSGA-II (see Algorithm 2 fits into the general MOEA framework (Algorithm with fixed population size N, offspring population size À N, and special survival selection. The survival selection uses the dominance as the first criterion. More precisely, it uses the non-dominated sorting to divide the combined population R, into several fronts Fi, F2.... such that F; consists of the non- dominated individuals of R, A U F,. For the critical front F+- with Ei= |F| < S [Fy, the crowding distance is calculated (see Algorithm 3p. The original NSGA-II directly removes
I0 Fil N individuals with smallest crowding distance in Fi- and selects the remaining ones in Fi.. This strategy only uses the initial crowding distance, and ignores the changes of crowding distance of remaining individuals after each removal. Hence, Kukkonen and Deb (D06) proposed the survival selection with the current crowding distance and Zheng and Doerr (Z25 proved approximation advancing against the original one. Since each removal only affects the crowding distance of four individuals, the update of the crowding distance can be effectively implemented [D255]
The following lemma shows that the NSGA-II with current crowding distance satisfies Property A when the population large enough.
2 3 2n + 3. Consider using the NSGA-II -II with the survival selection based on the current crowding distance to optimize LF', with problem size Assume that at some iteration the combined parent and offspring population R; = Pt U Qt contains an individual x with |x') = Then the next parent population Pe-1 also contains an individual y with yy'l k.
Lemma 8. Let N
With Lemma we casily apply Theorem to the NSGA-II with current crowding distance and obtain O(n log n) expected runtime to reach additive e-approximation w.r.t. LF', when setting N = (n))
Theorem Let 3 +3ddnd Pc. E [0, 1). Consider using the NSGA-II with the survival selection based on the current crowding distance and employing uniform selection and one-bit muiation or bit- wise mutation to optimize L.F', with problem size n. Then after an expected number of O(N logn) fitness evaluations, the population is an additive e-approximation w.r.t. LF..
5

---

Algorithm 2: NSGA-II using current crowding distance [KD06] ZD25
Generate Po by selecting N solutions uniformly and randomly from {0. 1)" with replacement;
for == ........ do
Generate the offspring population Q₁ with size N; Use fast-non--ommintted-sttll in [DPAM02 to divide R2 into fronts F1, F2.....
Find i* 2 1 such that | Fi < N and I Fil 2 N;
Use Algorithm to separately calculate the crowding distance of each individual in F1,...,P' Pi:;
while 1 F N do
7
Let a be the individual with the smallest crowding distance in Fe, chosen at random in case tie;
Find four neighbors of two in the sorted list with respect to fi and two for fz. Update the crowding distance of these four neighbors;
10
F.. F+- \ {x};
P+1 = U F
11
Algorithm 3: Computation of the crowding distance cDis(S)
DPAM02
Input: S {S1, S.,.., S|s})
Output: cSis(S)
(D)ss(())))) where (Sis((:) is the crowding
distance for S²
eDis(S) (0....,0))
2 for each objective fi do
Sort S in order of descending fi value: , cDis(S..)) +o0, cDis(S..js) +o0;
for j = 2.. do
f((S()-1) (S(,
DDis(S.,)) = cDi, [((S..)) [s((,))))
4.2 NSGA-III
The NSGA-II was reported to encounter difficulties for problems with more objectives (and recently it was proven that least exponential runtime is needed to cover the full Pareto front for mONEMINM AX, with three and more objectives [ZD24a]). Deb and Jain (J14) proposed new variant called the Non-dominated Sorting Genetic Algorithm III, NSGA-III, to overcome this difficulty. It also uses two criteria for the survival selection, but replaces the second criterion of the crowding distance in the NSGA-II by reference point mechanism. Other components the same as in the NSGA-II, see Algorithm 5
We now give brief introduction to the reference point mechanism. After dividing the combined population R₂ into serval fronts, all fronts F; with < i are selected and denoted as Z,. Following the first theory work for the NSGA-III [D233]
the improved and more detailed normalization in [DR19] That is, all individuals in Z, are normalized by fz) fx())=3 where 2 and synd are the ideal point estimate and the Nadir point estimate of objective j. Each normalized individual is then associated with reference point with the smallest distance. Finally it repeatedly selects the reference point with the fewest already-chosen solutions (breaking ties randomly), then adds the unselected solution closest to that reference point (again breaking ties randomly) until N Σ Di= of solutions are selected. See Algorithm for more details.
2
Fll number
The runtime of the NSGA-III is studied via the theoretical means since 2023, see [W233 ODNS24
WD24]. Those works all focused on the performance to cover the full Pareto front. Very recently, Deng al. [DZD25 established the first approximation guarantee of the NSGA-III and proved that the number of reference points is more important than the population size, which appeared be an important parameter for the NSGA-II [DD22 DQ23b). Until now, there is no other approximation

---

Algorithm 4: Normalization with threshold parameter Enad BDR
Input: F1 ...... Fi-
non-dominated fronts; f (fi,.... fm): objective function;
E Im observed max in each objective; 2j E RRm observed min in each objective;
E C Rm extreme points of previous iteration, initially {oo};
for j = 1,2, .......... m do
2j min 23. min f=)));
2) max [2)" m. fz(2));
Determine an extreme point e0i) in the j-th objective from R U E using an achievement scalarization function;
E {el)}:
volid False;
e(1)) ..... e(m) are linearly independent then
walid = True;
Let H be the hyperplane spanned by e(!) e eim);
10
for 1,2, M do Determine the intercept I of H with the j-th objective axis;
12
if 1 2,240 nad and 1 S 2j then snad 3 Ljj
13
14
else
valid False; break;
16
if valid False then
18
for j = 1 M do gnad )
19
m (z));
20
for j = 1,2, ..... m do
21
gnal 2j + Enad then gnad max f, fz);; )
22
(x))-2mii
23
Define (x)
for each x E (0, 1) and j 1,..., m. gynn
theory for the NSGA-III. Before we prove that the NSGA-III satisfies Property A, we first show the following lemma that the extremal objective values in the combined population Rd will pass on the next population P++1. Note that Deng et al. [DZD255 proved the optimal setting of N N, for approximating ONEMINMAX, and note that Deb and Jain [DJ4 suggests N N, for the general setting. Here we only consider the setting of N N,. It is not difficult to see from the proofs that our results also hold for 2 N,-
Algorithm 5: NSGA-III DIE!
Generate Po by selecting N solutions uniformly and randomly from (0, 1)" with replacement;
2 for t = 0, 1, 2... do
Generate the offspring population Qe with size N:
Use maat--oon-oominted--oom
[DPAM02] to divide R₁ = Pt U Q into fronts Fi, Fe....
Find i* > such that U Fl < N and IU F > N;
Z, = - Fe:
Use Algorithm to select F,. C F,. such that IZ F = N;
7
P = 7 J F.::
Lemma 10. Let N N, 2n and Enad 2 ne. Consider using the NSGA-III to optimize LF, with
problem size Define 2 min min(f,(2) E Re} and 2 max == max (f (x) x E Rt), 1,
7

---

Algorithm 6: Selection based on set U of reference points when maximizing f DJ
Input: Ze the multi-set already selected individuals;
Ff': the multi-set of individuals to choose from;
fni Normalize(f. Z = Z, FF)
Associate each individual E Z, U Ff to the reference point rp(x) based the smallest
distance to the reference rays; For each reference point E U, initialize pr : (x E Ze rp(2) =r]]:
3 Initialize F;" = and = U:
while True do
Let Tmin E U' such that Prain is minimal (breaking ties randomly);
Let Triin FP \\ P7 which is associated with Tmin and minimizes the distance between In (T(rri))) and T'in (breaking ties randomly); if Frim exists then Fi Ff' U (Irmin Priin = Priin + 1; if Zz + |
10
N then
11
return F
12
else
13
U' U' {rmin
Then the next parent population P(t1 will preserve two individuals x, y such that f1(Ø) = = and fi()) =2 2mnax
With Lemma 10 we easily see that once (0, ne) and (ne, 0) are covered by Rg they will be covered by the next population. The following lemma shows that after (0, ne) and (nE, 0) are covered by Rs, Property A will be satisfied.
Lemma 11. Let N = N, > 2n +3 and Eadd ne. Consider using the NSGA-III to optimize LF with problem size n. Assume that at some iteration t, the two extreme points (0, nE) and (nE, 0) are covered by the combined parent and offspring population R2 P. Qr. If Re contains an individual with le' k, then the next parent population P++1 also contains an individual with ly' = k,
and covers (0, nε) and (ne, 0) as well.
With Lemma 10 it is not difficult to obtain the runtime to cover ns) and (nE, 0). Then from Lemma asserting that Property A is satisfied, we use the general approximation theorem (The- orem to obtain an On log n.) (when setting N = (n))) expected runtime to reach an additive e-approximation w.r.t. LF
Theorem 12. Let N = N2 2n + 3. Enad ne and Pe [0, 1). Consider using the NSGA-III with uniform selection and one-bit mutation or bit-wise mutation to optimize LF,, with problem size n. Then after expected number of O log n) fitness evaluations, the population additive e-approximation of LF
4.3 SMS-EMOA
The SMS-EMOA BNE07 can be seen steady-state variant of the NSGA-II in which crowding distance is replaced by the hypervolume contribution indicator. In each generation, it generates one offspring and then only removes individual from R, The hypervolume indicator is the most widely used measure for approximation quality in evolutionary multi-objective optimizations [SIHP20] Given reference point the hypervolume of population S is calculated as
(S) - c U (rshsf(w)] Iriher") \uES
where is the Lebesgue measure. The hypervolume contribution an individual æ E F, is defined A, (z, F.-) == (F-)F:)) HV,(F,- \ {z)) for x E F,.. Algorithm gives the pseudo code of

---

Algorithm 7: SMS-EMOA BNE
Generate Po by selecting N solutions uniformly and randomly from {0. 1) with replacement;
for i == 1, ..... do
Generate one offisping y;
Use fist--on--omminate--oott [DPA to divide RG Pi u {y) into Fi..... F.....,...... Calculate (z, F.:) for all 2 E F2. and find = arg m (2,
Uniformly at random pick q D and P++1 Rs {q)
the SMS-EMOA. It fits into our general MOEA framework (Algorithm) D with fixed population size of N, offspring population size À = 1, and the survival selection based on hypervolume contribution.
Although Bian et al. [BZLQ23] and Zheng and Doerr [ZD24al have analyzed the runtime of the SMS-EMOA on bi- and many cojey-veeettvve benchmarks, its theoretical approximation performance remains unstudied. Brockhoff et al. [BFNO8] proved that the (μr + 1)-SIBEA algorithm, sim- plified version of the SMS-EMOA without fast non-dominated sorting, achieves multiplicative e-approximation of the LARGEFRONT, variant LFF in expected O log n) number of fitmess evaluations. No approximation results for the SMS-EMOA or (μr + 1)-SIBEA on LF', are given. As in the previous sections (also similar to the proof of (μ [u++] 1)-SBBA on L.F. [BN08 ) we first show that the SMS-EMOA has Property A w.r.t. LFF-
Lemma 13. Let N 2 B + 1 and r (f1,T2) with T1 S-E, 12 S -E. Consider using the SMS-EMOA optimize LF', with problem size n. Assume that at some iteration t the combined parent and offspring population R2 contains an individual x with [x')1 k. Then the next parent population P++1 contains an individual y such that 1y'11 k.
2
Combining Lemma 13 with our general theorem (Theorem 7. we obtain the expected runtime of O(Nn log n), which On log n) when N (n),, required to reach an additive e e-approximation w.r.t. LFF.
Theorem 14. Let N 2 n/2
(21,72) with vı S -, S - and Pe E [0, 1). Consider using the SMS-EMON to optimize LF", using uniform selection and one-bit mutation bit-wise mutation with problem size Then after an expected number of O log fitess evaluations, the population is an additive E e-approximation w.r.t. LE'
4.4 SPEA2
The SPEA2 algorithm ZCTTI is one of the most popular MOEAs. In the survival selection at generation I, creates a new parent population P++1 by selecting all non-dominated solutions from R, If 1 is smaller than the population size N, then it is supplemented with the best dominated individuals, determined by the strength and density estimation. If the number of non-dominated individuals exceeds the population size N, a truncation operator is used to iteratively remove solutions from Pt+1 until |P++1| = N. Let o denote the Euclidean distance (in the objective space) of the individual u to its k-th nearest neighbor in RG with = VN X. At each removal, an individual is chosen for removal with Sa e for all o E Pe+1, where
Sa U Y0
P P+1l
tf o.v P [(v0 <l< - A < <.
30
In other words, at each removal, it removes the individual with the smallest ncarest-neighhor distance and ties are broken by comparing their accondnearess distances and so forth. Once a solution is removed, its distances to other solutions are no longer considered. See Algorithm g for more details. The SPEA2 fits into the general MOEA framework (Algorithm with uniform parent selection, and the survival selection based on the truncation operator.
The first runtime analysis of the SPEA2 was conducted very recently RBLQ24] and proved the runtime bounds for the SPEA2 on three commonly used multi-objective problems, namely mONEEMINMX, mL.OTZ, and mOJZJ. Prior work by Horoba and Neumann [NN09 studied the approximation performance RADEMO (a simplified version of the SPEA2), and proved that achieves additive e-approximation w.r.t. LF', in polynomial runtime. Till now, no approximation

---

Algorithm 8: SPEA2I[ZZTTN)
Qo t- solutions uniformly and randomly selected from {0, 1 with replacement and Po 0:
for f = 0,1.2.... do
Pt+1 t- non-dominated solutions in R, Pt U Qu:
if [[++1 N then
Reduce Pr+1 by means the truncation operator;
else if P++1l < N then
L Fill P(+1 with dominated individuals in R,;
for 0,,, do
Generate one offspring r';
10
Q++ - Qt+ U {d'}:
guarantees for the SPEA2 on LF', were given. As in the previous sections, we first prove that the SPEA2 maintains Property A required for our general approximation theorem.
Lemma 15. Let N 2 n/2 2. Consider using the SPEA2 to optimize LF', with problem size n. If at some iteration, the combined population R& contains an individual x with |x') = k, then the next population Pe+1 will also include an individual y with |y'l k.
With Lemma 15 derive an expected runtime of (n log n) to reach additive e-approximation w.r.t. LF by setting N = (n) in our general approximation theorem.
Theorem 16. Let N 2 n/2 + 2 and Pe E [0, 1). Consider using the SPEA2 with uniform selection and one-bit mutation or bit-wise mutation to optimize LF' with problem size n. Then after an expected ONN log n) number of fitness evaluations, the population is additive s-approximation w.r.t. LF.
Conclusion and Discussion
The question of why popular MOEAs are popular in practice was not yet convincingly answered by theoretical methods. The few results indicating advantages only considered the performance cover the full Pareto front on newly designed benchmarks. This work tackled this question by considering the approximation ability of several popular MOEAs the established LARGEFRONT benchmark.
In contrast to the 20(x fitness evaluations (with high probability) the GSEMO takes to reach an gave general theorem showing polynomial runtimes for any MOEA additive e-approximation, O (n log n)) expected runtimes for four widely used MOEAs, namely with Property A, and proved
NSGA-II, NSGA-III, SMS-EMOA, and SPEA2. The reason for this advantage the second selection criterion of these popular MOEAs ensuring good diversity in the survival selection, compared to the GSEMO that relies only on the dominance criterion. This the first mathematical runtime analysis showing and explaining the superiority of popular MOEAs over simpler ones like the GSEMO for the central task of computing good approximations to the Pareto front. This work also the first approximation study for the SMS-EMOA.
Our results and proofs suggest advantages in approximation also for other benchmarks with large number of Pareto front points, but a more thorough and rigorous analysis on more general benchmark classes is necessary support this claim.
Acknowledgments and Disclosure of Funding
This work was supported by National Natural Science Foundation of China (Grant No. 62306086, 62350710797), Guangdong Basic and Applied Basic Research Foundation (Grant No. 2025A151501 1936), Xinjiang Tianshan Innovative Research Team (2025D14009), and Science, Technology and Innovation Commission of Shenzhen Municipality (Grant No. GXWI20020818111001188 This research benefited from the support of the FMJH Program PGMO.
10

---

References
[AD1I]
Anne Auger and Benjamin Doerr, editors. Theory of Randomized Search Heuristics. World Scientific Publishing, 2011.
[BDR19] Julian Blank, Kalyanmoy Deb, and Proteek Chandan Roy. Investigating the normalization procedure of NSGA-III. In International Conference on Evolutionayy Multi Multi-rriterion Criterion Optimization, EMO 2019, pages 229-240. 240. Springer, 2019.
[BFN08] Dimo Brockhoff, Tobias Friedrich, and Frank Neumann. Analyzing hypervolume indicator based algorithms. In Porallel Problem Solving from Nature, PPSN 2008, pages 651-660. Springer, 2008.
[BNE07]
Nicola Beume, Boris Naujoks, and Michael Emmerich. SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181: 181:163--169, 2007.
[BQ22]
Chao Bian and Chao Qian. Better running time of the non-dominated sorting genetic algorithm II (NSGA-II) by using stochastic tournament selection. In Parallel Problem Solving From Nature, PPSN 2022, pages 428 4.14. Springer, 2022.
[BT03]
Peter A.N. Bosman and Dirk Thierens. The balance between proximity and diversity in multiob- jective evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 7:174 188, 2003.
[BZLQ23]
Chao Bian, Yawen Zhou, Miqing Li, and Chao Qian. Stochastic population update can provably be helpful in objectvo evolutionary algorithms. In International Joint Conference on Artificial Intelligence, IJCAI 2023, pages 5513-5521. ijcai.org, 2023.
[CCRS04] Carlos A Coello Coello and Margarita Reyes Sierra. A study of the parallelization of a coevolu- tionary multi-bbjective evolutionary algorithm. In MICAI 2004 Advances in Artificial Intelligence: Third Mexican International Conference Artificial Intelligence, Mexico City, Mexico, April 26-30, 2004. Proceedings pages 688 697. Springer, 2004.
[DDHW23] Matthieu Dinot, Benjamin Doerr Ulysse Hennebelle, and Sebastian Will. Runtime analyses of multi-objective evolutionary algorithms
presence of noise. International Joint Conference on Artificial Intelligence, IJCAI 2023, pages 5549 5557. ijcai.org. 2023.
[DK255]
Benjamin Doerr, Tudor Ivan, and Martin S. Krejea. Speeding up the NSGA-II with a simple tie-breaking rule. In Conference on Artificial Intelligence, AAAI 2025, pages 26964-26972. AAAI Press, 2025.
[DJ14]
Kalyanmoy Deh and Himanshu Jain. An evolutionary many-ohjective optimization algorithm using snference-pointtbaaee nondominated sorting approach, part I: solving problems with box constraints. IEEF Transactions on Evolutionary Computation, 18:577-601, 2014.
[DN20] Benjamin Doerr and Frank Neumann, editors. Theory of Evolutionary Computation ReviitattiooRReentt Recent Devel- opments Discrete Optimization. Springer, 2020. Also available at http://wcwiixxooyycchhiiieg Baaabo//Bejaaii..Dooe
_ecrrruncuannnnnn www.annn_ooo..nnnnneoeeee book.html
[DNLA09] Juan Durillo, Antonio Nebro, Francisco Luna, Enrique Alba. On the effect of the steady- state selection scheme in multi-objective genetic algorithms. Evolutionary Multi- Criterion Optimization: 5th International Conference, EMO 2009, pages 183-199 197. Springer, 2009.
[DOS24] Duc-C Duc-Cuong Dang, Andre Opris, and Dirk Sudholt. Illustrating the efficiency of popular evolutionary multi-objective algorithms using runtime analysis. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2024, pages 484 494-492. ACM. 2024.
[DOS25]
Duc-Cuce Muc-Cuong Dang, Andre Opris, and Dirk Sudholt. Why dominance is not enough: Lessons from practical evolutionary multi-objective algorithms. In Genetic and Evolutionary Computation Conference. GECCO 2025, pages 1604-1612. ACM, 2025.
[DOSS23a] Duc-Cuong Dang, Andre Opris, Bahare Salehi, and Dirk Sudholt. Analysing the robustness of NSGA-II under noise. In Genetic and Evolutionary Computation Conference, GECCO 2023. pages 642-651. ACM, 2023.
[DOSS23b] Duc-Cuong Dang, Andre Opris, Bahare Salehi, and Dirk Sudholt. proof that using crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation. In Conference on Artificial Intelligence, AAAI 2023, pages 12390-12399 AAAI Press, 2023.
[DPAM02] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan. A fast and elitist multiohjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6: 6:182-197, 2002.
[DQ23a]
Benjamin Doerr and Zhongdi Qu. A first runtime analysis of the NSGA-II on a multimodal problem. IEEE Transactions Evolutionary Computation, 27:1288 1297, 2023.

---

[DQ23b]
Benjamin Doerr and Zhongdi Qu. From understanding the population dynamics of the NSGA-II to the first proven lower bounds. In Conference on Artificial Intelligence, AAAI 2023, pages 12408-12416. AAAI Press, 2023.
[DZ21]
Benjamin Doerr and Weijie Zheng. Theoretical analyses of multi-objecctvve evolutionary algorithms multi-modal objectives. In Conference Artificial Intelligence, AAAI 2021, pages 12293-12301. AAAI Press, 2021.
[DZD25]
The first thcoretical approximation guarantees for the non-dominated sorting genetic algorithm III (NSGA-III). In International Joint Conference on Artificial Intelligence, IJCAI 2025. pages 8867-8875. ijcai.org. 2025.
Renzhong Deng, Weijie 7heng, and Benjamin Doerr.
[D] Renzhong Deng, Weijie Zheng, Mingfeng Li, Jie Liu, and Benjamin Doerr. Runtime analysis for state-of-the-art multi-objective evolutionary algorithms the subset selection problem. In Parallel Problem Solving from Nature, PPSN 2024, Part III, pages 264-279. Springer, 2024.
[GL10]
Oliver Giel and Per Kristian Lehre. On the effect of populations in evolutionary multi-objective optimisation. Evolutionary Computation, 18:335-356, 2010.
[HN08]
Christian Horoha and Frank Neumann. Benefits and drawbacks for the use of epsilon-dominance in evolutionary multi-objective optimization. In Genetic and Evolutionary Computation Conference, GECCO 2008, pages 641-648. ACM, 2008
[HN09]
Christian Horoba and Frank Neumann. Additive approximations of pareto-optings sets by evo- lutionary oulti-objective algorithms. In Foundations of Genetic Algorithms, FOGA 2009, pages 79-86. ACM, 2009.
[Jan13]
Thomas Jansen. Analyzing Evolutionary Algorithms- The Computer Science Perspective. Springer, 2013.
[KD06]
Saku Kukkonen and Kalyammoy Deb. Improved pruning of non-dominated solutions based on crowding distance for bi-objective optimization problems. In Conference on Evolutionary Computation, CEC 2006, pages 1179 1186. IEEE, 2006.
[LTDZ02]
Marco Laumanns, Lothar Thiele, Kalyanmoy Deb, and Eckart Zitzler. Combining convergence and diversity in evolutionary multiobjective optimization. Evolutionary Computation, 10:263-282, 2002.
02] Marco Laumanns, Lothar Thiele, Eckart Zitzler, Emo Welzl, and Kalyanmoy Deb. Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem. In Parallel Problem Solving from Nature, PPSN 2002, pages 44-53. Springer, 2002.
[LTZ04]
Marco Laumanns, Lothar Thiele, and Eckart Zitzler. Running time analysis of multiobjective evolu- tionary algorithms on DeeuloB functions. IEEE Transactions on Evolutionary Computation, 8:170-18: 182, 2004.
[1.ZD25] Mingfeng Li, Weijie Zheng, and Benjamin Doerr. Scalable speed-ups for the SMS-EMOA from simple aging strategy. In International Joint Conference on Artificial Intelligence, IJCAI 2025. pages 8885-889) ijeai.org, 2025.
[NW10] Frank Neumann and Carsten Witt. Bioinspired Computation in Combinatorial Optimization Algorithms and Their Computational Complexity. Springer, 2010.
[ODNS24] Andre Opris, Due Cuong Dang, Frank Neumann, and Dirk Sudholt. Runtime analyses of NSGA-III on many-objective problems. In Genetic and Evolutionary Computation Conference, GECCO 2024, pages 1604. ACM, 2024.
[RBLQ24] Shengjie Ren, Chao Bian, Miqing Li, and Chao Qian. A first running time analysis the Strength Parcto Evolutionary Algorithm 2 (SPEA2). In Parallel Problem Solving from Nature, PPSN 2024, Part III, pages 295-312. Springer, 2024.
[SIHP20] Ke Shang, Hisao Ishibuchi, Linjun He, and Lie Meng Pang. A survey on the hypervolume indicator in cvolutionary multiobjective optimization. JEEE Transactions on Evolutionary Computation, 25(1):1-20, 2020.
[VVL98] David A Van Veldhuizen and Gary B Lamont. Evolutionary computation and convergence to pareto front. In Late Breaking Papers at the Genetic Programming 1998 Conference, pages 221-228. Stanford University Bookstore, 1998.
[WD23] Simon Wietheger and Benjamin Doem. A mathematical runtime analysis of the non-dominated sort- ing genetic algorithm III (NSGA-III) In International Joint Conference on Artificial Intelligence, IJCAI 2023, pages 5657-5665. ijcai.org 2023.
[WD24] Simon Wietheger and Benjamin Doerr. Near-tight runtime guarantees for many-objective evolu- tionary algorithms. In Parallel Problem Solving from Nature, PPSN 2024, Part IV, pages 153 168. Springer, 2024.
12

---

[2D22]
Weijie Zheng and Benjamin Doerr. Better approximation guarantees for the NSGA-II by using the current crowding distance. In Genetic and Evolutionary Computation Conference, GECCO 2022.
pages 611-619, ACM, 2022.
[2D23]
Weijie Zheng and Benjamin Doerr. Mathematical runtime analysis for the non dominated sorting genetic algorithm II (NSGA-II), Artificial Intelligence, 325:104016, 2023.
[ZD24a]
Weijie Zheng and Benjamin Doerr Runtime analysis for the NSGA-II: proving, quantifying, and explaining the inefficiency for many objectives. IEEE Transactions on Evolutionary Compitation, 28:1444: 1444-4444,, 2024.
[ZD24b]
Weijie Zheng and Benjamin Doerr. Runtime analysis the SMS-EMOA for many-objective optimization. In Conference on Artificial Intelligence, AAAI 2024, pages 20874-20882. AAAI Press, 2024.
[ZD255]
Weijie Zheng and Benjamin Doerr. Approximation guarantees for non-dominated sorting genetic algorithm II (NSGA-II), IEEE Transactions on Evolutionary Computation, 29:891-905, 2025.
[ZLD22] Weijie Zheng, Yufei Liu, and Benjamin Doerr dominated sorting genetic algorithm (NSGA-II). In Conference on Artificial Intelligence, AAAI 2022, pages 10408- 10416. AAAI Press, 2022.
mathematical runtime analysis the non-
[ZLDD24] Weijie Zheng, Mingfeng Renzhong Deng, and Benjamin Doem. use the Metropolis algorithm for multi-objective optimization? In Conference on Artificial Intelligence, AAAI 2024, pages 20883-20891. 1. AAAI Press, 2024.
[ZLTOI] Eckart Zitzler, Marco Laumanns, and Lothar Thiele. SPEA2: Improving the strength Pareto evolutionary algorithm. TIK report, 103, 2001.
[ZT98]
Eckart Zitzler and Lothar Thiele. Multiobjective optimization using evolutionary algorithms comparative case study. In Parallel Problem Solving from Nature, PPSN 1998, pages 292-301. Springer, 1998.
[ZYQ19] Zhi-Hua Zhou, Yang Yu, and Chao Qian. Evolutionary Learning: Advances in Theories and Algorithms. Springer, 2019.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Our main contribution is that establish the first mathematical runtime analysis showing the superiority of popular MOEAs over the simpler ones like the GSEMO for the central task of computing good approximations the Pareto front. Our technical claim is that all four widely used MOEAs (NSGA-II, NSGA-III, SMS-EMOA, SPEA2) achieve an additive e-approximation of the LF's benchmark expected O log n) number of fitness evaluations, contrasting the existing result of the exponential lower bound for the GSEMO. This claim accurately reflects our contribution based on the background introduction and literature review in abstract and introduction.
Justification:
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations in Section Although results might also indicate the advantages in approximation for other benchmark with large number of Pareto front points (a property that naturally holds for Pareto front curve containing continuous segment in continuous optimization), a more thorough and rigorous analysis on a more general benchmark classes will make theoretical findings more appreciated, and optimistic and shall try to address our future work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't aakknwlldgge in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification: All the theorems, lemmas, and proofs in this paper are numbered, cross- referenced. All required assumptions are stated precisely, e.g.. Theorem 7 specifies the Property A and the bounds μ4, X, Pe- Due to the page limit, complete, formal proofs are available in the supplementary material. Moreover, all intermediate results and classical lemmas invoked, e.g., Lemma R are cited with precise references.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: The paper is a theory paper and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
cases, in which
15

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (htips//miips.cc/ubblcc quiddss/CdeSuubmissionnPP
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https) for more details.
httpps.c/public/gudeee.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
We have read and strictly follows the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This work is purely theoretical, deriving approximation guarantees for widely used MOEAs on LF. While these insights may eventually deepen our understanding of algorithm behavior and have potential societal consequences, none of which we feel must be explicitly emphasized here. The main contribution of this paper is to advance the thcoretical understanding of popular MOEAs.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
17

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithede prtrss/whhhode.ccmaaatassee has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
19

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer our LLM policy http:://obuuis.ccccooocrre///sss for what should or should not be described.
20


Reviews:
[{"review_id": "d4s8FRPIV1", "reviewer": "Reviewer_LAZd", "summary": "This paper attempts to provide a theoretical explanation for the widespread use of popular multi-objective evolutionary algorithms (MOEAs) by analyzing their expected runtime performance. Specifically, the authors analyze four popular MOEAs—NSGA-II, NSGA-III, SMS-EMOA, and SPEA2—on the LargeFront benchmark, and prove that each of them has an expected runtime of $O(n^2 \\log n)$. The main contribution of this paper lies in establishing a theoretical runtime bound for several popular MOEAs on a benchmark specifically designed to model problems with large Pareto-optimal sets.", "questions": "- Could the authors clarify why decomposition-based MOEAs, such as MOEA/D, are not included in this theoretical study? A discussion on the exclusion of this important class of algorithms would help clarify the scope and limitations of the work.\n- The choice of algorithmic parameters, such as the crossover rate used in the four MOEAs, requires further clarification. It would be helpful to explain whether these parameters have any impact on the theoretical analysis. For instance, it is unclear why the crossover rate is set to 0 in SMS-EMOA and SPEA2.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strength\n- The paper provides theoretical justification for the use of MOEAs in solving multi-objective optimization problems, contributing to a better understanding of their practical effectiveness.\n- Overall, the paper is well written. \n\nWeakness:\n- The paper does not include any theoretical analysis for widely used decomposition-based MOEAs, such as MOEA/D, which limits the generality of the conclusions.\n- The theoretical analysis is limited to a relatively simple benchmark (LargeFront), which may not fully reflect the complexity of real-world multi-objective problems.", "was_revised": true, "final_justification": "The authors have clarified why MOEA/D was not included in their analysis and have explained the relevance of the benchmark problems to real-world applications. Overall, I believe this work is significant and provides valuable theoretical insights into four popular MOEAs.", "rebuttal": "Thanks a lot for your positive comments. We now respond to the weaknesses and questions one by one.\n- **(W1 \\& Q1) The analysis of the MOEA/D not included.** (1) As stated in the second paragraph in Section 1, the research line, aiming to understand why popular MOEAs are widely used, discussed NSGA-II, NSGA-III, and SMS-EMOA. Therefore, this work follows the same line and only discusses the MOEAs that do not decompose the original multi-objective problems, and this is the primary reason why the MOEA/D is not included. (2) Besides, also stated in the second paragraph in the introduction, \"the simpler algorithm\" (like GSEMO), compared to which we expect to see the advantages of popular MOEAs, only uses the dominance criterion for the survival selection. The popular MOEAs analyzed in this work share the same mechanism where an additional criterion is used. The comparison between these MOEAs with the simpler algorithm will lead to a clean and clear result on the effect of the additional criterion. However, the decomposition-based MOEAs like MOEA/D have a quite different framework, not good for cleanly locating the effect of a sole component. But we thank the reviewer for pointing out the important MOEA/D, and will set the approximation analysis of the MOEA/D as our interesting future work. \n- **(W2) Only limited to a simple benchmark (LargeFront).** (1) We first note that LargeFront is not one benchmark but a class of benchmarks w.r.t. $\\varepsilon$ (See Definition 1, Page 2). (2) Its relation to the real-world problems. As stated in the second paragraph in Section 2.1, \"the theory of evolutionary algorithms is majorly built on the discrete space\" and other widely analyzed benchmarks \"contain the polynomial number of Pareto (front) points\". LargeFront has \"exponential Pareto front points \", and is much closer to \"the continuous optimization as a segment of a continuous curve in the Pareto front contains infinite points\". Our results on LargeFront might shed some light on the understanding of the popular MOEAs for real-world continuous optimization. \n- **(Q2) The choice of algorithmic parameters.** (1) In general, the settings of related parameters are listed in the statement of our theorems. (2) Crossover rate. We mentioned that the crossover rate is set to 0 for the SMS-EMOA and the SPEA2, when we discussed how these two algorithms fit into our framework in Algorithm 1. This setting follows the previous theoretical studies on these algorithms, see [BZLQ23,ZD24c,RBLQ24] in the Reference section. Indeed, our general theorem (Theorem 7) holds for any fixed crossover rate $p_c\\in[0,1)$ (see the statement of Theorem 7). As demonstrated in our proofs, the crossover rate does not influence the asymptotic runtime bounds we establish. Thanks for raising this question, and we will make it clearer in our future version."}, {"review_id": "mHO79xepHa", "reviewer": "Reviewer_Pp8Y", "summary": "This paper establishes, for the first time, formal runtime guarantees that explain the superior performance of widely-used Multi-Objective Evolutionary Algorithms (MOEAs)—namely NSGA-II, NSGA-III, SMS-EMOA, and SPEA2—over simpler algorithms such as GSEMO. Specifically, the authors prove that these algorithms can compute an additive ε-approximation to the Pareto front of the LF′ₑ benchmark in expected O(n² log n) fitness evaluations, while GSEMO requires exponential time.\n\nThe analysis is grounded in a general theorem (Theorem 7) applicable to any MOEA satisfying a structural diversity-preserving condition called Property A. The authors then rigorously verify that all four popular MOEAs satisfy this property under standard settings, leading to provably efficient approximation performance.", "questions": "1. Is the O(n² log n) bound tight? Could it be improved for specific algorithms or tie-breaking strategies, e.g., for NSGA-II with stochastic tournament or steady-state variants?\n\n2. Are there meaningful examples of MOEAs that fail to satisfy Property A? Could the definition be relaxed, or is it necessary for achieving polynomial-time approximation?\n\n3. Could the techniques be extended to Pareto fronts that are non-convex, disconnected, or have degeneracies? For instance, what about problems with dominance plateaus?\n\n4. Are there insights here that suggest how to design MOEAs with provably fast approximation capabilities beyond the four studied?\n\n5. Can your framework handle m > 2 objectives? Or does the structure of LF′ₑ and Property A critically depend on bi-objective formulation?", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths\n\n* This is the first theoretical work to rigorously justify why popular MOEAs outperform simpler baselines like GSEMO on a challenging, established benchmark for multi-objective optimization.\n\n* The results move MOEA theory closer to practical concerns, such as scalable approximation of large or continuous Pareto fronts, which is more relevant than full front enumeration.\n\n* All results are stated with clear assumptions, and complete proofs are provided in the supplementary material. The use of LF′ₑ—an established and difficult benchmark—adds credibility to the claims.\n\nWeaknesses and Limitations: While the theoretical contributions are significant, a few limitations deserve more direct attention:\n\n* All results are derived on the LF′ₑ benchmark. While this is a well-motivated and rigorous test case, it remains a single instance of a broader problem class. The paper does not explore how the results generalize to other test suites, especially noisy, constrained, or real-valued domains.\n\n* Although this is a theoretical paper, providing empirical illustrations (e.g., convergence rates or ε-approximation quality for various algorithms on LF′ₑ) would help contextualize the significance of the runtime bounds and provide guidance for practitioners.\n\n* Real-world optimization often involves noise, discontinuities, or uncertainty. While the authors cite previous work analyzing NSGA-II under noise, this paper does not extend its framework or results to such settings, nor does it discuss potential obstacles.\n\nThese limitations do not undermine the core contribution, but a more explicit and detailed discussion—perhaps as a dedicated “Limitations” section—would enhance the paper’s clarity.", "was_revised": true, "final_justification": "My concerns have all been resolved, so I’ll keep my score as it is.", "rebuttal": "Thanks a lot for the positive evaluation and nice words. Indeed, many weaknesses (which you regard as limitations) and questions are quite nice topics for our future work. Thanks again for these suggestions. Here we will give our responses one by one.\n- **(W1) Only LargeFront Benchmark.** Although LargeFront is a benchmark class, we agree that noisy or constrained cases are quite interesting. We would say the real-valued domains (or say on the continuous space) could not be an easy one, as you might know that the current evolutionary theory community mainly works on the discrete search space. We and the theory community will try our best to work more on the continuous space.\n- **(W2) Lack of empirical illustrations.** We agree that empirical validation could help, but to keep the focus and space on the theoretical contributions we chose no experiments in the main paper. \n- **(W3) Lack of discussion on noise, discontinuities, or uncertainty.** We agree that real-world problems often involve noise, uncertainty, and discontinuities. While there has been some theory work on these topic, the theoretical understanding remains limited. Thank you for the suggestion, and we will consider analyzing problems with such properties in future work.\n- **(Q1) Is $O(n\\log n)$ tight? Could it be improved?** Yes, it is asymptotically tight for the algorithms analyzed in the paper. (i) For algorithms with additional mechanisms, an external-archive-based strategy that maintains a small population might achieve better runtime guarantees. (ii) Regarding the specific examples, for the steady-state variant of NSGA-II, we mentioned in the Section 4.1 (Page 5) that \"the proofs are quite similar for these two variants\" and \"we conjecture the similar result of the steady-state variant\". (iii) We also note that lower-bound results in this area are relatively difficult and often require a more delicate analysis of population dynamics. But they are important and we consider this an interesting direction for future work.\n- **(Q2) Are there meaningful examples of MOEAs that fail to satisfy Property $\\mathcal{A}$? Could it be relaxed, or is it necessary?** (i) Yes, even among the four analyzed MOEAs, inappropriate parameter choices, such as an insufficient population size, can cause the algorithm fail to satisfy Property $\\mathcal{A}$. (ii) As our proofs show, Property $\\mathcal{A}$ is crucial for achieving polynomial-time approximation in our framework. While relaxing it may be possible, this would likely require additional mechanisms, e.g. external archives, to preserve lost solutions and maintain sufficient coverage. Exploring such extensions could be an interesting direction for future work.\n- **(Q3) Could the techniques be extended?**  Broadly speaking, our analysis relies on two main components: (i) estimating the probability that the algorithm generates necessary solutions, and (ii) understanding how the survival selection chooses among mutually non-dominated solutions. In problems with dominance plateaus or disconnected fronts, the second aspect becomes especially important. If the survival mechanism retains solutions from multiple regions despite the presence of plateaus or structural gaps, this could provide a basis for extending the analysis to more general Pareto fronts. However, formalizing this would likely require new tools or problem-specific adaptations.\n- **(Q4) Are there insights on designing MEOAs?** Thanks for this nice question, and a potential insight appears to be how the survival selection mechanism balances convergence toward the Pareto front with sufficient diversity across the objective space. Algorithms that maintain well distributed solutions while keeping the population size under control may be more likely to approximate the Pareto front efficiently. We will clarify this more clearly in our future version.\n- **(Q5) Can the framework handle more objectives?** Good question. The current LargeFront problem is a bi-objective problem. A approach similar to how prior works (e.g. [ZD24c]) generalized bi-objective benchmarks to the many-objective cases could be taken to construct an m-objective version of LargeFront. However, at this stage, we have not yet extended our analysis to $m>2$, and both the current formulation of LargeFront and Property $\\mathcal{A}$ rely on the bi-objective setting. Thank the reviewer for pointing this out and we will consider analyzing the approximation for more objectives as an interesting direction for our future work."}, {"review_id": "ESkCeo1MlO", "reviewer": "Reviewer_RTSU", "summary": "This paper aims to address the gap in understanding why popular MOEAs outperform simpler MOEAs (Popular MOEAs have more sophisticated environmental selection strategies). The theoretical properties of four popular MOEAs are revealed using established benchmark problems.", "questions": "- Why is MOEA/D excluded from the analysis? To my knowledge, it is a representative decomposition-based MOEA.\n- What is the rationale for selecting SPEA2? I think that analyzing either NSGA-II or SPEA2 would be sufficient.\n- What is the significance of the exponential growth in the number of Pareto-optimal objective vectors in LARGEFRONT?\n- The mating pool selection is random in all analyzed MOEAs. Would it be possible to consider the mating pool selection strategy in the original MOEAs?", "limitations": "The conclusion section provides a brief discussion.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper is clearly and logically structured.\n- It addresses a research gap by providing a theoretical analysis of existing representative problems.\n- The analysis is conducted under a more appropriate optimality criterion.\n- A generalized theorem (Theorem 7) is proposed.\n\nWeaknesses:\n- The term \"sequential version\" introduced in the abstract is not referenced later; \"steady-state\" is instead used. It is recommended to maintain consistent terminology throughout the paper.\n- In the introduction, the paragraph beginning with \"However, ...\" is difficult to follow despite being a continuation of the previous paragraph. It is suggested to provide specific references and examples in this paragraph directly to clarify the points.\n- The additive $\\epsilon$-approximation seems to be applicable only to LARGEFRONT.\n- The paper does not specify the crossover operator employed. Additionally, there is no explanation provided for setting the crossover probability $p_c=0$ in SMS-EMOA and SPEA2.", "was_revised": true, "final_justification": "After careful consideration of all the discussions, I have decided to increase my score to support the acceptance of this work.\n\nMy major concern is the consistency of the assumptions in the theorems. The author(s) have agreed to provide proofs based on consistent assumptions in the revised version.", "rebuttal": "Thanks a lot for your comments and questions. We believe that our following responses will properly address them (we also note that some of the concerns might come from a misunderstanding), and hope that it raises the appreciation.\n- **(W1) Writing suggestion: Inconsistent terminology for \"sequential version\" and \"steady-state\".** Indeed, \"sequential version\" and \"steady-state\" are two strategies. We guess the reviewer means the inconsistent terminology for \"sequential version\" and \"using the current crowding distance\". Thanks, and we will modify our writing in our future version.\n- **(W2) Writing suggestion: One paragraph in the introduction.** Thanks, and we will reform it in our future version.\n- **(W3) The additive $\\varepsilon$-approximation only applicable to LargeFront.** It is not ture. As stated in Section 2.2 (Page 3), this additive $\\varepsilon$-approximation was \"first defined in [LTDZ02], that relaxes the usual dominance relation by allowing an additive slack $\\varepsilon$ in each objective\". Also from the formal definition (See Definition 3), no restrictions on problem are required. Also note that LargeFront was proposed in 2009, but the additive $\\varepsilon$-approximation was proposed in 2002. In summary, the additive $\\varepsilon$-approximation is a general measure and applicable to other problems. We will make this point clearer in the future version.\n- **(W4) Crossover operator.** Thanks for pointing this out. We noticed that a similar question is raised by the first reviewer. (1) Indeed, our general approximation theorem (Theorem 7) states \"Let the crossover rate $p_c\\in[0,1)$\", which means this result holds no matter the crossover is used (when $p_c\\in(0,1)$) or not (when $p_c=0$). We admit that we are missing the detail about the crossover, and this work uses the single-point crossover as used in the original work of the NSGA-II for binary code. (2) The reason to choose the crossover rate of 0 for the SMS-EMOA and SPEA2: we just follow the same setting (that only mutation is used) in previous theoretical analysis for these two algorithms, see [BZLQ23,ZD24c,RBLQ24]. We will make them clearer in our future version.\n- **(Q1) Excluded MOEA/D.** Thanks for this nice question, and we note that this is also raised by the first reviewer. The reason comes from two parts. (1) The existing theoretical results did not discuss the performance of the MOEA/D, when they tried to understand why popular MOEAs are popular (see the second paragraph in Section 1). (2) We expected a clean and clear understanding on the effect of algorithm component. The analyzed popular MOEAs share the similarity that they do not decompose the multi-objective problems and consider one more criterion in the survival selection, compared with the simple GSEMO where only dominance criterion is used. However, MOEA/D is a different framework. But we thank the reviewer for pointing this out and we will analyze the approximation of the MOEA/D as our interesting future work.\n- **(Q2) Why SPEA2 analyzed? Either NSGA-II or SPEA2 sufficient?**  We both agree that SPEA2 is one of the popular MOEAs. We note that NSGA-II and SPEA2 can behave differently from our theoretical perspective. For example, NSGA-II is proven to be inefficient (at least exponential runtime) to cover the full Pareto front for the OMM-type problems when the number of objectives is at least three (see [ZD24b]). However, [RBLQ24] showed the polynomial runtime for the above problems. Hence, we also analyzed the SPEA2 in addition to the NSGA-II.\n- **(Q3) Significance of the exponential Pareto front points.** Good question. Indeed, as stated in the second paragraph in Section 2.1, \"the theory of evolutionary algorithms is majorly built on the discrete space'' and other widely analyzed benchmarks \"contain the polynomial number of Pareto (front) points\". LargeFront has \"exponential Pareto front points\", and is much closer to \"the continuous optimization as a segment of a continuous curve in the Pareto front contains infinite points\". Our results on LargeFront might shed some light on the understanding of the popular MOEAs for real-world continuous optimization.\n- **(Q4) Other mating pool selection.** Yes, it is possible to consider other mating pool selection, but case-by-case probabilistic calculation is needed. A good evidence is that in the runtime analysis of the NSGA-II [ZD23], random selection, fair selection, and binary tournament selection are analyzed, and all lead to the same runtime complexity. We conjecture that our results also hold for other mating pool selections."}, {"review_id": "XpDtRh3NF9", "reviewer": "Reviewer_2K1g", "summary": "This paper analyzes popular Multi-Objective Evolutionary Algorithms (MOEAs) to explain their practical advantages in approximating the Pareto front. It addresses shortcomings in previous analyses, which often focused on computing the full Pareto front. The study analyzes how existing popular MOEAs approximate the Pareto front of the LARGEFRONT benchmark, specifically LF\\epsilon. The paper proves that popular MOEAs like NSGA-II, NSGA-III, SMS-EMOA, and SPEA2 require an expected O(n^2logn) function evaluations to compute an additive \\epsilon-approximation of the Pareto front of the LF\\epsilon benchmark. This is a significant improvement over the simple GSEMO algorithm, which has previously been proven to take an exponential runtime to approximate the same benchmark.", "questions": "1. The paper uses the additive \\epsilon-approximation definition. Do the authors know if the conclusions of the paper still holds if other definitions of approximation is used? In fact, why did the authors choose the additive version of \\epsilon-dominance instead of (1+\\epsilon)u \\geq v?\n2. Can the authors further elaborate on why LF\\epsilon is chosen, and if it can represent a larger class of benchmarks?\n3. The authors very briefly mention in the introduction that the advantage of MOEAs over GSEMO is the fact that they maintain a diverse population. However, the proofs of how the diversity mechanisms ensure property A and thus ensure the approximation guarantee are all pushed into the supplementary. It would be nice to see an illustration of this in the main paper, or even a dedicated section exploring the different diversity mechanisms, to deepen the analysis provided by the authors.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper provides a well-founded mathematical analysis of popular MOEAs for the task of approximating the Pareto front of the LF\\epsilon benchmark. The focus on approximation instead of recovering the full Pareto frontier is relevant since in practice, the size of the frontier could be exponential and impossible to be recovered fully.\n2. The paper covers a wide range of MOEAs, like NSGA-II, NSGA-III, SMS-EMOA, and SPEA2. This broad coverage enhances the impact and relevance of the findings.\n3. The paper uses the established benchmark LF\\epsilon, which contrasts with previous works that might rely on specialized newly designed benchmarks. \n4. The introduction of the general approximation theory in theorem 7 provides a venue for the analysis of more EAs under the same framework.\n5. The paper is well-written, clearly organized, and easy to read.\n\nWeaknesses:\n1. A major weakness is the lack of empirical validation. Even though the paper is theoretical in nature, its practicality could be greatly improved by including experiments that complement the theoretical results.\n2. The paper uses only one benchmark LF\\epsilon. It brings into question on the generalizability of the results on other benchmarks.", "was_revised": true, "final_justification": "The paper provides insights on several popular MOEAs. As other reviewers have mentioned, the paper is strong is its core contribution and the problem studied here is valuable. This is mainly the reason that I think the paper should be accepted. The paper has its drawbacks. For example, the lack of empirical studies is the main reason why I did not raise my score more.", "rebuttal": "Thanks a lot for your comments on weaknesses and questions. In the following, we respond to them one by one. With the following responses, we hope that you are convinced to raise your grade.\n- **(W1) Major weakness: no empirical validation.** The reviewer agrees that this is a pure theory paper. (1) Indeed, major AI conferences, like NeurIPS, AAAI, IJCAI, etc., accept the pure theory papers, not only for our evolutionary theory community (e.g.[1,2,3]), but also for other community (e.g. [4,5,6]). (2) Also mentioned by the second reviewer, empirical illustrations would be good. However, he/she also mentioned this is just a limitation, not the weakness, and \"do not undermine the core contribution\". (3) Limited space. The reviewer also noticed (in his/her Q3) that all our proofs are pushed into the supplementary material due to the limited space. We do not have more space for experiments as we set it the priority to sufficiently demonstrate our theoretical contribution. Hence, we kindly ask the reviewer to view it as a limitation not a major weakness for a negative score.\n- **(W2 \\& Q2) Only one LargeFront benchmark.** (1) We first note that LargeFront is not one benchmark but a class of benchmarks w.r.t. $\\varepsilon$ (See Definition 1, Page 2). (2) We would like to point its relation to the continuous problems. As stated in the second paragraph in Section 2.1, LargeFront has \"exponential Pareto front points\", and is much closer to \"the continuous optimization as a segment of a continuous curve in the Pareto front contains infinite points\". Our results on LargeFront might shed some light on the understanding of the popular MOEAs for real-world continuous optimization. \n- **(Q1) Why additive $\\varepsilon$-approximation?** We chose the additive $\\varepsilon$-approximation because it aligns naturally with the structure of the $LF_\\varepsilon'$ benchmark (see [HN09] also used additive $\\varepsilon$-approximation for the $LF_\\varepsilon'$ benchmark), and we chose $LF_\\varepsilon'$ as it \"shows more similarity to the arguably most popular ONEMAX benchmark\" (See the second paragraph in Section 2.1). For the question of whether the conclusion still holds for other approximation measures on the $LF_\\varepsilon'$ benchmark class, we want to say that we haven't considered it yet. We note that for the technical part to establish our results, we essentially try to calculate the time for the population to cover all $k$ ones for $k=0,1,\\dots,n/2$ (that is, the time to witness a population $P$ with $P\\cap ${$ x\\mid |x'|_1=k $} $\\neq \\emptyset$ for all $k\\in[0..n/2]$) (See Lemma 4). Hence, from this point of view, we could transfer our results to other measures by considering how well the population with the above characteristic approximates, but we are not sure how tight this calculation is. Definitely, it will be an interesting work to do in our future.\n- **(Q3) Omitted proofs in the main text.** Thanks a lot for your nice suggestions for adding more illustrations for the omitted proofs and findings. We will try to find some space for it in our future version.\n\n\n## References\n\n[1] Per kristian Lehre, Shishen Lin. No Free Lunch Theorem and  Black-Box Complexity Analysis for  Adversarial Optimisation. In Proceedings of the 38th Annual Conference on Neural Information Processing Systems, NeurIPS 2024, pages 121570-121597. \n\n[2] Sacha Cerf, Benjamin Doerr, Benjamin Hebras, Yakob Kahane, and Simon Wietheger. The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem. In International Joint Conference on Artificial Intelligence, IJCAI 2023, pages 5522-5530.\n\n[3] Duc-Cuong Dang, Andre Opris, Bahare Salehi, and Dirk Sudholt. A proof that using crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation. In Conference on Artificial Intelligence, AAAI 2023, pages 12390–12398.\n\n[4] Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. In Proceedings of the 36th Annual Conference on Neural Information Processing Systems, NeurIPS 2022, pages 22870-22882.\n\n[5] Cornelius Brand, Robert Ganian, and Kirill Simonov. A Parameterized Theory of PAC Learning. In Conference on Artificial Intelligence, AAAI 2023, pages 6834–6841.\n\n[6] Christel Baier, Florian Funke, and Rupak Majumdar. A game-theoretic account of responsibility allocation. In International Joint Conference on Artificial Intelligence, IJCAI 2021, pages 1773-1779."}]

Author rebuttal:

Meta-review: This paper provides formal complexity guarantees for a range of well-known Multi-Objective Evolutionary Algorithms. 
It is shown that these algorithms compute an additive approximations to the Pareto set of benchmark datasets 
in expected O(n^2 log n) time. On the other hand, other simpler methods requires exponential time for the same task. After a robust discussion, the consensus of the reviewers is that this is an interesting contribution that merits acceptance.
Decision: Accept (poster)