On the convergence rate of the Douglas-Rachford splitting algorithm

Hadi Abbaszadehpeivasti; Moslem Zamani

REVIEW 3 major objections 4 minor 30 references

On the convergence rate of the Douglas-Rachford splitting algorithm

T0 review · 3 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read The paper proves that for relaxation λ=1, Douglas-Rachford splitting has exact worst-case squared residual ((N-1)^{N-1}/N^N)‖w1−w*‖² after N steps, and that two subspaces in R² attain this bound.

desk verdict A mostly solid paper: the sharp O(1/N) rate for DRS with λ=1 is real, but the abstract overclaims and secondary results have gaps. read the letter →

arxiv 2509.06676 v2 pith:7NWKTQWB submitted 2025-09-08 math.OC

Hadi Abbaszadehpeivasti , Moslem Zamani This is my paper · ORCID

classification math.OC MSC 47H0565K1090C25

keywords Douglas-Rachfordsplittingmonotoneinclusionconvergencerateconvexfeasibilityerrorboundconditionlinearsilverstepsizescheduleperformanceestimation

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 pins down the exact worst-case behavior of the Douglas-Rachford splitting algorithm. For relaxation parameter λ=1, after N iterations the squared one-step residual is at most ((N-1)^(N-1)/N^N) times the squared distance of the starting point to a fixed point, and a convex feasibility problem defined by two subspaces in the plane attains equality. The paper also characterizes linear convergence: the distance to the fixed-point set shrinks linearly exactly when an error-bound condition holds, with an explicit contraction factor, and gives a new sufficient condition for that error bound when one operator is cocoercive and the problem satisfies restricted strong monotonicity. For convex composite optimization, it proves a tightened silver-stepsize rate for gradient descent and proposes several conjectured DRS rates, including an accelerated variant. If these claims hold, users would know both the precise worst-case slowdown of DRS and exactly which structural assumptions turn its convergence linear.

What carries the argument

The central object is the DR operator T=(1−λ/2)I + (λ/2)R_{γA}R_{γB}, an averaged nonexpansive operator built from reflected resolvents. Theorem 1's proof is a telescoping sum of two families of valid inequalities weighted so that all negative terms are absorbed; this yields the constant ((N−1)^(N−1)/N^N). The sharpness construction uses a two-subspace feasibility problem in R² whose DR operator is a scaled rotation, making the residual equality exact. For linear convergence, the load-bearing condition is the error bound D_{W*}(w) ≤ μ‖(I−T)w‖; Proposition 2 derives it from restricted strong monotonicity plus cocoercivity through a long algebraic identity.

What would settle it

Normalize β=1 and evaluate the polynomials D(γ, μ_f), E(γ, μ_f), and P2(γ, μ_f) from Proposition 2 on a dense grid of admissible pairs (γ∈(0,1], μ_f>0); any negative value breaks the claimed error-bound inequality. Separately, run DRS on the two-subspace example P={(x,0)}, Q={(x,x/√(N−1))} for N=2,3,4 with a unit starting point and verify ‖w_{N+1}−w_N‖² equals (N−1)^(N−1)/N^N exactly.

Watch

Extended reading notes

Core claim

For λ=1, the Douglas-Rachford iteration T satisfies ‖T w_N − w_N‖² ≤ ((N−1)^(N−1)/N^N)‖w₁−w*‖², and Theorem 2 builds two subspaces P={(x,0)} and Q={(x,x/√(N−1))} in R² whose normal-cone inclusion makes the DR operator a scaled rotation of angle arcsin(1/√N); on this example the inequality is an equality. The bound is therefore sharp for general monotone inclusions and for convex feasibility problems. The paper further proves that linear convergence of DRS is equivalent to an error-bound condition of the form D_{W*}(w) ≤ μ‖(I−T)w‖, with contraction factor √(1−(2/λ−1)/μ²), and that this condition follows when B is β-cocoercive and the inclusion satisfies restricted strong monotonicity, giving

