{"id":"2495a758-aaa3-402f-a65d-e42fb8e09694","arxiv_id":"2509.06676","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The Douglas-Rachford splitting method has worst-case residual rate ((N-1)^(N-1))/N^N for relaxation 1, and a two-subspace feasibility example attains it.","lead":"This paper derives an exact sublinear convergence rate for the Douglas-Rachford splitting algorithm and shows it is tight for convex feasibility problems. It also gives linear convergence conditions and several unproved conjectures for composite optimization.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the exact λ=1 rate bound and its sharpness construction are sound; secondary gaps do not affect the central claim.","rationale":"The paper's headline claim—an exact O(1/N) residual bound for DRS at λ=1 and a matching lower bound for convex feasibility—is well supported. Theorem 1's proof, though terse, is a valid performance-estimation certificate: the two inequalities are nonexpansivity applied to consecutive iterates and to the fixed point, and the lengthy identity is a telescoping sum with nonnegative multipliers, the output being a sum of squares plus the desired upper bound. I spot-checked N=2 and the identity is exact. Theorem 2's construction uses normal cones to two lines with angle arcsin(1/√N); the DR operator is c times a rotation by θ, yielding the stated residual after N steps; the numerics are consistent. The secondary issues the reader flags—unproved sign conditions D,E,P2≥0 in Proposition 2 and the one-line proof of Theorem 4—are real gaps in supporting results, but they do not bear on the central rate theorem. Therefore the appropriate verdict remains CONDITIONAL as the reader set, pending repair of those secondary derivations; the central claim itself is not endangered.","tokens_in":13616,"tokens_out":30070,"duration_ms":300067,"concrete_test":"Use exact arithmetic to verify the identity in Theorem 1 for N=2,...,10, and simulate the two-subspace example of Theorem 2 for N=2,...,10 by projecting onto P and Q in R^2 to confirm the residual equals (N-1)^{N-1}/N^N. This directly checks the central claim without relying on secondary sections.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—the O(1/N) residual bound for DRS with λ=1 and its sharpness—is well supported. Theorem 1 is a telescoping sum-of-squares certificate: the two displayed inequalities are immediate from nonexpansivity, and the stated identity uses nonnegative multipliers and yields the desired bound. I spot-checked N=2 and the identity is exact. Theorem 2 constructs two subspaces in R^2 whose normal cones yield a DR operator that is a scaled rotation by θ=arcsin(1/√N); the norms of w_N and w_{N+1} and the angle between them give exactly ||w_{N+1}-w_N||^2 = (N-1)^{N-1}/N^N. The reader's flagged concern about Proposition 2's unproved polynomial inequalities (D,E,P2≥0) is legitimate, but it concerns a supporting sufficient condition for linear convergence, not the main rate theorem. No load-bearing objection to the central claim.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":13895,"tokens_out":4154,"duration_ms":41584,"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":[{"comment":"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":"Section 4, Proposition 2"},{"comment":"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":"Section 5.1, Theorem 4"},{"comment":"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.","section":"Section 4, Theorem 3"}],"minor_comments":[{"comment":"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":"Section 3, Eq. (3)"},{"comment":"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":"Section 3, Theorem 1 proof"},{"comment":"The footnote \"Owing to external constraints...\" is informal and not appropriate for a research paper. Consider removing or rewording it.","section":"Section 5, footnote 1"},{"comment":"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.","section":"Section 4, Proposition 2"}],"recommendation":"major_revision","confidential_remarks":"The central sublinear-rate result (Theorems 1–2) appears sound and well-presented. The main concern is Proposition 2, whose proof relies on an unproved nonnegativity claim and a possible modulus inconsistency; this is a load-bearing gap for the paper's linear-convergence characterization. Theorem 4 also needs a complete proof or demotion. These are fixable within the manuscript's scope, hence major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nOne 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.\n\nWho 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.","headline":"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.","tokens_in":14311,"tokens_out":608,"would_cite":true,"duration_ms":9287,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["47H05","65K10","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Douglas-Rachford splitting","monotone inclusion","convergence rate","convex feasibility","error bound condition","linear convergence","silver stepsize schedule","performance estimation"],"falsifier":"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.","tokens_in":13533,"feed_emoji":"🔄","tokens_out":11312,"duration_ms":119488,"temperature":0.7,"pith_summary":"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.","feed_headline":"Douglas-Rachford worst-case rate is exactly ((N-1)^{N-1}/N^N)","feed_subtitle":"A two-subspace construction attains the bound, and an error-bound test tells when DRS converges linearly.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the monotone operator, resolvent, and reflected-resolvent theory used throughout, and the fixed-point convergence guarantee behind Assumption 1.","marker":"[5]"},{"why":"Introduces the performance-estimation proof technique that the paper uses to derive the exact convergence-rate inequality.","marker":"[9]"},{"why":"States the earlier bound (3) for relaxation parameters in a range; Theorem 1 reproves the λ=1 case with a self-contained argument.","marker":"[17]"},{"why":"Provides the DRS representation as an averaged operator and the nonexpansivity of the reflected-resolvent product used to apply Theorem 1.","marker":"[24]"},{"why":"Introduces the error-bound condition and the prior linear-convergence result that Theorem 3 and Proposition 1 extend to all stepsizes and relaxation parameters.","marker":"[22]"},{"why":"Defines the silver stepsize schedule and gives the gradient-descent bound that Lemma 1 and Theorem 4 refine.","marker":"[2]"},{"why":"Supplies the exact ADMM convergence rate that Conjecture 2's λ=1 case is said to match, anchoring the conjecture's comparison.","marker":"[29]"},{"why":"Provides the accelerated DRS template that Algorithm 3 modifies by changing the momentum coefficient.","marker":"[21]"}],"fun_headline_variants":["Exact Douglas-Rachford rate: ((N-1)^(N-1)/N^N)","Sharp DRS bound via two-subspace construction","Linear convergence of DRS equals an error-bound test","DRS converges linearly iff error bound holds"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Exact Douglas-Rachford rate: ((N-1)^(N-1)/N^N)","Sharp DRS bound via two-subspace construction","Linear convergence of DRS equals an error-bound test","DRS converges linearly iff error bound holds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000254,"raw_usage":{"total_tokens":1380,"prompt_tokens":692,"completion_tokens":688,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":436,"completion_tokens_details":{"reasoning_tokens":617}},"tokens_in":436,"tokens_out":688,"duration_ms":7964,"temperature":1.0,"reasoning_tokens":617,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T23:16:47.897407+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the monotone operator, resolvent, and reflected-resolvent theory used throughout, and the fixed-point convergence guarantee behind Assumption 1."},{"cited_title":"Mathematical Programming145(1):451–482","cited_arxiv_id":null,"evidence_quote":"Introduces the performance-estimation proof technique that the paper uses to derive the exact convergence-rate inequality."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the earlier bound (3) for relaxation parameters in a range; Theorem 1 reproves the λ=1 case with a self-contained argument."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the DRS representation as an averaged operator and the nonexpansivity of the reflected-resolvent product used to apply Theorem 1."},{"cited_title":"Linear convergence of the Douglas-Rachford algorithm via a generic error bound condition","cited_arxiv_id":"2111.06071","evidence_quote":"Introduces the error-bound condition and the prior linear-convergence result that Theorem 3 and Proposition 1 extend to all stepsizes and relaxation parameters."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the silver stepsize schedule and gives the gradient-descent bound that Lemma 1 and Theorem 4 refine."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the exact ADMM convergence rate that Conjecture 2's λ=1 case is said to match, anchoring the conjecture's comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the accelerated DRS template that Algorithm 3 modifies by changing the momentum coefficient."}],"review_version":1}