Pith. sign in

REVIEW 2 major objections 5 minor 32 references

New Primal-Dual Algorithm for Convex Problems

T0 review · 2 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

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

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

arxiv 2504.16876 v1 pith:CTFGZ5ZL submitted 2025-04-23 math.OC

Shuning Liu , Zexian Liu This is my paper · ORCID
classification math.OC MSC 49M2965K1065Y2090C25
keywords primal-dualalgorithmsaddle-pointproblemproximaltermconvex-concaveoptimizationglobalconvergenceergodicratelinesearchaccelerated
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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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.

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 (2)
  1. [§3.2, Theorem 4 and Eq. (42)] 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.
  2. [§3.1, Theorem 1 and Eq. (31)] 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.
minor comments (5)
  1. [Algorithm 2, initialization] 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.
  2. [Theorem 4 statement] 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.
  3. [Remark 2] The sentence 'NPAD reduces to the classical primal-dual algorithm' contains a typo: it should read 'NPDA'.
  4. [Throughout] 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.
  5. [Lemma 3] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence proofs are self-contained Lyapunov arguments; the only imported lemma is an external linesearch result, and the apparent O(1/N^2) gap in Theorem 4 is a mathematical correctness issue rather than a reduction of the conclusion to the assumptions.

full rationale

The paper's derivation chain does not use its target conclusions as inputs. Theorems 1 and 2 build a Lyapunov inequality from proximal optimality conditions (18)-(19) and the identities (21)-(23); summing (27) to obtain (31) and then invoking nonnegativity of the coefficients is a direct algebraic argument. No parameter is fitted to data that a theorem then predicts; the sequences {a_k}, {b_k} and the stepsizes are chosen a priori in Algorithms 1-3. In Section 3.2, the accelerated rate is claimed from the separate inequality (42); even if the final inference to the claimed bound is not valid, since (42) gives squared error of order sigma_{N-1}^2 and hence norm O(1/N), that is a proof error, not circularity, because the inequality is not defined in terms of the rate it is meant to establish. Lemma 3 is the only imported fact and is explicitly delegated to Lemma 3.3 of Malitsky and Pock [29]; that is a transparent external dependency, not a self-citation chain, and it does not smuggle in the paper's own conclusions. The ambiguity of 'non-monotonic decreasing' affects coefficient nonnegativity in (31) and is again a correctness/assumption concern. Numerical experiments are empirical comparisons and are not used as evidence in the proofs. No fitted-input-called-prediction, self-definitional, or renaming pattern is present.

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

The algorithm introduces no new physical or mathematical entities. The free parameters are standard stepsizes and weighting sequences; the proof relies on standard convex analysis plus the monotonicity condition on {a_k} and {b_k}, which is not clearly stated.

free parameters (3)
  • a_k, b_k = 0.01 or 0.005 in experiments
    User-chosen sequences controlling the convex combination weights of the auxiliary points. The theory only requires bounds, not specific values; the experiments set them constant.
  • tau and sigma (NPDA) = sigma = 1/||K||, tau = 2/(3 sigma) in matrix game; sigma = 3/(10 ||K||), tau = 3/||K|| in LASSO
    Stepsizes must satisfy sqrt(tau sigma) L < 1 - a_k (and 1 - b_k); specific values are hand-picked for experiments.
  • NPDAL parameters beta, delta, mu, tau_0 = beta = 1, delta = 0.96, mu = 0.7, tau_0 = sqrt(min{m,n})/||K||_F
    Linesearch parameters chosen from [29] and tuned for experiments.
assumptions (4)
  • domain assumption g and f are proper closed convex, K is a bounded linear operator, a saddle point exists
    Standard assumptions for the saddle problem (1), stated in the introduction.
  • ad hoc to paper {a_k} and {b_k} are non-increasing sequences so the Lyapunov coefficients are nonnegative
    The proof of Theorem 1 requires (1 - a_{k+1} - sqrt(tau sigma) L) >= 0; the text says 'non-monotonic decreasing', a nonstandard phrase that does not explicitly guarantee monotonicity.
  • domain assumption Lemma 3 (linesearch always terminates) holds as in [29] Lemma 3.3
    The proof is cited, not reproduced; if false, NPDAL may not terminate.
  • standard math Fenchel conjugate and proximal mapping properties (Lemmas 1 and 2)
    Standard convex analysis facts used throughout the proofs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of New Primal-Dual Algorithm for Convex Problems." pith.science (2026). https://pith.science/paper/CTFGZ5ZL

