Pith. sign in

REVIEW 3 major objections 4 minor 18 references

Worst-Case Complexity of High-Order Algorithms for Pareto-Front Reconstruction

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Provably bounded cost for high-order Pareto-front reconstruction

desk verdict 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. read the letter →

arxiv 2506.11929 v2 pith:ZAYFJ5A6 submitted 2025-06-13 math.OC

Andrea Cristofari , Marianna De Santis , Stefano Lucidi , Giampaolo Liuzzi This is my paper · ORCID
classification math.OC MSC 90C2990C3065Y20
keywords multiobjectiveoptimizationhigh-ordermethodsworst-caseiterationcomplexityParetofrontreconstructionregularizedmodelshypervolumeindicatorapproximatestationarityfunctionevaluation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Section 4.2, Eq. (29), Proposition 11, Remark 6] 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.
  2. [Section 4.1, proof of Theorem 2] 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.
  3. [Section 4.1, Theorem 1; Section 5, Theorem 3] 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.
minor comments (4)
  1. [Proposition 10, proof after Eq. (27)] 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}.
  2. [Lemma 2, proof] 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.
  3. [Theorem 2, proof, final display] 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.
  4. [Algorithm 2, line 5] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the complexity bounds are derived from the stated Lipschitz/taylor-remainder inequalities and a hypervolume potential, with no fitted parameter and no load-bearing self-citation.

full rationale

I followed the derivation chain of Theorems 1–3. The bound in Theorem 1 is obtained by summing the per-iteration hypervolume increase of Proposition 10(ii), HI(F(X_{k+1})) - HI(F(X_k)) >= c^m * ||v(x_k + s(x_k))||^{m(p+1)/p}, against the finite hypervolume budget HI - HI_0; Theorem 2 does the same with the single-objective decrease budget min_i(f_i(x_0) - f_i^min). The constant c in (26) is built from algorithmic parameters (eta, sigma_l^min, sigma_max) and the Lipschitz constant L_max; it is not calibrated to any target value, and epsilon enters only through the stopping sets K'_epsilon or K''_epsilon. Proposition 6 uses the KKT conditions of the regularized model (10) and the standard Lipschitz remainder bound (14), both stated as assumptions or external results; Lemma 1 and Proposition 3 are imported from the external references [10] and [11]. The self-citations [6], [8], and [16] appear only in the introduction and background discussions of set-based multiobjective methods; none of them supplies a premise of the complexity proof. I found no equation that is equivalent to its input by construction, no parameter fitted to the quantity being bounded, and no empirical pattern merely renamed. The inexact-minimizer analysis in Section 4.2 has an apparent validity gap: conditions (29b)–(29c) do not require lambda >= 0 and sum_i lambda_i = 1, so Lemma 2 cannot be invoked and Proposition 11 may fail; however, this is a correctness defect, not a circular reduction, since the claimed bound is not an input to itself. The small index shift in the proof of Theorem 2 is likewise a repairable typo rather than circularity. Finally, the assumption that the regularized subproblem can be solved globally is a tractability assumption, not a circular one: the complexity counts outer iterations and function evaluations under that stated oracle. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No numbers are fitted to data. The constants Li (Lipschitz constants), σ_l, σ_u, η, δ are inputs to the bounds, not tuned to the conclusion. The central claim rests on standard smoothness assumptions, a hypervolume boundedness assumption, and an oracle for solving the regularized subproblems.

