{"id":"d11df2bb-8b04-4673-9aae-11ba000569e4","arxiv_id":"2505.17594","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A family of derivative-free multi-objective line-search methods is proved to attain a Pareto-stationarity tolerance ε within O(n^q ε^{-2q}) iterations in the strong version and O(|L(ε)| ε^{-2q}) iterations in the light version.","lead":"Two derivative-free algorithms for multi-objective optimization, where only function values are available, are analyzed: a strong-exploration version is shown to need O(n^q ε^{-2q}) iterations to reach a prescribed stationarity tolerance ε, and a light version guarantees the tolerance for at least one point in O(|L(ε)| ε^{-2q}) iterations.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 2's displacement bound ||x_k-y_i^k||≤√n Δ is unproved for general r=O(n) direction sets; if it fails, the n-exponent q in every main bound worsens, so the O(n^q ε^{-2q}) claim is not established.","rationale":"The reader's identification of Assumption 3 as a major caveat is correct: all of the paper's bounds use it to convert μ(x)>ε into μ_D(x)>ε/(C+1), and the authors themselves acknowledge in Remark 1 that the assumption can fail for multi-objective problems even when the direction set has positive cosine measure. That concern alone would justify a conditional verdict. However, the more immediately load-bearing issue is an unproved and likely false displacement bound inside the proof of Proposition 2: the statement ‖x_k−y_i^k‖≤√n max_i α holds only if the directions used so far behave like one step in each of at most n orthogonal directions, but the algorithm accumulates steps along an arbitrary r=O(n) direction set. Even in the single-objective case q=1, where Assumption 3 is automatically satisfied by any positive spanning set with bounded cosine measure, one can choose a positive spanning set with two nearly parallel directions; a successful expansion then produces an endpoint whose distance from x_k is about 2Δ for n=2, exceeding √n Δ. The term Lmax√n enters the constant hat{c} and is raised to the power 2q in Proposition 5, so this is not a cosmetic constant issue: it changes the stated bound from O(n^q ε^{-2q}) to O(n^{2q} ε^{-2q}) under a natural reading of the proof. I therefore keep the conditional verdict but strengthen the condition: the authors must either prove the √n bound under an appropriate structural assumption on D_k, or correct the n-exponents in the main theorems. If the exponents change, the comparison with existing DMS bounds in the table also needs revision.","tokens_in":24537,"tokens_out":20572,"duration_ms":177416,"concrete_test":"Independently re-derive Proposition 2 replacing the step ‖x_k−y_i^k‖≤√n max_i α with the valid accumulation bound ‖x_k−y_i^k‖≤r max_i α, and propagate the resulting hat{c} through Propositions 5, 6, 13, 14, 17, and 18. To make the issue concrete, run DFMOstrong with q=1, n=2, D_k={(1,0),(cosθ,sinθ),(-1,0),(0,-1)} on f(x)=x_1^2/2−x_1; after a successful expansion record ‖y_i^k−x_k‖/max α. If for θ=5° this ratio exceeds √2, the asserted √n bound in Proposition 2 is false, and the complexity exponents must be recomputed.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The weakest load-bearing step is the displacement bound inside Proposition 2, case (a). To pass from y_i^k to x_k, the proof uses ‖x_k − y_i^k‖ ≤ √n max_i {α̃^i_{k+1}}. But y_i^k = x_k + Σ_{l<i} α_l d_l, with r=O(n) not necessarily orthogonal directions; the general bound is r max_l α_l, not √n times the stepsize. Assumption 3 does not repair this: it allows r=O(n) arbitrary unit directions, and for q=1 any positive spanning set with positive cosine measure satisfies Assumption 3 with finite C. For n=2 take D_k={(1,0),(cosθ,sinθ),(-1,0),(0,-1)} with θ small; a successful expansion along the first two directions gives ‖y_i^k−x_k‖≈2Δ, while √n Δ≈1.41Δ. The Lmax√n term enters c1, hence hat{c}=max{c1+Lmax√n,c2} in Proposition 5 and Proposition 13. If the correct factor is O(n) instead of O(n^{1/2}), then hat{c}=O(n) and |K_ε| becomes O(n^{2q} ε^{-2q}) (and evaluation counts worsen correspondingly), breaking the claimed O(n^q ε^{-2q}) headline. The proof as written therefore does not establish the stated n-dependence.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two derivative-free algorithms for unconstrained multi-objective optimization with a posteriori Pareto-set approximation. DFMOstrong explores all current non-dominated points at each iteration using an expansion line search along a set of r = O(n) directions, while DFMOlight explores only one selected point per iteration, with special instances DFMOmin and DFMOmax. The authors derive worst-case iteration and evaluation complexity bounds to drive a Pareto criticality measure below a tolerance ε, using hypervolume progress and an auxiliary potential function. The headline claims are O(n^q ε^{-2q}) iterations for DFMOstrong to make all points in the list ε-critical, O(|L(ε)| ε^{-2q}) iterations for DFMOlight to produce one ε-critical point, and corresponding evaluation counts. The analysis follows the framework of Custódio et al. (2021) and the authors' earlier line-search expansion work.","tokens_in":24847,"tokens_out":20953,"duration_ms":159112,"significance":"If the stated n-dependence is correct, the paper gives a useful extension of worst-case complexity results from directional direct search to expansion-based line-search methods for multi-objective optimization, and it provides explicit constants and a transparent hypervolume-potential argument. The comparison with the DMS method and the separate treatment of min/max selection rules are valuable. However, the advertised n-exponent in the DFMOstrong and per-linked-sequence bounds rests on a geometric estimate that is not established for general direction sets, and one proof case in the potential-function argument is missing. These issues affect load-bearing parts of the derivation and must be fixed before the main complexity claims can be accepted.","major_comments":[{"comment":"In the successful-exploration case, the proof uses the bound ||x_k − y_i^k|| ≤ √n max_{i=1,...,r} α̃^i_{k+1} to pass from gradients at y_i^k to gradients at x_k. This bound is not justified. From the algorithm, y_i^k = x_k + ∑_{l<i} α_l d_l with ||d_l|| = 1 and arbitrary directions, so the general estimate is ||x_k − y_i^k|| ≤ ∑_{l<i} α_l ≤ r max_l α_l, not √n times the maximum step. Assumption 3 only requires |D_k| ≤ r = O(n) and does not impose orthogonality; the positive spanning sets discussed in Remark 1 can consist of arbitrarily oriented unit vectors. For n = 2, taking D_k = {(1,0), (cosθ,sinθ), (-1,0), (0,-1)} and expanding along the first two directions gives ||y_i^k − x_k|| ≈ 2Δ, which exceeds √2 Δ. Consequently, the constant ĉ in Proposition 5 should be O(n) rather than O(n^{1/2}), and the proof of |K_ε| ≤ O(n^q ε^{-2q}) collapses; the written argument yields at best O(r^q ε^{-2q}), i.e. O(n^{2q} ε^{-2q}) under r = O(n). The same ĉ appears in Propositions 10, 13, 14, 17, and 18, so the advertised n-dependence of those bounds is not established.","section":"Proposition 2, Section 3.1"},{"comment":"Proposition 3 asserts that a successful iteration can only have Δ̄_k = Δ̄_{k+1} or Δ̄_k < Δ̄_{k+1}. If Algorithm 1 line 6 uses the same c ∈ (0,1) as Algorithm 3, this dichotomy is false. A point with the current maximum step can fail, reducing its step to θΔ̄_k, while another point succeeds with a step in [cΔ̄_k, θΔ̄_k); the iteration is then successful but Δ̄_{k+1} < Δ̄_k. In such a case the hypervolume increase can be as small as (γ c^2 Δ̄_k^2)^q, which can be much smaller than the quantity (γ c2 Δ̄_{k+1}^2)^q used in the proof of Proposition 4. The missing case must be handled explicitly (for example, using the η(1−θ^{2q})/θ^{2q} term already present in c̃, or adding a constant depending on c/θ), or DFMOstrong must be specified with c = 1. As written, the proof of the universal decrease of Φ_k, which underpins Propositions 5, 6, 10, 13, 14, 17, and 18, is incomplete.","section":"Propositions 3 and 4, Section 3.1"}],"minor_comments":[{"comment":"The abstract refers to algorithms DFMOnew and DFMOlight, but the body of the paper uses DFMOstrong and DFMOlight; please harmonize the names.","section":"Abstract"},{"comment":"Algorithm 1 line 6 uses a constant c in cΔ̄_k, but c is not declared in the data statement; Algorithm 3 declares c ∈ (0,1). Please clarify the value of c for DFMOstrong and its role in Proposition 3.","section":"Algorithm 1"},{"comment":"The proof says 'For every i = 1, ..., n', but the direction set has r directions; it should read i = 1, ..., r.","section":"Proposition 2"},{"comment":"The first sentence states N_f^{j_ε} ≤ O(n L(ε) ε^{-2q}), but the displayed bound and Table 1 give O(n^{q+1} L(ε) ε^{-2q}) because of the ĉ^{2q} factor; please correct the sentence or the display.","section":"Proposition 6"},{"comment":"In the proof of the 'only if' part, the sets Y_j are defined for each coordinate j and ε as a minimum over them, but some Y_j may be empty; for example, different points may be improved in different coordinates. The equivalence is true, but the proof needs a case distinction or a different construction of the positive-volume box.","section":"Appendix A, Proposition 19"},{"comment":"The symbol L(ε) is used for max_k |L_k| in Proposition 6 and for the number of linked sequences in Proposition 9; please use distinct names to avoid confusion.","section":"Notation"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope and the overall proof strategy is sound, but the unproved displacement bound in Proposition 2 changes the n-exponent of several central claims. The missing case in Proposition 3 is a second gap that should be resolved during revision. Both issues are repairable, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper does something useful. It takes the line-search expansion machinery from single-objective DFO and adapts it to a posteriori multiobjective methods, producing worst-case iteration and evaluation bounds for four algorithm variants. DFMOlight matches the existing DMS bound, and the strong-exploration variants add a full-set guarantee. The proof architecture is mostly solid, with explicit Lipschitz and hypervolume arguments, no fitted parameters, and the paper openly discusses Assumption 3 and its limitations. But there is a real bug in Proposition 2 that affects the n-dependence of the strong variants.\n\nThe problem is the displacement bound. To pass from y_i^k back to x_k in the successful case, the proof uses ||x_k − y_i^k|| ≤ √n max_i α̃^i_{k+1}. But y_i^k is reached by taking up to r steps along arbitrary unit directions in D_k, and Assumption 3 only says r = O(n), not that the directions are orthogonal. The general bound is r times the max step, not √n. For n=2, a set of four nearly parallel positive-spanning directions satisfies Assumption 3 (single objective), and two successful steps along the first two directions give displacement ≈ 2Δ, which exceeds √2 Δ. So the constant ĉ in Propositions 5, 13, and 17 becomes O(n) instead of O(n^{1/2}), and the bounds O(n^q ε^{-2q}) turn into O(n^{2q} ε^{-2q}). The DFMOlight result in Propositions 9–11 is unaffected, since it only uses the unsuccessful-case bound with c2, which is independent of n. So the headline claim \"aligned with the DMS bound\" survives for DFMOlight, but the strong-exploration n-exponents are not established.\n\nAssumption 3 is strong, but the authors state it plainly and discuss it in Remark 1; it's the same kind of assumption used in the DMS literature. Minor typos: the abstract says DFMOnew, the text says DFMOstrong, and Proposition 2 quantifies over i=1,...,n while it should be r.\n\nThis paper is for the worst-case complexity subfield. The DFMOlight bound is genuinely useful and deserves citation. The strong-exploration results are interesting if the displacement bound can be repaired, either by assuming orthonormal directions or by accepting the O(n^{2q}) dependence. I'd send it to referees, with a note to the authors to fix Proposition 2 before it's in final form.","headline":"Useful extension of DFO worst-case bounds to multiobjective a posteriori methods, but Proposition 2's displacement bound is wrong and breaks the claimed n-dependence in the strong-exploration results.","tokens_in":25373,"tokens_out":7604,"would_cite":true,"duration_ms":56346,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C29","90C30","90C56"],"pacs":[],"model":"deepseek-v4-flash","headline":"Derivative-free multi-objective methods hit ε-Pareto criticality in O(n^q ε^{-2q}) iterations","keywords":["multi-objective optimization","derivative-free optimization","worst-case complexity","Pareto criticality","hypervolume indicator","linesearch expansion","a posteriori methods","non-dominated solutions"],"falsifier":"Run DFMOstrong on a smooth bi-objective quadratic in R^n with D_k the 2n coordinate directions, record for every iterate the ratio μ_Dk(x_k)/Δ_{k+1}, and compare it to the constant c from Proposition 2; a single iterate exceeding that constant, or an iterate with μ(x_k)>0 but μ_Dk(x_k)=0, would violate the paper's key inequality. Alternatively, inspect the iteration count needed to reach Γ(X_k)≤ε on random instances; if it grows faster than O(n^q $ε^{{-2q}}$) for fixed n and q, the bound would be contradicted.","tokens_in":2281,"feed_emoji":"🎯","tokens_out":6129,"duration_ms":122913,"temperature":0.7,"pith_summary":"This paper establishes worst-case complexity bounds for two derivative-free, a posteriori multi-objective optimization algorithms, DFMOstrong and DFMOlight, which produce sets of non-dominated points using only function evaluations. The main result is that DFMOstrong reaches a list in which every point has Pareto criticality at most ε in O(n^q $ε^{{-2q}}$) iterations, with O($n^{{q+1}}$ L(ε) $ε^{{-2q}}$) function evaluations, where n is the dimension, q the number of objectives, and L(ε) the maximum list size. DFMOlight, which explores around only one point per iteration, finds at least one ε-critical point in O(|L(ε)| $ε^{{-2q}}$) iterations, matching the bound previously known for directional direct-search methods. These results quantify how the number of objectives and problem dimension affect the cost of certifying Pareto-stationary approximations of the front. A sympathetic reader would care because these bounds are the first for set-based derivative-free methods with the linesearch expansion technique, and they provide a benchmark for practical a posteriori algorithms.","feed_headline":"New bound: O(n^q ε^{-2q}) iterations to Pareto-critical set","feed_subtitle":"Step-size expansion plus hypervolume progress yields worst-case guarantees for derivative-free multi-objective methods.","key_machinery":"The key machinery is the Approximate Optimization procedure, a linesearch expansion that moves along each direction d_i in the current set D_k. Starting with a trial step β equal to the current step size, it repeatedly tests y+β d_i; the point is accepted into the set if it is sufficiently non-dominated, i.e. F(y+β d_i) is not componentwise greater than F(z) - γ $β^{2}$ 1 for every z in the current set. When the trial fails, the procedure returns the largest accepted step; this failure condition, combined with the Lipschitz continuity of the gradients, gives the step-size bound on μ_Dk(x_k). Progress is measured by the hypervolume indicator HI(F(X_k)) with a reference point ρ = f_max + s 1, and the auxiliary cost function Φ_k = -HI(F(X_k)) + η $Δ_k^{{2q}}$ decreases by a fixed amount at every iteration. Telescoping that decrease over iterations is what converts hypervolume gains into iteration counts of order $ε^{{-2q}}$.","core_discovery":"The central discovery is that a linesearch expansion procedure links step sizes to the Pareto criticality measure, turning step-size decrease into a stationarity certificate for the whole list. In Proposition 2, the paper proves that for every point x_k and every direction set D_k, the approximate criticality measure μ_Dk(x_k) is bounded above by a constant times the maximum step size Δ_{k+1} produced by the expansion, either c1 Δ_{k+1} on successful explorations or c2 Δ_{k+1} on failures. Because each successful iteration increases the hypervolume of the list by a fixed multiple of Δ_{k+1}^{2q}, the cost function Φ_k = -HI(F(X_k)) + η $Δ_k^{{2q}}$ decreases by at least c~ (Δ_{k+1}^2)^q at every iteration. Summing these decreases yields Proposition 5: the number of iterations with Γ(X_k)>ε is at most O(n^q $ε^{{-2q}}$). The same mechanism, applied along linked sequences, gives the DFMOlight, DFMOmin, and DFMOmax variants their respective bounds. In short, the paper proves that step-size decrease plus hypervolume growth is enough to certify Pareto stationarity in worst case.","pith_inferences":["The O(ε^{-2q}) scaling is likely a fundamental limitation for a posteriori methods that rely on hypervolume progress alone; it sets a baseline that gradient-based or sample-based multi-objective methods might aim to beat.","A direct testable extension is to instrument DFMOmin and DFMOmax on smooth bi-objective problems and measure the empirical exponent of iteration counts versus ε, which could reveal whether the constants in Proposition 2 are loose.","Because Assumption 3 involves a constant C that may not be known a priori, an algorithmic extension would be to adaptively enrich D_k with a common descent direction when μ_Dk(x_k)=0, making the bound constructive.","The hypervolume-based proof suggests that replacing the hypervolume with a weaker but cheaper progress measure, such as a scalarized improvement, could yield similar bounds with smaller constants and cheaper hypervolume computations."],"forward_implications":["If the central bounds are correct, the single-objective case q=1 reproduces the classical O(ε^{-2}) iteration complexity and O(n ε^{-2}) evaluation complexity of line-search derivative-free methods.","DFMOlight's bound O(|L(ε)| ε^{-2q}) shows that exploring only one point per iteration costs no more asymptotically than directional direct-search methods, at least for finding one ε-critical point.","DFMOstrong certifies the entire list is ε-critical in O(n^q ε^{-2q}) iterations, without an explicit list-size factor in the iteration count; the price is a factor n in per-iteration evaluations.","The exponent 2q implies that any method in this class will struggle as the number of objectives grows: reducing ε by a factor of ten multiplies the worst-case iteration count by 10^{2q}.","The convergence corollaries imply that DFMOstrong's list asymptotically converges to a set of Pareto critical points, and DFMOmax retains that all-points guarantee along a subsequence."],"supporting_citations":[{"why":"It supplies the worst-case bound O(|L(ε)| ε^{-2q}) for the directional multisearch method and the linked-sequence machinery, which DFMOlight extends.","marker":"[1]"},{"why":"It provides Lemma 1 on the properties of the Pareto criticality measure μ(x), used throughout the step-size-to-stationarity argument.","marker":"[14]"},{"why":"It introduces the Direct Multisearch method and the list-of-points exploration that the two DFMO variants are built on.","marker":"[15]"},{"why":"It provides the derivative-free multi-objective linesearch framework and the list-of-pairs representation used by both algorithms.","marker":"[16]"},{"why":"It gives the single-objective steepest-descent O(ε^{-2}) iteration bound that the q=1 specialization of the new results matches.","marker":"[3]"}],"fun_headline_variants":["O(n^q ε^{-2q}) iterations to Pareto-criticality proven","Step-size expansion yields tight worst-case bound for black-box multi-objective","Hypervolume growth certifies Pareto stationarity in derivative-free methods","New proof: derivative-free multi-objective worst-case complexity","Linesearch expansion gives O(n^q ε^{-2q}) Pareto-critical bound"],"cache_read_input_tokens":27520,"weakest_assumption_plain":"All complexity results rest on Assumption 3: at every iterate, the distance between the true Pareto criticality measure and its discrete approximation must be bounded by a constant times the discrete measure, and the direction set must have size r=O(n); if some noncritical point has no common descent direction in D_k, the step-size-to-stationarity bounds may fail and the $ε^{{-2q}}$ guarantees no longer follow.","fun_headline_variants_meta":{"raw":{"variants":["O(n^q ε^{-2q}) iterations to Pareto-criticality proven","Step-size expansion yields tight worst-case bound for black-box multi-objective","Hypervolume growth certifies Pareto stationarity in derivative-free methods","New proof: derivative-free multi-objective worst-case complexity","Linesearch expansion gives O(n^q ε^{-2q}) Pareto-critical bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000977,"raw_usage":{"total_tokens":4159,"prompt_tokens":961,"completion_tokens":3198,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":577,"completion_tokens_details":{"reasoning_tokens":3104}},"tokens_in":577,"tokens_out":3198,"duration_ms":18124,"temperature":1.0,"reasoning_tokens":3104,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:44:53.012070+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run DFMOstrong on a smooth bi-objective quadratic in R^n with D_k the 2n coordinate directions, record for every iterate the ratio μ_Dk(x_k)/Δ_{k+1}, and compare it to the constant c from Proposition 2; a single iterate exceeding that constant, or an iterate with μ(x_k)>0 but μ_Dk(x_k)=0, would violate the paper's key inequality. Alternatively, inspect the iteration count needed to reach Γ(X_k)≤ε on random instances; if it grows faster than O(n^q $ε^{{-2q}}$) for fixed n and q, the bound would be contradicted.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the worst-case bound O(|L(ε)| ε^{-2q}) for the directional multisearch method and the linked-sequence machinery, which DFMOlight extends."},{"cited_title":"Fliege and B","cited_arxiv_id":null,"evidence_quote":"It provides Lemma 1 on the properties of the Pareto criticality measure μ(x), used throughout the step-size-to-stationarity argument."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It introduces the Direct Multisearch method and the list-of-points exploration that the two DFMO variants are built on."},{"cited_title":"Liuzzi, S","cited_arxiv_id":null,"evidence_quote":"It provides the derivative-free multi-objective linesearch framework and the list-of-pairs representation used by both algorithms."},{"cited_title":"Cartis, N","cited_arxiv_id":null,"evidence_quote":"It gives the single-objective steepest-descent O(ε^{-2}) iteration bound that the q=1 specialization of the new results matches."}],"review_version":1}