Load-bearing premise

The proof of Proposition 2 depends on the unshown claim that three algebraic expressions D, E, and P2 are nonnegative for every admissible stepsize and restricted-strong-monotonicity modulus; if any is negative for some allowed parameters, the sufficient condition for linear convergence collapses.

Editorial extensions

If this is right

For any maximally monotone inclusion solved by DRS with λ=1, the O(1/N) residual rate with constant ((N−1)^(N−1)/N^N) cannot be improved; adding cocoercivity of one operator alone does not help, since the rotation example already satisfies it.
Linear convergence of DRS is fully characterized by the error-bound condition: if the bound holds, the squared fixed-point distance contracts by the explicit factor 1−(2/λ−1)/μ², and if the iteration is linearly convergent, the bound must hold.
The sufficient condition for the error bound is checkable in advance: when B is β-cocoercive and restricted strong monotonicity holds with modulus μ_f, the error-bound constant is explicit, so a user can certify linear convergence and read off the contraction rate before iterating.
The proven silver-stepsize gradient-descent bound F(x_N)−F* ≤ ‖x₀−x*‖²/(4ρ^{k−2}) holds for every k, refining the existing silver-schedule rate and supplying a proof template for the paper's DRS silver-schedule conjecture.
In convex feasibility, the sharpness example also reproduces the known alternating-projection distance rate, so DRS and alternating projection have the same worst-case constant in this setting.

Reading between the lines

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

The sharpness example shows the constant ((N−1)^(N−1)/N^N) is exact for every averaged nonexpansive iteration, not only DRS: Theorem 1 states the upper bound for any nonexpansive S, and the two-subspace construction provides a nonexpansive S that attains it.
The explicit μ formula implies that within the allowed range 0<γ≤β, the contraction factor improves as γ approaches β and as λ approaches 2; the authors do not spell out this monotonicity, but it follows directly from their formula and could guide step-size selection.
If the paper's conjectured composite rates are true, DRS with λ=1 would match the exact ADMM rate, the silver relaxation schedule would give a 1/(γρ^k)-type objective gap, and the momentum variant would reach O(1/N²) without strong convexity—an acceleration that so far is proven only in restricted settings.
A natural next step is to verify the conjectured DRS rates by running the same performance-estimation computations on small synthetic problems; the conjectures are numerically motivated but not proven, so those computations are the fastest route to either proof or counterexample.

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.

Desk Editor's Note

read the letter

The core result is real and worth knowing. For λ=1, the paper gives a clean proof of the sublinear rate ‖T w_N − w_N‖² ≤ ((N−1)^(N−1)/N^N)‖w_1 − w*‖², and Theorem 2 shows it's tight with a concrete two-subspace example in R². The proof is a telescoping sum-of-squares certificate; I spot-checked small N and it holds. The sharpness construction is genuinely new as far as I know. They also give a correct necessary-and-sufficient characterization of linear convergence under the error bound condition, and the restricted strong monotonicity route (Proposition 2) is a reasonable idea. The conjectures are honestly labeled and the numerical experiments are not used to prove theorems, so no circularity.

The soft spots are real but mostly secondary. Proposition 2 has an unproved algebraic claim: "By doing some algebra, one can show that D, E, P2 ≥ 0." Those are nasty polynomials in γ and μ_f. That's a gap in a supporting sufficient condition, not in the main rate theorem, but it needs to be fixed or the proposition downgraded to a conjecture. Theorem 4, the silver stepsize improvement, is essentially stated without proof—Lemma 1's induction is sketched at best, and the final theorem is one line. The abstract's phrase "exact rate of convergence" is misleading for the general case: the rate itself is quoted from Lieder's thesis for λ>1, and the proof given is only for λ=1. That overclaim should be corrected.

