The Chen-Teboulle algorithm is the proximal point algorithm

Stephen Becker

REVIEW 2 major objections 3 minor 12 references

The Chen-Teboulle algorithm is the proximal point algorithm

T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read The Chen-Teboulle algorithm is the proximal point algorithm carried out in a weighted norm, and this identification permits a larger step size.

desk verdict A real conceptual link with a repairable proof gap; the step-size bound is likely correct but the equivalence needs an explicit variable shift. read the letter →

arxiv 1908.03633 v1 pith:RPBRZ76U submitted 2019-08-09 math.OC

Stephen Becker This is my paper · ORCID

classification math.OC MSC 90C2547H0565K05

keywords Chen-Teboullealgorithmproximalpointprimal-dualsplittingweightednormstep-sizeboundmonotoneoperatorconvexoptimizationresolvent

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

The paper argues that the Chen-Teboulle splitting method for minimizing $f(x)+g(Ax)$ is not a standalone predictor-corrector scheme but a special case of the proximal point algorithm. The special case is obtained by choosing a weighted norm whose metric $V$ is engineered to decouple the $x$ and $z$ updates of the monotone inclusion. If the identification is correct, Chen-Teboulle inherits the full convergence theory of proximal point methods, and its step-size constraint improves from $\lambda<1/(2L)$ to $\lambda\le 1/\sqrt{\|A\|^2+1}$. A sympathetic reader would care because the same weighted-norm viewpoint turns one algorithm into a template for constructing and analyzing primal-dual splitting methods.

What carries the argument

The load-bearing object is the metric operator $V$ of equation (12): a positive-definite block matrix with diagonal blocks $\tau_x I$, $\tau_z I$, $\tau_y I$ and off-diagonal blocks chosen so that $V+\mathcal A$ has zero upper-triangular blocks. That cancellation makes the resolvent block-separable, so the $x$ and $z$ updates decouple and the $y$ update is a simple affine correction, which is precisely the predictor-corrector structure of Chen-Teboulle. The same $V$ carries the convergence argument: applying the Schur complement test to $V\succ 0$ produces the improved step-size condition.

What would settle it

Take $f=0$, $g=0$, $A=I$, $\lambda=1/2$, start both algorithms at the same triple $(x_0,z_0,y_0)$, and compare the first iterates of equations (5)–(8) with those of (13)–(15). The paper's identification predicts identical iterates; a direct computation shows they differ, so this example either falsifies the claimed equality or forces a precise restatement of the 're-organizing the steps' equivalence.

Watch

Extended reading notes

Core claim

The paper's central claim is an identity between two iteration rules. The saddle-point conditions for (1) are written as a monotone inclusion $0\in\mathcal A(x,z,y)$ with $\mathcal A(x,z,y)=(\partial f(x)+A^*y,\ \partial g(z)-y,\ z-Ax)$. Choosing the Hermitian positive-definite metric $V$ in equation (12) cancels the upper-triangular coupling of $\mathcal A$, so the resolvent $(V+\mathcal A)^{-1}$ separates into independent proximal steps in $x$ and $z$ plus an affine update in $y$. The proximal point iteration $\mathbf{x}_{k+1}=(V+\mathcal A)^{-1}V\mathbf{x}_k$ then reproduces the Chen-Teboulle updates after a re-ordering of the steps. Under that identification, the condition $V\succ 0$ yields the refined step-size bound $\lambda\le 1/\sqrt{\|A\|^2+1}$, replacing the original $\lambda<1/(2L)$.

Load-bearing premise

The load-bearing premise is that the proximal point updates (13)–(15) are, after re-ordering the steps, exactly the Chen-Teboulle updates (5)–(8); if those two iteration rules are not the same, the improved step-size bound does not transfer to Chen-Teboulle.

Editorial extensions

If this is right

For $\|A\|\ge 1$, the admissible step size grows from roughly $1/(2\|A\|)$ to roughly $1/\|A\|$, so the method can take larger steps without leaving the convergence regime.
Because the algorithm is an instance of proximal point, it inherits weak convergence guarantees and allowance for inexact evaluations of the proximal steps.
Distinct weights $\tau_x\neq\tau_z\neq\tau_y$ are permitted; the paper highlights $\tau_x=\|AA^*\|$, $\tau_z=1$, $\tau_y<1/2$ as a usable parameter choice.
The same weighted-metric construction extends the analysis to more general compositions such as $f(E_1x+b_1)+g(E_2x+b_2)$, as the paper states follows from the viewpoint.

