arxiv: 2604.06423 · v1 · submitted 2026-04-07 · 🧮 math.OC

Recognition: no theorem link

The Chambolle-Pock method also converges weakly with 0 < θ le 1 and τσ\|L\|² < 4θ(2-θ)/(1 - 2θ + 9θ² - 4θ³)

Manu Upadhyaya

Authors on Pith no claims yet

Pith reviewed 2026-05-10 18:31 UTC · model grok-4.3

classification 🧮 math.OC

keywords Chambolle-Pock methodprimal-dual hybrid gradientweak convergenceLyapunov functionsaddle-point problemsergodic duality gapconvex optimization

0 comments

The pith

The Chambolle-Pock method converges weakly to KKT points for all relaxation parameters 0 < θ ≤ 1 when the step-size product satisfies τσ‖L‖² ≤ 4θ(2-θ)/(1-2θ+9θ²-4θ³).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves convergence results for the Chambolle-Pock primal-dual algorithm applied to convex-concave saddle-point problems in Hilbert spaces. Under the stated bound on the product of step sizes τ and σ with the squared norm of the linear operator L, the ergodic duality gap converges at rate O(1/k). When the bound holds strictly, the iterates converge weakly to a KKT point. This covers the full interval 0 < θ ≤ 1 for the relaxation parameter, including the range θ ≤ 1/2 that previously lacked weak-convergence guarantees. The argument rests on a single Lyapunov function shown to decrease uniformly across the entire interval of θ values.

Core claim

If τσ|L|² ≤ 4θ(2-θ)/(1 - 2θ + 9θ² - 4θ³), then the ergodic duality gap converges at rate O(1/k), and that, when the inequality is strict, the primal-dual iterates converge weakly to a KKT point. In particular, this extends the weak-convergence theory to the previously unexplored regime 0<θ≤1/2. The proof is based on a Lyapunov function that remains uniformly valid over the entire interval 0<θ≤1.

What carries the argument

A Lyapunov function that decreases uniformly for every relaxation parameter θ in (0,1] and yields exactly the stated bound on τσ‖L‖².

If this is right

The ergodic duality gap converges to zero at rate O(1/k) whenever the step-size condition holds.
The sequence of primal-dual iterates converges weakly to a KKT point when the inequality on τσ‖L‖² is strict.
The guarantees apply uniformly for all relaxation parameters in the interval 0 < θ ≤ 1.
The results hold in real Hilbert spaces for problems involving two proper convex functions and a bounded linear operator.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Larger values of the relaxation parameter θ near 1 may now be used with the same theoretical backing, which could improve practical speed in some applications.
The cubic polynomial appearing in the denominator of the bound suggests that the analysis may be close to sharp for this particular algorithm.
Analogous uniform Lyapunov constructions might extend parameter ranges for other primal-dual splitting methods.
If the bound can be improved, there would exist step sizes strictly larger than the present threshold that still guarantee convergence for some problems.

Load-bearing premise

A Lyapunov function can be constructed that decreases uniformly for every relaxation parameter in the closed interval 0 < θ ≤ 1 and yields exactly the stated bound on τσ‖L‖².

What would settle it

A concrete convex-concave saddle-point problem together with θ in (0,1] and step sizes τ,σ satisfying the given inequality for which the primal-dual iterates fail to converge weakly to any KKT point or the ergodic duality gap fails to decay at rate O(1/k).

read the original abstract

