Pith. sign in

REVIEW 5 minor 32 references

Preconditioned primal-dual dynamics in convex optimization: non-ergodic convergence rates

T0 review · 0 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This paper claims that a time-dependent preconditioner, built from the linear operator and independent of the functions being optimized, restores non-ergodic convergence to the continuous primal-dual saddle flow.

desk verdict Mostly solid Lyapunov analysis of preconditioned primal-dual flows with one genuinely new regime; the main theorem holds, but the first worked example in Remark 4.8 violates the paper's own condition. read the letter →

arxiv 2506.00501 v1 pith:SSDX7SE7 submitted 2025-05-31 math.OC

Vassilis Apidopoulos , Cesare Molinari , Juan Peypouquet , Silvia Villa This is my paper
classification math.OC MSC 34D0565K0565K1090C25
keywords primal-dualdynamicspreconditioningnon-ergodicconvergenceratesdualitygapconvexoptimizationsaddle-pointproblemArrow-HurwiczflowChambolle-Pock
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 studies a continuous saddle-point flow for minimizing $f(x)+g(Ax)$, and tries to show that a time-dependent preconditioner—chosen independently of $f$ and $g$—restores non-ergodic convergence that the classical Arrow-Hurwicz flow lacks. For linearly constrained problems it establishes explicit rates on the duality gap, feasibility error, and objective error, all decaying like $1/(\nu_0+\int_0^t \Xi(s)\,ds)$. For the general problem, asymptotically antisymmetric preconditioners force the non-ergodic duality gap to decay at a rate set by $\int_0^t 1/Z(s)\,ds$, so that every weak subsequential limit of the trajectory is a primal-dual solution. The interest is that preconditioning is exactly the mechanism that makes the discrete Chambolle-Pock algorithm converge, and this paper transfers that mechanism to continuous time.

What carries the argument

The engine is the energy identity of Lemma 2.3, which differentiates the anchoring function $V_{u,v}(t)=\frac{\sigma(t)}2\|x(t)-u\|^2+\frac{\tau(t)}2\|y(t)-v\|^2$ together with the duality gap $\Delta_{u,v}$ and the Bregman divergence $d_{u,v}$. Choosing $\sigma=\alpha\Xi$, $\tau=\delta\Xi$, $\eta=\Xi$, and $Z=(\beta-\gamma)/2$, the coefficient definitions in Assumption 4.5 make the $\|x-u\|^2$ and $\|y-v\|^2$ terms vanish, leaving $\dot E^G_{u,v}+R_{u,v}\le0$ with $R_{u,v}\ge0$; Grönwall's inequality then gives the exponential bound. The positivity condition $\|A\||\beta+\gamma|\le\sqrt{\alpha\delta}$ keeps $\alpha,\delta>0$ and makes the Young-inequality remainders non-positive, which is what turns the differential identity into a Lyapunov decay.

What would settle it

Take $X=Y=\mathbb{R}$, $A=1$, $f(x)=x^2/2$, $g(y)=y^2/2$, set $\beta(t)=1+t$, $\gamma(t)=-(1+t)$, $\alpha(t)=\delta(t)=1$, and integrate system (6) from a nonzero initial point. This satisfies Assumption 4.1, so Theorem 4.3 predicts $\Delta(t)\le D\exp(-\int_0^t 1/(1+s)\,ds)=D/(1+t)$; observing the gap above this bound at any finite time, or a decay slower than $1/t$, would refute the claimed non-ergodic rate.

Watch

Extended reading notes

Core claim

