{"id":"7a04f0e0-e0f4-4e72-a279-9c65957ba2e6","arxiv_id":"2412.14007","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A FISTA-style method with a new backtracking line search claims O(1/k^2) convergence for convex multiobjective optimization when the Lipschitz constant is unknown.","lead":"This paper proposes a backtracking variant of an accelerated proximal gradient method for multiobjective optimization, for cases where the smoothness constant is unknown. It claims a quadratic convergence rate to weakly Pareto optimal solutions, matching the rate of FISTA for single-objective problems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The O(1/k^2) proof inherits a growth bound from [13, Lemma 3.4] that Algorithm 1's line search does not imply; as printed, the algorithm also fails to define the sequences it bounds.","rationale":"Read in good faith, the paper aims to extend FISTA with backtracking to multiobjective optimization and to prove an O(1/k^2) rate without knowing L(f). The single most load-bearing condition is the transfer of the [13] growth bound to this algorithm's line search. The reader's weakest assumption identifies this same dependency, so I agree. An independent check shows a concrete failure mode: Step 4 is not the standard composite descent test and can require L_k near 2 for a problem whose true Lipschitz constant is epsilon, so L_k^{-1} t_k^2 >= k^2/(4 beta L(f)) cannot be guaranteed. The algorithm's undefined initialization and missing updates for y_k, t_k, and omega_k are an independent blocker: the theorem states a rate for sequences generated by Algorithm 1, but the printed algorithm does not generate any sequence. Both issues point to the central claim being unsupported, not merely to a missing reference. Since the reader already reached REJECT, my read does not change that verdict.","tokens_in":9814,"tokens_out":22986,"duration_ms":197589,"concrete_test":"Run the scalar composite problem F(x)=100x+(epsilon/2)x^2+x^2 through Algorithm 1's Step 4 at y=0, with beta=2. Record the first accepted L_k. With epsilon=10^{-6}, the test rejects every L < 2+epsilon and accepts L=2+epsilon, so L_k/(beta L(f)) is about 10^6, directly falsifying the premise L_k <= beta L(f) needed to transfer [13, Lemma 3.4]. Independently, a line-by-line execution of Algorithm 1 for K=2 fails at Steps 2-3 because L_0, x_1, and y_2 are undefined.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 9's bound u0(xk) <= 4 beta L(f) R/(k+1)^2. The proof's final step uses L_k^{-1} t_k^2 >= k^2/(4 beta L(f)), imported from [13, Lemma 3.4]. In [13], that bound follows because the backtracking test is the standard composite L-smoothness test and stops with L_k <= beta L(f). Algorithm 1 does not satisfy this premise. Step 4 tests F_i(xhat_k) <= <grad f_i(y_k), xhat_k-y_k> + F_i(y_k) + (L_k/2)||xhat_k-y_k||^2, i.e. the nonsmooth reference is g_i(y_k), not g_i(xhat_k). This is not the inequality used in Proposition 7, and it can force L_k far above L(f). Concretely, for m=1, f(x)=100x+(epsilon/2)x^2, g(x)=x^2, y=0, the subproblem minimizer is xhat = -100/(2+epsilon+L), and Step 4 holds only when L >= 2+epsilon, while L(f)=epsilon. Thus L_k is not bounded by beta L(f), and the k^2/(4 beta L(f)) growth bound has no basis; the stated constant and rate are unsupported. Compounding this, Algorithm 1 is not executable as printed: L_0 is used at k=1 though only L_1 is input, x_1 is used before generation, and the accepted branch never updates y_k, t_k, or omega_k, so no well-defined sequence exists.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a backtracking variant of the accelerated proximal gradient method for composite multiobjective optimization, i.e., problem (1) where each objective is the sum of a smooth convex function and a nonsmooth convex function. The central claim is Theorem 9: if Algorithm 1 generates the sequences under Assumptions 2 and 5, then the merit function satisfies u0(xk) ≤ 4βL(f)R/(k+1)^2, giving an O(1/k^2) convergence rate without prior knowledge of the Lipschitz constant L(f). The argument combines a FISTA-type momentum sequence {t_k}, a non-monotone Lipschitz estimate {L_k}, the auxiliary sequence σ_k(z) from [12], and a growth bound imported from [13]. The paper also reports numerical experiments comparing the proposed method with mFISTA.","tokens_in":10253,"tokens_out":5184,"duration_ms":48038,"significance":"If the central claim were valid, the paper would address a practically important gap: extending FISTA-type acceleration to multiobjective problems when the Lipschitz constant is unknown. The idea of combining a non-monotone backtracking rule with the auxiliary sequences of [12] and the momentum sequence of [13] is a reasonable research direction, and the numerical section shows promising raw timings on several test problems. However, the manuscript as written does not establish the claimed rate: the algorithm is not fully specified, the line search condition is not the one needed for the proof, and several load-bearing steps in the proof of Theorem 9 are asserted rather than derived. For these reasons, the contribution cannot be evaluated as a valid convergence guarantee in its current form.","major_comments":[{"comment":"Algorithm 1 is not well-defined. The input sets L1 > 0, but line 2 at iteration k=1 executes L1 ← L0/σ, so L0 is undefined. Line 3 computes x̂_k = p_{L_k}(x_k, y_k), but at k=1 the point x_1 has not yet been generated. Most importantly, the accepted branch (lines 7–9) contains no update of y_k, t_k, or ω_k after setting x_{k+1} ← x̂_k; these momentum quantities are updated only inside the rejected branch via FISTA-Step. Consequently, the 'sequences generated by Algorithm 1' to which Theorems 8 and 9 refer are not uniquely defined, and the algorithm does not implement the accelerated momentum coupling that the proof requires.","section":"Section 3, Algorithm 1"},{"comment":"Inequality (17), namely 2L_0^{-1}σ_1(z) + ||x_1 - z||^2 ≤ ||x_0 - z||^2, is asserted without proof and is load-bearing: it is the starting point of the telescoping argument that leads to the bound on σ_{k+1}(z). No preceding lemma establishes it, and it is not a routine algebraic identity because σ_1(z) can be negative. The proof of Theorem 9 therefore has a gap at its first nontrivial step.","section":"Section 4, Theorem 9, Eq. (17)"},{"comment":"The line search condition in Step 4 tests F_i(x̂_k) ≤ ⟨∇f_i(y_k), x̂_k − y_k⟩ + F_i(y_k) + (L_k/2)||x̂_k − y_k||^2, which uses g_i(y_k) on the right-hand side, not g_i(x̂_k). This is not the composite descent inequality needed in Proposition 7, which requires a bound involving the nonsmooth term at x̂_k. Consequently the proof cannot legitimately borrow [13, Lemma 3.4] to conclude L_k^{-1} t_k^2 ≥ k^2/(4βL(f)); in [13] the backtracking test is a standard descent test that stops with L_k ≤ βL(f). For a concrete failure of that bound, take m=1, f(x)=100x+(ε/2)x^2, g(x)=x^2, y=0; the subproblem minimizer satisfies x̂ = -100/(2+ε+L), and Step 4 holds only when L ≥ 2+ε, whereas L(f)=ε. Thus the growth bound and the final O(1/k^2) constant are unsupported.","section":"Section 3, Step 4; Section 4, Theorem 9"},{"comment":"The proof of Theorem 9 is not complete: the final inequality u0(xk) ≤ 4βL(f)R/(k+1)^2 is said to follow 'with similar arguments used in the proof of Theorem 3.1 (see [41, Theorem 5.2])', but reference [41] does not exist in the bibliography, which contains only 23 entries. Moreover, Proposition 4 and Theorem 8 are stated with proofs omitted ('the proof is similar...'), yet Theorem 8 (boundedness of each Fi(xk) by Fi(x0)) is essential for using the constant R in Assumption 5, and Algorithm 1 differs from the algorithm in [12] in its line search and momentum updates. These omissions are not cosmetic; they break the derivation of the central rate.","section":"Section 4, Theorem 9; Section 4, Theorem 8; Proposition 4"}],"minor_comments":[{"comment":"Assumption 2 is stated for 'f : R^n → R' with ∇f Lipschitz, but in problem (1) f is vector-valued with components f_i; the notation should define ∇f as the collection of gradients and state the Lipschitz condition componentwise or in an appropriate norm.","section":"Section 2, preliminary material"},{"comment":"The maximum in the definition of φ_{L(f)} is over 'i=1,...,n' but should be over the m objectives; this typo appears in Eq. (5).","section":"Section 3, subproblem (5)"},{"comment":"The indexing in Theorem 6(iii), θ_{k+1}^2 ≤ L_k/L_{k+1} < 1, is not clearly consistent with the definitions θ_{k+1} = (t_k−1)/t_{k+1} and ω_k = L_{k+1}/L_k; the condition should be stated with the correct subscripts and a proof rather than 'derived simply'.","section":"Section 3, FISTA-Step and Theorem 6"},{"comment":"Assumption 5 contains a grammatical and logical error: 'then there exists x ∈ X* such that F(x*) ≤ F(x)' uses x* before it is quantified, and the definition of R is incomplete. Corollary 10 then refers to 'Assumption 3', which is not defined; it presumably means Assumption 5.","section":"Section 4, Assumption 5"},{"comment":"The numerical section uses three names for the same method: Algorithm 1, mFISTA with backtracking, and NBPGMO (with APGMO as the comparator). The relation between NBPGMO/APGMO and the algorithm in Section 3 should be stated explicitly, and the implementation details needed to reproduce the experiments should be provided, especially since Algorithm 1 as printed is not executable.","section":"Section 5, numerical experiments"},{"comment":"There are numerous formatting and citation problems: the abstract writes O(1/k2) rather than O(1/k^2), the reference list has items without page ranges or complete titles, and the final proof refers to nonexistent reference [41]. These issues should be corrected in any revision.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The central claim is not established. The algorithm is not well-defined as printed, the line search condition does not imply the composite descent inequality used in the proof, and the key growth bound is imported from a setting whose backtracking test is different. These are not local fixes: repairing them would require redesigning the line search or substantially changing the proof, and the current numerical experiments cannot compensate for the absence of a valid convergence theorem. I therefore recommend rejection. If the authors can provide a corrected algorithm with a line search that genuinely bounds L_k by a constant multiple of L(f), and a complete proof of the rate, the underlying idea may be salvageable in a future submission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I read this paper, and the reader's take plus the stress-test note match my own reading. The combination is genuinely new: Scheinberg-Goldfarb-Bai's t_k recurrence grafted onto Tanabe-Fukuda-Yamashita's multiobjective FISTA, with a backtracking rule aimed at the unknown-Lipschitz case. That is a useful extension if it works, and the authors cite the relevant prior work honestly. The non-increasing L_k idea and the attempt to dodge the σ_k non-negativity obstruction are also sensible directions.\n\nBut the manuscript is not close to correct as written. Algorithm 1 is not executable: L_0 is used at k=1 although only L_1 is given, x_1 is used before it is generated, and the accepted branch never updates y_k or t_k, so the next iteration's subproblem is undefined. These might be fixable typos, but they mean there is no well-defined sequence for Theorem 9 to bound.\n\nThe proof trouble is deeper. Theorem 9 imports L_k^{-1} t_k^2 >= k^2/(4 beta L(f)) from [13, Lemma 3.4]. That lemma's premise is the standard composite backtracking test, which includes g at the new point. Algorithm 1's Step 4 instead compares against F_i(y_k), omitting the g_i(xhat)-g_i(y_k) term. The stress-test example is correct: with m=1, f(x)=100x + (epsilon/2)x^2, g(x)=x^2, y=0, the Step 4 test forces L >= 2+epsilon while L(f)=epsilon. So L_k is not bounded by beta L(f), and the growth bound has no basis. That is a load-bearing flaw, not a missing detail.\n\nOther gaps reinforce the verdict: Equation (17) is asserted without proof, Proposition 4 and Theorem 8 are omitted with a pointer to 'similar' proofs, and the final u0 bound cites a nonexistent [41, Theorem 5.2]. The numerics are not strong enough to compensate: twenty test problems, but no error bars, no sigma value, no code, and the iteration counts are often worse than the baseline. The paper does show that the authors know the area, but the central object is not well-defined and the central rate proof contradicts the stated algorithm.\n\nWho is this for? Researchers in multiobjective first-order methods, provided the algorithm and proof are reworked. For the current version I would desk reject, not referee: the flaws are in the main mechanism rather than the presentation. If the authors either change the line-search test to match the proof or prove the needed growth bound under the actual test, a fresh submission would deserve a serious referee.","headline":"Plausible mFISTA-plus-backtracking extension, but as printed the algorithm is undefined and the O(1/k^2) proof relies on a growth bound the line search does not imply.","tokens_in":10674,"tokens_out":6613,"would_cite":false,"duration_ms":59455,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C29","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proposes a backtracking accelerated proximal gradient method for multiobjective optimization and proves an O(1/k^2) weak-Pareto convergence rate without prior knowledge of the Lipschitz constant.","keywords":["backtracking strategy","accelerated proximal gradient","multiobjective optimization","convergence rate","Lipschitz constant estimation","FISTA","weak Pareto optimality","composite convex optimization"],"falsifier":"A direct check is to run the algorithm on a two-objective problem with a known Lipschitz constant, record $u_0(x_k)$ at every accepted iterate, and test whether the decay matches the claimed $1/(k+1)^2$ bound; any observed exponent worse than $k^{-2}$, or a stall caused by the accepting branch not refreshing $y_k$ and $t_k$, would contradict Theorem 9.","tokens_in":9624,"feed_emoji":"⚡","tokens_out":17729,"duration_ms":125564,"temperature":0.7,"pith_summary":"This paper introduces a backtracking accelerated proximal gradient method for composite convex multiobjective optimization, targeting problems of the form $\\min (f_1(x)+g_1(x), \\ldots, f_m(x)+g_m(x))$ where each $f_i$ is smooth with Lipschitz gradient and each $g_i$ is convex and possibly nonsmooth. The method adaptively estimates the unknown Lipschitz constant $L(f)$ through a line-search procedure that can both increase and decrease the estimate, and the paper proves that the weak-Pareto merit function $u_0$ decreases as $O(1/k^2)$, specifically $u_0(x_k) \\le 4\\beta L(f)R/(k+1)^2$. The practical significance is that the method achieves the same accelerated convergence rate as single-objective FISTA without requiring the user to supply a valid Lipschitz bound in advance. The contribution also addresses a known technical obstacle: earlier multiobjective FISTA proofs could fail when an auxiliary sequence lost non-negativity, and the new momentum sequence is designed specifically to bypass that difficulty.","feed_headline":"Backtracking FISTA for multiobjective problems hits O(1/k^2) rate","feed_subtitle":"An adaptive line search removes the need to know the gradient's Lipschitz constant in advance.","key_machinery":"The load-bearing construction is a pair of coupled sequences: the backtracking estimates $\\{L_k\\}$ for the gradient's Lipschitz constant and the momentum parameters $\\{t_k\\}$, linked by the ratio $\\omega_k = L_{k+1}/L_k$. The update $t_{k+1} = \\frac{1+\\sqrt{1+4\\omega_k t_k^2}}{2}$ defines a FISTA-style acceleration whose key algebraic feature is $L_{k+1}^{-1} t_{k+1}(t_{k+1}-1) = L_k^{-1} t_k^2$; this identity makes the error bound telescope across iterations. The line search in Step 4 of Algorithm 1 accepts a candidate $\\hat{x}_k$ only when the vector-valued descent inequality $F(\\hat{x}_k) \\preceq \\langle JF(y_k), \\hat{x}_k - y_k\\rangle + F(y_k) + \\frac{L_k}{2}\\|\\hat{x}_k - y_k\\|^2 e_m$ holds, multiplying $L_k$ by $\\beta$ when it fails and dividing by $\\sigma$ when it passes. The merit function $u_0(x) = \\sup_z \\min_i [F_i(x) - F_i(z)]$ serves as the scalar measure of weak Pareto optimality, equaling zero precisely at weakly Pareto optimal points and providing the quantity whose decay is bounded in Theorem 9.","core_discovery":"The paper proves that Algorithm 1, a multiobjective FISTA variant with a new backtracking rule, attains an $O(1/k^2)$ convergence rate for weak Pareto optimality even though the Lipschitz constant $L(f)$ of the gradient is never provided. The quantitative form of the claim is $u_0(x_k) \\le 4\\beta L(f)R/(k+1)^2$ for every iterate $k$, where $\\beta$ is the line-search growth factor, $L(f)$ is the true Lipschitz constant, and $R$ is the squared distance from the initial point to the set of weakly Pareto optimal points. The proof rests on a reparameterized momentum sequence $t_{k+1} = (1 + \\sqrt{1 + 4\\omega_k t_k^2})/2$ with $\\omega_k = L_{k+1}/L_k$, whose defining identity $L_{k+1}^{-1} t_{k+1}(t_{k+1}-1) = L_k^{-1} t_k^2$ makes the gap terms telescope. The authors argue that this identity is exactly what lets the analysis go through even when the auxiliary sequence $\\sigma_k(z)$ is not non-negative, and that the non-monotone $L_k$ updates keep step sizes from collapsing after a rejected trial point. Consequently, every accumulation point of $\\{x_k\\}$ is weakly Pareto optimal, and strict convexity upgrades this to Pareto optimality.","pith_inferences":["An obvious next test, which the authors do not run, is to probe how the constant $4\\beta L(f)$ depends on the backtracking parameters $\\beta$ and $\\sigma$ and whether a schedule of decreasing $\\beta$ can shrink the constant without losing the rate.","The algebraic identity $L_{k+1}^{-1} t_{k+1}(t_{k+1}-1) = L_k^{-1} t_k^2$ is not specific to the proximal-gradient subproblem, so it may transfer to accelerated Douglas-Rachford splitting or ADMM for vector optimization once a suitable merit function is chosen.","A natural extension is to relax the exact-solution requirement for the proximal subproblem; testing inexact solves would show whether the $O(1/k^2)$ rate survives when each subproblem is solved only to a tolerance.","The non-monotone update of $L_k$ could be combined with Barzilai-Borwein step-size rules, potentially giving a multiobjective method whose practical speed matches its proved rate."],"forward_implications":["Multiobjective composite problems can be solved at the accelerated $O(1/k^2)$ rate without a precomputed Lipschitz constant, eliminating a practical hurdle for applying mFISTA to real problems.","Because the backtracking rule lets the estimated constant $L_k$ both increase and decrease, the step sizes avoid the monotone growth that makes fixed-line-search FISTA take tiny steps after a single rejection.","The telescoping identity for $\\{t_k\\}$ gives a proof mechanism that works without assuming the auxiliary gap sequence $\\sigma_k$ is non-negative, which was the blocking point in earlier convergence analyses of backtracked mFISTA.","As a direct corollary, any accumulation point of the iterates is weakly Pareto optimal; if each component $F_i$ is strictly convex, the accumulation points are Pareto optimal.","In the numerical comparisons on a standard test suite, the backtracking variant attains higher-purity Pareto fronts in less CPU time than mFISTA with a fixed conservative step size, despite occasionally using more iterations."],"supporting_citations":[{"why":"Defines the multiobjective accelerated proximal gradient method (mFISTA) and its auxiliary sequences, which this paper extends; also supplies the comparison baseline for numerical tests.","marker":"[12]"},{"why":"Provides the momentum sequence $\\{t_k\\}$ and the growth bound $L_k^{-1} t_k^2 \\ge k^2/(4\\beta L(f))$ that Theorem 9 borrows directly.","marker":"[13]"},{"why":"Original FISTA paper whose backtracking step-size strategy is the starting point for the new line search.","marker":"[8]"},{"why":"Introduces the merit function $u_0$ used to measure weak Pareto optimality in the main theorem.","marker":"[16]"},{"why":"Gives the descent lemma used to derive the composite descent inequality in Proposition 7.","marker":"[14]"},{"why":"Supplies the Moreau-envelope gradient identity $\\nabla M_h(x) = x - \\mathrm{prox}_h(x)$ that underlies the proximal subproblem.","marker":"[15]"}],"fun_headline_variants":["Multiobjective FISTA gets O(1/k^2) rate without Lipschitz constant","Backtracking trick unlocks O(1/k^2) for multiobjective FISTA","New backtracking rule gives multiobjective optimization O(1/k^2)","No Lipschitz? Still O(1/k^2) for multiobjective FISTA","O(1/k^2) rate for multiobjective FISTA with adaptive backtracking"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The rate proof assumes the backtracking line search always terminates with an $L_k$ satisfying the descent inequality used in Proposition 7, and that the borrowed lower bound $L_k^{-1} t_k^2 \\ge k^2/(4\\beta L(f))$ holds for the sequence produced by this algorithm; if either of these fails, the $O(1/k^2)$ conclusion does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Multiobjective FISTA gets O(1/k^2) rate without Lipschitz constant","Backtracking trick unlocks O(1/k^2) for multiobjective FISTA","New backtracking rule gives multiobjective optimization O(1/k^2)","No Lipschitz? Still O(1/k^2) for multiobjective FISTA","O(1/k^2) rate for multiobjective FISTA with adaptive backtracking"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000635,"raw_usage":{"total_tokens":2923,"prompt_tokens":932,"completion_tokens":1991,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":548,"completion_tokens_details":{"reasoning_tokens":1877}},"tokens_in":548,"tokens_out":1991,"duration_ms":12850,"temperature":1.0,"reasoning_tokens":1877,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:34:48.013908+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A direct check is to run the algorithm on a two-objective problem with a known Lipschitz constant, record $u_0(x_k)$ at every accepted iterate, and test whether the decay matches the claimed $1/(k+1)^2$ bound; any observed exponent worse than $k^{-2}$, or a stall caused by the accepting branch not refreshing $y_k$ and $t_k$, would contradict Theorem 9.","supporting_citations":[{"cited_title":"An accelerated proximal gradient method for multiobjective optimization[J]","cited_arxiv_id":null,"evidence_quote":"Defines the multiobjective accelerated proximal gradient method (mFISTA) and its auxiliary sequences, which this paper extends; also supplies the comparison baseline for numerical tests."},{"cited_title":"Fast first-order methods for composite convex optimization with backtracking[J]","cited_arxiv_id":null,"evidence_quote":"Provides the momentum sequence $\\{t_k\\}$ and the growth bound $L_k^{-1} t_k^2 \\ge k^2/(4\\beta L(f))$ that Theorem 9 borrows directly."},{"cited_title":"A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J]","cited_arxiv_id":null,"evidence_quote":"Original FISTA paper whose backtracking step-size strategy is the starting point for the new line search."},{"cited_title":"Tanabe, E","cited_arxiv_id":null,"evidence_quote":"Introduces the merit function $u_0$ used to measure weak Pareto optimality in the main theorem."},{"cited_title":"Nonlinear Programming, Athena Scientific, Belmont, Massachusetts[J]","cited_arxiv_id":null,"evidence_quote":"Gives the descent lemma used to derive the composite descent inequality in Proposition 7."},{"cited_title":"Rockafellar, Convex analysis, Princeton University Press, 1997","cited_arxiv_id":null,"evidence_quote":"Supplies the Moreau-envelope gradient identity $\\nabla M_h(x) = x - \\mathrm{prox}_h(x)$ that underlies the proximal subproblem."}],"review_version":1}