One thing I disagree with the reader on: the stress-test note is right that the central claim is sound, but I'd push back on calling the sharpness example merely "plausible." I checked the rotation construction and it works exactly. The paper deserves engagement not because it's flawless but because the main result is sharp and the conceptual contribution—showing DRS can't do better on feasibility than on general inclusions—is clean.

Who is this for? People working on operator splitting and performance estimation. It's a useful foundational result, even if some parts are rough. I'd send it to a serious referee who can verify the algebra in Proposition 2 and push on Theorem 4. The paper is not ready as is, but it's a legitimate contribution that should be reviewed rather than desk-rejected.

Referee Report

3 major / 4 minor

Summary. The paper studies convergence rates of Douglas-Rachford splitting (DRS) for monotone inclusions. Its main result is a sublinear bound on the DRS residual, ||T w_N - w_N||^2 ≤ ((N-1)^{N-1}/N^N) ||w_1 - w*||^2 for relaxation λ=1, proved via a telescoping-sum certificate for general nonexpansive operators (Theorem 1), and a sharpness construction for convex feasibility (Theorem 2). The paper also studies linear convergence: Theorem 3 gives a linear rate under an error-bound condition, Proposition 1 shows a converse, and Proposition 2 attempts a sufficient condition via restricted strong monotonicity. Sections 5 and 6 present results and conjectures for composite convex optimization, including a silver stepsize schedule for gradient descent and an accelerated DRS variant.

Significance. The sharp O(1/N) sublinear rate for DRS with λ=1 and its equality example are valuable and likely correct; the proof technique is explicit and self-contained. The characterization of linear convergence via error bound is also of interest. The paper is strengthened by clearly labeled conjectures and numerical motivation, avoiding circularity. However, the sufficiency part of the linear-convergence characterization rests on an unproved algebraic claim in Proposition 2, and Theorem 4 is stated without proof. These gaps must be addressed before the results can be fully trusted.

major comments (3)

[Section 4, Proposition 2] The proof contains the statement "By doing some algebra, one can show that D, E, P2 ≥ 0" and then concludes the error bound. This nonnegativity claim is load-bearing: it is exactly what turns the sum of inequalities into 0 ≤ μ^2 ||T w_k - w_k||^2 - ||w_k - w*||^2. No derivation or certificate is given. Furthermore, the displayed identity appears to use α3 times an expression with μ_f, while the restricted strong monotonicity inequality was stated with ar μ_f = min(μ_f,1); the mismatch must be resolved. Please provide a complete proof of the nonnegativity and clarify the modulus used.
[Section 5.1, Theorem 4] The proof is only "The theorem is derived from Lemma 1." No detailed derivation is provided, and the claimed tightness via a "proper Huber function" is unsupported. Since Theorem 4 is stated as a formal result, either supply a full proof linking Lemma 1 to inequality (17), or demote it to a conjecture/remark with the numerical evidence. If this result is tangential to the DRS focus, that should be made explicit.
[Section 4, Theorem 3] The proof uses [22, Theorem 1] to assert w_k ∈ W, where W = {w : D_W*(w) ≤ D_W*(w_1)}. This inclusion is essential for applying the error bound (6). The citation is not self-contained and the exact statement used is not given. Please either state the relevant result explicitly or prove that Algorithm 1 keeps iterates in W under Assumption 1.

minor comments (4)

[Section 3, Eq. (3)] The relaxation interval is written as λ ∈ [1, 1+√((k-1)/k)); the symbol k is undefined—presumably N is intended. Also clarify the scope: the self-contained Theorem 1 covers λ=1, while (3) is cited from [17] for other λ.
[Section 3, Theorem 1 proof] The telescoping identity is asserted after listing the summed inequalities. A brief derivation or an explicit statement of how the multipliers produce the square terms would improve verifiability.
[Section 5, footnote 1] The footnote "Owing to external constraints..." is informal and not appropriate for a research paper. Consider removing or rewording it.
[Section 4, Proposition 2] The parameter β is normalized to 1 at the start, but the original statement allows γ ≤ β. The scaling argument is only sketched; please make it explicit to avoid confusion about the admissible ranges of γ and μ_f.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main λ=1 rate bound and its sharpness construction are self-contained; the general-λ rate is cited from an independent source, and the conjectures are explicitly unproven.