The central claim is Theorem 4.7: under Assumption 4.5, with $\beta>\gamma$, $Z=(\beta-\gamma)/2$, and $\alpha,\delta$ built from $\beta,\gamma$ so that $\|A\||\beta+\gamma|\le\sqrt{\alpha\delta}$, every trajectory of system (6) satisfies $\Delta_{u,v}(t)\le D_{u,v}(0)\exp(-\int_0^t ds/Z(s))$ for every $(u,v)$ and every primal-dual solution. Hence whenever $\int_0^\infty 1/Z=\infty$, the non-ergodic duality gap tends to zero and every weak subsequential limit point is a primal-dual solution; strong convexity of $f$ or smoothness of $g$ upgrades this to strong convergence of $x(t)$ or $y(t)$. The parallel Theorem 3.3 treats the linearly constrained case, where $\alpha$ and $\delta$ decay like $\exp(-\int\zeta)$ and $\nu$ solves $\dot\nu+\zeta\nu=1$, yielding gap, feasibility, and optimality rates of order $1/(\nu_0+\int_0^t \Xi)$.

Load-bearing premise

The load-bearing premise is that the user can pick $\beta$ and $\gamma$ so that, at every instant, the coupling condition $\|A\||\beta+\gamma|\le\sqrt{\alpha\delta}$ holds with $\alpha$ and $\delta$ built from $\beta$ and $\gamma$; if that tuned condition fails, the Lyapunov function need not decay and no non-ergodic rate is established.

Editorial extensions

If this is right

  • For linearly constrained problems, the primal-dual gap, the feasibility error $\|Ax(t)-b\|$, and the objective error $|f(x(t))-f(\bar x)|$ all decay at least like $1/(\nu_0+\int_0^t \Xi(s)\,ds)$, which is already $O(1/t)$ for $\zeta=0$ and becomes exponential when $\Xi$ grows (for example, $\zeta\equiv1$, $\nu_0=0$ recovers the $e^{-t}$ rates of the earlier triangular flow).
  • In the general problem, antisymmetric preconditioning gives a non-ergodic duality-gap bound of $D\exp(-\int_0^t 1/Z)$, so a divergent $\int 1/Z$ forces the gap to zero without any ergodic averaging.
  • If $f$ is $\mu$-strongly convex, the primal variable converges strongly to the unique minimizer at the same exponential rate; if $g$ is $L$-smooth, the dual variable does the same.
  • Weak subsequential limit points of the trajectory are primal-dual solutions in both the linearly constrained and the asymptotically antisymmetric settings.
  • In the linearly constrained case the rates are largely insensitive to the non-diagonal coefficient $\beta$, which can be any nonnegative function; symmetric preconditioning, by contrast, only yields ergodic convergence in the general case.

Reading between the lines

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

  • The construction suggests a discrete analogue: a Chambolle-Pock-type iteration with time-varying primal and dual step sizes obeying the same ratio and decay identities should inherit non-ergodic $1/t$ or exponential gap bounds; the paper does not analyze discretization, so this is an extension.
  • The proof only needs the cross terms to be controlled by the positivity condition, so one could try preconditioners where $\beta+\gamma$ oscillates rather than simply decays; condition (41) would need reformulation, and a numerical test could show whether oscillation alone suffices.
  • The paper leaves trajectory convergence open; if one could show that $\|(x(t),y(t))-(\bar x,\bar y)\|$ has a limit, then weak cluster-point optimality would upgrade to weak convergence of the whole trajectory.
  • The feasibility constraint ties achievable decay speed to the norm of $A$; in large-scale imaging problems where $A$ has large norm, the tuning condition $\|A\||\beta+\gamma|\le\sqrt{\alpha\delta}$ may limit the practical rate, which would matter for deployment.
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

0 major / 5 minor

Summary. This paper introduces a continuous-time primal-dual flow with a time-varying preconditioner for minimizing f(x)+g(Ax). The core of the analysis is a general energy identity (Lemma 2.3), from which the authors derive non-ergodic convergence rates for the primal-dual gap: a rate of order 1/(ν0+∫_0^t exp(∫_0^s ζ)) in the linearly constrained case (Theorem 3.3), and a rate exp(-∫_0^t 1/Z(s) ds) for asymptotically antisymmetric preconditioners (Theorem 4.7). Under the corresponding integrability conditions, every weak subsequential limit point of the trajectory is shown to be a primal-dual solution. The paper also includes numerical experiments comparing antisymmetric, symmetric, and triangular preconditioners.