Reading between the lines

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

The hinge of the argument is the 're-organizing the steps' step in Section 2.1; my own spot check on $f=g=0$, $A=I$, $\lambda=1/2$ gives different first iterates for (13)–(15) versus (5)–(8), so the equivalence is a substantive claim to verify rather than a notational relabeling.
If the identity holds, the Schur-complement condition in (16) is a general recipe: other primal-dual splittings correspond to other choices of the off-diagonal block $B$, and each would inherit a step-size bound of the form $\tau_y I\succ\tau_x^{-1}AA^*+\tau_z^{-1}BB^*$.
A practical test of the larger bound would be to run Chen-Teboulle with $\lambda$ between $1/(2L)$ and $1/\sqrt{\|A\|^2+1}$ on a small quadratic program; the old theory predicts possible divergence and the new theory predicts convergence, so the experiment separates the two claims.

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.

Desk Editor's Note

read the letter

Hi —

The short version: this note has a real insight, but the central equivalence is not established as written. I think the gap is fixable and the result is probably correct, so it deserves a serious referee—not a desk reject.

What is actually new: the paper reads Chen-Teboulle as the proximal point algorithm under the scaled norm (12), and derives the step-size condition λ ≤ 1/√(‖A‖²+1), which is looser than the original λ < 1/(2L) from [CT94]. That bound is a genuine improvement for a method the author honestly describes as “not widely used.” The scaled-norm technique is credited to [HY12], so the novelty is the application to Chen-Teboulle and the sharper condition. The algebra up to the Schur complement test is clean and self-contained; no fitted parameters, no overclaiming about numerical behavior.

Where it softens: Section 2.1 says that after “re-organizing the steps” the PPA scheme (13)–(15) is Chen-Teboulle. That is the load-bearing step, and the paper does not prove it. The reader checked a trivial case—f=g=0, A=I, λ=1/2—and gets different iterates from (5)–(8) and (13)–(15). I rechecked; the reader is right. The displayed equations are not the same map on the same variables. The stress-test note shows how to fix it: the PPA dual variable should be the Chen-Teboulle predictor p_{k+1} = y_k + λ(Ax_k − z_k), not y_k. With that shift, (13)–(15) do correspond to (5)–(8). But the paper never states this transformation; its claim that p^{k+1} equals y_{k+1} is off by one index. So the transfer of the PPA convergence and the bound (17) to Chen-Teboulle is not proven as written.

This is a serious but narrow flaw, not a sign of incoherence. The paper is honest about prior work and the derivation is reproducible. The fix is a few paragraphs. The lack of numerical experiments is fine for a theoretical note; the contribution is conceptual.

Who gets value: anyone working on primal-dual splitting methods, especially the lineage from Chen-Teboulle through Chambolle-Pock, Condat-Vu, and related methods. The improved step-size bound is practically interesting if the equivalence holds.

Recommendation: send to review. The editor should not desk-reject; the idea is sound and the flaw is repairable. I would ask for a major revision that reworks Section 2.1 with an explicit change of variables and a correct index. If that lands, the paper would be a useful short contribution.

Referee Report

2 major / 3 minor

Summary. The paper claims that the Chen-Teboulle algorithm (equations (5)-(8)) is exactly the proximal point algorithm applied to the monotone inclusion (4) with a specially chosen metric V defined in (12). On the basis of this equivalence, the author derives the step-size condition lambda <= 1/sqrt(||A||^2+1) in (17), which is weaker than the original condition lambda < 1/(2L) in (9). The paper is a short technical report; its main contribution is the identification with a variable-metric proximal point method and the resulting improved step-size bound.

Significance. If the central equivalence were correctly established, the paper would provide a clean and conceptually useful derivation of the Chen-Teboulle algorithm and a genuinely less restrictive step-size condition, inheriting proximal point convergence guarantees. The Schur complement computation leading to (17) is straightforward and self-contained, with no fitted parameters. However, the load-bearing claim that equations (13)-(15) recover Chen-Teboulle is asserted without a proof and, as written, is false because the dual variable is misidentified. The underlying identification is likely repairable by shifting the dual variable, but the present manuscript does not contain the required statement or proof.

major comments (2)