full rationale

The central claim is Theorem 1's proof of inequality (4), which is a telescoping sum-of-squares certificate built directly from nonexpansivity; the displayed identity after summing is exact and yields the bound without any fitted quantity or input-dependent parameter. The sharpness example in Theorem 2 constructs two subspaces P and Q, computes the DR operator as a scaled rotation, and uses the law of cosines to obtain exactly the claimed equality; this is an independent construction, not an imported or fitted result. The general-λ inequality (3) is quoted from Lieder [17], an external source, and is not derived from the paper's own conjectures or numerical experiments. The linear-convergence section uses Theorem 3 as a direct algebraic consequence of monotonicity and the external error-bound condition from [22]; Proposition 1 is a short direct proof. Proposition 2 contains an unverified algebraic claim—'By doing some algebra, one can show that D, E, P2 ≥ 0'—which is a missing proof or potential gap in a supporting sufficient condition, but it is not circular because those polynomial nonnegativities are neither assumed as inputs nor imported from a self-citation. The conjectures at the end are explicitly labeled as conjectures informed by numerical experiments and are never used to derive the theorems. Self-citations to [1,28,29,30] occur only in remarks or related-work comparisons and are not load-bearing. Therefore no prediction reduces to its input by construction, and no self-citation chain forces the central result.

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

The proven results introduce no free parameters or invented entities; they rely on standard monotone operator theory and two domain assumptions (existence of a fixed point, smoothness). The only ad hoc elements are the unproved algebraic nonnegativity in Proposition 2 and the empirically motivated conjectures, which are honestly labeled as conjectures.

assumptions (8)

standard math Resolvents of maximally monotone operators are firmly nonexpansive; reflected resolvents are nonexpansive.
Used to define the DR operator and to invoke nonexpansivity in Theorem 1 and throughout; see Section 2.
domain assumption Assumption 1: A and B are maximally monotone and the DR operator admits a fixed point.
Guarantees convergence of the algorithm; used in Theorems 1, 3 and Propositions 1, 2.
domain assumption Assumption 2: f and g are closed proper convex, f is L-smooth, and the DR operator has a fixed point.
Used for the composite optimization section and conjectures, Section 5.
domain assumption Error bound condition (6) holds for the DR operator on the sublevel set W.
Assumed in Theorem 3 to derive linear convergence; also discussed in Proposition 1 as necessary.
domain assumption Restricted strong monotonicity (9) holds with modulus μ_f > 0.
Used in Proposition 2 to establish the error bound condition.
standard math Nesterov's interpolation inequality for 1-smooth convex functions.
Invoked in Lemma 1 (base case and induction) as [20, Theorem 2.1.5].
ad hoc to paper The algebraic expressions D, E, and P2 in Proposition 2 are nonnegative for admissible γ and μ_f.
Stated without proof ('By doing some algebra'); the proof of Proposition 2 depends on it. If false, the error bound derivation fails.
ad hoc to paper The rate in Theorem 4 is tight via an unspecified 'proper Huber function'.
The tightness is asserted but not demonstrated; this supports the claimed silver stepsize result.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the convergence rate of the Douglas-Rachford splitting algorithm." pith.science (2026). https://pith.science/paper/7NWKTQWB

@misc{pith2026250906676,
  author       = {Pith},
  title        = {Pith review of: On the convergence rate of the Douglas-Rachford splitting algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7NWKTQWB}},
  note         = {Machine review of arXiv:2509.06676}
}

read the original abstract