Significance. The contribution is significant for the continuous-time analysis of primal-dual splitting methods. The Lyapunov framework is clean and general, and the obtained non-ergodic rates are explicit in terms of user-chosen coefficient functions. The exact antisymmetric case (β+γ≡0) provides a genuinely non-vacuous instance of the main assumption, and the numerical experiments support the theoretical findings. The paper is a valuable addition to the literature on preconditioned Arrow-Hurwicz dynamics.

minor comments (5)
  1. [Remark 4.8] The first claimed admissible parameter pair, β−γ∼t and β+γ∼1/(t+1), actually violates condition (41): with Z∼t/2 and Ξ(t)∼2Z0 t, one obtains Ξ(t)W(t)∼C/t, so the integral in (41) diverges logarithmically. The second pair, β−γ≡2Z0 and |β+γ|∼e^{-κt} with κZ0>1, is admissible, so Assumption 4.5 remains non-vacuous; the first pair should be replaced or adjusted.
  2. [Theorem 4.7 proof] The sentence 'Since 1/Z < L1' is unclear; the subsequent conclusion that limsup_{t→∞} Δ_{u,v}(t)≤0 requires ∫_0^∞ 1/Z(s)ds = ∞, so the text should instead say 'Since 1/Z is not integrable' or 'Since ∫_0^∞ 1/Z = ∞'.
  3. [Section 3, display (23)] The displayed condition appears as 'ν˙η + (ν˙+ζν−1)η≤0', but the coefficient of Δ in the preceding computation is ν η˙ + (ν˙+ζν−1)η; the factors on η˙ and ν˙ are swapped and should be corrected.
  4. [System (6) and existence] The paper does not discuss well-posedness of the differential inclusion (6). Since the main theorems are stated conditionally on the existence of a solution, the rates themselves are not affected, but a brief remark or reference on existence for time-dependent preconditioned monotone inclusions would strengthen the presentation.
  5. [Throughout] There are several typos and notation slips: in the proof of Theorem 4.3 the superscript G appears in E^G_{u,v} although the energy was defined as E^A_{u,v}; in Section 6 'trjectories' should be 'trajectories'; the figure captions use 'Langrangian gap' instead of 'Lagrangian gap'; Figure 1 has 'with with'; and Example 5.3 has 'a a Gaussian'. These should be cleaned up.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity found: the non-ergodic rates are derived from Lyapunov estimates whose parameter conditions are explicit user choices, with no fitted-input-as-prediction or load-bearing self-citation.

full rationale

The paper's central claims (Theorem 3.3 and Theorem 4.7) are upper bounds on the non-ergodic duality gap obtained by differentiating an explicitly defined Lyapunov functional V_u,v and using Grönwall-type arguments. The rate functions beta, gamma, zeta, alpha, delta, and nu are user-chosen parameter functions satisfying stated differential identities, such as alpha(t) = alpha_0 / Xi(t), delta(t) = delta_0 / Xi(t), and nu_dot + zeta nu = 1 in Assumption 3.2, or the integrals in Assumption 4.5. These identities are hypotheses, not conclusions derived from the target rate; the proof of Theorem 4.7 verifies the cancellation sigma_dot + omega sigma/(4Z) = 0 directly from the chosen definitions and then invokes Grönwall's inequality to conclude the claimed bound. The positivity condition (41) is an explicit admissibility condition ensuring alpha and delta remain positive, not a hidden reuse of the theorem's conclusion. The paper does not fit parameters to data and then predict the same quantity; the numerical experiments are illustrative rather than evidence treated as derived from the theory. Self-citations, such as [12, Theorem 5.3] for weak convergence of averages of monotone semigroups and [31, Proposition 11] for the feasibility-optimality implication, concern standard external results and are not used to assume the non-ergodic rate proved here. The appendix's symmetric case is presented as a time-reparameterization of the classical Arrow-Hurwicz flow and yields ergodic rates, which is consistent with, rather than circularly identical to, the non-ergodic results. The only soft spot is the first asymptotic example in Remark 4.8 (beta - gamma ~ t with beta + gamma ~ 1/(t+1)) appearing to violate condition (41) because the integral of Xi W seems to diverge logarithmically; this is a possible exposition or admissibility-check issue in an illustrative example and does not affect the main derivation, which explicitly requires (41). No load-bearing argument reduces to its own inputs, so the circularity score is 0.

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

