Pith. sign in

REVIEW 4 major objections 6 minor 23 references

Accelerated Proximal Gradient Method with Backtracking for Multiobjective Optimization

T0 review · 4 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read 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.

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

arxiv 2412.14007 v2 pith:IRRP5GYJ submitted 2024-12-18 math.OC

Chengzhi Huang , Jian Chen , Liping Tang This is my paper · ORCID
classification math.OC MSC 90C2590C2965K05
keywords backtrackingstrategyacceleratedproximalgradientmultiobjectiveoptimizationconvergencerateLipschitzconstantestimationFISTAweakParetooptimalitycompositeconvex
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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

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

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

4 major / 6 minor

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.

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 (4)
  1. [Section 3, Algorithm 1] 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.
  2. [Section 4, Theorem 9, Eq. (17)] 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.
  3. [Section 3, Step 4; Section 4, Theorem 9] 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.
  4. [Section 4, Theorem 9; Section 4, Theorem 8; Proposition 4] 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.
minor comments (6)
  1. [Section 2, preliminary material] 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.
  2. [Section 3, subproblem (5)] 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).
  3. [Section 3, FISTA-Step and Theorem 6] 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'.
  4. [Section 4, Assumption 5] 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.
  5. [Section 5, numerical experiments] 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.
  6. [Throughout] 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.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the O(1/k^2) claim is imported from external prior work, not fitted or defined into existence; remaining issues are correctness gaps, not circularity.

full rationale

The paper's convergence proof does not reduce to its own inputs. Theorem 9 bounds u0(xk) by 4βL(f)R/(k+1)^2, and the proof derives this from an invariant involving σk and ρk, using auxiliary sequences taken from [12] (Tanabe, Fukuda, Yamashita) and the growth bound L_k^{-1} t_k^2 ≥ k^2/(4βL(f)) taken from [13, Lemma 3.4] (Scheinberg, Goldfarb, Bai). These are external, non-self sources; the paper's authors are not the authors of either cited chain. There is no fitted parameter that is later called a prediction and no quantity defined in terms of the target bound. The only self-citation in the reference list ([20], by Chen and Tang) is used as a source of a test problem, not to justify the convergence theorem, and is therefore not load-bearing. The manuscript does have serious non-circular correctness problems: the backtracking test in Step 4 uses F_i(y_k) where the proof of Proposition 7 requires g_i(x_{k+1}) in the nonsmooth term, so the line-search acceptance condition does not imply the inequality used in the proof; the claimed transfer of [13, Lemma 3.4] requires L_k ≤ βL(f), which the printed line search does not guarantee; and Algorithm 1 is not executable as written (L0 is used before being set, and the accepted branch never updates y_k or t_k). These are gaps in the derivation, but they are not cases where a prediction is equivalent to its inputs by construction. Under the circularity rubric, the honest finding is no significant circularity.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard convex smoothness and boundedness assumptions, on borrowed lemmas from [12] and [13], and on two unproved, load-bearing premises: the line search guarantee and inequality (17). The algorithm hyperparameters beta, sigma, and L1 are chosen by hand but are not fitted to data.

free parameters (3)
  • beta = 2 in experiments
    Line search multiplicative increase; appears in the rate constant 4*beta*L(f)*R in Theorem 9. Chosen by hand, not fitted.
  • sigma = not specified (stated >1)
    Line search reduction factor L_k <- L_{k-1}/sigma; algorithmic hyperparameter, not fitted.
  • L1 = 1 in experiments
    Initial Lipschitz estimate; chosen by hand. The theoretical proof does not depend on its value, but the algorithm as printed needs an L0 that is never defined.
