Pith. sign in

REVIEW 2 major objections 3 minor 1 cited by

Lyapunov Analysis For Monotonically Forward-Backward Accelerated Algorithms

T0 review · 2 major / 3 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 proves that monotone NAG and M-FISTA, which never let the objective increase, still converge linearly on strongly convex problems, matching the accelerated rate of the originals via a kinetic-free Lyapunov function.

desk verdict Real and mostly correct core analysis of M-NAG, but the printed theorem statements invert the contraction factor and the M-FISTA extension is unsupported as written. read the letter →

arxiv 2412.13527 v3 pith:W423MVNG submitted 2024-12-18 math.OC cs.NAmath.NAstat.ML

Mingwei Fu , Bin Shi This is my paper · ORCID
classification math.OCcs.NAmath.NAstat.ML MSC 90C2565K05
keywords NesterovacceleratedgradientmonotoneaccelerationLyapunovfunctionlinearconvergencestrongconvexityFISTAproximalalgorithmsmixedsequence
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

Nesterov's accelerated gradient method (NAG) converges faster than gradient descent, but its function values can temporarily rise, which makes progress hard to monitor. The monotone variant M-NAG, and its proximal counterpart M-FISTA, accept only steps that do not increase the objective, and whether this safeguard destroys the accelerated linear rate under strong convexity has been open. This paper proves it does not: for any $\mu$-strongly convex objective with $L$-Lipschitz gradient, any step size $0 < s < 1/L$, and momentum $r \ge 2$, both M-NAG and M-FISTA converge linearly at the accelerated rate of NAG and FISTA, with a starting index $K$ that depends only on $r$ and not on the conditioning or the step size. The key structural insight is that the M-NAG update alone, not the full NAG iteration, carries enough information for the proof, which is what makes the composite extension to M-FISTA possible.

What carries the argument

The central object is a redefined mixed sequence $S_k := R_k - (k+r)s\nabla f(y_k)$, built from the classical mixed sequence $R_k = (k-1)\sqrt{s}\,v_k + r x_k$ of the implicit-velocity phase representation. Absorbing the gradient into the sequence makes the iteration difference forward-indexed, $S_{k+1} - S_k = -(k+r+1)s\nabla f(y_{k+1})$, and the symmetric insertion of the new gradient term cancels the gradient-velocity cross term in the energy balance. The resulting Lyapunov function $E(k) = s(k+1)(k+r+1)(f(x_{k+1}) - f(x^\star)) + \tfrac{1}{2}\|k(y_k - x_k) + r(y_k - x^\star) - (k+r)s\nabla f(y_k)\|^2$ contains mixed energy but no kinetic term, so it can be written entirely in terms of $x_k$ and $y_k$ and is therefore valid for M-NAG, whose update never supplies the velocity through an explicit position update. The proof establishes $E(k+1) - E(k) \le -\frac{\mu s(1-Ls)}{4}\,E(k+1)$ for every $k \ge K$, which is a geometric contraction of the Lyapunov function; the threshold $K$ is the point where the coefficient comparison in the proof first turns favorable.

What would settle it

Run M-FISTA exactly as written in (4.16) on a strongly convex composite problem, for instance $f(x) = \tfrac{1}{2}\|Ax - b\|^2 + \tfrac{\mu}{2}\|x\|^2$ with $g(x) = \lambda\|x\|_1$, and record $\Phi(x_{k+1}) - \Phi(x_k)$ at every iteration; any accepted step with a positive value shows the full-objective monotonicity the proof invokes is not implied by the printed test. A separate arithmetic check: on a quadratic, test whether the factor $[1 + (1-Ls)\mu s/4]^k$ in the numerator of (4.2) can ever be part of an informative bound, since the proof's decrement (4.14) gives a contraction only when that factor is inverted.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that monotonicity is compatible with accelerated linear convergence. For $f \in S^1_{\mu,L}(\mathbb{R}^d)$ with unique minimizer $x^\star$, any step size $0 < s < 1/L$, and momentum $r \ge 2$, the M-NAG iterates (1.2) satisfy, for all $k \ge \max\{1, K\}$ with $K := \max\{0, (3r^2-4r-12)/8\}$, an error bound of the form $f(x_k) - f(x^\star) \le C/(k(k+r))$ multiplied by a geometric contraction factor, with $C = (r+1)(f(x_1)-f(x^\star)) + r^2 L\|x_1 - x^\star\|^2$, and the identical statement holds for M-FISTA with $\Phi = f + g$. The proof's engine is the decrement inequality $E(k+1) - E(k) \le -(\mu s(1-Ls)/4)\, E(k+1)$ for a Lyapunov function $E$ built from a new mixed sequence $S_k = R_k - (k+r)s\nabla f(y_k)$; iterating this inequality gives a contraction ratio $1/(1 + \mu s(1-Ls)/4)$ per step. The same construction re-proves linear convergence for NAG and FISTA themselves without any kinetic-energy term, and the paper further shows that recovering the full NAG iterate sequence from M-NAG requires exactly one extra assumption, either the position update or the phase-coupling relation, so the Lyapunov argument uses the minimal necessary structure.

