{"id":"c2691eda-ccb9-4e97-bf08-38b67eb34875","arxiv_id":"2506.08181","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A cubic regularization method for multiobjective optimization that finds approximate Pareto-critical points in O(epsilon^-3/2) iterations under standard smoothness assumptions.","lead":"The authors introduce a cubic regularization algorithm for multiobjective optimization, where several objectives are minimized simultaneously, and prove that it reaches an approximate trade-off point in a bounded number of iterations. The result is relevant to anyone who needs automated methods to balance competing goals, such as error versus model complexity in machine learning.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The abstract's finite-difference complexity exponents do not match the bounds proved in the paper; the advertised O(n^(1-beta)) iterations should read O(n^(3(1-beta)/2)).","rationale":"The reader's verdict is CONDITIONAL with HIGH confidence, and the main reason given in the rationale is precisely the mismatch between the abstract's dimension-dependent complexity claims and the bounds actually derived in Remark 3.15. My independent recomputation of the n-dependence confirms that the abstract overclaims: the proved iteration bound is O(n^(3(1-beta)/2) epsilon^(-3/2)) and the function-evaluation bound is O(m n^((7-3beta)/2) epsilon^(-3/2)), not the advertised O(n^(1-beta)) and O(m n^(3-beta)). This is the most load-bearing concern because it concerns the central advertised contribution of the derivative-free variant, and it is an internal inconsistency rather than a matter of external consensus. The proof of Theorem 3.3 itself appears coherent, and the local convergence arguments in Theorems 3.6-3.8 are internally consistent. I also examined the reader's weakest_assumption about the subproblem solver oracle; it is a reasonable caveat, but existence of an approximate KKT point satisfying (3.2) follows from the coercivity of the subproblem, and treating the solver as an oracle is standard in this literature, so it is less decisive than the arithmetic overclaim. A secondary technical gap is that Algorithm 2 defines h proportional to ||x_t - x_{t-1}|| and would be undefined if a zero step occurred, but this is avoidable with a stopping safeguard and is not the central issue. For these reasons I recommend keeping the reader's CONDITIONAL verdict unchanged, conditional on correcting the advertised complexity exponents.","tokens_in":26617,"tokens_out":20201,"duration_ms":228347,"concrete_test":"Recompute the n-dependence of the constant C in Theorem 3.3 by substituting kappa_G = L n^((1-2beta)/2) and kappa_H = L n^(1-beta) from Lemmas 3.9 and 3.14 into Delta_0 as defined in (3.6). Compare the resulting exponent of n in the iteration bound O(Delta_0 Delta_1 epsilon^(-3/2)) with the abstract's O(n^(1-beta) epsilon^(-3/2)). Then multiply by the O(m n^2) cost per inner iteration from Lemma 3.2 and compare the total function-evaluation exponent with the abstract's O(m n^(3-beta) epsilon^(-3/2)). If the exponents differ (they should: 3(1-beta)/2 versus 1-beta, and (7-3beta)/2 versus 3-beta), the abstract and introduction must be revised to match the proved bounds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline derivative-free complexity claims in the abstract and Section 1 are not supported by the proof. From Lemmas 3.9 and 3.14, the finite-difference error tolerances yield kappa_G = L n^((1-2beta)/2) and kappa_H = L n^(1-beta). Substituting these into Delta_0 in (3.6), the dominant term is sigma_max + 2 kappa_G + 2 kappa_H ~ kappa_H for beta < 1, so Delta_0 ~ (n^(1-beta))^(3/2) = n^(3(1-beta)/2). Theorem 3.3 therefore gives an iteration bound of O(n^(3(1-beta)/2) epsilon^(-3/2)), not the O(n^(1-beta) epsilon^(-3/2)) stated in the abstract. Multiplying by the O(m n^2) function evaluations per inner iteration (Lemma 3.2) gives O(m n^((7-3beta)/2) epsilon^(-3/2)), not O(m n^(3-beta) epsilon^(-3/2)). This is an internal arithmetic inconsistency in the central advertised result: the proof actually establishes a weaker dimension dependence than claimed. It does not invalidate the O(C epsilon^(-3/2)) iteration bound for the exact-derivative method, but it requires either correcting the abstract and introduction or finding a different finite-difference step choice that yields the advertised exponents.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a multiobjective cubic regularization method (M-CRM) for nonconvex unconstrained multiobjective optimization. At each outer iteration, the algorithm constructs cubic-regularized models from approximate gradients and Hessians of the objective components, solves the resulting subproblem approximately in the KKT sense, and adjusts both the regularization parameter and the derivative-approximation accuracy through a nonmonotone line search. The main theoretical results are an O(C ε^{-3/2}) iteration bound for reaching an ε-approximate Pareto critical point under globally Lipschitz Hessians and bounded-below objectives, finite-difference variants of the algorithm, global convergence to weak Pareto critical points, and local superlinear or quadratic convergence under strong convexity of the objectives on a level set. Numerical experiments compare exact and inexact versions of the method against a safeguarded multiobjective Newton method, and a derivative-free variant is applied to a regularized logistic regression problem.","tokens_in":26856,"tokens_out":12937,"duration_ms":138389,"significance":"If the stated complexity claims are corrected, this is a valuable contribution. The exact-derivative version delivers the expected O(ε^{-3/2}) complexity for multiobjective cubic regularization, the joint adaptive control of the regularization parameter and derivative accuracy is a useful algorithmic idea, and the numerical study is reasonably extensive for a methods paper. The paper also contains careful proofs of global convergence and local rates, and the derivative-free implementation is accompanied by detailed finite-difference error bounds. The main weakness is that the abstract and introduction advertise finite-difference complexity exponents that are stronger than what the proofs establish; the correct exponents already appear in Remarks 3.13 and 3.15, so the discrepancy is internally visible and, in principle, fixable by rewriting the advertised claims.","major_comments":[{"comment":"The derivative-free complexity claims in the Abstract and Section 1 are not supported by the proof. Lemma 3.9 gives κ̄_G = L n^{(1-2β)/2} and Lemma 3.14 gives κ̄_H = L n^{1-β} for the finite-difference gradient and Hessian. Substituting these into Δ_0 in Eq. (3.6), the dominant term for β<1 is α(2κ̄_H)/2 ~ L n^{1-β}, so Δ_0 ~ n^{3(1-β)/2}. Theorem 3.3 therefore yields O(n^{3(1-β)/2} ε^{-3/2}) iterations, and multiplying by the O(m n^2) function evaluations per inner iteration (Lemma 3.2) gives O(m n^{(7-3β)/2} ε^{-3/2}) function evaluations. These are exactly the bounds stated in Remark 3.15, but they contradict the Abstract's O(n^{1-β} ε^{-3/2}) iterations and O(m n^{3-β} ε^{-3/2}) function evaluations. The advertised exponents are off by a factor of (3/2) in the iteration exponent and by n^{1/2} in the evaluation exponent; the Abstract and Section 1 should be corrected to match Remark 3.15, unless a different finite-difference step choice can justify the stronger bound.","section":"Abstract, Section 1, and Remark 3.15"},{"comment":"The same dimension-exponent error appears in the claim for exact gradients with Hessians computed by finite differences based on gradient values. Section 1 states an iteration bound of O(n^{(1-2β)/2} ε^{-3/2}) and O(m n^{(3-2β)/2}) function and gradient evaluations for β∈[0,1/2]. However, Lemma 3.12 gives κ̄_H = L n^{(1-2β)/2}; with κ̄_G = 0, Eq. (3.6) gives Δ_0 ~ n^{3(1-2β)/4}, so Theorem 3.3 yields O(n^{3(1-2β)/4} ε^{-3/2}) iterations and, with O(m n) evaluations per inner iteration, O(m n^{(7-6β)/4} ε^{-3/2}) total evaluations. These are precisely the bounds stated in Remark 3.13. The Section 1 claims again omit the 3/2 power on the dimension-dependent factor and should be corrected.","section":"Section 1 and Remark 3.13"}],"minor_comments":[{"comment":"The displayed formula for the central-difference Hessian appears to have a typo in the last column: it reads ∇F_j(x+he_n) - ∇F_j(x-he_1), which should presumably be ∇F_j(x+he_n) - ∇F_j(x-he_n).","section":"Lemma 3.12, Eq. (3.38)"},{"comment":"The expression for the step size h in Lemma 3.9 is typeset ambiguously: h := √6‖x_t-x_{t-1}‖/(n^β α^{(i-1)})^{1/2} should be written as h = sqrt(6) ‖x_t-x_{t-1}‖ / (n^β α^{i-1})^{1/2}, and the same ambiguity affects Algorithm 2's definition of h. The derivation in Appendix A confirms the intended exponent, but the notation should be clarified.","section":"Lemma 3.9 and Algorithm 2"},{"comment":"The formula for δ_T has an unbalanced parenthesis: it should read δ_T ≤ δ[2T + log_α(2(L + 3α(2κ̄_G + κ̄_H)) + σ_1) - log_α(σ_1)].","section":"Lemma 3.2, Eq. (3.5)"},{"comment":"The caption of Figure 2 refers to 'M-CRM-I-DF2' while the text consistently calls the method 'M-CRM-I-DF'; the caption should be made consistent.","section":"Figure 2 and Section 4.2"}],"recommendation":"major_revision","confidential_remarks":"The central algorithmic framework and the main complexity theorem for the exact-derivative case appear sound, and the correct finite-difference exponents are already stated in Remarks 3.13 and 3.15. The problem is that the abstract and introduction repeat a different, stronger set of exponents that the proofs do not support. Since the correct bounds are present in the body, this is fixable by editing the advertised claims. The paper would benefit from a careful pass to ensure that every statement of the finite-difference complexity uses the same exponents. In my view this is a major revision rather than a rejection: the underlying results are defensible, but the abstract's headline numbers are currently misleading."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nTwo things to know: this is a serious extension of cubic regularization to multiobjective problems, and the advertised derivative-free complexity exponents in the abstract and introduction do not match what the proofs actually show. The exact-derivative O(epsilon^{-3/2}) iteration bound is correct; the finite-difference claims need fixing.\n\nWhat's actually new: the method minimizes a cubic-regularized max model, allows inexact gradients and Hessians with error tolerances tied to the previous step, and adjusts the regularization parameter and derivative accuracy together through a nonmonotone line search. That joint adjustment is not in the multiobjective literature. The convergence machinery is careful: Corollary 2.3 gives the telescoping decrease, Theorem 3.3 gives the O(Delta_0 Delta_1 epsilon^{-3/2}) bound under Lipschitz Hessians, and the local analysis gives superlinear and quadratic rates under local strong convexity. The finite-difference lemmas in the appendix are worked out with explicit constants. The numerical experiments on 44 test problems with 4,400 instances, compared against a safeguarded multiobjective Newton method, are honest and reasonably extensive.\n\nThe soft spot is the abstract. From Lemmas 3.9 and 3.14, the finite-difference gradient error kappa_G ~ n^{(1-2beta)/2} and Hessian error kappa_H ~ n^{1-beta} enter Delta_0 through (sigma_max + 2 kappa_G + 2 kappa_H)^{3/2}, which is dominated by n^{3(1-beta)/2}. Remark 3.15(i) states exactly this: O(n^{3(1-beta)/2} epsilon^{-3/2}) iterations and O(m n^{(7-3beta)/2} epsilon^{-3/2}) evaluations. But the abstract and introduction claim O(n^{1-beta}) and O(m n^{3-beta}). Those are the advertised numbers and they are wrong. The fix is straightforward: correct the abstract and introduction to match Remark 3.15. This does not touch the exact-derivative complexity or the local rates.\n\nOne more caveat, minor but real: the algorithm relies on an oracle that returns an approximate KKT point of the cubic subproblem satisfying (3.2) with fixed theta. The paper mentions Algencan for numerics but gives no complexity or guarantee for the subproblem solver. That is standard in this literature, but it is worth a sentence acknowledging the oracle is load-bearing.\n\nWho it's for: researchers in multiobjective optimization who want a cubic-regularization baseline and a derivative-free variant. It deserves a serious referee. The abstract should be fixed before publication, but the core is sound and the novelty is genuine.\n\nRecommendation: send it to review, with the referee asked to focus on the finite-difference exponent correction.","headline":"A solid multiobjective cubic regularization paper with a genuine algorithmic novelty and correct main complexity bound, but the abstract's derivative-free dimension exponents don't match the proofs and need correcting.","tokens_in":27409,"tokens_out":2304,"would_cite":true,"duration_ms":25561,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["49M15","65K05","90C26","90C29"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims a cubic regularization method using approximate gradients and Hessians and a nonmonotone acceptance rule reaches an $\\epsilon$-approximate Pareto critical point in at most $O(C\\epsilon^{-3/2})$ iterations, with explicit…","keywords":["cubic regularization","multiobjective optimization","Pareto critical point","iteration complexity","finite differences","derivative-free optimization","nonconvex optimization","nonmonotone line search"],"falsifier":"On a smooth nonconvex multiobjective instance with known Lipschitz constants, run the method for a sequence of tolerances $\\epsilon$ and record the first iteration where $\\|\\sum_j \\lambda_t^j \\nabla F_j(x_t)\\le \\epsilon$; the central claim predicts the count grows at most like a constant times $\\epsilon^{-3/2}$, so observing a steeper growth rate, or a failure of the inner solver to meet (3.2), would refute the theorem.","tokens_in":26393,"feed_emoji":"🎯","tokens_out":10968,"duration_ms":123172,"temperature":0.7,"pith_summary":"This paper introduces M-CRM, a cubic regularization method for unconstrained multiobjective optimization that builds a model from the maximum of cubic-regularized component models and minimizes it at every iteration. It tries to establish that, when each objective has a globally Lipschitz Hessian and is bounded below, the method produces an $\\epsilon$-approximate Pareto critical point in at most $O(C\\epsilon^{-3/2})$ iterations, where $C$ collects the Lipschitz constant, initial data, and inexactness parameters. The method deliberately allows gradient and Hessian approximations, and it tunes the regularization parameter and the required derivative accuracy together through a nonmonotone line search, so no user-supplied decrease tolerance is needed. For finite-difference implementations the paper gives iteration and function-evaluation bounds that depend on the dimension $n$, the number of objectives $m$, and a stepsize exponent $\\beta$; under local strong convexity it also shows superlinear convergence with exact gradients and quadratic convergence with exact gradients and Hessians. The contribution matters because it transfers the worst-case guarantees of scalar cubic regularization to the multiobjective setting while tolerating inexact derivative information.","feed_headline":"Cubic regularization reaches Pareto criticality in O(ε^{-3/2}) steps","feed_subtitle":"Approximate gradients and Hessians still give global convergence and an ε^{-3/2} iteration bound.","key_machinery":"The carrying object is the regularized model $M_{x,\\sigma}(y)=\\max_{j\\in\\mathcal{J}} M^j_{x,\\sigma}(y)$, with $M^j_{x,\\sigma}(y)=\\langle \\bar\\nabla F_j(x),y-x\\rangle+\\tfrac12\\langle \\bar\\nabla^2 F_j(x)(y-x),y-x\\rangle+\\tfrac{\\sigma}{6}\\|y-x\\|^3$, together with the approximate KKT conditions (3.2) on subproblem (1.3). The cubic term makes the model coercive, so a solution exists, and it yields the key decrease inequality (2.9), which converts Taylor-model error and finite-difference derivative errors into a step-size-dependent decrease. The nonmonotone acceptance test (3.3) then raises $\\sigma$ (and tightens the derivative-error tolerances (3.1)) until that inequality holds, producing the telescoping sum that gives the $\\epsilon^{-3/2}$ iteration bound.","core_discovery":"The central claim is that the scalar cubic-regularization paradigm survives the passage to several objectives: a point $(x_{t+1},\\lambda_{t+1})$ generated from an approximate KKT point of subproblem (1.3) decreases every component of $F$ by an amount controlled by the cubic step, and this decrease is strong enough to make the weighted gradient sums $\\sum_j \\lambda_t^j \\nabla F_j(x_t)$ tend to zero. Consequently all limit points of the sequence are Pareto critical, and an $\\epsilon$-approximate Pareto critical point is certified in at most $O(C\\epsilon^{-3/2})$ outer iterations under assumptions (A1)-(A2). When derivatives are unavailable, the paper shows that central finite-difference formulas with step proportional to $\\|x_t-x_{t-1}\\|/n^\\beta$ satisfy the required error conditions, leading to $O(n^{1-\\beta}\\epsilon^{-3/2})$ iterations and $O(mn^{3-\\beta}\\epsilon^{-3/2})$ function evaluations for the derivative-free variant. Under the local convexity assumption (A3), the same sequence is shown to converge to a local Pareto solution, superlinearly if gradients are exact and quadratically if both gradients and Hessians are exact.","pith_inferences":["The practical cost of the derivative-free variant is dominated by the shrinking finite-difference step: as the iterates approach a Pareto critical point, $\\|x_t-x_{t-1}\\|\\to 0$, so $h\\to 0$ and function evaluations eventually suffer cancellation; choosing $\\beta$ close to $1$ keeps $h$ larger but weakens the iteration bound, so the experimental choice $\\beta=1/2$ is a plausible middle point.","Subproblem (1.3) has a strictly feasible point and satisfies a constraint qualification, so any generic nonlinear programming solver that returns a point meeting (3.2) can be substituted for the augmented-Lagrangian solver used in the experiments; the method's guarantees are solver-agnostic.","The error conditions (3.1) only require that gradient and Hessian errors decay with the previous step, so subsampled or randomized derivative estimators could plausibly be plugged in place of finite differences, at the price of probabilistic versions of Lemmas 3.9-3.14."],"forward_implications":["If the central claim is right, smooth nonconvex multiobjective problems can be solved with provable worst-case guarantees using only approximate gradients and Hessians, matching the scalar cubic-regularization rate of $O(\\epsilon^{-3/2})$.","The derivative-free variant makes the cost of missing analytic derivatives explicit: with $\\beta\\in[0,1]$ controlling the finite-difference step, the iteration count is $O(n^{1-\\beta}\\epsilon^{-3/2})$ and the function-evaluation count is $O(mn^{3-\\beta}\\epsilon^{-3/2})$, allowing a trade-off between larger steps (fewer, cheaper iterations) and smaller steps (more reliable derivative approximations","Under local convexity the method does not sacrifice speed: exact gradients give superlinear convergence, and exact gradients plus Hessians give quadratic convergence, so the inexactness controls mainly affect the earlier, global phase of the run.","Because the acceptance rule is nonmonotone and parameter-free, the algorithm can be used as a black-box stop when the weighted gradient norm, or its finite-difference proxy, falls below a tolerance, without pre-tuning a sufficient-decrease parameter."],"supporting_citations":[{"why":"Defines scalar cubic regularization and its global $O(\\epsilon^{-3/2})$ complexity, the template the multiobjective method extends.","marker":"[29]"},{"why":"Supplies the implementable inexactness conditions and finite-difference Hessian approximation bounds reused in the M-CRM analysis.","marker":"[24]"},{"why":"The prior high-order regularization framework for multiobjective problems that M-CRM is contrasted with and shown not to fall into.","marker":"[11]"},{"why":"The safeguarded multiobjective Newton method used as the numerical baseline and source of test problems.","marker":"[22]"},{"why":"Provides the multiobjective Newton and KKT optimality background behind Pareto criticality and the weighted-gradient conditions.","marker":"[14]"},{"why":"Gives the lazy and first- and zeroth-order regularized Newton analysis whose finite-difference Hessian bounds support Lemma 3.14.","marker":"[13]"}],"fun_headline_variants":["Multiobjective cubic regularization: O(ε^{-3/2}) to Pareto critical","Cubic regularization for multiobjective: global convergence and O(ε^{-3/2})","Approximate derivatives still give cubic multiobjective convergence","Derivative-free cubic method achieves O(ε^{-3/2}) for Pareto criticality"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The analysis assumes that every iteration can call a subroutine that returns an approximate solution of the cubic subproblem satisfying the fixed tolerance conditions (3.2), and that all objective Hessians are globally Lipschitz; if either fails, the stated iteration bounds are not guaranteed.","fun_headline_variants_meta":{"raw":{"variants":["Multiobjective cubic regularization: O(ε^{-3/2}) to Pareto critical","Cubic regularization for multiobjective: global convergence and O(ε^{-3/2})","Approximate derivatives still give cubic multiobjective convergence","Derivative-free cubic method achieves O(ε^{-3/2}) for Pareto criticality"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000698,"raw_usage":{"total_tokens":3240,"prompt_tokens":1121,"completion_tokens":2119,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":737,"completion_tokens_details":{"reasoning_tokens":2035}},"tokens_in":737,"tokens_out":2119,"duration_ms":19355,"temperature":1.0,"reasoning_tokens":2035,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:19:19.194939+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a smooth nonconvex multiobjective instance with known Lipschitz constants, run the method for a sequence of tolerances $\\epsilon$ and record the first iteration where $\\|\\sum_j \\lambda_t^j \\nabla F_j(x_t)\\le \\epsilon$; the central claim predicts the count grows at most like a constant times $\\epsilon^{-3/2}$, so observing a steeper growth rate, or a failure of the inner solver to meet (3.2), would refute the theorem.","supporting_citations":[{"cited_title":"Nesterov and B","cited_arxiv_id":null,"evidence_quote":"Defines scalar cubic regularization and its global $O(\\epsilon^{-3/2})$ complexity, the template the multiobjective method extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the implementable inexactness conditions and finite-difference Hessian approximation bounds reused in the M-CRM analysis."},{"cited_title":"Calder \\'o n, M","cited_arxiv_id":null,"evidence_quote":"The prior high-order regularization framework for multiobjective problems that M-CRM is contrasted with and shown not to fall into."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The safeguarded multiobjective Newton method used as the numerical baseline and source of test problems."},{"cited_title":"Fliege, L","cited_arxiv_id":null,"evidence_quote":"Provides the multiobjective Newton and KKT optimality background behind Pareto criticality and the weighted-gradient conditions."}],"review_version":1}