assumptions (4)
  • domain assumption The p-th derivatives of each objective function fi are Lipschitz continuous with constants Li > 0.
    Stated in Section 3 before Equation (13). This is the key smoothness condition that powers the Taylor remainder bounds (13)-(14), which are used in Propositions 6 and 7.
  • domain assumption Assumption 1: for all i, f_i^min > -inf and f_i^max < +inf on the set of points not dominated by x0.
    Introduced in Section 2. It guarantees that the hypervolume reference point ρ is finite and that HI is bounded above, which is essential for the counting arguments in Theorems 1 and 3.
  • ad hoc to paper At each RS invocation, a global minimizer of the regularized model (9), or a point satisfying the approximate conditions (29), can be computed.
    The algorithm's analysis assumes such an oracle. The paper discusses how to obtain approximate minimizers but does not analyze the cost or feasibility of solving the nonconvex subproblem. This is load-bearing for every iteration of the algorithm.
  • standard math Standard Taylor expansion bounds for functions with Lipschitz p-th derivatives (Equations (13) and (14)).
    These bounds are cited from [2,4] and used in Propositions 6, 7, and 10. They are a standard consequence of Lipschitz smoothness.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Worst-Case Complexity of High-Order Algorithms for Pareto-Front Reconstruction." pith.science (2026). https://pith.science/paper/ZAYFJ5A6

@misc{pith2026250611929,
  author       = {Pith},
  title        = {Pith review of: Worst-Case Complexity of High-Order Algorithms for Pareto-Front Reconstruction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZAYFJ5A6}},
  note         = {Machine review of arXiv:2506.11929}
}
abstract

In this paper, we are concerned with a worst-case complexity analysis of a-posteriori algorithms for unconstrained multiobjective optimization. Specifically, we propose an algorithmic framework that generates sets of points by means of $p$th-order models regularized with a power $p+1$ of the norm of the step. Through a tailored search procedure, several trial points are generated at each iteration and they can be added to the current set if a decrease is obtained for at least one objective function. Building upon this idea, we devise two algorithmic versions: at every iteration, the first tries to update all points in the current set, while the second tries to update only one point. Under Lipschitz continuity of the derivatives of the objective functions, we derive worst-case complexity bounds for both versions. For the first one, we show that at most $\mathcal O(\epsilon^{-m(p+1)/p})$ iterations are needed to generate a set where all points are $\epsilon$-approximate Pareto-stationary, with $m$ being the number of objective functions, requiring at most $\mathcal O(|X(\epsilon)|\epsilon^{-m(p+1)/p})$ function evaluations, where $X(\epsilon)$ is the largest set of points computed by the algorithm. Additionally, at most $\mathcal O(\epsilon^{-(p+1)/p})$ iterations are needed to generate at least one $\epsilon$-approximate Pareto-stationary point, requiring at most $\mathcal O(|X(\epsilon)|\epsilon^{-(p+1)/p})$ function evaluations. For the second version, we get $\mathcal O(\epsilon^{-m(p+1)/p})$ worst-case complexity bounds on the number of iterations and function evaluations for generating at least one $\epsilon$-approximate Pareto-stationary point. Our results align with those for single objective optimization and generalize those obtained for methods that produce a single Pareto-stationary point.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 12 canonical work pages

  1. [3]

    Calder´ on, M

    L. Calder´ on, M. A. Diniz-Ehrhardt, and J. M. Mart ´ ınez. On high-order model regu- larization for multiobjective optimization. Optimization Methods and Software , 37(1): 175–191, 2022. doi: 10.1080/10556788.2020.1719408

    arXiv 2022

  2. [10]

    A. L. Cust´ odio, Y. Diouane, R. Garmanjani, and E. Riccietti. Worst-case com- plexity bounds of directional direct-search methods for multiobjective optimization. Journal of Optimization Theory and Applications , 188(1):73–93, 2021. doi: 10.1007/ s10957-020-01781-z

    work page 2021

  3. [1]

    D. P. Bertsekas. Nonlinear programming. Athena Scientific, Belmont, MA, 1999

    1999

  4. [2]

    E. G. Birgin, J. L. Gardenghi, J. M. Mart ´ ınez, S. A. Santos, and P. L. Toint. Worst- case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. Mathematical Programming, 163:359–368, 2017. doi: 10.1007/ s10107-016-1065-8

    work page 2017

  5. [4]

    Cartis, N

    C. Cartis, N. I. M. Gould, and P. L. Toint. Second-order optimality and beyond: characterization and evaluation complexity in convexly constrained nonlinear opti- mization. Foundations of Computational Mathematics , 18:1073–1107, 2018. doi: 10.1007/s10208-017-9363-y

    work page doi:10.1007/s10208-017-9363-y 2018

  6. [5]

    Cocchi and M

    G. Cocchi and M. Lapucci. An augmented Lagrangian algorithm for multi-objective optimization. Computational Optimization and Applications , 77(1):29–56, 2020. doi: 10.1007/s10589-020-00204-z

    work page doi:10.1007/s10589-020-00204-z 2020

  7. [6]

    Cocchi, G

    G. Cocchi, G. Liuzzi, S. Lucidi, and M. Sciandrone. On the convergence of steepest descent methods for multiobjective optimization. Computational Optimization and Ap- plications, 77:1–27, 2020. doi: 10.1007/s10589-020-00192-0

    work page doi:10.1007/s10589-020-00192-0 2020

  8. [7]

    Cocchi, M

    G. Cocchi, M. Lapucci, and P. Mansueto. Pareto front approximation through a multi- objective augmented Lagrangian method. EURO Journal on Computational Optimiza- tion, 9:100008, 2021. doi: 10.1016/j.ejco.2021.100008

    arXiv 2021