Load-bearing premise

For the composite result, the proof assumes the algorithm's acceptance step makes the full objective $\Phi = f + g$ non-increasing, but the M-FISTA scheme as printed compares only the smooth part, $f(z_k)$ against $f(x_k)$; if the nonsmooth term can rise on an accepted step, the monotonicity premise for $\Phi$ fails and the Lyapunov decrement no longer follows.

Editorial extensions

If this is right

  • Monotone descent costs no rate: M-NAG and M-FISTA converge linearly on strongly convex problems for every step size $0 < s < 1/L$ and momentum $r \ge 2$, with the same accelerated error decay as NAG and FISTA.
  • The starting index $K = \max\{0, (3r^2-4r-12)/8\}$ is independent of $\mu$, $L$, $s$, and the initial point, so the linear-convergence guarantee is uniform in the conditioning of the problem.
  • Because the Lyapunov function uses only the M-NAG update rule, the technique transfers to any forward-backward method whose update is a combination of the gradient step and the momentum step, without needing the full NAG iterate structure.
  • For composite objectives $\Phi = f + g$, the two proximal inequalities (2.7) and (2.8) carry the smooth-case argument through unchanged, so the linear rate covers Lasso-type problems solved by FISTA and M-FISTA.
  • As a by-product, NAG and FISTA receive a new Lyapunov proof of linear convergence (Theorems 3.1 and 3.2) that removes the kinetic-energy term used by earlier analyses.

Reading between the lines

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

  • Read literally, the displayed rates in Theorems 3.1 through 4.2 put the factor $[1 + (1-Ls)\mu s/4]^k$ in the numerator, which grows with $k$ and would make the bounds vacuous; the proof's own decrement (4.14) implies the intended factor is inverted, $[1 + \mu s(1-Ls)/4]^{-(k-K)}$, so the paper's real claim is a genuine geometric contraction and the displayed exponent appears to be a slip.
  • The cleanest repair of the composite gap is to test the full objective in the acceptance step: comparing $\Phi(z_k)$ with $\Phi(x_k)$ in (4.16b) would make the hypothesis of Theorem 4.2 match its proof, and the same Lyapunov machinery would apply unchanged.
  • Because the new Lyapunov function has no kinetic energy, it is a natural candidate for the monotone strong-convex variant M-NAG-SC that the paper proposes in Section 5 but leaves open, where the kinetic term was exactly the obstacle it names.
  • The structural observation that M-NAG needs either the position update or the phase-coupling relation to reproduce NAG suggests the monotone filter discards precisely the velocity information those relations encode; one could probe how much is lost by testing whether the $k(k+r)$ denominator in the new bound is tight on quadratics.
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

2 major / 3 minor

Summary. This paper studies monotone accelerated forward-backward methods under strong convexity. The authors introduce a new mixed sequence S_k = R_k - (k+r)s\nabla f(y_k) (or its proximal analogue with sG_s(y_k)), build a Lyapunov function without a kinetic-energy term, and derive contraction estimates. The main claims are linear convergence of NAG and FISTA (Theorems 3.1 and 3.2) and of M-NAG and M-FISTA (Theorems 4.1 and 4.2), with a starting index K that depends only on the momentum parameter r. The body contains detailed algebraic proofs for NAG, FISTA, and M-NAG; the M-FISTA extension is only sketched.

Significance. If the stated results are corrected, the paper would close a natural open question: monotonic variants of accelerated gradient methods retain linear convergence under strong convexity. The Lyapunov construction is explicit, the contraction estimate is algebraic and does not fit parameters to the conclusion, and the index K is independent of \mu,L,s, which is a useful feature. The proximal extension via Lemmas 2.3 and 2.4 is a sensible use of existing machinery. However, as printed the main theorems do not state a meaningful linear rate, and the M-FISTA result is unsupported; these issues must be resolved before the contribution is valid.