@misc{pith2026250416876,
  author       = {Pith},
  title        = {Pith review of: New Primal-Dual Algorithm for Convex Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CTFGZ5ZL}},
  note         = {Machine review of arXiv:2504.16876}
}
read the original abstract

Primal-dual algorithm (PDA) is a classic and popular scheme for convex-concave saddle point problems. It is universally acknowledged that the proximal terms in the subproblems about the primal and dual variables are crucial to the convergence theory and numerical performance of primal-dual algorithms. By taking advantage of the information from the current and previous iterative points, we exploit two new proximal terms for the subproblems about the primal and dual variables. Based on two new proximal terms, we present a new primal-dual algorithm for convex-concave saddle point problems with bilinear coupling terms and establish its global convergence and O(1/N ) ergodic convergence rate. When either the primal function or the dual function is strongly convex, we accelerate the above proposed algorithm and show that the corresponding algorithm can achieve O(1/N^2) convergence rate. Since the conditions for the stepsizes of the proposed algorithm are related directly to the spectral norm of the linear transform, which is difficult to obtain in some applications, we also introduce a linesearch strategy for the above proposed primal-dual algorithm and establish its global convergence and O(1/N ) ergodic convergence rate . Some numerical experiments are conducted on matrix game and LASSO problems by comparing with other state-of-the-art algorithms, which demonstrate the effectiveness of the proposed three primal-dual algorithms.

Figures

Figures reproduced from arXiv: 2504.16876 by the authors.

Figure 1
Figure 1. Matrix game The numerical results for the primal-dual gap G(xk, yk) at each iteration versus CPU time are shown in [PITH_FULL_IMAGE:figures/full_fig_p020_1.png] view at source ↗
Figure 2
Figure 2. LASSO 5. Conclusion. Due to the significant importance of proximal terms for PDA, we utilize the previous iterative points to exploit two new points x md k and y md k for proximal terms and present a new proximal-dual algorithm (NPDA) for convex-concave minimax problem with bilinear coupling term. The global convergence and convergence rate are also established. When either f or g is a strongly convex function, we i… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 29 canonical work pages

  1. [29]

    Malitsky and T

    Y. Malitsky and T. Pock, A first-order primal-dual algorithm with linesearch, SIAM J. Optim., 28 (2018), pp. 411–432

    work page 2018

  2. [1]

    Chambolle and T

    A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with appli- cations to imaging, J.Math.Imaging Vision., 40 (2011), pp. 120–145

    work page 2011

  3. [2]

    Chambolle and T

    A. Chambolle and T. Pock, On the ergodic convergence rates of a first-order primal-dual algo- rithm, Math. Program., 159 (2016), pp. 253–287

    work page 2016

  4. [3]

    B. S. He, H. Yang, and S. L. Wang, Alternating direction method with self-adaptive penalty pa- rameters for monotone variational inequalities, J. Optim. Theory Appl., 106 (2000), pp. 337–356

    work page 2000

  5. [4]

    B. S. He and X. M. Yuan, Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective, SIAM J. Imaging Sci., 5 (2012), pp. 119–149

    work page 2012

  6. [5]

    B. S. He, Y. F. You, and X. M. Yuan, On the convergence of primal-dual hybrid gradient algorithm, SIAM J. Imaging Sci., 7 (2014), pp. 2526–2537

    work page 2014

  7. [6]

    D. P. Bertsekas and E. M. Gafni, Projection methods for variational inequalities with application to the traffic assignment problem, Math. Program. Stud., 17 (1982), pp. 139–159

    work page 1982

  8. [7]

    Gabay and B

    D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Comput Math Appl., 2 (1976), pp. 17–40

    work page 1976