[Section 2.1, equations (13)-(15) and the claim after (15)] The paper asserts that choosing tau_x = tau_y = tau_z = 1/lambda and re-organizing the steps recovers the Chen-Teboulle algorithm, but the displayed updates are not the same map on the same variables. For f = g = 0, A = I, and lambda = 1/2, starting from (x0,z0,y0) = (1,0,0), the Chen-Teboulle updates (5)-(8) give (x1,z1,y1) = (0.75, 0.25, 0.25), while the proximal updates (13)-(15) give (1, 0, 0.5). This numerical discrepancy shows that the equivalence as stated is false, and since the step-size bound (17) and the proximal point convergence results are transferred to Chen-Teboulle through this equivalence, the paper's central claim is not proven as written.
[Section 2.1, sentence comparing p^{k+1} and y_{k+1}] The statement that 'the p^{k+1} in (5) is the same as the y_{k+1} in (15)' is off by one index. The correct identification appears to be v_k = p_{k+1} = y_k + lambda(A x_k - z_k): with this shift, equation (6) matches (13), equation (7) matches (14), and equation (15) yields v_{k+1} = p_{k+2}. The manuscript needs to introduce this shifted dual variable explicitly and prove the equivalence in detail; until this is done, the improved bound (17) has not been shown to apply to Chen-Teboulle.

minor comments (3)

[Equation (17)] The condition for V to be positive definite requires the strict inequality lambda < 1/sqrt(||A||^2+1), because at equality the Schur complement is only positive semidefinite. The paper writes 'lambda <=' in (17); if the endpoint is meant to be included, a separate argument or a non-strict variant of the convergence result is needed.
[Equation (10) and surrounding text] The 'matrix-multiplication' notation in (10) is described as 'A . (x,y,z)', but the block vector in the surrounding text is (x,z,y); please make the ordering consistent.
[Section 1.1] The notation 'zero(A)' is introduced but not used later; the non-emptiness assumption is stated once and then the text proceeds. Consider defining the set of zeros once and referring back to it when needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the V-metric is constructed to match Chen-Teboulle, and the step-size bound follows from Schur complements rather than from an assumed conclusion.

full rationale

The paper's load-bearing step is the identification of the Chen-Teboulle updates (5)-(8) with the proximal point algorithm in a V-norm. This is done by constructing V in equation (12) so that (V+A)^{-1} is block-separable, then 're-organizing the steps' to recover the Chen-Teboulle iteration. No data are fitted, no parameter is calibrated to the claimed conclusion, and no load-bearing self-citation is used. The improved step-size bound (17) is derived from the Schur complement condition for V ≻ 0, not imported from the Chen-Teboulle paper or assumed as an input. Even if the numerical counterexample in the reader's take correctly shows an off-by-one index issue between p^{k+1} and y_{k+1}, that would be a soundness or correctness problem in proving the equivalence, not circularity. The claimed bound is not equivalent by construction to any input of the derivation. The analysis is therefore self-contained from a circularity standpoint, and the appropriate score is 0.

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

The derivation uses standard convex analysis and monotone operator results. The only novel assumption is the equivalence of Chen-Teboulle to the V-metric proximal point algorithm, which is unsupported and appears false.

assumptions (4)

domain assumption A is a maximal monotone operator (e.g., subdifferential of a proper lsc convex function) and zero(A) is non-empty.
Standard for monotone operator theory; used in Section 1.1 to ensure resolvents are well-defined and firmly non-expansive.
domain assumption Strong duality and existence of saddle points for the Fenchel-Rockafellar dual, e.g., 0 in sri(dom g - A(dom f)).
Needed for the optimality conditions (3)-(4); stated in Section 2 before equation (3).
standard math For maximal monotone A and V positive definite, V^{-1}A is maximal monotone in the ||.||_V norm.
Invoked to transfer proximal point convergence theory; plausible but not proved in this note.
ad hoc to paper The Chen-Teboulle algorithm is exactly the proximal point algorithm with the chosen V block-structure.
This is the load-bearing equivalence asserted in Section 2.1 ('re-organizing the steps, we recover the Chen-Teboulle algorithm'). It is not proved and is contradicted by a direct comparison of (5)-(8) with (13)-(15) for f=g=0, A=I.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Chen-Teboulle algorithm is the proximal point algorithm." pith.science (2026). https://pith.science/paper/RPBRZ76U