major comments (2)
  1. [Theorems 3.1, 3.2, 4.1, 4.2, Eqs. (3.11), (3.24), (4.2), (4.18)] The factor [1+(1-Ls)\mu s/4]^k is placed in the numerator of the displayed bounds. For 0<s<1/L this factor is strictly larger than 1, so each right-hand side grows exponentially in k and the displayed inequalities are vacuous for large k; they do not assert linear convergence. The contraction derived in (3.18) and (4.14) rearranges to E(k+1) \le (1 + \mu s(1-Ls)/4)^{-1} E(k), so the factor should appear in the denominator, equivalently as [1 + \mu s(1-Ls)/4]^{-k}, in all four theorem statements.
  2. [Section 4.2, Theorem 4.2, algorithm (4.16)] The acceptance test (4.16b) compares only f(z_k) with f(x_k), but the convergence target is the composite objective \Phi=f+g. To carry over the M-NAG proof, the composite version of step (4.4) requires \Phi(x_{k+2}) \le \Phi(z_{k+1}) before Lemma 2.3 can be applied to the accepted point, since G_s and Lemma 2.3 are statements about \Phi. The displayed f-only test gives no control over the nonsmooth term g, so the claimed generalization of (4.4), (4.8), and (4.11) to the M-FISTA setting is not justified. As written, Theorem 4.2 is stated without proof and its sketched route does not go through; either the algorithm should use the full-objective comparison \Phi(z_k) \le \Phi(x_k) with a corresponding proof supplied, or the theorem should be restricted accordingly.
minor comments (3)
  1. [Section 3.3, text before Theorem 3.2] "As seed in Section 3.2" should read "As seen in Section 3.2".
  2. [Section 4.1, proof of Theorem 4.1] After Eq. (4.10), the text says "Substituting this bound (3.15) into (4.10)"; the reference should be to the analogous strong-convexity lower bound in the current section, not to Eq. (3.15).
  3. [Throughout] There are several typos and residual errors: "seqeunce", "comparision", "Lyapnov", "tern", and "This Lyapunov function p is" near Eq. (4.1) should be corrected.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular reduction: the Lyapunov derivation is self-contained algebra; Theorem 4.2 has a non-circular correctness gap.

full rationale

The paper does not fit parameters, rename a known result as a prediction, or import a uniqueness conclusion from its own prior work. The central NAG and M-NAG arguments construct the Lyapunov function (3.10)/(4.1) explicitly from the mixed-sequence identity (1.10)/(1.12), and the decrement estimates rely only on the standard strong-convexity inequalities (2.3)-(2.4), the Lipschitz condition (2.1), and the monotone acceptance property f(x_{k+2}) <= f(z_{k+1}), which follows from the M-NAG rule (1.2b). The proximal extension invokes Lemmas 2.3-2.4 from Li et al. [2024a,b]; these are prior results with overlapping authorship, but they are intermediate proximal inequalities stated in the paper, not the target linear-convergence theorem, and they are not fitted to, or equivalent to, the conclusion of Theorem 4.2. Thus no load-bearing step reduces by construction to its own input. Two non-circular concerns remain. First, Theorem 4.2 is not proved as printed: the M-FISTA acceptance test (4.16b) compares f(z_k) with f(x_k), whereas the generalized versions of (4.4), (4.8), and (4.11) require a full-objective comparison Phi(x_{k+2}) <= Phi(z_{k+1}); the paper asserts this generalization via Lemma 2.3 and Lemma 2.4 without supplying the missing argument, so the theorem is unsupported but not circular. Second, the displayed rates (3.11), (4.2), and (4.18) contain a factor [1 + (1-Ls) mu s / 4]^k, which grows rather than contracts and is inconsistent with the contraction obtained in (3.18) and (4.14); this appears to be a typographical error, not a circular step.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The central proof introduces no new particles, forces, or independent dynamical entities. The mixed sequences R_k and S_k are proof devices, not entities with independent falsifiable handles. The only hand-chosen quantity is the Lyapunov coefficient tau(k), which is exact and not fitted. The main assumptions are standard strong-convexity/smoothness conditions plus two cited proximal lemmas; the M-FISTA full-objective monotonicity assumption is flagged as a gap.

free parameters (1)
  • Lyapunov potential coefficient tau(k) = (k+1)(k+r+1)
    Chosen by hand to cancel the inner-product terms I and II in the Lyapunov difference (equations 3.9 and 3.4). It is an exact algebraic choice, not a number fitted to data, and it does not change the algorithm.
