{"id":"c853e8df-a072-4799-a17f-d9058a2a117c","arxiv_id":"2506.07117","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A triple-Bregman balanced primal-dual algorithm for saddle point problems achieves O(1/N) ergodic convergence, allows larger step sizes than PDHG in a Euclidean setting, and has accelerated variants under strong convexity.","lead":"This paper introduces a primal-dual algorithm for convex-concave saddle point problems that adds three flexible Bregman distance terms and an extra dual update to balance the workload between primal and dual subproblems. If the convergence claims hold, it offers a general framework that can reproduce several classical methods while allowing larger step sizes than standard PDHG.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.2's proof of global convergence has an invalid 'lim a_k = 0' step; even where (3.29) holds, whole-sequence convergence is not established as written.","rationale":"The reader's weakest assumption focuses on condition (3.29) being unverified for general Bregman kernels, which is a real limitation. I agree that this matters, but I regard the invalid 'lim a_k = 0' step in the proof of Theorem 3.2 as the single more load-bearing issue, because it affects the global-convergence claim even in the Euclidean case where (3.29) is verified. The A=0 example shows that the proof's final inference is simply false under the stated hypotheses; the theorem may still be true, but the argument does not establish it. The fix appears available through standard Fejér-monotonicity/Bregman-continuity reasoning, and the O(1/N) ergodic bound and Euclidean step-size enlargement are not damaged. Since the gaps are identifiable and likely repairable rather than fatal, the CONDITIONAL verdict remains appropriate; hence I recommend no change to the reader's verdict.","tokens_in":28800,"tokens_out":21690,"duration_ms":206711,"concrete_test":"Instantiate Theorem 3.2 with A=0, X=Y=[0,1], f=g=0, Euclidean Bregman kernels, reference saddle point (x̂,ŷ)=(0,0), and starting point (x0,y0)=(0.5,0). All premises, including (3.29), are satisfied; the generated sequence is constant, the cluster point is a saddle point, but a_k is identically μ/4 > 0, contradicting the proof's 'lim a_k = 0' assertion. This isolates the invalid inference. Then check whether redefining a_k with the cluster point as the reference saddle point, together with explicit Bregman continuity/coercivity assumptions, yields a valid proof of whole-sequence convergence.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing problem is in the proof of Theorem 3.2, not merely in the abstractness of condition (3.29). After obtaining a cluster point (x∞,y∞) that is a saddle point, the proof asserts 'lim_k a_k = lim_j a_{k_j} = 0' from boundedness and monotonicity of a_k. This inference is invalid: a_k is nonincreasing and bounded below, so it can converge to a positive limit, and the fact that the cluster point is a saddle point does not force the Bregman distance to the originally fixed reference saddle point (x̂,ŷ) to tend to zero. A concrete witness is A=0, f=g=0, X=Y=[0,1], with Euclidean kernels and starting point x0≠x̂. Every point is a saddle point, inequality (3.29) holds vacuously with b_k=0, and the algorithm is constant, yet a_k = μBψ(x̂,x0) > 0. Thus the proof's asserted mechanism for deducing whole-sequence convergence is false as stated. A standard repair would re-apply the descent inequality at the cluster point and invoke Bregman continuity and coercivity, but those hypotheses are absent from the paper. The ergodic O(1/N) rate in Theorem 3.4 is independent of this step and appears sound; however, the first half of the central claim, global convergence, is not proven by the argument supplied.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes TBDA, a primal-dual algorithm for convex-concave saddle point problems with a bilinear coupling term. The method performs two dual Bregman proximal updates and one primal Bregman proximal update, with an extrapolation step, in order to balance primal and dual subproblem costs. The authors derive a basic descent inequality (Lemma 3.1), claim global convergence (Theorem 3.2) and an ergodic O(1/N) rate (Theorem 3.4), give a Euclidean-kernel step-size verification (Remark 3.3), and propose two accelerated variants under relative strong convexity (Algorithms 2 and 3). Numerical experiments on quadratic optimization and RPCA compare the method with PDHG and SPIDA.","tokens_in":29099,"tokens_out":12034,"duration_ms":129557,"significance":"If the theoretical claims were fully established, the paper would be a useful contribution. The algorithmic framework is flexible and several existing schemes, including ALM, linearized ALM, balanced ALM, and SPIDA, are recovered as special cases. The ergodic-rate argument in Theorem 3.4 is clean and does not depend on the additional descent inequality (3.29); that part of the paper is a genuine strength. The Euclidean verification in Remark 3.3 is also a useful concrete check. However, the global-convergence proof in Theorem 3.2 currently contains an invalid limit argument, and the step-size comparison with PDHG is overstated as written. These issues are repairable but currently block the advertised central claim.","major_comments":[{"comment":"The inference \"Using the boundedness and monotonically decreasing property of the sequence {a_k} implies lim_{k→∞} a_k = lim_{j→∞} a_{k_j}=0\" is invalid. Monotonicity and boundedness only give convergence of a_k to some nonnegative limit; the fact that a cluster point is a saddle point does not force the Bregman distance to the initially fixed reference saddle point (x̂, ŷ) to tend to zero. A concrete witness is A=0, f=g=0, X=Y=[0,1], Euclidean kernels, and x0≠x̂: every point is a saddle point, inequality (3.29) holds with zero left- and right-hand sides, the algorithm is constant, and a_k = μBψ(x̂,x0)>0. Therefore the proof does not establish whole-sequence convergence. A repair would need to re-apply the descent inequality at a cluster point and invoke additional coercivity and continuity properties of the Bregman kernels, which are not stated.","section":"Theorem 3.2, proof paragraph after (3.32)"},{"comment":"The global-convergence result is conditional on the existence of positive constants c1,c2,c3 satisfying (3.29), but this inequality is not derived from primitive conditions for general Bregman kernels. Remark 3.3 verifies (3.29) only in the Euclidean case. The same type of unproven sufficient condition is assumed in Theorem 4.1 and Theorem 4.3. The phrase \"under some mild conditions\" therefore overstates the support for the general Bregman setting. The paper should state (3.29) as a standing hypothesis with guidance on how to check it, or provide verifiable sufficient conditions on the kernels and step sizes from which (3.29) follows.","section":"Assumption (3.29), Theorems 3.2, 4.1, 4.3"},{"comment":"The claimed comparison with PDHG is not correct as stated. For the Euclidean case with τ=θγ and σ≥0, the condition for 1≤θ<2 is μγ > 2(1+σ)^2/((θ+1)(1+2σ)) ‖A^T A‖. At θ=1 and σ=1 this is μγ > 4/3 ‖A^T A‖, which is stricter than the PDHG condition μγ>‖A^T A‖ in (1.5), not larger. The displayed bound \"> 2/3 ‖A^T A‖\" only gives a lower bound and does not imply a comparison with the coefficient 1 appearing in PDHG. The statement that TBDA allows larger step sizes than PDHG when θ≥1 must be restricted to parameter regimes where the coefficient is actually below 1, and the comparison should account for the extrapolation parameter used in each method.","section":"Remark 3.3, Eq. (3.42)"}],"minor_comments":[{"comment":"The phrase \"globally convergence\" should be \"globally convergent\".","section":"Introduction, page 3"},{"comment":"\"Jesen inequality\" should be \"Jensen inequality\".","section":"Proof of Theorem 3.4"},{"comment":"\"easily seen form (3.42)\" should be \"easily seen from (3.42)\".","section":"Remark 3.3, final sentence"},{"comment":"The displayed identity \"t_N = Σ_{k=1}^N 1/β_{k+1}\" is inconsistent with the definition t_N = Σ_{k=1}^N 1/β_{k-1} in Theorem 4.1; the index should be corrected.","section":"Remark 4.2"},{"comment":"Algorithm 1 labels the output \"approximate saddle point (x̂, ŷ)\", which collides with the fixed saddle point (x̂, ŷ) used throughout the convergence analysis; a different notation for the output would avoid confusion.","section":"Algorithm 1 and convergence analysis"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the manuscript has a sound ergodic-rate core and a flexible algorithmic framework, but the global-convergence proof in Theorem 3.2 contains a genuine logical gap and the PDHG comparison in Remark 3.3 is overstated. I recommend major revision rather than rejection because the flaws appear repairable within the paper's scope: clarify the standing assumptions, repair the limit argument in Theorem 3.2, and correct the step-size comparison."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: TBDA is a legitimate new template—two dual updates with three independent Bregman kernels plus an extrapolation step—and the Euclidean step-size calculation in Remark 3.3 is correct enough to support the larger-step claim. The O(1/N) ergodic rate in Theorem 3.4 follows directly from Lemma 3.1 and does not depend on the shaky part.\n\nThe shaky part is Theorem 3.2. The proof assumes inequality (3.29) without deriving it for general kernels, and then uses an invalid inference: from a cluster point being a saddle point and a_k monotone bounded, it claims lim a_k = 0. A monotone bounded sequence can converge to a positive limit. The stress-test counterexample makes this concrete: with A=0, f=g=0, X=Y=[0,1], every point is a saddle point, (3.29) holds trivially, and the algorithm is constant, yet a_k stays at a positive Bregman distance to the chosen reference point. So whole-sequence convergence is not established even assuming (3.29). The likely fix is to re-run the descent inequality at the cluster point and add coercivity or continuity hypotheses, but those are absent. This is a load-bearing gap affecting the first half of the central claim, not the ergodic rate.\n\nAlso minor: in Algorithm 2, the update beta_{k+1} = min{ mu beta_k/(mu+rho_1), 1/p } is inconsistent with the remark that 1/beta_{k+1} = ((mu+rho_1)/mu)(1/beta_k); the reciprocal of a min is a max. The numerical section is suggestive but thin: only PDHG and SPIDA baselines, limited variance reporting, and in the real-video experiments TBDA reaches lower objective values but worse relative fit error, which is not discussed.\n\nIf I were refereeing, I would ask for a repaired Theorem 3.2 or a clearly conditional statement, a fix to the beta update, and broader numerics. The core idea is sound, the framework is likely useful, and the ergodic rate plus Euclidean verification are real content. This deserves a serious referee, not a desk reject. I would not cite it myself until the convergence gap is closed.","headline":"A genuinely useful algorithmic template with a clean ergodic rate, but the global convergence proof relies on an unproven inequality and contains a real gap that needs repair.","tokens_in":29644,"tokens_out":3121,"would_cite":false,"duration_ms":33265,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65K05","65K10","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"A new primal-dual algorithm for convex-concave saddle point problems splits the dual update into two Bregman subproblems, allowing larger step sizes than PDHG while retaining an O(1/N) ergodic convergence rate.","keywords":["primal-dual algorithm","saddle point problem","Bregman distance","Bregman proximity operator","convex-concave optimization","PDHG","larger step sizes","ergodic convergence rate"],"falsifier":"Take a non-Euclidean Bregman kernel, for example the Kullback-Leibler Bregman distance on the probability simplex, and choose positive step sizes that satisfy the paper's stated convergence conditions but lie outside the Euclidean-verified region; if inequality (3.29) cannot be certified for that kernel, then the global-convergence theorem has no content for that setting. A concrete check is to run TBDA with step sizes in the claimed enlarged range $\\frac{2}{3}\\|A^\\top A\\| < \\mu\\gamma < \\|A^\\top A\\|$ on a small saddle point problem and see whether the iterates actually converge; convergence would support the step-size claim, divergence or oscillation would refute it.","tokens_in":28541,"feed_emoji":"⚖️","tokens_out":9168,"duration_ms":86609,"temperature":0.7,"pith_summary":"The paper proposes an algorithm for convex-concave saddle point problems with a bilinear coupling term, aimed at situations where the dual subproblem is much cheaper than the primal one. Instead of the standard PDHG pattern of one primal update followed by one dual update, TBDA performs a preliminary dual step, then a primal step, then a second dual step, with a separate Bregman proximal term in each subproblem. The authors claim that this rebalancing preserves global convergence and the standard $O(1/N)$ ergodic convergence rate while allowing strictly larger step sizes: under Euclidean kernels with $\\tau = \\theta\\gamma$ and $\\theta\\ge 1$, convergence is guaranteed when $\\mu\\gamma > \\frac{2}{3}\\|A^\\top A\\|$, weaker than PDHG's $\\mu\\gamma > \\|A^\\top A\\|$. Two strengthened versions are shown to give a better $O(1/N)$ rate when $f$ is relatively strongly convex, and an $O(1/\\omega^N)$ linear rate when both $f$ and $g$ are relatively strongly convex. Numerical experiments on quadratic programs and robust PCA support the claim that the extra dual pass pays off in practice.","feed_headline":"Two-pass dual update lets primal-dual solver take larger steps","feed_subtitle":"New algorithm keeps O(1/N) convergence while cutting PDHG's step-size restriction by a third.","key_machinery":"The central object is Algorithm 1 (TBDA), whose updates are $\\tilde y^{k+1}=\\arg\\min_y\\{g(y)-\\langle Ax^k,y\\rangle+\\gamma B_\\phi(y,y^k)\\}$, $x^{k+1}=\\arg\\min_x\\{f(x)+\\langle Ax,\\tilde y^{k+1}\\rangle+\\mu B_\\psi(x,x^k)\\}$, followed by the extrapolation $\\bar x^{k+1}=x^{k+1}+\\sigma(x^{k+1}-x^k)$ and a second dual update $y^{k+1}=\\arg\\min_y\\{g(y)-\\langle A\\bar x^{k+1},y\\rangle+\\tau B_\\varphi(y,y^k)\\}$. Each update uses its own Bregman distance $B_h(x,y)=h(x)-h(y)-\\langle\\nabla h(y),x-y\\rangle$, which generalizes the Euclidean proximal term and lets the user move computational effort between the primal and dual sides. The load-bearing part of the proof is the descent inequality of Lemma 3.1, which expresses the decrease of the weighted sum of Bregman distances to a saddle point in terms of three successive Bregman terms and the cross term $\\langle A(x^{k+1}-x^k), y^{k+1}-\\tilde y^{k+1}\\rangle$. Theorem 3.2 turns this into global convergence whenever the sufficient condition (3.29) holds with positive constants $c_1,c_2,c_3$, and Theorem 3.4 sums the same inequality and applies Jensen's inequality to obtain the ergodic $O(1/N)$ rate. The larger-step conclusion is obtained in Remark 3.3 by verifying (3.29) for Euclidean kernels through Cauchy-Schwarz and Young's inequalities, which yields the explicit conditions in (3.42).","core_discovery":"On its own terms, the paper's central claim is that a primal-dual algorithm can be rebalanced by computing the dual variable twice, once as a predictor for the primal update and once after an extrapolation step, with independent Bregman kernels for the two dual subproblems and the primal subproblem. This triple-Bregman balanced primal-dual algorithm is globally convergent for convex-concave saddle point problems of the form $\\min_x \\max_y \\{f(x)+\\langle Ax,y\\rangle - g(y)\\}$, and its iterates satisfy the ergodic bound $G(\\bar x^N,\\bar y^N)=O(1/N)$. In the Euclidean specialization the paper proves a strictly weaker step-size condition, $\\mu\\gamma > \\frac{2}{3}\\|A^\\top A\\|$ when $\\tau=\\theta\\gamma$ and $\\theta\\ge 1$, compared with the classical PDHG condition $\\mu\\gamma > \\|A^\\top A\\|$, and it exhibits variants with improved rates under relative strong convexity: an $O(1/N)$ bound with better constants and a linear $O(1/\\omega^N)$ bound. The convergence argument rests on a descent inequality, Lemma 3.1, combined with the sufficient condition (3.29) that three positive constants control the Bregman terms and the coupling cross term; Theorem 3.2 turns that inequality into global convergence and Theorem 3.4 into the ergodic rate. The framework is also shown to specialize to several existing methods, including ALM, linearized and balanced ALM, SPIDA, and multi-block splitting schemes.","pith_inferences":["Inference: the two-dual-pass construction suggests a general 'rebalance the cheap side' template: any primal-dual method whose dual update is a cheap projection can spend an extra dual solve as a predictor, so the same idea could be transplanted to stochastic or online variants of PDHG.","Inference: the coefficient $2/3$ in the Euclidean step-size bound is suggestive: the extremal case $\\theta\\ge 2$ in (3.41) is exactly where the constant becomes $2/3$, so it would be natural to test whether a golden-ratio choice of the extrapolation parameter $\\sigma$ produces the same or a sharper bound.","Inference: because inequality (3.29) is verified only for Euclidean kernels, a direct extension of the paper would be to certify it for entropy-type Bregman kernels; if it holds, TBDA would apply cleanly to problems such as optimal transport where the subproblems then have closed-form updates."],"forward_implications":["For problems whose dual subproblem is much cheaper than the primal one, the extra dual solve is nearly free, so TBDA can be faster in wall-clock time than PDHG while keeping the same $O(1/N)$ worst-case guarantee.","Under Euclidean kernels with $\\tau=\\theta\\gamma$ and $\\theta\\ge 1$, TBDA converges under the weaker step-size condition $\\mu\\gamma > \\frac{2}{3}\\|A^\\top A\\|$, so users may take larger steps than PDHG's $\\mu\\gamma > \\|A^\\top A\\|$.","The three independent Bregman kernels give users freedom to match each subproblem to the geometry of $X$ and $Y$; the framework reproduces ALM, linearized ALM, balanced ALM, SPIDA, and multi-block splitting methods as special cases.","When $f$ is strongly convex relative to $\\psi$, Algorithm 2 keeps $O(1/N)$ with a tighter bound, and when both $f$ and $g$ are relatively strongly convex, Algorithm 3 achieves a linear $O(1/\\omega^N)$ rate."],"supporting_citations":[{"why":"introduces the PDHG method and the classical convergence condition $\\mu\\gamma>\\|A^\\top A\\|$ that TBDA extends and compares against.","marker":"[14]"},{"why":"proposes the symmetric primal-dual algorithm SPIDA, whose dual-computed-twice structure TBDA builds on.","marker":"[33]"},{"why":"introduces the balancing strategy for ALM, recovered as a special case of TBDA for linearly constrained problems.","marker":"[32]"},{"why":"supplies the alternating-extragradient prediction idea used to form the first dual update in TBDA.","marker":"[8]"},{"why":"extends the extragradient idea to non-Euclidean projections, motivating the Bregman proximal terms.","marker":"[10]"},{"why":"provides the nonconvergence example for Arrow-Hurwicz used in the toy comparison of Figure 1.","marker":"[29]"},{"why":"gives generalized PDHG methods with improved convergence conditions against which TBDA shows a larger step-size range.","marker":"[26]"},{"why":"defines strong convexity relative to a Bregman kernel, the assumption behind Algorithms 2 and 3.","marker":"[41]"}],"fun_headline_variants":["Triple-Bregman primal-dual solver takes bigger steps","Two-pass dual update relaxes PDHG step-size bound","Rebalanced PDHG-style algorithm with larger step sizes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that one can actually find positive constants $c_1,c_2,c_3$ making inequality (3.29) hold for the chosen Bregman kernels and step sizes; the paper verifies this directly only for Euclidean kernels (Remark 3.3), so for a general Bregman kernel the global-convergence theorem is conditional on an unverified inequality.","fun_headline_variants_meta":{"raw":{"variants":["Triple-Bregman primal-dual solver takes bigger steps","Two-pass dual update relaxes PDHG step-size bound","Rebalanced PDHG-style algorithm with larger step sizes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000713,"raw_usage":{"total_tokens":3317,"prompt_tokens":1166,"completion_tokens":2151,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":782,"completion_tokens_details":{"reasoning_tokens":2097}},"tokens_in":782,"tokens_out":2151,"duration_ms":17688,"temperature":1.0,"reasoning_tokens":2097,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:42:31.702700+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a non-Euclidean Bregman kernel, for example the Kullback-Leibler Bregman distance on the probability simplex, and choose positive step sizes that satisfy the paper's stated convergence conditions but lie outside the Euclidean-verified region; if inequality (3.29) cannot be certified for that kernel, then the global-convergence theorem has no content for that setting. A concrete check is to run TBDA with step sizes in the claimed enlarged range $\\frac{2}{3}\\|A^\\top A\\| < \\mu\\gamma < \\|A^\\top A\\|$ on a small saddle point problem and see whether the iterates actually converge; convergence would support the step-size claim, divergence or oscillation would refute it.","supporting_citations":[{"cited_title":"Chambolle and T","cited_arxiv_id":null,"evidence_quote":"introduces the PDHG method and the classical convergence condition $\\mu\\gamma>\\|A^\\top A\\|$ that TBDA extends and compares against."},{"cited_title":"A symmetric primal-dual algorithmic framework for saddle point problems","cited_arxiv_id":"2212.07587","evidence_quote":"proposes the symmetric primal-dual algorithm SPIDA, whose dual-computed-twice structure TBDA builds on."},{"cited_title":"Balanced Augmented Lagrangian Method for Convex Programming","cited_arxiv_id":"2108.08554","evidence_quote":"introduces the balancing strategy for ALM, recovered as a special case of TBDA for linearly constrained problems."},{"cited_title":"Bonettini and V","cited_arxiv_id":null,"evidence_quote":"supplies the alternating-extragradient prediction idea used to form the first dual update in TBDA."},{"cited_title":"Bonettini and V","cited_arxiv_id":null,"evidence_quote":"extends the extragradient idea to non-Euclidean projections, motivating the Bregman proximal terms."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the nonconvergence example for Arrow-Hurwicz used in the toy comparison of Figure 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives generalized PDHG methods with improved convergence conditions against which TBDA shows a larger step-size range."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defines strong convexity relative to a Bregman kernel, the assumption behind Algorithms 2 and 3."}],"review_version":1}