@misc{pith2026190803633,
  author       = {Pith},
  title        = {Pith review of: The Chen-Teboulle algorithm is the proximal point algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RPBRZ76U}},
  note         = {Machine review of arXiv:1908.03633}
}

read the original abstract

We revisit the Chen-Teboulle algorithm using recent insights and show that this allows a better bound on the step-size parameter.

Figures

Figures reproduced from arXiv: 1908.03633 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

H. H. Bauschke and P. L. Combettes, Convex analysis and monotone operator theory in Hilbert spaces , Springer-Verlag, New York, 2011

work page 2011
[2]

Condat, A primal-dual splitting method for convex optimization involving L ipschitzian, proximable and linear composite terms , J

L. Condat, A primal-dual splitting method for convex optimization involving L ipschitzian, proximable and linear composite terms , J. Optim. Theory Appl. (2013), 460--479

work page 2013
[3]

P. L. Combettes and J.-C. Pesquet, A D ouglas- R achford splitting approach to nonsmooth convex variational signal recovery , IEEE J. Sel. Topics Signal Processing 1 (2007), no. 4, 564--574

work page 2007
[4]

Chambolle and T

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision 40 (2010), no. 1, 120--145

work page 2010
[5]

Chen and M

G. Chen and M. Teboulle, A proximal-based decomposition method for convex minimization problems, Math. Prog. 64 (1994), no. 1-3, 81--101

work page 1994
[6]

Esser, X

E. Esser, X. Zhang, and T. 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), no. 4, 1015--1046

work page 2010
[7]

He and X

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. (2012), 119--149

work page 2012
[8]

Moreau, Fonctions convexes duales et points proximaux dans un espace hilbertien, R

J.-J. Moreau, Fonctions convexes duales et points proximaux dans un espace hilbertien, R. Acad. Sci. Paris S\'er. A Math. 255 (1962), 2897--2899

work page 1962

Show all 12 references

[9]

R. T. Rockafellar, Convex analysis, Princeton Landmarks in Mathematics and Physics, Princeton University Press, Princeton, NJ, 1970

1970
[10]

Tseng, On accelerated proximal gradient methods for convex-concave optimization, SIAM J

P. Tseng, On accelerated proximal gradient methods for convex-concave optimization, SIAM J. Optim., submitted (2008)

2008
[11]

B. C. V \ u , A splitting algorithm for dual monotone inclusions involving cocoercive operators, Adv. Comput. Math 38 (2013), no. 3, 667--681

2013
[12]

Zhu and T

M. Zhu and T. Chan, An efficient primal-dual hybrid gradient algorithm for total variation image restoration, Tech. Report CAM08-34, UCLA, 2008, Available at ftp://ftp.math.ucla.edu/pub/camreport/cam08-34.pdf

2008

Pith tools

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

[1] [1]

H. H. Bauschke and P. L. Combettes, Convex analysis and monotone operator theory in Hilbert spaces , Springer-Verlag, New York, 2011

work page 2011

[2] [2]

Condat, A primal-dual splitting method for convex optimization involving L ipschitzian, proximable and linear composite terms , J

L. Condat, A primal-dual splitting method for convex optimization involving L ipschitzian, proximable and linear composite terms , J. Optim. Theory Appl. (2013), 460--479

work page 2013

[3] [3]

P. L. Combettes and J.-C. Pesquet, A D ouglas- R achford splitting approach to nonsmooth convex variational signal recovery , IEEE J. Sel. Topics Signal Processing 1 (2007), no. 4, 564--574

work page 2007

[4] [4]

Chambolle and T

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision 40 (2010), no. 1, 120--145

work page 2010

[5] [5]

Chen and M

G. Chen and M. Teboulle, A proximal-based decomposition method for convex minimization problems, Math. Prog. 64 (1994), no. 1-3, 81--101

work page 1994

[6] [6]

Esser, X

E. Esser, X. Zhang, and T. 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), no. 4, 1015--1046

work page 2010

[7] [7]

He and X

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. (2012), 119--149

work page 2012

[8] [8]

Moreau, Fonctions convexes duales et points proximaux dans un espace hilbertien, R

J.-J. Moreau, Fonctions convexes duales et points proximaux dans un espace hilbertien, R. Acad. Sci. Paris S\'er. A Math. 255 (1962), 2897--2899

work page 1962