This work is concerned with the convergence rate analysis of the Douglas-Rachford splitting (DRS) method for finding a zero of the sum of two maximally monotone operators. We obtain an exact rate of convergence for the DRS algorithm and demonstrate its sharpness in the setting of convex feasibility problems. Furthermore, we investigate the linear convergence of the DRS algorithm, providing both necessary and sufficient conditions that characterize this behavior. We further examine the performance of the DRS method when applied to convex composite optimization problems. The paper concludes with several conjectures on the convergence behavior of the DRS algorithm for this class of problems.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 28 canonical work pages

[1]

Abbaszadehpeivasti H (2024)Performance analysis of optimization methods for machine learning. Ph.D. thesis, Tilburg University

work page 2024
[2]

Altschuler JM, Parrilo PA (2024) Acceleration by stepsize hedging: Silver stepsize schedule for smooth convex optimization.Mathematical Programming1–14

work page 2024
[3]

Altschuler JM, Parrilo PA (2025) Acceleration by stepsize hedging: Multi-step descent and the silver stepsize schedule.Journal of the ACM72(2):1–38

work page 2025
[4]

Aspelmeier T, Charitha C, Luke DR (2016) Local linear convergence of the ADMM/Douglas–Rachford algorithms without strong convexity and application to statistical imaging.SIAM Journal on Imaging Sciences9(2):842–868

work page 2016
[5]

Bauschke HH, Combettes PL (2017)Convex Analysis and Monotone Operator Theory in Hilbert Spaces (Springer), 2nd edition

work page 2017
[6]

Bok J, Altschuler JM (2025) Optimized methods for composite optimization: a reduction perspective.arXiv preprint arXiv:2506.23756

arXiv 2025
[7]

Combettes PL (2018) Monotone operator theory in convex optimization.Mathematical Programming170(1):177– 206

work page 2018
[8]

Douglas J, Rachford HH (1956) On the numerical solution of heat conduction problems in two and three space variables.Transactions of the American mathematical Society82(2):421–439

work page 1956

Show all 30 references

[9]

Mathematical Programming145(1):451–482

Drori Y, Teboulle M (2014) Performance of first-order methods for smooth convex minimization: a novel approach. Mathematical Programming145(1):451–482

2014
[10]

Eckstein J, Bertsekas DP (1992) On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators.Mathematical Programming55(1):293–318

1992
[11]

16 Convergence rate of the DRS algorithm

Giselsson P (2017) Tight global linear convergence rate bounds for Douglas–Rachford splitting.Journal of Fixed Point Theory and Applications19(4):2241–2270. 16 Convergence rate of the DRS algorithm

2017
[12]

IEEE Transactions on Automatic Control62(2):532–544

Giselsson P, Boyd S (2016) Linear convergence and metric selection for Douglas-Rachford splitting and ADMM. IEEE Transactions on Automatic Control62(2):532–544

2016
[13]

Glowinski R, Osher SJ, Yin W (2017)Splitting methods in communication, imaging, science, and engineering (Springer)

2017
[14]

Goldstein T, O’Donoghue B, Setzer S, Baraniuk R (2014) Fast alternating direction optimization methods.SIAM Journal on Imaging Sciences7(3):1588–1623

2014
[15]

Grimmer B, Shu K, Wang AL (2025) Accelerated objective gap and gradient norm convergence for gradient descent via long steps.INFORMS Journal on Optimization7(2):156–169

2025
[16]

Karimi H, Nutini J, Schmidt M (2016) Linear convergence of gradient and proximal-gradient methods under the Polyak- Lojasiewicz condition.Joint European conference on machine learning and knowledge discovery in databases, 795–811 (Springer)

2016
[17]

Lieder F (2018)Projection based methods for conic linear programming—optimal first order complexities and norm constrained quasi newton methods. Ph.D. thesis, Dissertation, D¨ usseldorf, Heinrich-Heine-Universit ¨at, 2018

2018
[18]

Lions PL, Mercier B (1979) Splitting algorithms for the sum of two nonlinear operators.SIAM Journal on Numerical Analysis16(6):964–979

1979
[19]

SIAM Journal on Control and Optimization30(2):408–425