The Chambolle-Pock method, also known as the primal-dual hybrid gradient method, is a standard first-order algorithm for convex-concave saddle-point problems and composite convex optimization involving two proper, lower semicontinuous, convex functions and a bounded linear operator $L$. We study its convergence in real Hilbert spaces for step sizes $\tau,\sigma>0$ and relaxation parameter $0<\theta\le 1$. We prove that, if $\tau\sigma|L|^{2} \leq 4\theta(2-\theta)/(1 - 2\theta + 9\theta^{2} - 4\theta^{3})$, then the ergodic duality gap converges at rate $O(1/k)$, and that, when the inequality is strict, the primal-dual iterates converge weakly to a KKT point. In particular, this extends the weak-convergence theory to the previously unexplored regime $0<\theta\le 1/2$. The proof is based on a Lyapunov function that remains uniformly valid over the entire interval $0<\theta\le 1$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper fills the gap for weak convergence of Chambolle-Pock down to θ ≤ 1/2 with one uniform Lyapunov function that produces a specific cubic bound on the step-size product.

read the letter

This paper shows that the Chambolle-Pock method converges weakly for every relaxation parameter in the closed interval 0 < θ ≤ 1, provided the step sizes satisfy τσ‖L‖² ≤ 4θ(2-θ)/(1-2θ+9θ²-4θ³). The new part is the uniform Lyapunov construction that covers the previously open regime θ ≤ 1/2 without case splitting, while still recovering the known results for larger θ. The ergodic O(1/k) rate on the duality gap and the weak convergence of the iterates to a KKT point under the strict inequality follow directly from the decrease of this single function. That is a concrete, self-contained extension of existing primal-dual analysis. The authors keep the argument systematic and stay inside the standard Hilbert-space setting for the algorithm. The bound itself is the main soft spot. The cubic denominator is not obviously optimal, and it is not clear whether a simpler expression would suffice or whether the algebra introduces any hidden sign changes or singularities inside the interval. A referee will need to check the explicit form of the Lyapunov function and the exact algebraic steps that produce this particular threshold rather than a looser one. The paper is aimed at people who already work with first-order primal-dual methods and need precise parameter ranges for convergence proofs or tuning. It is coherent on its own terms and addresses a documented gap, so it deserves to go to peer review rather than a desk rejection. I would send it out.

Referee Report

0 major / 2 minor

Summary. The manuscript extends weak convergence theory for the Chambolle-Pock primal-dual algorithm (with relaxation parameter θ) in real Hilbert spaces. It proves that whenever τσ‖L‖² ≤ 4θ(2-θ)/(1-2θ+9θ²-4θ³), the ergodic duality gap converges at rate O(1/k); when the inequality is strict, the primal-dual iterates converge weakly to a KKT point. The argument relies on a single Lyapunov function asserted to decrease uniformly for every θ ∈ (0,1], thereby covering the previously open interval 0<θ≤1/2 without case distinctions.

Significance. If the central claim holds, the result meaningfully enlarges the admissible step-size region for a widely used first-order method, especially in the low-relaxation regime. The derivation of an explicit, θ-dependent but otherwise parameter-free bound directly from the non-positivity condition on the Lyapunov decrement is a technical strength; the uniform validity of the Lyapunov function over the closed interval 0<θ≤1 avoids the need for separate analyses and supplies a concrete, falsifiable prediction for step-size selection.

minor comments (2)

[Abstract] Abstract and title: the abstract states the duality-gap result under ≤ while the title uses <; a single clarifying sentence on whether equality is admissible for the O(1/k) rate (but not for weak convergence) would remove ambiguity.
[Throughout] Notation: the operator norm is written both as |L| and ‖L‖; consistent use of ‖·‖ throughout would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment and recommendation of minor revision. The report correctly summarizes the extension of weak convergence for the Chambolle-Pock method to 0 < θ ≤ 1 via a uniform Lyapunov function and the explicit step-size bound. No major comments were raised requiring point-by-point rebuttal.

Circularity Check

0 steps flagged

No circularity: Lyapunov function constructed to derive bound

full rationale

The paper constructs a Lyapunov function V_k that decreases uniformly for all θ in (0,1] and derives the precise cubic bound on τσ‖L‖² directly from the non-positivity condition on its decrease. This yields the ergodic O(1/k) duality gap and weak convergence as standard consequences, without the bound being presupposed, fitted to data, or reduced to a self-citation chain. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The central claim rests on the existence of a Lyapunov function valid uniformly over 0 < θ ≤ 1 together with standard properties of Hilbert spaces and convex functions; no free parameters or new entities are introduced.

