{"id":"083a9edb-4f14-4612-9f8d-127b115729ff","arxiv_id":"2412.13527","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"M-NAG and M-FISTA converge linearly under strong convexity, proved with a new kinetic-energy-free Lyapunov function built from a shifted mixed sequence.","lead":"The authors prove that two monotone variants of Nesterov's accelerated gradient method, M-NAG and M-FISTA, converge linearly on strongly convex problems, closing an open theoretical question. They do this with a new Lyapunov function built from a shifted mixed sequence that avoids kinetic-energy terms.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"M-FISTA's linear convergence proof requires full-objective monotonicity, but algorithm (4.16b) tests only f; Theorem 4.2 is unsupported as stated.","rationale":"The reader's weakest assumption is precisely the M-FISTA acceptance test comparing f instead of Phi, and my reading confirms that this is the most load-bearing gap. The M-NAG proof itself is coherent: the acceptance rule gives f(x_{k+2}) <= f(z_{k+1}), the Lyapunov decrement is valid, and the contraction-factor comparison works for k beyond the stated K. The M-FISTA extension, however, is not a routine substitution: the proximal inequalities (2.7)-(2.8) are stated for Phi, and the copied proof would need full-objective monotonicity. As written, (4.16b) does not provide it, and no proof of Theorem 4.2 is included. The separate display error in the theorem statements, with [1 + (1-Ls)mu s/4]^k in the numerator rather than the denominator, is real but mechanical; correcting it does not address the substantive gap in the composite monotone setting. These issues are correctable, so a conditional verdict rather than rejection is appropriate.","tokens_in":17497,"tokens_out":18716,"duration_ms":170977,"concrete_test":"Re-derive the composite analogue of (4.4) and check whether (4.16b) implies Phi(x_{k+2}) <= Phi(z_{k+1}). A direct numerical check is to run M-FISTA (4.16) with the printed f-only test on a one-dimensional composite problem, e.g. f(x) = (x-1)^2, g(x) = lambda|x|, s = 0.05, r = 2, scanning lambda over a grid while tracking Phi(x_k) - Phi(x_{k-1}). If any run shows an increase in Phi while f decreases, the f-only acceptance rule fails the full-objective monotonicity on which the Lyapunov decrement depends. If instead the test is changed to the full objective Phi, the decrement proof should be written explicitly and checked at each inequality.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.2 asserts that Lemmas 2.3 and 2.4 let the M-NAG proof be copied for M-FISTA. In the M-NAG proof, the acceptance rule enters at (4.4) and (4.8): both need f(x_{k+2}) <= f(z_{k+1}) so that the fundamental inequality can be applied with the accepted iterate. The composite analogue must control Phi(z_{k+1}) - Phi(x_{k+1}), hence needs Phi(x_{k+2}) <= Phi(z_{k+1}). However, algorithm (4.16b) accepts z_k only when f(z_k) <= f(x_k); the nonsmooth term g is never compared, so the displayed rule does not imply the required full-objective comparison. Since G_s and Lemmas 2.3-2.4 are statements about Phi, the f-only test does not make the generalized (4.4), (4.8), and (4.11) valid. If the intended algorithm is the standard Beck-Teboulle monotone FISTA, the test should read Phi(z_k) <= Phi(x_k) and a proof of Theorem 4.2 must be supplied. As printed, Theorem 4.2 is stated without proof and its only sketched route does not go through.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17742,"tokens_out":9365,"duration_ms":75474,"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":[{"comment":"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.","section":"Theorems 3.1, 3.2, 4.1, 4.2, Eqs. (3.11), (3.24), (4.2), (4.18)"},{"comment":"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.","section":"Section 4.2, Theorem 4.2, algorithm (4.16)"}],"minor_comments":[{"comment":"\"As seed in Section 3.2\" should read \"As seen in Section 3.2\".","section":"Section 3.3, text before Theorem 3.2"},{"comment":"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).","section":"Section 4.1, proof of Theorem 4.1"},{"comment":"There are several typos and residual errors: \"seqeunce\", \"comparision\", \"Lyapnov\", \"tern\", and \"This Lyapunov function p is\" near Eq. (4.1) should be corrected.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"For the editor: the manuscript borrows Lemmas 2.3 and 2.4 from work with which the second author overlaps; the borrowing is acknowledged and appears appropriate, and I do not see a circularity problem. The central issue is that Theorem 4.2 as printed is not proven and appears to analyze a different acceptance rule than the one stated. The numerator/denominator error in all four theorem statements is elementary but substantive because it removes the claimed linear rate. I would encourage a resubmission after the theorems are restated correctly and the M-FISTA proof is supplied."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core M-NAG analysis is real and mostly right; what the paper claims is not what the displayed theorems say. All four theorem statements put the factor [1+(1−Ls)µs/4]^k in the numerator, so the right-hand sides grow with k and the displayed rates are vacuous. The proof itself derives a contraction E(k+1) ≤ (1/(1+ρ)) E(k), so the factor should be in the denominator. This looks like a repeated typo rather than a broken argument, but it must be fixed before anything is cited.\n\nWhat is genuinely new: the mixed sequence S_k = R_k − (k+r)s∇f(y_k), the Lyapunov function without the kinetic energy term, and the explicit starting index K that depends only on r. The M-NAG proof in Section 4.1 is detailed and, as far as I can tell, algebraically sound. The extension from NAG to M-NAG is the first linear-convergence proof for these monotone variants, and the contribution is significant if the statements are corrected. The reliance on Li et al. for the proximal inequalities is legitimate: those are published results, and the self-citation does not bother me.\n\nThe soft spots are real but localized. First, the theorem statement typo is load-bearing because the abstract and introduction promise linear convergence. Second, Theorem 4.2 for M-FISTA is stated without a proof; Section 4.2 only says the M-NAG proof can be copied. Third, and more substantive, the M-FISTA acceptance test in (4.15b)/(4.16b) compares f(z_k) ≤ f(x_k), not Φ(z_k) ≤ Φ(x_k). The composite Lyapunov argument needs Φ(x_{k+2}) ≤ Φ(z_{k+1}) to apply Lemma 2.3, and an f-only test does not control the nonsmooth term g when the candidate is rejected. The standard Beck–Teboulle monotone FISTA uses the full objective, so this looks like a definition error rather than a deep obstacle, but as written Theorem 4.2 does not follow.\n\nI would send this to peer review. A serious referee can verify the M-NAG algebra, flag the inverted factors, and require a real proof of Theorem 4.2 with the correct acceptance rule. The central idea deserves referee time; it just needs to be presented accurately.","headline":"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.","tokens_in":18319,"tokens_out":3841,"would_cite":false,"duration_ms":35163,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Nesterov accelerated gradient","monotone acceleration","Lyapunov function","linear convergence","strong convexity","FISTA","proximal algorithms","mixed sequence"],"falsifier":"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.","tokens_in":17229,"feed_emoji":"⚡","tokens_out":17625,"duration_ms":123474,"temperature":0.7,"pith_summary":"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.","feed_headline":"Monotone NAG keeps its speed: linear convergence proved","feed_subtitle":"New Lyapunov proof shows M-NAG and M-FISTA keep Nesterov's accelerated linear rate on strongly convex problems.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces M-NAG and M-FISTA, the monotone algorithms whose linear convergence is the paper's target.","marker":"Beck and Teboulle [2009b]"},{"why":"Introduces NAG, the base accelerated scheme whose rate the monotone variants are required to preserve.","marker":"Nesterov [1983]"},{"why":"Introduces FISTA and the proximal fundamental inequality that the composite analysis generalizes.","marker":"Beck and Teboulle [2009a]"},{"why":"Supplies the high-resolution differential-equation framework and the implicit-velocity representation that organizes the analysis.","marker":"Shi et al. [2022]"},{"why":"Introduces the classical mixed sequence $R_k$ and the phase-coupling relation that the new sequence modifies.","marker":"Chen et al. [2022a]"},{"why":"Provides the principled Lyapunov-construction approach the paper follows.","marker":"Chen et al. [2022b]"},{"why":"Proves the prior linear-convergence result for FISTA whose kinetic-energy Lyapunov term blocks extension to M-NAG, and supplies proximal inequality (2.8).","marker":"Li et al. [2024a]"},{"why":"Supplies the proximal fundamental inequality (2.7) used to extend the argument to composite objectives.","marker":"Li et al. [2024b]"}],"fun_headline_variants":["Linear convergence proved for monotone NAG and FISTA","Lyapunov function shows M-NAG retains accelerated rate","Monotonicity and speed coexist in M-NAG, Lyapunov proves","New proof: M-NAG and M-FISTA converge linearly"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Linear convergence proved for monotone NAG and FISTA","Lyapunov function shows M-NAG retains accelerated rate","Monotonicity and speed coexist in M-NAG, Lyapunov proves","New proof: M-NAG and M-FISTA converge linearly"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000561,"raw_usage":{"total_tokens":2778,"prompt_tokens":1174,"completion_tokens":1604,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":790,"completion_tokens_details":{"reasoning_tokens":1526}},"tokens_in":790,"tokens_out":1604,"duration_ms":13364,"temperature":1.0,"reasoning_tokens":1526,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T13:02:55.687619+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}