assumptions (6)
  • domain assumption f belongs to S^1_{mu,L}(R^d), i.e., mu-strongly convex with L-Lipschitz gradient.
    Section 2, equations (2.1)-(2.2). This is the problem class for all four linear convergence theorems.
  • domain assumption Step size obeys 0 < s < 1/L.
    Used throughout; guarantees s - Ls^2/2 > 0 and 1-Ls > 0, which the Lyapunov contraction needs.
  • domain assumption Momentum parameter r >= 2.
    Defined with the NAG scheme (1.1); the coefficient (r-2)k + r^2 - 3 in (3.14) becomes nonnegative only for sufficiently large k, hence the starting index K depends on r.
  • standard math Fundamental inequalities (2.3) and (2.4).
    Stated in Section 2 as consequences of strong convexity and Lipschitz smoothness; the paper does not prove them, but they are standard.
  • standard math Lemma 2.3 and Lemma 2.4 from Li et al. 2024a,b.
    Proximal analogs of (2.3)-(2.4), cited rather than proved. The present second author overlaps with those references, so this is self-citation but not circular.
  • ad hoc to paper M-FISTA comparison gives full-objective monotonicity Phi(x_{k+2}) <= Phi(z_{k+1}).
    This is needed to generalize the M-NAG potential-energy bound to the composite setting, but equations (4.15b) and (4.16b) only compare f. The paper does not flag this gap.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Lyapunov Analysis For Monotonically Forward-Backward Accelerated Algorithms." pith.science (2026). https://pith.science/paper/W423MVNG

@misc{pith2026241213527,
  author       = {Pith},
  title        = {Pith review of: Lyapunov Analysis For Monotonically Forward-Backward Accelerated Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W423MVNG}},
  note         = {Machine review of arXiv:2412.13527}
}
read the original abstract

Nesterov's accelerated gradient method (NAG) achieves faster convergence than gradient descent for convex optimization but lacks monotonicity in function values. To address this, Beck and Teboulle [2009b] proposed a monotonic variant, M-NAG, and extended it to the proximal setting as M-FISTA for composite problems such as Lasso. However, establishing the linear convergence of M-NAG and M-FISTA under strong convexity remains an open problem. In this paper, we analyze M-NAG via the implicit-velocity phase representation and show that an additional assumption, either the position update or the phase-coupling relation, is necessary to fully recover the NAG iterates. The essence of M-NAG lies in controlling an auxiliary sequence to enforce non-increase. We further demonstrate that the M-NAG update alone is sufficient to construct a Lyapunov function guaranteeing linear convergence, without relying on full NAG iterates. By modifying the mixed sequence to incorporate forward-indexed gradients, we develop a new Lyapunov function that removes the kinetic energy term, enabling a direct extension to M-NAG. The required starting index depends only on the momentum parameter and not on problem constants. Finally, leveraging newly developed proximal inequalities, we extend our results to M-FISTA, establishing its linear convergence and deepening the theoretical understanding of monotonic accelerated methods.

Figures

Figures reproduced from arXiv: 2412.13527 by the authors.

