{"id":"8bce56e4-080f-48dd-a921-d9201346242f","arxiv_id":"2506.11929","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"New worst-case iteration and function-evaluation bounds for high-order set-generating multiobjective optimization algorithms, with exponents depending on the number of objectives and the model order.","lead":"This paper derives worst-case complexity bounds for algorithms that reconstruct an entire Pareto front in multiobjective optimization using high-order Taylor models. It shows that updating all points in the current set yields O(ε^{-m(p+1)/p}) iterations to make every point ε-stationary, while a lighter version is slower but cheaper per iteration.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Inexact-minimizer analysis in §4.2 is unsupported: condition (29) permits λ=0, voiding Lemma 2; a 1-D counterexample breaks Proposition 11.","rationale":"Reading the paper in good faith, the set-based hypervolume argument (Proposition 10, Theorem 1) is a genuine contribution: it avoids linked sequences and yields dimension-independent bounds for the exact-minimizer version. The proof of Theorem 2 has an indexing slip but is repairable by constructing a chain x_{k+1} ∈ X_{k+1} with F(x_{k+1}) ≤ F(x_k+s(x_k)) and using ||v(x_k+s(x_k))|| ≥ ε for k ∈ K''_ε. The unanalyzed oracle cost is a standard limitation and not by itself fatal. The decisive issue is Section 4.2: the proposed inexact conditions (29) are too weak. Since (29b) does not require multipliers to form a convex combination, λ=0 is always admissible, making (29c) vacuous. The proof of Proposition 11 applies Lemma 2, which requires the multiplier to lie in the simplex, so the proof does not carry through, and the scalar counterexample shows the proposition is false as stated. This matters because the inexact analysis is the paper's stated remedy for the nonconvexity of subproblem (9); without it, the practical relevance of the bounds is not established. I therefore keep the verdict CONDITIONAL: the exact-minimizer core is likely sound, but Section 4.2 and the abstract typos must be corrected before acceptance.","tokens_in":16515,"tokens_out":16986,"duration_ms":227553,"concrete_test":"Run the scalar counterexample above: take m=1, p=1, f(x)=x^2/2, x=1, σ=2, s=-0.01, δ=1, τ=0.1, λ=0. Verify that (29a)–(29c) all hold and compute ||v(x+s)|| versus the Proposition 11 bound. If the inequality fails (0.99 > 0.051), the proof of Proposition 11 is broken; then strengthen (29) to include simplex constraints on λ and re-derive the bound. Also re-check whether any nontrivial s (not just s=0) satisfies the corrected conditions; if not, the inexact complexity claims remain unproven.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing soft spot is the inexact-minimizer analysis in Section 4.2, not the general oracle assumption. The stated approximate-KKT conditions (29) allow λ=0: (29b) only requires Σ|λ_i| ≤ δ with δ ≥ 1, and (29c) then becomes 0 ≤ τ||s||^p, which is vacuous. Consequently, every s with mp(x,s) ≤ 0 satisfies (29). The proof of Proposition 11 invokes Lemma 2, which requires the multiplier λ to be a convex combination (λ ≥ 0, Σλ_i = 1); under (29) this property is not enforced, so the proof does not go through. The proposition is false as stated. Example: m=1, p=1, f(x)=x^2/2 (L=1), x=1, σ=2, s=-0.01, τ=0.1, δ=1, λ=0. Then (29a)–(29c) hold, but ||v(x+s)|| = 0.99, while the bound in Proposition 11 is [0.1 + 1·((2·2)/1 + 1/0!)]·0.01 = 0.051. This invalidates the claimed complexity bounds for the inexact version, which is the paper's stated remedy for the nonconvexity of subproblem (9). The exact-minimizer Theorems 1–2 appear recoverable (the Theorem 2 indexing slip is repairable), but Section 4.2 and Remark 6 need a corrected condition, e.g., requiring λ_i ≥ 0, Σλ_i = 1, and a small residual, before the claims as stated can be accepted.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two a-posteriori algorithms, HOP and LHOP, for unconstrained multiobjective optimization. HOP maintains a set of mutually nondominated points and, at each iteration, applies a Regularized Search (RS) procedure to every non-stationary point in the set; RS generates trial points by (approximately) minimizing the max of p-th-order Taylor models regularized by a power p+1 of the step norm, increases the regularization parameters until a sufficient decrease is obtained for all objectives, and collects trial points that improve at least one objective. LHOP applies RS to a single chosen point per iteration. Under Lipschitz continuity of the p-th derivatives and Assumption 1, the paper claims worst-case bounds: HOP requires O(epsilon^{-m(p+1)/p}) iterations to make every point epsilon-approximate Pareto-stationary and O(epsilon^{-(p+1)/p}) iterations to produce at least one such point; LHOP requires O(epsilon^{-m(p+1)/p}) iterations for the latter. The function-evaluation counts are multiplied by |X(epsilon)| in HOP and not in LHOP. The same bounds are claimed when subproblems are solved inexactly under conditions (29). The bounds are independent of the dimension n and match single-objective high-order complexity when m=1.","tokens_in":16898,"tokens_out":19805,"duration_ms":212975,"significance":"The exact-minimizer part is a genuine contribution: the hypervolume-increase argument (Lemma 1 and Propositions 6-10) is well suited to set-valued methods and avoids linked sequences, and it generalizes the single-point high-order bounds of [3] to front reconstruction. The proofs in Section 4.1 are mostly careful, the constants are explicit, and the dimension independence is attractive. However, the inexact analysis in Section 4.2 is currently invalid because conditions (29) are vacuous, and the proof of Theorem 2 contains an unjustified replacement of v(x_k+s(x_k)) by v(x_{k+1}). Both issues are repairable, and the displayed bounds in Theorems 1 and 3 also contain a sign error that must be corrected. With these fixes the paper would be a solid contribution; in its present form the central claims are only partially supported.","major_comments":[{"comment":"The approximate-KKT conditions (29) are vacuous because lambda=0 is always admissible. Indeed (29b) requires only sum_i |lambda_i| <= delta with delta >= 1, and (29c) then reads 0 <= tau ||s||^p, so any s with mp(x,s) <= 0 satisfies (29). Proposition 11 is therefore false as stated. A concrete counterexample is: m=1, p=1, f(x)=x^2/2, x=1, sigma=2, s=-0.01, tau=0.1, delta=1, lambda=0. Then (29a)-(29c) hold, but ||v(x+s)||=0.99 while the claimed bound is [0.1 + 1*((2*2)/1 + 1/0!)]*0.01 = 0.051. The proof invokes Lemma 2, which requires lambda >= 0 and sum_i lambda_i = 1; these properties are not enforced by (29). Consequently Remark 6 and the inexact-version complexity bounds are unsupported. The condition should be corrected, for example by requiring lambda_i >= 0, sum_i lambda_i = 1, and a residual bound ||sum_i lambda_i grad_s m_i^p(x,s)|| <= tau ||s||^p, so that Lemma 2 applies.","section":"Section 4.2, Eq. (29), Proposition 11, Remark 6"},{"comment":"The proof of Theorem 2 contains an unjustified replacement: it displays f_i(x_k)-f_i(x_{k+1}) >= f_i(x_k)-f_i(x_k+s(x_k)) >= c||v(x_{k+1})||^{(p+1)/p}. Item (i) of Remark 4 bounds the decrease in terms of ||v(x_k+s(x_k))||^{(p+1)/p}, while the construction only guarantees F(x_{k+1}) <= F(x_k+s(x_k)); there is no monotonicity of v along this sequence. The final summation over ell in K''_epsilon also mixes indices, writing ||v(x_k)|| where the index should be either x_ell+s(x_ell) or x_{ell+1}. The theorem is repairable by summing the directly available lower bounds c||v(x_k+s(x_k))||^{(p+1)/p} over k in K''_epsilon, but as written the proof is incomplete.","section":"Section 4.1, proof of Theorem 2"},{"comment":"The displayed upper bounds in Theorem 1 and Theorem 3 place epsilon^{-m(p+1)/p} in the denominator, i.e. |K| <= (HI-HI_0)/(c^m epsilon^{-m(p+1)/p}) = O(epsilon^{m(p+1)/p}), which vanishes as epsilon tends to zero and contradicts the abstract. The proof of Theorem 1 yields |K| c^m epsilon^{m(p+1)/p} <= HI-HI_0, so the denominator should contain epsilon^{m(p+1)/p}; the same correction is needed in Theorem 3. Please fix the sign in all displayed bounds.","section":"Section 4.1, Theorem 1; Section 5, Theorem 3"}],"minor_comments":[{"comment":"The exponent m(p+1) in ||s_j(x_k)||^{m(p+1)} should be p+1; the preceding inequality and the subsequent argument concern ||s_j||^{p+1}.","section":"Proposition 10, proof after Eq. (27)"},{"comment":"There are typos: 'mulitplier' should be 'multiplier', 'left-hand sided' should be 'left-hand side', and in the dual problem the constraint should read sum_{i=1}^m lambda_i = 1 with the subscript on lambda.","section":"Lemma 2, proof"},{"comment":"The summation over ell in K''_epsilon is written with ||v(x_k)|| instead of a consistent index; please correct this after repairing the proof as suggested in the major comment.","section":"Theorem 2, proof, final display"},{"comment":"The condition 'F(x+s_j) not> F(y)-... for all y in Y^j(x)' is hard to parse due to the negated vector inequality and the quantifier; consider rewriting it explicitly as 'for every y in Y^j(x), it is not true that F(x+s_j) > F(y)-...' and use the same convention in Proposition 10.","section":"Algorithm 2, line 5"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper is the first to give worst-case complexity bounds for high-order methods that reconstruct a Pareto front, and the hypervolume-based argument is a genuine step forward. The exact-minimizer results in Theorem 1 look sound, and the exponents (m(p+1)/p for making all points stationary, (p+1)/p for one point) are new and match single-objective rates when m=1. The framework is clean and the paper is honest about its relation to [3] and [10].\n\nThe soft spots are real. Section 4.2 on inexact minimizers is not just sloppy; it is wrong. Condition (29) allows λ=0 because (29b) only bounds the sum of absolute values and δ≥1. Then (29c) is vacuous, so any s with m_p(x,s)≤0 satisfies the conditions. Lemma 2, which requires λ to be a convex combination (λ≥0, Σλ_i=1), cannot be applied. Proposition 11 is false: for f(x)=x^2/2, x=1, σ=2, s=-0.01, τ=0.1, δ=1, λ=0, conditions (29) hold but ||v(x+s)||=0.99 while the claimed bound is 0.051. This invalidates the complexity claims for the inexact version, which is the paper's stated remedy for the nonconvex subproblem. It is likely fixable by adding λ_i≥0, Σλ_i=1 and a small residual, but as written it is a load-bearing flaw.\n\nTheorem 2's proof also has a gap: it substitutes ||v(x_{k+1})|| for ||v(x_k+s(x_k))|| without justification. The constructed sequence {x_k} does not guarantee x_{k+1}=x_k+s(x_k); that point may be dominated and absent from X_{k+1}. I suspect the result is true and repairable, but the repair is not a typo fix.\n\nThe abstract contains exponent typos (missing minus signs), which should be corrected.\n\nOverall: the exact-case contribution is solid and worth refereeing. The inexact section must be corrected before the claims as stated can be accepted. A serious referee should engage with this paper and require those fixes. Not a desk reject.","headline":"First complexity bounds for high-order set-generating multiobjective methods, but the inexact-minimizer analysis is broken as written and Theorem 2's proof needs repair.","tokens_in":17401,"tokens_out":4105,"would_cite":true,"duration_ms":46798,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C29","90C30","65Y20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Provably bounded cost for high-order Pareto-front reconstruction","keywords":["multiobjective optimization","high-order methods","worst-case iteration complexity","Pareto front reconstruction","regularized models","hypervolume indicator","approximate Pareto stationarity","function evaluation complexity"],"falsifier":"Run HOP with p=1 on a two-objective problem with Lipschitz gradients, say $f_1(x)=x_1^2+x_2^2$ and $f_2(x)=(x_1-1)^2+(x_2+1)^2$, and record the number of Regularized Search calls until $\\max_{x\\in X}\\|v(x)\\|\\le\\varepsilon$ for $\\varepsilon=10^{-1}$ down to $10^{-6}$. The all-points bound predicts at most $O(\\varepsilon^{-4})$ iterations and the one-point bound at most $O(\\varepsilon^{-2})$. If the observed iteration counts, after controlling for the fixed constants in (26), grow with a strictly worse exponent, or if any single RS call requires more $\\sigma$-increases than the finite number in (23), the theorems are contradicted.","tokens_in":16320,"feed_emoji":"🎯","tokens_out":8430,"duration_ms":93466,"temperature":0.7,"pith_summary":"This paper establishes worst-case iteration and function-evaluation complexity bounds for a-posteriori multiobjective algorithms that reconstruct an entire Pareto front using high-order regularized models. It introduces a framework (HOP) that, at each step, generates trial points from a current set of nondominated points and keeps those that improve at least one objective, plus a lighter variant (LHOP) that updates only one point. Under Lipschitz continuity of the p-th derivatives, the paper proves that all points in the set become ε-approximate Pareto-stationary within O($ε^{{-m(p+1)/p}}$) iterations, and at least one such point is found within O($ε^{{-(p+1)/p}}$) iterations for HOP; LHOP achieves only the former exponent for one point. The bounds are independent of the ambient dimension n and reduce to the known single-objective complexity when m=1. These results matter because they give provable performance guarantees to the common practice of maintaining a set of trade-off points to approximate the Pareto front.","feed_headline":"Provably bounded cost for high-order Pareto-front reconstruction","feed_subtitle":"For m objectives, full-front sets need O(ε^{-m(p+1)/p}) steps; one point needs O(ε^{-(p+1)/p}).","key_machinery":"The load-bearing machinery is the p-th-order regularized model $m^p(x,s) = \\max_i ( \\sum_{j=1}^p \\frac{1}{j!} \\nabla^j f_i(x)[s]^j + \\frac{\\sigma_i}{p!} \\|s\\|^{p+1} )$, whose global (or approximate) minimizer $s(x)$ yields a step that decreases all objectives once the regularization parameters are large enough. The Regularized Search procedure generates several trial points by increasing the $\\sigma_i$ for objectives that fail a sufficient-decrease test, retaining all trial points that improve some objective. The proof then chains two inequalities: Proposition 6 bounds the first-order Pareto-stationarity violation $\\|v(x+s)\\|$ by a constant times $\\|s\\|^p$, and Proposition 10 converts any added point's objective decrease into an increase of the hypervolume indicator (via Lemma 1), so summing hypervolume increases over the whole run gives the iteration counts in Theorems 1–3.","core_discovery":"On the paper's own terms, the central discovery is that the worst-case cost of reconstructing a Pareto front with p-th-order regularized models can be controlled by a hypervolume-accumulation argument rather than by the linked-sequence arguments used in prior a-posteriori analyses. Theorem 1 states that HOP, updating all points and using exact model minimizers, needs at most O($ε^{{-m(p+1)/p}}$) iterations and O(|X(ε)| $ε^{{-m(p+1)/p}}$) function evaluations to reach a set in which every point is ε-approximate Pareto-stationary. Theorem 2 states that the same algorithm needs only O($ε^{{-(p+1)/p}}$) iterations (and O(|X(ε)| $ε^{{-(p+1)/p}}$) evaluations) to produce at least one such point, matching the single-objective high-order bound when m=1. Theorem 3 shows the light version LHOP has O($ε^{{-m(p+1)/p}}$) worst-case bounds for both iterations and evaluations for producing at least one ε-stationary point. All bounds persist, up to constant factors, when the regularized subproblems are solved via approximate KKT conditions (29) instead of exactly.","pith_inferences":["The hypervolume-accumulation technique used here replaces linked sequences, suggesting it could be adapted to prove worst-case bounds for other set-based multiobjective schemes, such as derivative-free or trust-region front-reconstruction methods.","The dimension independence of the exponents is encouraging for many-objective problems with large $n$, but the exponential growth in $m$ implies the practical bottleneck shifts to the number of objectives; a testable prediction is that methods exploiting problem structure to reduce the effective $m$ would outperform the generic bound.","The oracle assumption on the subproblem is the main gap between theory and practice: unless efficient global or certified local solvers for the p-th-order regularized model are available, the bounds are not automatically inherited by a concrete implementation; a practical extension would analyze the inner complexity of solving (9) under additional convexity or structural assumptions.","Because the constants in (26) and (30) depend on $L_{\\max}$ and the regularization range, choosing $p$ optimally in a given problem requires balancing a better exponent $(p+1)/p$ against larger constants; a numerical study of this trade-off would be a natural next step."],"forward_implications":["For the full HOP algorithm, an ε-approximate Pareto-stationary set is obtained after at most $O(\\varepsilon^{-m(p+1)/p})$ iterations and $O(|X(\\varepsilon)| \\varepsilon^{-m(p+1)/p})$ function evaluations, with no dependence on the dimension $n$.","To find just one ε-approximate Pareto-stationary point, HOP needs $O(\\varepsilon^{-(p+1)/p})$ iterations, exactly the high-order bound known from single-objective optimization ($m=1$).","The light variant LHOP, which updates one point per iteration, still guarantees $O(\\varepsilon^{-m(p+1)/p})$ iterations and evaluations to find at least one ε-stationary point, at the price of a worse exponent in $m$.","All bounds survive, up to constants, when the nonconvex regularized subproblems are solved inexactly via approximate KKT conditions, so the theory does not require exact global minimization in principle.","Because the bounds do not depend on $n$, the framework's complexity is governed by the number of objectives $m$ and the model order $p$, not by the dimensionality of the decision space."],"supporting_citations":[{"why":"Defines the first-order regularized model and the stationarity measure v(x) used throughout the paper.","marker":"[11]"},{"why":"Extends high-order regularized models to multiobjective optimization and gives the single-point complexity baseline that Theorem 2 matches.","marker":"[3]"},{"why":"Establishes the p-th order Taylor regularization framework and the Lipschitz derivative bounds used in inequalities (13)-(14).","marker":"[2]"},{"why":"Supplies the hypervolume indicator definition and Lemma 1 relating hypervolume increase to adding a nondominated point, the accumulator for the proof.","marker":"[10]"},{"why":"Provides the Fritz-John and KKT conditions invoked in Propositions 5 and 6.","marker":"[1]"},{"why":"Contributes the tensor norm notation and Lipschitz p-th derivative bounds for high-order models.","marker":"[4]"},{"why":"Gives the first-order O(ε^{-2}) complexity result that the paper's p=1 multiobjective bounds generalize.","marker":"[12]"}],"fun_headline_variants":["High-order Pareto-front reconstruction: provable worst-case cost","Worst-case guarantees for high-order Pareto-front methods","Provable efficiency for high-order Pareto-front reconstruction","Complexity bounds for Pareto-front reconstruction with high-order models","Tight worst-case bounds for high-order Pareto-front algorithms"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The analysis assumes that at each step a (possibly approximate) global minimizer of a generally non-convex regularized model can be computed, and it counts only outer iterations and objective evaluations, not the cost or even the guaranteed availability of such a minimizer.","fun_headline_variants_meta":{"raw":{"variants":["High-order Pareto-front reconstruction: provable worst-case cost","Worst-case guarantees for high-order Pareto-front methods","Provable efficiency for high-order Pareto-front reconstruction","Complexity bounds for Pareto-front reconstruction with high-order models","Tight worst-case bounds for high-order Pareto-front algorithms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001087,"raw_usage":{"total_tokens":4655,"prompt_tokens":1169,"completion_tokens":3486,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":785,"completion_tokens_details":{"reasoning_tokens":3408}},"tokens_in":785,"tokens_out":3486,"duration_ms":30480,"temperature":1.0,"reasoning_tokens":3408,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T01:01:47.069385+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run HOP with p=1 on a two-objective problem with Lipschitz gradients, say $f_1(x)=x_1^2+x_2^2$ and $f_2(x)=(x_1-1)^2+(x_2+1)^2$, and record the number of Regularized Search calls until $\\max_{x\\in X}\\|v(x)\\|\\le\\varepsilon$ for $\\varepsilon=10^{-1}$ down to $10^{-6}$. The all-points bound predicts at most $O(\\varepsilon^{-4})$ iterations and the one-point bound at most $O(\\varepsilon^{-2})$. If the observed iteration counts, after controlling for the fixed constants in (26), grow with a strictly worse exponent, or if any single RS call requires more $\\sigma$-increases than the finite number in (23), the theorems are contradicted.","supporting_citations":[{"cited_title":"Fliege and B","cited_arxiv_id":null,"evidence_quote":"Defines the first-order regularized model and the stationarity measure v(x) used throughout the paper."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the p-th order Taylor regularization framework and the Lipschitz derivative bounds used in inequalities (13)-(14)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the hypervolume indicator definition and Lemma 1 relating hypervolume increase to adding a nondominated point, the accumulator for the proof."},{"cited_title":"Cartis, N","cited_arxiv_id":null,"evidence_quote":"Contributes the tensor norm notation and Lipschitz p-th derivative bounds for high-order models."}],"review_version":1}