assumptions (5)
  • domain assumption Each f_i is convex and continuously differentiable with Lipschitz gradient L(f); each g_i is convex (Assumption 2 and problem (1)).
    Used throughout Sections 3 and 4 to define the subproblem, the descent lemma, and Proposition 7.
  • domain assumption The boundedness Assumption 5 holds: R = sup inf ||x0-z||^2 < infinity over weakly Pareto points dominating the initial level set.
    Needed in Theorem 9 to replace ||x0-z||^2 by R in the u0 bound. The assumption is stated in a garbled way and mis-numbered as Assumption 1 and Assumption 3.
  • standard math The telescoping identity in Theorem 6(ii) and the growth bound L_k^{-1} t_k^2 >= k^2/(4*beta*L(f)) from [13, Lemma 3.4].
    Borrowed from Scheinberg et al. without proof; the paper merely says 'using the same discussion'.
  • ad hoc to paper Inequality (17): 2*L_0^{-1}*sigma_1(z) + ||x1-z||^2 <= ||x0-z||^2.
    Asserted without proof in Theorem 9; it is load-bearing for the telescoping bound.
  • ad hoc to paper The line search in Algorithm 1 terminates and yields accepted L_k satisfying the composite descent inequality for F including the nondifferentiable g term.
    Steps 4-6; the convergence proof assumes this, but the criterion may be too strong for composite F and termination for arbitrary g is not shown.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Accelerated Proximal Gradient Method with Backtracking for Multiobjective Optimization." pith.science (2026). https://pith.science/paper/IRRP5GYJ

@misc{pith2026241214007,
  author       = {Pith},
  title        = {Pith review of: Accelerated Proximal Gradient Method with Backtracking for Multiobjective Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IRRP5GYJ}},
  note         = {Machine review of arXiv:2412.14007}
}
abstract

This paper proposes a new backtracking strategy based on the FISTA accelerated algorithm for multiobjective optimization problems. The strategy focuses on solving the problem of Lipschitz constant being unknown. It allows estimate parameter updates non-increasingly. Furthermore, the proposed strategy effectively avoids the limitation in convergence proofs arising from the non-negativity of the auxiliary sequence, thus providing a theoretical guarantee for its performance. We demonstrate that, under relatively mild assumptions, the algorithm achieves the convergence rate of $O(1/k2)$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [12]

    An accelerated proximal gradient method for multiobjective optimization[J]

    Tanabe H, Fukuda E H, Yamashita N. An accelerated proximal gradient method for multiobjective optimization[J]. Computational Optimization and Applications, 2023, 86(2): 421-455

    work page 2023

  2. [13]

    Fast first-order methods for composite convex optimization with backtracking[J]

    Scheinberg K, Goldfarb D, Bai X. Fast first-order methods for composite convex optimization with backtracking[J]. Foundations of Computational Mathematics, 2014, 14: 389-417

    work page 2014

  3. [1]

    Bonnel, A

    H. Bonnel, A. N. Iusem and B. F. Svaiter, Proximal methods in vector optimization, SIAM Journal on Optimization, 2005, 15(4): 953-970

    work page 2005

  4. [2]

    G. A. Carrizo, P. A. Lotito and M. C. Maciel, Trust region globaliza- tion strategy for the nonconvex unconstrained multiobjective optimization problem, Mathematical Programming, 2016, 159: 339-369

    work page 2016

  5. [3]

    Fliege and B

    J. Fliege and B. F. Svaiter, Steepest descent methods for multicriteria optimization, Mathematical Methods of Operations Research, 2000, 51: 479-494

    work page 2000

  6. [4]

    Fliege, L

    J. Fliege, L. M. G. Drummond and B. F. Svaiter, Newton’s method for multiobjective optimization, SIAM Journal on Optimization, 2009, 20(2): 602-626

    work page 2009

  7. [5]

    E. H. Fukuda and L. M. Graca Drummond, Inexact projected gradi- ent method for vector optimization, Computational Optimization and Applications, 2013, 54: 473-493

    work page 2013

  8. [6]

    L. R. Lucambio P´erez and L. F. Prudente, Nonlinear conjugate gradient methods for vector optimization, SIAM Journal on Optimization, 2018, 28(3): 2690-2720

    work page 2018