The derivation is self-contained: the only free inputs are user-chosen time functions, and no new physical or mathematical entities are postulated.

free parameters (3)
  • beta(t)
    User-chosen positive function in Assumption 4.1; the gap rate is exp(-integral 1/beta), so the function directly sets the convergence speed.
  • gamma(t) and Z(t) = (beta - gamma)/2
    User-chosen pair in Assumption 4.5; must satisfy beta > gamma and the integral condition (41), which couples them to alpha, delta and the operator norm.
  • zeta(t)
    User-chosen locally integrable damping in Assumption 3.2; controls the linearly-constrained rate through Xi = exp(integral zeta).
assumptions (5)
  • domain assumption f and g* are proper, lower semicontinuous, convex functions on Hilbert spaces X and Y, with A bounded linear.
    Standing assumption in (1) and throughout; standard in convex optimization.
  • domain assumption The primal-dual solution set S is nonempty.
    Invoked in Lemma 2.1 and Theorems 3.3, 4.3, 4.7 to define the gap and anchor the Lyapunov function to (xbar,ybar).
  • domain assumption Trajectories (x(t), y(t)) satisfying the differential inclusion (6) exist on [0, infinity) for the chosen coefficients.
    All results quantify over such trajectories; well-posedness is not proved in the paper, relying on standard maximal monotone operator theory.
  • standard math Classical calculus rules, Gronwall's inequality, and Young's inequalities are applied in the energy estimates.
    Used throughout Sections 2-4, especially in the proofs of Theorem 3.3 and Theorem 4.7.
  • ad hoc to paper The positivity condition ||A|| |beta + gamma| <= sqrt(alpha delta), equivalently (41), holds for all time.
    This nonstandard condition is tailored to the Lyapunov argument in Assumption 4.5; it ensures alpha and delta stay positive and makes the energy identity sigma_dot + omega sigma/(4Z) = 0 hold.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Preconditioned primal-dual dynamics in convex optimization: non-ergodic convergence rates." pith.science (2026). https://pith.science/paper/SSDX7SE7

@misc{pith2026250600501,
  author       = {Pith},
  title        = {Pith review of: Preconditioned primal-dual dynamics in convex optimization: non-ergodic convergence rates},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SSDX7SE7}},
  note         = {Machine review of arXiv:2506.00501}
}
abstract

We introduce and analyze a continuous primal-dual dynamical system in the context of the minimization problem $f(x)+g(Ax)$, where $f$ and $g$ are convex functions and $A$ is a linear operator. In this setting, the trajectories of the Arrow-Hurwicz continuous flow may not converge, accumulating at points that are not solutions. Our proposal is inspired by the primal-dual algorithm of Chambolle and Pock (2011), where convergence and splitting on the primal-dual variable are ensured by adequately preconditioning the proximal-point algorithm. We consider a family of preconditioners, which are allowed to depend on time and on the operator $A$, but not on the functions $f$ and $g$, and analyze asymptotic properties of the corresponding preconditioned flow. Fast convergence rates for the primal-dual gap and optimality of its (weak) limit points are obtained, in the general case, for asymptotically antisymmetric preconditioners, and, in the case of linearly constrained optimization problems, under milder hypotheses. Numerical examples support our theoretical findings, especially in favor of the antisymmetric preconditioners.

Figures

Figures reproduced from arXiv: 2506.00501 by the authors.