Show all 18 references
  1. [8]

    Cristofari, M

    A. Cristofari, M. De Santis, and S. Lucidi. On Necessary Optimality Conditions for 21 Complexity of Multiobjective High-Order Algorithms Sets of Points in Multiobjective Optimization. Journal of Optimization Theory and Applications, pages 1–20, 2024. doi: 10.1007/s10957-024-02478-3

    2024 doi

  2. [9]

    A. L. Cust´ odio, J. A. Madeira, A. I. F. Vaz, and L. N. Vicente. Direct multisearch for multiobjective optimization. SIAM Journal on Optimization , 21(3):1109–1140, 2011. doi: 10.1137/10079731X

    2011 doi

  3. [11]

    Fliege and B

    J. Fliege and B. F. Svaiter. Steepest descent methods for multicriteria optimiza- tion. Mathematical Methods of Operations Research , 51:479–494, 2000. doi: 10.1007/ s001860000043

  4. [12]

    Fliege, A

    J. Fliege, A. I. F. Vaz, and L. N. Vicente. Complexity of gradient descent for multi- objective optimization. Optimization Methods and Software , 34(5):949–959, 2019. doi: 10.1080/10556788.2018.1510928

    2019

  5. [13]

    M. Lapucci. Convergence and complexity guarantees for a wide class of descent al- gorithms in nonconvex multi-objective optimization. Operations Research Letters, 54: 107115, 2024. doi: 10.1016/j.orl.2024.107115

    2024

  6. [14]

    Lapucci and P

    M. Lapucci and P. Mansueto. Improved front steepest descent for multi-objective opti- mization. Operations Research Letters, 51(3):242–247, 2023. doi: 10.1016/j.orl.2023.03. 001

    2023 doi

  7. [15]

    Lapucci, P

    M. Lapucci, P. Mansueto, and D. Pucci. Effective Front-Descent Algorithms with Con- vergence Guarantees. arXiv preprint arXiv:2405.08450 , 2024

    2024 arXiv

  8. [16]

    Liuzzi and S

    G. Liuzzi and S. Lucidi. Worst-case complexity analysis of derivative-free methods for multi-objective optimization. arXiv preprint arXiv:2505.17594 , 2025

    2025 arXiv

  9. [17]

    Liuzzi, S

    G. Liuzzi, S. Lucidi, and F. Rinaldi. A derivative-free approach to constrained mul- tiobjective nonsmooth optimization. SIAM J. Optim. , 26(4):2744–2774, 2016. doi: 10.1137/15M1037810

    2016 doi

  10. [18]

    Mohammadi and A

    A. Mohammadi and A. L. Cust´ odio. A trust-region approach for computing Pareto fronts in multiobjective optimization. Computational Optimization and Applications , 87 (1):149–179, 2024. doi: 10.1007/s10589-023-00510-2. 22

    2024 doi

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.