Figure 1
Figure 1. Numerical comparison of the iterative progressio [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Illustration of how M-NAG consolidates the momentum and gradient steps of classical NAG into a unified update rule. Each solid arrow A → B indicates that B is a component or derived step of A. The acceleration mechanism of NAG was rigorously uncovered by the high-resolution differen￾tial equation framework proposed by Shi et al. [2022]. In particular, the implicit-velocity scheme has been shown to outperform the gra… view at source ↗
Figure 3
Figure 3. Illustration of how M-NAG recovers the NAG update though the implicit-velocity phase￾representation. Each solid arrow A → B indicates that B is a component or derived step of A, while each dashed arrow represents a conditional relation required to establish the connection. particularly transparent when examining the logical equivalence among the velocity update (1.4b), the mixed-sequence iteration (1.7), and the M-N… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Numerical comparison of the progression of functi [PITH_FULL_IMAGE:figures/full_fig_p020_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A Family of Controllable Momentum Coefficients for Forward-Backward Accelerated Algorithms

    math.OC 2025-01 conditional novelty 6.0 of 10

    A family of Nesterov-type methods with power-law momentum achieves controllable O(1/k^{2α}) convergence for strongly convex objectives at the critical step size, including monotone and proximal variants.

Reference graph

Works this paper leans on

21 extracted references · 5 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Attouch and J

    H. Attouch and J. Peypouquet. The rate of convergence of nesterov's accelerated forward-backward method is actually faster than 1/k^2 . SIAM Journal on Optimization, 26 0 (3): 0 1824--1834, 2016

    2016

  2. [2]

    Attouch, P.-E

    H. Attouch, P.-E. Maing \'e , and P. Redont. A second-order differential system with hessian-driven damping; application to non-elastic shock laws. Differential Equations and Applications, 4 0 (1): 0 27--65, 2012

    2012

  3. [3]

    Attouch, J

    H. Attouch, J. Peypouquet, and P. Redont. A dynamical approach to an inertial forward-backward algorithm for convex minimization. SIAM Journal on Optimization, 24 0 (1): 0 232--256, 2014

    2014

  4. [4]

    A. Beck. First-order methods in optimization. SIAM, 2017

    2017

  5. [5]

    Beck and M

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

    2009

  6. [6]

    A. Cauchy. M \'e thode g \'e n \'e rale pour la r \'e solution des systemes d’ \'e quations simultan \'e es. Comp. Rend. Sci. Paris, 25 0 (1847): 0 536--538, 1847

  7. [7]

    Chambolle and T

    A. Chambolle and T. Pock. An introduction to continuous optimization for imaging. Acta Numerica, 25: 0 161--319, 2016

    2016

  8. [8]

    S. Chen, B. Shi, and Y.-x. Yuan. Gradient norm minimization of nesterov acceleration: o(1/k^ 3 ) . arXiv preprint arXiv:2209.08862, 2022 a

    arXiv 2022

Show all 21 references
  1. [9]

    S. Chen, B. Shi, and Y.-x. Yuan. Revisiting the acceleration phenomenon via high-resolution differential equations. arXiv preprint arXiv:2212.05700, 2022 b

    2022 arXiv

  2. [10]

    S. Chen, B. Shi, and Y.-x. Yuan. On underdamped nesterov's acceleration. arXiv preprint arXiv:2304.14642, 2023

    2023 arXiv

  3. [11]

    Giselsson and S

    P. Giselsson and S. Boyd. Monotonicity and restart in fast gradient methods. In 53rd IEEE Conference on Decision and Control, pages 5058--5063. IEEE, 2014

    2014

  4. [12]

    B. Li, B. Shi, and Y.-X. Yuan. Linear convergence of ISTA and FISTA . arXiv preprint arXiv:2212.06319, 2022 a

    2022 arXiv

  5. [13]

    B. Li, B. Shi, and Y.-x. Yuan. Proximal subgradient norm minimization of ista and fista. arXiv preprint arXiv:2211.01610, 2022 b

    2022 arXiv

  6. [14]

    B. Li, B. Shi, and Y.-x. Yuan. Linear convergence of forward-backward accelerated algorithms without knowledge of the modulus of strong convexity. SIAM Journal on Optimization, 34 0 (2): 0 2150--2168, 2024 a

    2024

  7. [15]

    B. Li, B. Shi, and Y.-X. Yuan. Linear convergence of ISTA and FISTA . Journal of the Operations Research Society of China, pages 1--19, 2024 b

    2024

  8. [16]

    Nesterov

    Y. Nesterov. A method of solving a convex programming problem with convergence rate o(1/k^2) . Soviet Mathematics-Doklady,, 27 0 (2): 0 372--376, 1983

    1983

  9. [17]

    Nesterov

    Y. Nesterov. Lectures on Convex Optimization, volume 137. Springer, second edition, 2018

    2018

  10. [18]

    O’Donoghue and E

    B. O’Donoghue and E. Candes. Adaptive restart for accelerated gradient schemes. Foundations of computational mathematics, 15: 0 715--732, 2015

    2015

  11. [19]

    B. Shi, S. S. Du, M. I. Jordan, and W. J. Su. Understanding the acceleration phenomenon via high-resolution differential equations. Mathematical Programming, pages 79--148, 2022

    2022

  12. [20]

    W. Su, S. Boyd, and E. J. Candes. A differential equation for modeling nesterov's accelerated gradient method: Theory and insights. Journal of Machine Learning Research, 17 0 (153): 0 1--43, 2016

    2016

  13. [21]

    Wibisono, A

    A. Wibisono, A. C. Wilson, and M. I. Jordan. A variational perspective on accelerated methods in optimization. proceedings of the National Academy of Sciences, 113 0 (47): 0 E7351--E7358, 2016

    2016

Pith tools

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