Show all 23 references
  1. [7]

    A method for solving the convex programming problem with convergence rate O(1/k2)[C]//Dokl akad nauk Sssr

    Nesterov Y. A method for solving the convex programming problem with convergence rate O(1/k2)[C]//Dokl akad nauk Sssr. 1983, 269: 543

    1983

  2. [8]

    A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J]

    Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J]. SIAM journal on imaging sciences, 2009, 2(1): 183-202

    2009

  3. [9]

    Introductory lectures on convex optimization: A basic course[M]

    Nesterov Y. Introductory lectures on convex optimization: A basic course[M]. Springer Science & Business Media, 2013

    2013

  4. [10]

    Smooth minimization of non-smooth functions[J]

    Nesterov Y. Smooth minimization of non-smooth functions[J]. Mathe- matical programming, 2005, 103: 127-152. Accelerated Proximal Gradient Method with Backtracking for MOP 15

    2005

  5. [11]

    On accelerated proximal gradient methods for convex-concave optimization[J]

    Tseng P. On accelerated proximal gradient methods for convex-concave optimization[J]. submitted to SIAM Journal on Optimization, 2008, 2(3)

    2008

  6. [14]

    Nonlinear Programming, Athena Scientific, Belmont, Massachusetts[J]

    Bertsekas D P. Nonlinear Programming, Athena Scientific, Belmont, Massachusetts[J]. MR3444832, 1999

    1999

  7. [15]

    Rockafellar, Convex analysis, Princeton University Press, 1997

    M. Rockafellar, Convex analysis, Princeton University Press, 1997

    1997

  8. [16]

    Tanabe, E

    H. Tanabe, E. H. Fukuda, and N. Yamashita, New merit functions for multiobjective optimization and their properties, Optimization, 2023, 1- 38

    2023

  9. [17]

    A review of multiobjective test problems and a scalable test problem toolkit[J]

    Huband S, Hingston P, Barone L, et al. A review of multiobjective test problems and a scalable test problem toolkit[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(5): 477-506

    2006

  10. [18]

    Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems[J]

    Das I, Dennis J E. Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems[J]. SIAM journal on optimization, 1998, 8(3): 631-657

    1998

  11. [19]

    Generalized homotopy approach to multiobjective opti- mization[J]

    Hillermeier C. Generalized homotopy approach to multiobjective opti- mization[J]. Journal of Optimization Theory and Applications, 2001, 110(3): 557-583

    2001

  12. [20]

    A Barzilai-Borwein descent method for mul- tiobjective optimization problems[J]

    Chen J, Tang L, Yang X. A Barzilai-Borwein descent method for mul- tiobjective optimization problems[J]. European Journal of Operational Research, 2023, 311(1): 196-209

    2023

  13. [21]

    Dynamic weighted aggregation for evolutionary multi-objective optimization: Why does it work and how[C]//Proceedings of the genetic and evolutionary computation con- ference

    Jin Y, Olhofer M, Sendhoff B. Dynamic weighted aggregation for evolutionary multi-objective optimization: Why does it work and how[C]//Proceedings of the genetic and evolutionary computation con- ference. 2001: 1042-1049

    2001

  14. [22]

    Pareto set and EMOA behavior for simple multimodal multiobjective functions[C]//International Conference on Parallel Problem Solving from Nature

    Preuss M, Naujoks B, Rudolph G. Pareto set and EMOA behavior for simple multimodal multiobjective functions[C]//International Conference on Parallel Problem Solving from Nature. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006: 513-522. 16 Accelerated Proximal Gradient Met...

    2006

  15. [23]

    Numerical algorithms for the treatment of parametric multiobjective optimization problems and applications[D]

    Witting K. Numerical algorithms for the treatment of parametric multiobjective optimization problems and applications[D]. , 2012

    2012

Pith tools

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