Show all 32 references
  1. [8]

    Esser, X

    E. Esser, X. Q. Zhang, and T. F. Chan, A general framework for a class of first order primal- dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sci., 3 (2010), pp. 1015–1046

    2010

  2. [9]

    Jonathan and P

    E. Jonathan and P. Dimitri, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), pp. 293–318

    1992

  3. [10]

    G. Lan, Y. Li, A Novel Catalyst Scheme for Stochastic Minimax Optimization, arXiv preprint arXiv(2023), 2311.02814

    2023 arXiv

  4. [12]

    J. Y. Yang and Y. Zhang, Alternating direction algorithms for l1-problems in compressive sensing, SIAM J. Sci. Comput., 33 (2011), pp. 250–278

    2011

  5. [13]

    Duchi, S

    J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra, Efficient projections onto the l1-ball for learning in high dimensions, ICML., (2008), pp. 272–279

    2008

  6. [14]

    K. J. Arrow, L. Hurwicz, and H. Uzawa, Iterative methods for concave programming, Studies in Linear and Nonlinear Programming, SUP, Stanford, CA., (1958), pp. 154–165

    1958

  7. [15]

    Condat, A primal–dual splitting method for convex optimization involving Lipschitzian, prox- imable and linear composite terms, J

    L. Condat, A primal–dual splitting method for convex optimization involving Lipschitzian, prox- imable and linear composite terms, J. Optim. Theory Appl., 158 (2013), pp. 460–479

    2013

  8. [16]

    M. L. Vladarean, Y. Malitsky, and V. Cevher, A first-order primal-dual method with adaptivity to local smoothness, NeurIPS., (2021), pp. 6171–6182

    2021

  9. [17]

    M. G. Zhu and T. Chan, An efficient primal-dual hybrid gradient algorithm for total variation image restoration, Comput. Sci. Eng., (2008)

    2008

  10. [18]

    P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16 (1979), pp. 964–979

    1979

  11. [19]

    Jiang, A

    R. Jiang, A. Mokhtari, Generalized optimistic methods for convex-concave saddle point problems, arXiv preprint arXiv(2022), 2202.09674. 23

    2022 arXiv

  12. [20]

    Glowinski and A

    R. Glowinski and A. Marrocco, Sur l’approximation, par ´ el´ ements finis d’ordre un, et la r´ esolution, par p´ enalisation-dualit´ e, d’une classe de probl` emes de Dirichlet non lin´ eaires, Rev. R.A.I.R.O., 9 (1975), pp. 41–76

    1975

  13. [21]

    Hayden and O

    S. Hayden and O. Stanley, A low patch-rank interpretation of texture, SIAM J. Imaging Sci., 6 (2013), pp. 226–262

    2013

  14. [22]

    Goldstein, M

    T. Goldstein, M. Li, and X. Yuan, Adaptive primal-dual splitting methods for statistical learning and image processing, NeurIPS., 2 (2015), pp. 2089–2097

    2015

  15. [23]

    Goldstein, M

    T. Goldstein, M. Li, X. Yuan, E. Esser, and R. Baraniuk, Adaptive primal-dual hybrid gradient methods for saddle-point problems, arXiv:(2013) 1305.0546

    2013 arXiv

  16. [24]

    Pock and A

    T. Pock and A. Chambolle, Diagonal preconditioning for first order primal-dual algorithms in convex optimization, IEEE Int. Conf. Comput. Vis., (2011), pp. 1762–1769

    2011

  17. [25]

    Bouwmans, N

    T. Bouwmans, N. S. Aybat, and E. H. Zahzah, Handbook of “Robust low-rank and sparse matrix decomposition, Appl. Image Video Process., (2016)

    2016

  18. [26]

    X. K. Chang and J. F. Yang, A golden ratio primal-dual algorithm for structured convex opti- mization, J. Sci. Comput., 87 (2021), pp. 47

    2021

  19. [27]

    X. K. Chang, J. F. Yang, and H. C. Zhang, Golden ratio primal-dual algorithm with linesearch, SIAM J. Optim., 32(2022), pp. 1584–1613

    2022

  20. [28]

    Ouyang, Y

    Y. Ouyang, Y. Xu, Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems, Math Program., 185( (2021), pp. 1-35

    2021

  21. [30]

    Malitsky, Golden ratio algorithms for variational inequalities, Math

    Y. Malitsky, Golden ratio algorithms for variational inequalities, Math. Program., 184 (2020), pp. 383–410

    2020

  22. [31]

    Y. L. Liu, Y. B. Xu, and W. T. Yin, Acceleration of primal-dual methods by preconditioning and simple subproblem procedures, J. Sci. Comput., 86 (2018)

    2018

  23. [32]

    Y. Y. Ouyang, Y. M. Chen, G. H. Lan, and E. Pasiliao, An accelerated linearized alternating direction method of multipliers, SIAM J. Imaging Sci., 8(1) (2015), pp. 644–681

    2015

  24. [33]

    On lower iteration complexity bounds for the convex concave saddle point problems, Math Program., 194(2022), pp

    Zhang J, Hong M, Zhang S. On lower iteration complexity bounds for the convex concave saddle point problems, Math Program., 194(2022), pp. 901-935. 24

    2022

Pith tools

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