axioms (3)

standard math The underlying space is a real Hilbert space
Standard setting stated in the abstract for the saddle-point problem and weak convergence.
domain assumption The functions are proper, lower semicontinuous, and convex
Required for the problem to be well-posed and for the duality gap to be meaningful.
domain assumption L is a bounded linear operator
Used to define the operator norm appearing in the step-size condition.

pith-pipeline@v0.9.0 · 5520 in / 1611 out tokens · 62633 ms · 2026-05-10T18:31:05.961181+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

11 extracted references · 9 canonical work pages

[1]

Applegate, M

D. Applegate, M. Díaz, O. Hinder, H. Lu, M. Lubin, B. O’Donoghue, and W. Schudy. Practical large-scale linear programming using primal-dual hybrid gradient. InAdvances in Neural Information Processing Systems, volume 34, pages 20243–20257, 2021

2021
[2]

Applegate, M

D. Applegate, M. Díaz, H. Lu, and M. Lubin. Infeasibility detection with primal-dual hybrid gradient for large-scale linear programming.SIAM Journal on Optimization, 34(1):459–484, 2024.doi:10.1137/22M1510467

work page doi:10.1137/22m1510467 2024
[3]

Applegate, O

D. Applegate, O. Hinder, H. Lu, and M. Lubin. Faster first-order primal-dual methods for linear programming using restarts and sharpness.Mathematical Programming, 201(1):133– 184, 2023.doi:10.1007/s10107-022-01901-9

work page doi:10.1007/s10107-022-01901-9 2023
[4]

Banert, M

S. Banert, M. Upadhyaya, and P. Giselsson. The Chambolle–Pock method converges weakly withθ>1/2and τσ∥L∥2< 4/(1 + 2θ).Optimization Letters, 20(3):503–520, 2026. doi:10.1007/s11590-025-02250-0

work page doi:10.1007/s11590-025-02250-0 2026
[5]

H. H. Bauschke and P. L. Combettes.Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics. Springer International Publishing, Cham, 2017. doi:10.1007/978-3-319-48311-5

work page doi:10.1007/978-3-319-48311-5 2017
[6]

Journal of Mathematical Imaging and Vision40(1), 120–145 (2010)

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

work page doi:10.1007/s10851-010-0251-1 2011
[7]

Chambolle and T

A. Chambolle and T. Pock. An introduction to continuous optimization for imaging.Acta Numerica, 25:161–319, 2016.doi:10.1017/S096249291600009X

work page doi:10.1017/s096249291600009x 2016
[8]

Chambolle and T

A. Chambolle and T. Pock. On the ergodic convergence rates of a first-order primal- dual algorithm.Mathematical Programming, 159(1-2):253–287, 2016. doi:10.1007/ s10107-015-0957-3. 16

2016
[9]

Lu and J

H. Lu and J. Yang. cuPDLP.jl: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia.Operations Research, 73(6):3440–3452, 2025. doi:10.1287/opre.2024.1069

work page doi:10.1287/opre.2024.1069 2025
[10]

Upadhyaya, S

M. Upadhyaya, S. Banert, A. B. Taylor, and P. Giselsson. Automated tight Lyapunov analysis for first-order methods.Mathematical Programming, 209:133–170, 2025. doi: 10.1007/s10107-024-02061-8

work page doi:10.1007/s10107-024-02061-8 2025
[11]

Upadhyaya, S

M. Upadhyaya, S. Das Gupta, A. B. Taylor, S. Banert, and P. Giselsson. The AutoLyap software suite for computer-assisted Lyapunov analyses of first-order methods, 2026.arXiv: 2506.24076v2. 17

work page arXiv 2026