Luo ZQ, Tseng P (1992) On the linear convergence of descent methods for convex essentially smooth minimization. SIAM Journal on Control and Optimization30(2):408–425

1992
[20]

(2018)Lectures on convex optimization, volume 137 (Springer)

Nesterov Y, et al. (2018)Lectures on convex optimization, volume 137 (Springer)

2018
[21]

Patrinos P, Stella L, Bemporad A (2014) Douglas-Rachford splitting: Complexity estimates and accelerated variants.53rd IEEE Conference on Decision and Control, 4234–4239 (IEEE)

2014
[22]

Pe ˜na J, Vera JC, Zuluaga LF (2021) Linear convergence of the Douglas-Rachford algorithm via a generic error bound condition.arXiv preprint arXiv:2111.06071

2021 arXiv
[23]

Ryu EK, Taylor AB, Bergeling C, Giselsson P (2020) Operator splitting performance estimation: Tight contraction factors and optimal parameter selection.SIAM Journal on Optimization30(3):2251–2271

2020
[24]

Ryu EK, Yin W (2022)Large-scale convex optimization: algorithms & analyses via monotone operators(Cam- bridge University Press)

2022
[25]

Taylor A (2024)Towards principled and systematic approaches to the analysis and design of optimization algorithms. Ph.D. thesis, PSL Research University

2024
[26]

Taylor AB, Hendrickx JM, Glineur F (2017) Smooth strongly convex interpolation and exact worst-case perfor- mance of first-order methods.Mathematical Programming161(1):307–345

2017
[27]

Wang B, Ma S, Yang J, Zhou D (2024) Relaxed proximal point algorithm: Tight complexity bounds and acceleration without momentum.arXiv preprint arXiv:2410.08890. 17 A. Peivasti and Zamani

2024 arXiv
[28]

Zamani M, Abbaszadehpeivasti H, de Klerk E (2024) Convergence rate analysis of the gradient descent–ascent method for convex–concave saddle-point problems.Optimization Methods and Software39(5):967–989

2024
[29]

Zamani M, Abbaszadehpeivasti H, de Klerk E (2024) The exact worst-case convergence rate of the alternating direction method of multipliers.Mathematical Programming208(1):243–276

2024
[30]

Zamani M, Glineur F (2024) Exact convergence rate of the subgradient method by using Polyak step size.arXiv preprint arXiv:2407.15195. 18

2024 arXiv

Pith tools

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

[1] [1]

Abbaszadehpeivasti H (2024)Performance analysis of optimization methods for machine learning. Ph.D. thesis, Tilburg University

work page 2024

[2] [2]

Altschuler JM, Parrilo PA (2024) Acceleration by stepsize hedging: Silver stepsize schedule for smooth convex optimization.Mathematical Programming1–14

work page 2024

[3] [3]

Altschuler JM, Parrilo PA (2025) Acceleration by stepsize hedging: Multi-step descent and the silver stepsize schedule.Journal of the ACM72(2):1–38

work page 2025

[4] [4]

Aspelmeier T, Charitha C, Luke DR (2016) Local linear convergence of the ADMM/Douglas–Rachford algorithms without strong convexity and application to statistical imaging.SIAM Journal on Imaging Sciences9(2):842–868

work page 2016

[5] [5]

Bauschke HH, Combettes PL (2017)Convex Analysis and Monotone Operator Theory in Hilbert Spaces (Springer), 2nd edition

work page 2017

[6] [6]

Bok J, Altschuler JM (2025) Optimized methods for composite optimization: a reduction perspective.arXiv preprint arXiv:2506.23756

arXiv 2025

[7] [7]

Combettes PL (2018) Monotone operator theory in convex optimization.Mathematical Programming170(1):177– 206

work page 2018

[8] [8]

Douglas J, Rachford HH (1956) On the numerical solution of heat conduction problems in two and three space variables.Transactions of the American mathematical Society82(2):421–439

work page 1956