{"id":"860e84c7-ee7b-47f7-91da-535557316222","arxiv_id":"2504.16876","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A new primal-dual algorithm with memory-based proximal centers attains O(1/N) ergodic convergence, but its claimed O(1/N^2) accelerated rate rests on a square-root error.","lead":"Researchers propose a new primal-dual algorithm that centers each update on a weighted average of previous solutions, proving standard convergence and running favorably on matrix games and LASSO problems. A claimed faster convergence rate in the strongly convex case is not supported by the paper's own derivation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's advertised O(1/N^2) rate does not follow from inequality (42): the derived bound gives ||y_N - ŷ|| = O(σ_{N-1}) = O(1/N) under the algorithm's own parameter update.","rationale":"The reader's verdict is CONDITIONAL with high confidence, and I agree with that assessment. The single most load-bearing issue is Theorem 4: the paper's headline accelerated rate is O(1/N^2), but inequality (42) and the parameter recurrence (37) force only O(1/N) for the dual iterate. This is a direct algebraic consequence, not a question of interpretation, so the accelerated claim cannot stand as stated. The reader's explicit weakest_assumption concerned the monotonicity of {a_k} and {b_k}; that is a genuine gap in Theorem 1's proof and should be fixed. Note that the coefficient in (28) is a_{k+3} - a_{k+2}, so the proof requires nondecreasing coefficients, or constant coefficients as used in the experiments, not the stated 'non-monotonically decreasing' condition. But that issue is repairable by a clarifying assumption, whereas the O(1/N^2) error cannot be repaired by wording. Thus the manuscript needs revision: either prove a valid O(1/N) rate for ANPDA or supply a new argument for acceleration. This supports the existing CONDITIONAL verdict rather than altering it to ACCEPT or REJECT; the NPDA and NPDAL convergence results may still be salvageable, and the numerical experiments are not called into question by this proof-level failure.","tokens_in":21457,"tokens_out":11876,"duration_ms":103987,"concrete_test":"Re-derive the step from (42) at k = N-1 without the theorem's concluding sentence, keeping the exact factor 1/(2σ_{N-1}^2) on the left-hand side. Then solve the recurrence (37) numerically for γ = 0.1, σ0 = 1 to confirm σ_N ∼ 2/(γN). As a numerical cross-check, run ANPDA on the one-dimensional saddle problem min_x max_y (xy + x^2/2 - y^2/2) and fit log||y_N - y*|| versus log N; an exponent near 1 rather than 2 would confirm that the claimed O(1/N^2) rate is not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central accelerated claim rests on Theorem 4, but the proof's final step misuses its own estimate. From (42), the term controlling the dual iterate is (1/(2σ_{N-1}^2))(1 - sqrt(τ0σ0)L) ||y_N - ŷ||^2, so the inequality yields ||y_N - ŷ|| ≤ sqrt(2C1/(1 - sqrt(τ0σ0)L)) · σ_{N-1}. Algorithm 2's update (37) gives σ_{k+1} = σ_k / sqrt(1 + γσ_k), which implies γσ_N ∼ 1/N, i.e. σ_N = O(1/N), as the proof itself invokes. Therefore the derived bound is ||y_N - ŷ|| = O(1/N), not O(1/N^2). The proof appears to read the σ_{N-1}^2 factor as if it directly produced squared error of order 1/N^4; in fact it produces squared error of order 1/N^2. No later estimate supplies the missing factor. Thus the advertised acceleration for ANPDA is not merely unproven; it is contradicted by the paper's own Lyapunov inequality.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a new primal-dual algorithm (NPDA) for convex-concave saddle point problems with bilinear coupling. NPDA uses two auxiliary averaged points, x^ag and y^ag, to define new proximal centers x^md and y^md in the primal and dual subproblems. The paper claims global convergence and an O(1/N) ergodic rate for NPDA, an accelerated version (ANPDA) with an O(1/N^2) rate for the dual variable when f* is strongly convex, and a linesearch variant (NPDAL) with global convergence and O(1/N) ergodic rate. Numerical experiments on matrix games and LASSO are reported.","tokens_in":21779,"tokens_out":8101,"duration_ms":67982,"significance":"If the O(1/N^2) acceleration for ANPDA were valid, it would be a useful contribution to the primal-dual literature, complementing Chambolle-Pock-type acceleration with a Lyapunov analysis. The idea of using averaged auxiliary points in the proximal terms is interesting and the numerical comparisons suggest practical promise. The O(1/N) proofs are self-contained Lyapunov arguments, and the dependence on [29] in Lemma 3 is transparent rather than circular. However, the central accelerated claim in Theorem 4 contains a square-root error and is not established by the paper's own inequality; this must be addressed before the contribution can be accepted.","major_comments":[{"comment":"The claimed O(1/N^2) rate for ||y_N - ŷ|| does not follow from the proof. Inequality (42) gives (1/(2σ_{N-1}^2))(1 - sqrt(τ0σ0) L) ||y_N - ŷ||^2 ≤ C1, hence ||y_N - ŷ|| ≤ sqrt(2C1/(1 - sqrt(τ0σ0) L)) · σ_{N-1}. The update (37) gives σ_k = σ_{k-1}/sqrt(1 + γσ_{k-1}), so γσ_N ~ 1/N and σ_{N-1} = O(1/N). Therefore the established bound is ||y_N - ŷ|| = O(1/N), not O(1/N^2). The proof's final sentence appears to square σ_{N-1} twice; the missing factor is not supplied anywhere else. The abstract, introduction, Algorithm 2 discussion, and Theorem 4 must be corrected, or a genuinely different argument for the O(1/N^2) rate must be supplied.","section":"§3.2, Theorem 4 and Eq. (42)"},{"comment":"The proofs require the coefficients in the Lyapunov inequality (31) to be nonnegative, but the manuscript only states that {a_k} and {b_k} are 'non-monotonic decreasing sequences'. This phrase is undefined and does not imply the needed monotonicity. For example, the coefficient 2 - a_{k+2} - 1/a_{k+3} + (1 - a_{k+3})^2/a_{k+3} simplifies to a_{k+3} - a_{k+2}; this is nonnegative only if the sequence is non-decreasing, which is the opposite of 'decreasing'. The same issue affects the coefficient conditions in ANPDA and NPDAL. The authors need to state the precise monotonicity assumption in Algorithms 1–3 and verify that every coefficient in (31), and its analogues for the other algorithms, is nonnegative under that assumption.","section":"§3.1, Theorem 1 and Eq. (31)"}],"minor_comments":[{"comment":"The initialization line references √στL, but τ and σ are not defined before Step 4; the condition should be stated in terms of τ_0, σ_0, for example √(τ_0 σ_0) L < 1 - a_k and < 1 - b_k.","section":"Algorithm 2, initialization"},{"comment":"The second part of Theorem 4 gives only the ergodic bound C1/N, which is the same order as the non-accelerated rate; the text should clarify that the claimed acceleration applies only to the dual iterate, not to the ergodic gap.","section":"Theorem 4 statement"},{"comment":"The sentence 'NPAD reduces to the classical primal-dual algorithm' contains a typo: it should read 'NPDA'.","section":"Remark 2"},{"comment":"There are several typos and grammar issues, including 'linsearch' for 'linesearch', 'quit complicated' for 'quite complicated', and 'the four example' in the numerical section; these should be corrected.","section":"Throughout"},{"comment":"Lemma 3 is cited to Lemma 3.3 of [29] rather than proved; since the linesearch condition here is essentially that of [29], this is acceptable, but the manuscript should state explicitly that Lemma 3 is an external result and verify that the cited lemma applies verbatim to the present linesearch condition.","section":"Lemma 3"}],"recommendation":"major_revision","confidential_remarks":"The paper's main advertised contribution is the O(1/N^2) accelerated rate for ANPDA. The proof of Theorem 4 is invalid as written: the final step confuses a bound on ||y_N - ŷ||^2 with a bound on ||y_N - ŷ||. If the authors cannot supply a valid alternative proof, they should downgrade the claim to O(1/N) and revise the abstract and introduction accordingly. The monotonicity specification for {a_k} and {b_k} is also a genuine gap in all three convergence proofs. I have recommended major revision rather than rejection because the O(1/N) results and the numerical study may still be salvageable after these corrections."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know about this one. The headline acceleration, O(1/N^2), does not follow from the proof: inequality (42) gives ||y_N - ŷ|| ≤ C σ_{N-1}, and the parameter update (37) makes σ_{N-1} = Θ(1/N), so the actual bound is O(1/N). The proof's last line treats a σ^2 factor as if it produced 1/N^4 when it only produces 1/N^2. And the global-convergence proof of NPDA requires the coefficient in (31), which is a_{k+3} - a_{k+2}, to be nonnegative; that means the sequence must be non-decreasing, not 'non-monotonic decreasing' as stated. As written, that step is backwards.\n\nCredit where due: the proximal centers x^md and y^md are a genuinely new combination of GRPDA's convex combination idea with PDA's extrapolation, and the O(1/N) ergodic rates for NPDA and NPDAL look like they hold; I did not find a comparable slip in those parts. The linesearch termination is transparently delegated to Malitsky-Pock's Lemma 3.3, and the numerics, with code provided, are encouraging.\n\nThat said, the two errors above are load-bearing for the advertised contributions. The monotonicity mistake is fixable by changing the assumption to non-decreasing (or constant, which is what the numerical experiments use). The rate mistake is not fixable within the current Lyapunov argument, because the update rule itself forces σ_N ~ 1/N; either a different argument is needed or the O(1/N^2) claim should be retracted. There are also a fair number of typos, and the paper says 'either' strongly convex but only proves the f* case.\n\nWho this is for: people building practical primal-dual solvers with linesearch may find NPDAL useful. The paper deserves a serious referee—the new construction and reproducible code are real—but the referee should insist the acceleration claim be fixed or removed before publication. I would not cite the accelerated result as it stands.","headline":"New proximal centers are a real contribution, but the advertised O(1/N^2) acceleration doesn't follow from the paper's own inequalities, and the monotonicity assumption in the main convergence proof has the wrong sign.","tokens_in":22253,"tokens_out":7781,"would_cite":false,"duration_ms":62795,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["49M29","65K10","65Y20","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"NPDA replaces standard proximal centers with convex combinations of past iterates, keeping global convergence at O(1/N) and reaching O(1/N^2) under strong convexity.","keywords":["primal-dual algorithm","saddle-point problem","proximal term","convex-concave optimization","global convergence","ergodic convergence rate","linesearch","accelerated algorithm"],"falsifier":"Run NPDA on the one-dimensional problem $\\min_x\\max_y\\,xy$ (so $K=1$, $L=1$) with $\\tau=\\sigma=0.5$ and a coefficient sequence that increases at a single step, such as $a_1=0.005$, $a_2=0.01$, then constant; inequality (31) then has a negative coefficient at that step. If the iterates still converge with the claimed $O(1/N)$ gap, the proof's monotonicity requirement is too strong; if they diverge or the bound fails, the theorem needs the non-increasing condition to be stated explicitly.","tokens_in":21268,"feed_emoji":"🔄","tokens_out":10480,"duration_ms":82277,"temperature":0.7,"pith_summary":"This paper proposes a new primal-dual algorithm (NPDA) for convex-concave saddle-point problems of the form $\\min_x\\max_y\\,g(x)+\\langle Kx,y\\rangle-f^*(y)$. The central claim is that replacing the usual proximal centers with convex combinations of all previous primal and dual iterates preserves global convergence while keeping the extrapolation step that makes classical primal-dual methods fast; the ergodic primal-dual gap is $O(1/N)$. When either $f^*$ or $g$ is strongly convex, an accelerated version (ANPDA) is claimed to reach $\\|y_N-\\hat y\\|=O(1/N^2)$. A linesearch variant (NPDAL) keeps the $O(1/N)$ rate without requiring the spectral norm of $K$. Numerical experiments on matrix games and LASSO problems show the new proximal centers improving on several existing primal-dual methods.","feed_headline":"Two new proximal terms push primal-dual solvers to O(1/N^2)","feed_subtitle":"A convex-concave saddle solver keeps the extrapolation step, converges globally, and adds a linesearch variant.","key_machinery":"The central objects are two pairs of auxiliary points $x^{\\mathrm{ag}}_k=(1-a_k)x^{\\mathrm{ag}}_{k-1}+a_kx_{k-1}$ and $y^{\\mathrm{ag}}_{k+1}=(1-b_{k+1})y^{\\mathrm{ag}}_k+b_{k+1}y_k$, together with the middle points $x^{\\mathrm{md}}_k=(1-a_k)x_{k-1}+a_kx^{\\mathrm{ag}}_k$ and $y^{\\mathrm{md}}_{k+1}=(1-b_{k+1})y_k+b_{k+1}y^{\\mathrm{ag}}_{k+1}$. These middle points replace $x_k$ and $y_k$ in the proximal terms of the primal and dual subproblems, and the identities (21)-(23) make the Lyapunov inequality telescope so the ergodic gap is bounded by a constant divided by the number of iterations.","core_discovery":"On the paper's own terms, the discovery is that the proximal terms in a primal-dual algorithm need not be centered at the current iterate. Using middle points $x^{\\mathrm{md}}_k=(1-a_k)x_{k-1}+a_kx^{\\mathrm{ag}}_k$ and $y^{\\mathrm{md}}_{k+1}=(1-b_{k+1})y_k+b_{k+1}y^{\\mathrm{ag}}_{k+1}$, where $x^{\\mathrm{ag}}$ and $y^{\\mathrm{ag}}$ are themselves convex combinations of all earlier iterates, yields a globally convergent algorithm whose Lyapunov inequality still telescopes. The auxiliary points carry the whole trajectory into the proximal subproblems without discarding the extrapolation step that makes PDA effective. Under strong convexity, adapting the stepsizes through $\\theta_k=(1+\\gamma\\sigma_{k-1})^{-1/2}$ gives the accelerated $O(1/N^2)$ bound on the dual variable. The linesearch variant replaces the spectral-norm condition with a checkable inequality involving $\\|K^Ty_{k+1}-K^Ty_k\\|$, making the method usable when $\\|K\\|$ is unknown.","pith_inferences":["The same auxiliary/middle-point telescoping identities could be transplanted to other proximal splitting algorithms, such as alternating-direction methods, because the argument only uses convexity and the algebraic identities (7)-(8); the paper does not make this extension.","The $O(1/N^2)$ result is stated for the dual variable when $f^*$ is strongly convex; duality suggests an analogous primal rate when $g$ is strongly convex, which the paper leaves implicit.","Larger $a_k,b_k$ increase the memory of the auxiliary points but tighten the stepsize condition $\\sqrt{\\tau\\sigma}\\|K\\|<1-a_k,\\,1-b_k$, so tuning these sequences adaptively is a possible practical refinement not explored in the paper.","A natural testable extension is to let the linesearch in NPDAL also drive $a_k,b_k$, producing a fully parameter-free method; the paper fixes them as small constants in its experiments."],"forward_implications":["NPDA converges globally for every convex-concave saddle problem (1), with ergodic gap $G_{\\hat x,\\hat y}(X_N,Y_N)\\le C/N$.","Under strong convexity of $f^*$ (or of $g$, by symmetry), ANPDA attains $\\|y_N-\\hat y\\|=O(1/N^2)$, a quadratic improvement over the $O(1/N)$ ergodic rate.","NPDAL retains global convergence and the $O(1/N)$ ergodic rate while replacing the spectral-norm condition on $K$ with a linesearch condition on $\\|K^Ty_{k+1}-K^Ty_k\\|$.","The method reduces to the classical PDA when $a_k=b_k=0$, so the new proximal centers form a strict generalization of an established solver.","The reported matrix-game and LASSO experiments show the new proximal centers and their linesearch variant reducing the primal-dual gap or objective error compared with PDA, GRPDA, PDAL and GRPDAL on most test problems."],"supporting_citations":[{"why":"It supplies the baseline primal-dual algorithm and the O(1/N) convergence template that NPDA extends.","marker":"[1]"},{"why":"It introduces the golden-ratio primal-dual algorithm whose convex combination of past iterates is the direct predecessor of the auxiliary points here.","marker":"[26]"},{"why":"It provides the linesearch strategy for primal-dual algorithms and the termination lemma that NPDAL adapts.","marker":"[29]"},{"why":"It motivates the auxiliary/middle-point construction used in the proximal terms of NPDA.","marker":"[32]"},{"why":"It supplies the golden-ratio primal-dual algorithm with linesearch used both as a comparison method and as a linesearch framework.","marker":"[27]"}],"fun_headline_variants":["Middle-point proximal terms yield O(1/N^2) for strongly convex primal-dual","Linesearch strategy for primal-dual when spectral norm is unknown","Saddle-point solver converges globally with middle-point proximal terms","From O(1/N) to O(1/N^2) via middle-point proximal terms"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the main theorem requires the coefficients in its Lyapunov inequality to be nonnegative, which forces the sequences $\\{a_k\\}$ and $\\{b_k\\}$ to be non-increasing; the paper states only that they are 'non-monotonic decreasing', an ambiguous condition that does not guarantee this.","fun_headline_variants_meta":{"raw":{"variants":["Middle-point proximal terms yield O(1/N^2) for strongly convex primal-dual","Linesearch strategy for primal-dual when spectral norm is unknown","Saddle-point solver converges globally with middle-point proximal terms","From O(1/N) to O(1/N^2) via middle-point proximal terms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001994,"raw_usage":{"total_tokens":7824,"prompt_tokens":1032,"completion_tokens":6792,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":648,"completion_tokens_details":{"reasoning_tokens":6709}},"tokens_in":648,"tokens_out":6792,"duration_ms":46384,"temperature":1.0,"reasoning_tokens":6709,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T10:53:45.369275+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run NPDA on the one-dimensional problem $\\min_x\\max_y\\,xy$ (so $K=1$, $L=1$) with $\\tau=\\sigma=0.5$ and a coefficient sequence that increases at a single step, such as $a_1=0.005$, $a_2=0.01$, then constant; inequality (31) then has a negative coefficient at that step. If the iterates still converge with the claimed $O(1/N)$ gap, the proof's monotonicity requirement is too strong; if they diverge or the bound fails, the theorem needs the non-increasing condition to be stated explicitly.","supporting_citations":[{"cited_title":"Chambolle and T","cited_arxiv_id":null,"evidence_quote":"It supplies the baseline primal-dual algorithm and the O(1/N) convergence template that NPDA extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It introduces the golden-ratio primal-dual algorithm whose convex combination of past iterates is the direct predecessor of the auxiliary points here."},{"cited_title":"Malitsky and T","cited_arxiv_id":null,"evidence_quote":"It provides the linesearch strategy for primal-dual algorithms and the termination lemma that NPDAL adapts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It motivates the auxiliary/middle-point construction used in the proximal terms of NPDA."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the golden-ratio primal-dual algorithm with linesearch used both as a comparison method and as a linesearch framework."}],"review_version":1}