Figure 1
Figure 1. Comparison of the antisymmetric and symmetric system, with two di [PITH_FULL_IMAGE:figures/full_fig_p015_1.png] view at source ↗
Figure 2
Figure 2. The convergence of the duality gap along the trajectories of the antisymmetric system [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 2
Figure 2. Comparison of the antisymmetric with the symmetric and the triangular ODE system for 50-dimensional [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗
Figures from the paper (1 more)
Figure 3
Figure 3. Figure 3: Comparison of the trajectories generated by the antisymmetric and symmetric system for the LASSO problem, [PITH_FULL_IMAGE:figures/full_fig_p017_3.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

32 extracted references · 31 canonical work pages

  1. [29]

    Luo, A primal-dual flow for a ffine constrained convex optimization, ESAIM: Control, Optimisation and Calculus of Variations 28 (2022) 33

    H. Luo, A primal-dual flow for a ffine constrained convex optimization, ESAIM: Control, Optimisation and Calculus of Variations 28 (2022) 33

    work page 2022

  2. [30]

    B. Li, B. Shi, Understanding the PDHG algorithm via high-resolution differential equations, arXiv preprint arXiv:2403.11139 (2024)

    arXiv 2024

  3. [1]

    Chambolle, T

    A. Chambolle, T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, Journal of Mathematical Imaging and Vision 40 (2011) 120–145

    work page 2011

  4. [2]

    Attouch, G

    H. Attouch, G. Buttazzo, G. Michaille, Variational analysis in Sobolev and BV spaces. Applications to PDE’s and Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 2006

    work page 2006

  5. [3]

    F. Bach, R. Jenatton, J. Mairal, G. Obozinski, Convex optimization with sparsity-inducing norms, in: Optimization for machine learning, The MIT Press, Cambridge (MA), 2011, pp. 19–53

    work page 2011

  6. [4]

    Chambolle, T

    A. Chambolle, T. Pock, An introduction to continuous optimization for imaging, Acta Numerica 25 (2016) 161–319

    work page 2016

  7. [5]

    O’Donoghue, G

    B. O’Donoghue, G. Stathopoulos, S. Boyd, A splitting method for optimal control, IEEE Transactions on Control Systems technology 21 (2013) 2432–2442

    work page 2013

  8. [6]

    P. Yi, L. Pavel, An operator splitting approach for distributed generalized Nash equilibria computation, Automatica 102 (2019) 111–121

    work page 2019

Show all 32 references
  1. [7]

    B. C. Vu, A splitting algorithm for dual monotone inclusions involving cocoercive opera- tors, Advances in Computational Mathematics 38 (2013) 667–681

    2013

  2. [8]

    L. Condat, A primal–dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, Journal of Optimization Theory and Applications 158 (2013) 460–479

    2013

  3. [9]

    Arrow, L

    K. Arrow, L. Hurwicz, H. Uzawa, Studies in linear and non-linear programming: Stanford Mathematical Studies In The Social Sciences., Stanford University Press, 1958

    1958

  4. [10]

    K. J. Arrow, L. Hurwicz, A gradient method for approximating saddle points and con- strained maxima, Springer, Basel, 2014

    2014

  5. [11]

    Brezis, Opérateurs maximaux monotones et semi-groupes de contractions dans les es- paces de Hilbert, North-Holland Pub

    H. Brezis, Opérateurs maximaux monotones et semi-groupes de contractions dans les es- paces de Hilbert, North-Holland Pub. Co., Amsterdam, 1973

    1973

  6. [12]

    Peypouquet, S

    J. Peypouquet, S. Sorin, Evolution equations for maximal monotone operators: asymptotic analysis in continuous and discrete time, Journal of Convex Analysis 17 (2010) 1113–1163

    2010

  7. [13]

    Holding, I

    T. Holding, I. Lestas, On the convergence to saddle points of concave-convex functions, the gradient method and emergence of oscillations, in: 53rd IEEE Conference on Decision and Control, IEEE, 2014, pp. 1143–1148

    2014

  8. [14]

    Cherukuri, B

    A. Cherukuri, B. Gharesifard, J. Cortes, Saddle-point dynamics: conditions for asymptotic stability of saddle points, SIAM Journal on Control and Optimization 55 (2017) 486–511

    2017

  9. [15]

    Cherukuri, E

    A. Cherukuri, E. Mallada, S. Low, J. Cortés, The role of convexity in saddle-point dynam- ics: Lyapunov function and robustness, IEEE Transactions on Automatic Control 63 (2017) 2449–2464. 20

    2017

  10. [16]

    Holding, I

    T. Holding, I. Lestas, Stability and instability in saddle point dynamics - part i, IEEE Transactions on Automatic Control 66 (2020) 2933–2944

    2020

  11. [17]

    Holding, I

    T. Holding, I. Lestas, Stability and instability in saddle point dynamics - part ii: The subgradient method, IEEE Transactions on Automatic Control 66 (2020) 2945–2960

    2020

  12. [18]

    Cherukuri, E

    A. Cherukuri, E. Mallada, J. Cortés, Asymptotic convergence of constrained primal–dual dynamics, Systems & Control Letters 87 (2016) 10–15

    2016

  13. [19]

    Feijer, F

    D. Feijer, F. Paganini, Stability of primal–dual gradient dynamics and applications to net- work optimization, Automatica 46 (2010) 1974–1981

    2010

  14. [20]

    S. K. Niederländer, On the Arrow–Hurwicz di fferential system for linearly constrained convex minimization, Optimization 73 (2024) 2313–2345

    2024

  15. [21]

    Battahi, Z

    F. Battahi, Z. Chbani, S. Niederländer, H. Riahi, Asymptotic behavior of the Arrow-Hurwicz di fferential system with Tikhonov regularization, arXiv preprint arXiv:2411.17656 (2024)

    2024 arXiv

  16. [22]

    Ozaslan, P

    I. Ozaslan, P. Patrinos, M. Jovanovi ´c, Stability of primal-dual gradient flow dynamics for multi-block convex optimization problems, arXiv preprint arXiv:2408.15969 (2024)

    2024

  17. [23]

    B. Li, B. Shi, Understanding the ADMM algorithm via high-resolution di fferential equa- tions, arXiv preprint arXiv:2401.07096 (2024)

    2024 arXiv

  18. [24]

    Apidopoulos, C

    V . Apidopoulos, C. Molinari, L. Rosasco, S. Villa, Regularization properties of dual sub- gradient flow, in: 2023 European Control Conference (ECC), IEEE, 2023, pp. 1–8

    2023

  19. [25]

    Attouch, Z

    H. Attouch, Z. Chbani, J. Fadili, H. Riahi, Fast convergence of dynamical ADMM via time scaling of damped inertial dynamics, Journal of Optimization Theory and Applications 193 (2022) 704–736

    2022

  20. [26]

    X. Sun, L. He, X. Long, Inertial primal-dual dynamics with Hessian-driven damping and Tikhonov regularization for convex-concave bilinear saddle point problems, arXiv preprint arXiv:2412.05931 (2024)

    2024

  21. [27]

    K. Ding, J. Fliege, P. T. Vuong, Fast convergence of the primal-dual dynamical system and corresponding algorithms for a nonsmooth bilinearly coupled saddle point problem, Computational Optimization and Applications (2024) 1–42

    2024

  22. [28]

    F. F. Battahi, Z. Chbani, H. Riahi, On the simultaneous convergence of values and trajec- tories of continuous inertial dynamics with Tikhonov regularization to solve convex mini- mization with affine constraints., Applied Set-Valued Analysis & Optimization 7 (2025)

    2025

  23. [31]

    Molinari, M

    C. Molinari, M. Massias, L. Rosasco, S. Villa, Iterative regularization for low complexity regularizers, Numer. Math. 156 (2024) 641–689

    2024

  24. [32]

    P. L. Combettes, V . R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale modeling & simulation 4 (2005) 1168–1200. 21

    2005

Pith tools

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