{"id":"d5eeca2f-1ec5-4323-8e53-c9e6e8ab34f3","arxiv_id":"2602.05893","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"MO-Adagrad finds Pareto critical points at rate O(1/√k) in the squared norm of a common descent direction while evaluating no objective function.","lead":"This paper introduces MO-Adagrad, a multi-objective optimizer that never evaluates objective functions, using only gradients to get a shared descent direction and an adaptive Adagrad-style step. The authors prove a worst-case O(1/√k) convergence rate and show competitive robustness on benchmark and multi-task problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 15 proof uses threshold ς^2 e^{2Γ0/Lmax} that does not imply inequality (16) for ς<1/2; the case split omits a region, so the stated constant is unproven.","rationale":"The central claim is the O(1/√k) rate. The proof of Theorem 15 has a genuine gap: the threshold used to switch cases does not justify the substitution of Γ0 via (16) for ς<1/2. This is a correctness issue in the main theorem's proof, not merely a loose constant: for the experimental value ς=10^{-2}, the proof as written fails for an interval of possible S values. However, the gap is local and fixable by replacing ς² with ς/2 in the threshold; the rate order survives. I therefore do not see a need to reject the paper, but the condition should be updated. The reader's weakest_assumption about exact subproblem solves is also real, but it concerns the algorithm's practical implementation rather than the mathematical statement; the ς-threshold issue is more directly load-bearing for Theorem 15. Independent support: the descent lemma (Lemma 11) uses only Lipschitz gradients and the exact-subproblem identity (Lemma 10), which is proven under the stated exact-solve assumption.","tokens_in":18571,"tokens_out":25573,"duration_ms":223851,"concrete_test":"Verify the implication (15)⇒(16) directly: set ς=0.01, Γ0=Lmax=1, S=0.02. Then S≥max{0.01, 0.0001e²}=0.01, so (15) holds, but the right-hand side of (16) is 0.5·log(4)≈0.693 < 1, so (16) fails. This demonstrates the case split is incomplete; if the proof is corrected by replacing ς² with ς/2, the theorem's constant must be updated accordingly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 15's proof assumes (15) S ≥ max{ς, ς²e^{2Γ0/Lmax}} implies (16) Γ0 ≤ Lmax/2 log(2S/ς). This implication is false for ς<1/2: (16) requires S ≥ (ς/2)e^{2Γ0/Lmax}, and since ς² < ς/2, there is a gap ς²e^{...} ≤ S < (ς/2)e^{...}. For example, ς=0.01, Γ0=Lmax=1, S=0.02 satisfies (15) but (16) gives 1 ≤ 0.5 log(4) ≈ 0.693, false. The proof then uses (16) to replace Γ0 in (14) and obtain the O(1/(k+1)) bound; without it the argument stops. The numerical implementation uses ς=10^{-2}, so this is not a corner case. The theorem's constant θ = max{ς, ς²e^{...}, 2048Lmax^4/ς} should read max{ς, (ς/2)e^{...}, 2048Lmax^4/ς}; the order O(1/√k) is unaffected, but Theorem 15 as stated is not proven for ς<1/2.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes MO-Adagrad, an Adagrad-norm-type method for unconstrained multi-objective optimization. At each iteration it computes a common descent direction -g^s_k by solving the convex subproblem that minimizes the norm of a convex combination of gradients, then takes a step -g^s_k / w_k, where w_k accumulates past values of ||g^s_ℓ||. The method never evaluates objective functions and does not use line search or knowledge of Lipschitz constants. The main theoretical result, Theorem 15, gives an O(1/√(k+1)) bound on the average of ||g^s_ℓ||², hence on the criticality measure ω, under smoothness and boundedness of Φ = max_j f_j. Numerical experiments on CUTEst-based bi-objective instances, noisy variants, and two multi-task classification problems compare MO-Adagrad with a line-search steepest-descent method.","tokens_in":18913,"tokens_out":11896,"duration_ms":117266,"significance":"If the rate theorem is correct, the paper provides a clean function-free, line-search-free multi-objective method with essentially the same O(1/√k) worst-case criticality rate as standard first-order methods, extending objective-function-free Adagrad theory to the multi-objective setting. Strengths include self-contained proofs of the relation between the subproblem solution and the criticality measure (Lemmas 9–10), a concise descent analysis (Lemma 11), and broad numerical validation including a noisy setting. The main theorem, however, has a proof gap in the parameter regime actually used in the experiments; the gap is fixable and does not appear to threaten the rate itself. The analysis also assumes exact subproblem solutions while the implementation uses approximate ones, an issue that should be addressed.","major_comments":[{"comment":"The proof assumes that S := Σ_{ℓ=0}^k ||g^s_ℓ||² ≥ max{ς, ς² e^{2Γ0/Lmax}} implies Γ0 ≤ (Lmax/2) log(2S/ς). This implication requires S ≥ (ς/2) e^{2Γ0/Lmax}. For ς < 1/2, ς² e^{2Γ0/Lmax} < (ς/2) e^{2Γ0/Lmax}, so (15) does not imply (16). Example: ς=0.01, Γ0=Lmax=1, S=0.02 satisfies (15) but (16) gives 1 ≤ 0.5 log(4) ≈ 0.693, which is false. Since Algorithm 1 is run with ς=10^{-2} in Section 4, this is the operative parameter regime, and the stated θ is not proven. The fix is to replace the threshold by max{ς, (ς/2)e^{2Γ0/Lmax}} and the second term of θ by (ς/2)e^{2Γ0/Lmax}; alternatively, one can apply Lemma 13 directly to (14) with b=Γ0, avoiding (16) entirely and yielding a smaller constant. The O(1/√k) rate is preserved, but Theorem 15 as written is not proven.","section":"Theorem 15 / proof of Eqs. (15)–(16)"},{"comment":"The convergence analysis assumes that (Ω(x_k)) is solved exactly at every iteration: Lemma 10's identity ||g^s_k||² = -max_j ∇f_j(x_k)^T(-g^s_k) and Lemma 11's descent inequality use the exact minimizer g^s_k. In the experiments, (Ω) is solved with fmincon to finite tolerance, and no account is taken of the resulting inexactness. The numerical section therefore does not directly validate the theorem, and the algorithm as implemented is not covered by the rate guarantee. Please either analyze the inexact case (for example, with a subproblem tolerance criterion that preserves the descent bound) or clearly state and discuss the assumption and its practical implications.","section":"Algorithm 1, Step 2 and Theorem 15"}],"minor_comments":[{"comment":"The sentence 'any efficient point for (MOP) is also efficient for (MOP)' should read 'also weakly efficient for (MOP)'.","section":"Section 2, after Definition of weak efficiency"},{"comment":"The phrase 'does not require neither knowledge of Lipschitz constants nor the use of line search procedures' contains a double negative; use 'requires neither ... nor' or 'does not require either ... or'.","section":"Abstract"},{"comment":"The definition of O uses a limit, but ratios of sequences need not have a limit; limsup is the standard notion and avoids excluding oscillating cases.","section":"Footnote 3"},{"comment":"The constant '64² Lmax⁴ / ς²' is easy to misread after OCR; please write it explicitly as '4096 Lmax⁴ / ς²' for clarity.","section":"Theorem 15 proof, after Eq. (19)"},{"comment":"The text says both algorithms solve the 5 benchmark problems for all noise levels, but Table 2 includes CUTEst instances with failures; please clarify the distinction between the benchmark set and the CUTEst-based set.","section":"Section 4.2, Table 2"}],"recommendation":"major_revision","confidential_remarks":"The central rate claim appears defensible, but Theorem 15 has a genuine proof gap in a parameter regime actually used in the experiments, and the exact-subproblem assumption is not matched by the implementation. Both issues are fixable within the manuscript's scope, so I recommend major revision rather than rejection. The concurrent work [18] is acknowledged, and attribution/citation practices do not raise concerns for me."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the new thing: the paper proposes MO-Adagrad, an Adagrad-norm style method for unconstrained multi-objective optimization that never evaluates the objective functions. The step is a scaled common descent direction obtained from a convex subproblem, and the main result is an O(1/√k) rate on the average squared norm of the criticality measure. That is a real step for function-free multi-objective methods, and the proof structure—duality in Lemma 9/10, descent Lemma 11, then the standard Adagrad log-sum inequality—is mostly clean. The numerical study is reasonable: 124 CUTEst-derived bi-objective problems and two small multi-task classification examples; the noise robustness observation is plausible.\n\nThe main soft spot is a gap in the proof of Theorem 15. The stress-test note is correct: inequality (16) does not follow from assumption (15) when ς < 1/2. The threshold should be (ς/2)e^{2Γ0/Lmax} rather than ς²e^{2Γ0/Lmax}; since the experiments use ς=10^{-2}, the theorem as stated is unproven in the practical range. The order of the rate is likely unaffected, but the constant needs correction.\n\nA second, minor gap: the theory requires an exact solution of the subproblem (Ω(x_k)) at every iteration, while the experiments use fmincon to finite tolerance. No analysis quantifies the effect of approximate solutions on the bound. Also, the data/code are not public; the paper just says \"available upon request.\"\n\nOverall, I think the paper is honest and technically interesting, and the flaw is repairable. It deserves a serious referee rather than a desk reject. I'd send it to review with a request to fix the theorem's case split, comment on the subproblem tolerance, and release the code/data.","headline":"A useful MO-Adagrad algorithm with a clean O(1/√k) rate proof, except the main theorem's proof has a threshold gap for the practical ς<1/2 range; worth refereeing but needs a fix.","tokens_in":19400,"tokens_out":7762,"would_cite":true,"duration_ms":65470,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C29","90C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that multi-objective optimization can be done without ever evaluating objective functions, using an Adagrad-style adaptive step, and still converge to Pareto critical points at rate O(1/√k).","keywords":["multi-objective optimization","objective-function-free optimization","Adagrad-like algorithm","common descent direction","convergence rate","Pareto critical point","multi-task learning","noisy optimization"],"falsifier":"Run MO-Adagrad on a smooth bi-objective problem, solving the subproblem exactly or with a certified tolerance, and plot min_{ℓ≤k}∥g^s_ℓ∥ against √(θ/(k+1)) with θ from Theorem 15; a persistent violation of that bound would refute the theorem. A cheaper check is to evaluate the identity ∥g^s_k∥² = -max_j ∇f_j(x_k)ᵀ(-g^s_k) at every iterate: if it fails by more than numerical noise, the descent argument in Lemma 10 is invalid.","tokens_in":18470,"feed_emoji":"📉","tokens_out":7577,"duration_ms":76119,"temperature":0.7,"pith_summary":"The paper proposes MO-Adagrad, a first-order method for unconstrained multi-objective problems that never evaluates the objective functions. At each step it computes a common descent direction — the negative of the minimal-norm convex combination of the gradients — and scales it by an Adagrad-style weight built from past gradient norms. The paper proves that the average squared norm of this direction decays as θ/(k+1), so the best direction found in the first k iterations has norm at most O(1/√k). This matters because the method needs no line search, no Lipschitz constants, and no dominance test for accepting new points, making it attractive when objective evaluations are expensive, noisy, or comparable in cost to gradient evaluations. Numerical tests on bi-objective benchmarks and small multi-task learning problems support the theory and show improved robustness over a line-search descent method.","feed_headline":"No function values: multi-objective optimization converges at O(1/√k)","feed_subtitle":"All it needs is gradients and an Adagrad-style step: no line search, no Lipschitz constants, no dominance test.","key_machinery":"The load-bearing object is the common descent direction -g^s_k, where g^s_k is the unique minimal-Euclidean-norm vector in the convex hull of the gradients at x_k, obtained by solving the small convex subproblem Ω(x_k); if this vector is zero, x_k is Pareto critical. The step is s_k = -g^s_k / w_k with w_k = √(ς + Σ_{ℓ≤k}∥g^s_ℓ∥²), an Adagrad-norm accumulator that makes the stepsize adaptive. The key identity ∥g^s_k∥² = -max_j ∇f_j(x_k)ᵀ(-g^s_k) shows that the same quantity measures both criticality and the local decrease of the max objective Φ, which lets the convergence proof proceed without evaluating Φ or any f_j. A descent lemma for Φ then yields the telescoping sum whose careful accoun","core_discovery":"The central result is Theorem 15: if MO-Adagrad is run on a smooth multi-objective problem whose gradients are Lipschitz and for which max_j f_j is bounded below, then the average over the first k+1 iterates of the squared norm of the common descent direction g^s_ℓ is at most θ/(k+1), where θ depends only on the initial gap in the max objective, the Lipschitz constants, and the parameter ς. Consequently the minimum of ∥g^s_ℓ∥ over ℓ ≤ k is at most √(θ/(k+1)), an O(1/√(k+1)) global rate for the norm of the common descent direction. The proof rests on the identity ∥g^s_k∥² = -max_j ∇f_j(x_k)ᵀ(-g^s_k), which connects the minimal-norm convex combination of gradients to the steepest common descen","pith_inferences":["A natural testable extension is to allow approximate solutions of the subproblem and quantify how the approximation error enters θ; the current proof requires the exact minimal-norm convex combination, while the experiments use a finite-precision solver.","The average-type rate implies that a uniformly random iterate among the first k is near-critical in the Cesàro sense; this could support cheap front exploration by multistart, an extension the paper flags but does not develop.","The robustness to noise seen in the preliminary experiments suggests that a stochastic version using gradient estimates could inherit the same adaptive-stepsize structure; providing high-probability rates in that setting is a natural next step not covered in the paper."],"forward_implications":["A multi-objective optimizer can drive all objectives toward a Pareto critical point using only gradient information; objective values are never needed, so the method applies when function evaluations are noisy, expensive, or unavailable.","The stepsize is fully automatic: past gradient norms set the learning rate, so no line search and no knowledge of Lipschitz constants is required, matching the simplicity of single-objective Adagrad.","The convergence guarantee is global and explicit: after k iterations the best common descent direction found has norm at most √(θ/(k+1)), so the worst-case iteration count to reach criticality ε is O(1/ε²).","In the paper's experiments, MO-Adagrad solved more of the 124 bi-objective test instances than the line-search descent method (89% versus 77%), and under added noise its identified critical points stayed closer to the noise-free solutions.","On the two small multi-task classification problems, MO-Adagrad reached comparable test accuracy roughly three times faster than the line-search method, because it never evaluates the losses."],"fun_headline_variants":["MO-Adagrad: multi-objective optimization without function values","Gradient-only multi-objective optimization hits O(1/√k) rate","No line search, no Lipschitz constants: multi-objective Adagrad","Common descent direction only: O(1/√k) multi-objective convergence"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof assumes the convex subproblem that produces the common descent direction is solved exactly at every iteration; if it is only solved approximately, the key identity ∥g^s_k∥² = -max_j ∇f_j(x_k)ᵀ(-g^s_k) can fail, and the paper gives no bound on how this error affects the O(1/√k) rate.","fun_headline_variants_meta":{"raw":{"variants":["MO-Adagrad: multi-objective optimization without function values","Gradient-only multi-objective optimization hits O(1/√k) rate","No line search, no Lipschitz constants: multi-objective Adagrad","Common descent direction only: O(1/√k) multi-objective convergence"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00069,"raw_usage":{"total_tokens":2967,"prompt_tokens":756,"completion_tokens":2211,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":500,"completion_tokens_details":{"reasoning_tokens":2128}},"tokens_in":500,"tokens_out":2211,"duration_ms":16073,"temperature":1.0,"reasoning_tokens":2128,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T04:05:47.125611+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run MO-Adagrad on a smooth bi-objective problem, solving the subproblem exactly or with a certified tolerance, and plot min_{ℓ≤k}∥g^s_ℓ∥ against √(θ/(k+1)) with θ from Theorem 15; a persistent violation of that bound would refute the theorem. A cheaper check is to evaluate the identity ∥g^s_k∥² = -max_j ∇f_j(x_k)ᵀ(-g^s_k) at every iterate: if it fails by more than numerical noise, the descent argument in Lemma 10 is invalid.","supporting_citations":[],"review_version":1}