{"id":"a7331a00-b03a-4296-a15b-0b314d7cfda2","arxiv_id":"2505.13927","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"CABRA is a matrix-parametrized resolvent splitting algorithm for monotone inclusions with linear coupling, with SDP-based parameter selection and weak convergence guarantees.","lead":"This paper introduces CABRA, a new algorithm for solving optimization problems where a sum of operators acts on overlapping subsets of variables. It lets users tune the algorithm via a semidefinite program to enable parallel or decentralized execution, and tests show faster convergence than the prior method it extends.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"CABRA's convergence requires operator ordering condition (13); Example 5.1 shows it can fail, so the abstract's unqualified applicability claim is too broad.","rationale":"The reader identified the same load-bearing concern: condition (13) is the structural assumption that makes the algorithm executable and provably convergent. I agree that this is the weakest point. The proof of Lemma 7 explicitly relies on the existence of i*_j, and Lemma 3 and Theorem 1 inherit that dependence. The paper is honest about the failure mode in Example 5.1, but the abstract's wording ('finds the zero of a sum ... composed with linear selection operators') is unconditional. A conditional theorem is not a false theorem, so I do not propose rejecting the paper; the appropriate verdict is unchanged (CONDITIONAL). Secondary issues (α=10 outside the proven range in Section 5.3, absence of code/data, minor typos) do not affect the core convergence argument. The concrete test would settle the scope question by exhibiting an instance in the claimed problem class where (13) fails and the forward substitution cannot be performed. If the authors add an explicit characterization or a preprocessing/ordering strategy, the scope concern would be resolved.","tokens_in":29430,"tokens_out":27095,"duration_ms":238465,"concrete_test":"Implement the Example 5.1 operator sets but take a single cocoercive operator B_1 with K^B_1 = {1,3}. Compute \\bar{i}_1 = max(first user of y1, first user of y3) = 3 and i\\bar{_1} = min(last user of y1, last user of y3) = 2, so (13) is violated. Using the same A_i and linear forms, attempt to execute Algorithm 2's forward substitution (5); verify that the equation for the block of the last operator using y_3 (operator 2) contains an unresolved output of B_1 that depends on a later block, so no sequential solve exists. This demonstrates a problem in the claimed class for which CABRA is undefined, confirming the ordering condition is load-bearing.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim in the abstract is that CABRA finds a zero of (1) for sums of maximal monotone and cocoercive operators composed with linear selection operators. The proof of Theorem 1 and the well-definedness of Algorithm 2 both depend on the operator ordering assumption (13): for every cocoercive B_j, the earliest operator index supplying all of B_j's inputs must be strictly smaller than the latest operator index needing B_j's output. Only under (13) does a cutoff i*_j exist, and only then do the sparsity constraints (14) make LA and Q_A B K_A strictly block lower triangular (Lemmas 6-7), so that the forward substitution (5) solves the implicit resolvent equation. If (13) fails, no i*_j exists, (14) is vacuous, Q_A B K_A is generally not block lower triangular, and the algorithm's step (4) cannot be evaluated sequentially; the convergence proof has no basis. This is not a purely technical edge case: Example 5.1 exhibits a concrete selection structure (K^B = {1,3}) where \\bar{i}_1 = 3 > 2 = i\\bar{_1}, and the authors' only remedy is to enlarge operator domains, i.e., change the problem. The abstract and introduction do not state this caveat, so the proven scope is materially narrower than the claimed scope.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces CABRA, a matrix-parametrized resolvent splitting algorithm for finding a zero of a sum of maximal monotone operators and cocoercive operators composed with linear selection operators. The algorithm assigns to each subvector a lifted copy per operator and uses matrix parameters satisfying (11) and (14) to make the implicit step (4) solvable by forward substitution. Under an ordering condition on the coupling structure, the paper proves weak convergence of the z- and x-iterates when a solution exists (Theorem 1), and it develops an SDP framework (38) for choosing parameters that promote parallel execution, diagonal scaling, and prescribed communication structure. Numerical experiments cover diagonal scaling for halfspace projections and quadratic operators, a comparison against the uncoupled Algorithm 1, and an application to a relaxed multi-stage stochastic weapon target assignment problem.","tokens_in":29669,"tokens_out":10868,"duration_ms":98890,"significance":"If the stated scope is made precise, this is a useful contribution to the frugal resolvent splitting literature. The paper extends the matrix-parametrized forward-backward framework to coupled inclusions with selection operators, gives a clean SDP design space for parallelism, scaling, and communication constraints, and supports the theory with a detailed and mostly self-contained convergence proof. The stochastic weapon target assignment application is concrete and relevant. The main caveats are that the abstract and introduction currently overstate the applicability of the algorithm by omitting the ordering hypothesis (13), which is genuinely load-bearing, and that one of the numerical demonstrations runs the algorithm with parameters outside the proven range. These issues are repairable within the manuscript's scope.","major_comments":[{"comment":"The abstract and introduction claim CABRA solves problem (1) without qualification, but the well-definedness of the iteration and the convergence proof both rely on the ordering assumption \\bar{i}_j < i\\bar{}_j for every cocoercive operator B_j. If this condition fails, no cutoff index i*_j exists, the sparsity constraints (14) are vacuous, and Q_A B K_A is generally not strictly block lower triangular, so step (3) of Algorithm 2 cannot be evaluated by the stated forward substitution and Theorem 1 does not apply. The paper itself acknowledges this in Example 5.1, where the selection pattern for a cocoercive operator fails the condition and must be modified. Please state condition (13) explicitly as a hypothesis in the abstract, introduction, and Theorem 1, and note that CABRA applies to couplings that admit such an ordering.","section":"Section 3.1, Eq. (13); Algorithm 2; Theorem 1"},{"comment":"The numerical experiment for the stochastic weapon target assignment problem uses alpha = 10 and gamma = 1, and the text explicitly states that alpha = 10 is beyond the proven set of valid parameters. Lemma 3 and Theorem 1 require alpha in (0,4), and for alpha = 10 the quantity 2 - alpha/2 is negative, so the convergence guarantee does not cover the runs plotted in Figure 6. As a result, the comparison with Algorithm 1 is not supported by the paper's theory as written. Please either rerun the experiment with alpha in (0,4) or clearly label this experiment as heuristic, separate from the validated claims.","section":"Section 5.3, WTA experiment"}],"minor_comments":[{"comment":"The text says the uniform matrices are generated as described in 'Example 40', but no Example 40 exists in the manuscript; please provide the correct reference or re-label this item.","section":"Section 5.2.3"},{"comment":"The text states m_k = |S_bt| + 1 for the number of cocoercive derivative operators, but the displayed K_tb is in R^{|S_bt| x (1+|S_bt|)}, which requires m_k = |S_bt|. This is presumably a typo and should be corrected, since it affects verification of conditions (11e) and (11f).","section":"Section 5.3"},{"comment":"The notation 'K^B = {1,3}' is undefined and confusing; the intended set appears to be the selection pattern for a cocoercive operator, and it should be written consistently with the definitions of K_i^B.","section":"Section 5.1"},{"comment":"Table 1 has a typo ('T able 1'), and the figure labels contain raw /uni... escape sequences, suggesting a font-embedding problem that should be fixed before publication.","section":"Table 1 and Figure 1"},{"comment":"The word 'selectin' in the opening sentence should be 'selection'.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"The core algorithm and proofs are sound, but the abstract's unqualified claim is broader than the proven scope, and the alpha = 10 experiment is outside the theoretical regime. Both are fixable in a revision; I would not reject the paper on these grounds."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on arXiv:2505.13927. The paper delivers what it says in the body: a matrix-parametrized frugal splitting (CABRA) for sums of maximal monotone and cocoercive operators composed with selection operators, plus an SDP framework for choosing the matrix parameters. The generalization of the forward-backward splitting in Akerman et al. and Dao et al. to linear selection operators is real and useful, and the convergence proof is the strongest part. I checked the algebra in Lemmas 2 and 3; the nonexpansivity proof and the fixed-point correspondence are clean. The forward substitution argument leveraging strict block lower triangularity is well explained. The SDP parameter selection with communication constraints is a genuine addition.\n\nThe soft spots are proportionate. First, the abstract overstates the scope. The convergence theorem requires condition (13) on the ordering of the selection structure—that for every cocoercive operator the earliest index that supplies all its inputs is strictly before the latest index that needs its output. Without that, no cutoff exists, the sparsity constraints (14) are vacuous, and the forward substitution is not well-defined. Example 5.1 even shows a concrete failure. This is not a flaw in the theorem—the theorem is honestly stated—but the abstract and introduction don't mention it, so the proven scope is narrower than claimed. The authors should either add the caveat or prove a variant that handles cycles.\n\nSecond, the WTA experiment runs with alpha=10, outside the proven range (0,4). The authors admit it, and it may be fine as a heuristic, but it should not be the headline evidence for acceleration. I'd want to see the experiment rerun within the proven range or clearly labeled as empirical and outside the theoretical guarantee. Also, no code or data are provided, and there are minor typos (the 'Example 40' reference, the WTA matrix definitions). Those are fixable.\n\nOverall, the math is solid, the contribution is modest but real, and the paper deserves a serious referee. It should be sent to review, with a request to fix the abstract and either justify or flag the alpha=10 experiment.","headline":"Solid incremental algorithm paper; convergence proof is careful, but abstract overclaims without condition (13) and the headline experiment runs outside the proven parameter range.","tokens_in":30230,"tokens_out":3219,"would_cite":true,"duration_ms":30157,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["47H05","47J25","65K10","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"CABRA provably splits sums of monotone and cocoercive operators with linear couplings into resolvents solvable by forward substitution, with an SDP framework for choosing the splitting matrices.","keywords":["resolvent splitting","maximal monotone operators","cocoercive operators","linear coupling operators","minimal lifting","semidefinite programming","decentralized optimization","stochastic programming"],"falsifier":"Construct a problem with $K^A_1=\\{1\\}$, $K^A_2=\\{1,2\\}$, and $K^B_1=\\{1,2\\}$, so that $\\bar{i}_1 = i_{\\bar{1}} = 2$ and condition (13) fails. Implementing Algorithm 2 with any feasible matrices, the forward substitution (5) will need $x_2$ to compute the $B_1$ term in the first resolvent, so either the iterate is undefined or the algorithm diverges. A direct check that Lemma 7's conclusion fails—that $Q_A B K_A$ is not strictly lower triangular—would settle that the ordering condition is necessary for the stated guarantees.","tokens_in":29183,"feed_emoji":"🧮","tokens_out":6938,"duration_ms":62292,"temperature":0.7,"pith_summary":"This paper develops CABRA, a resolvent splitting algorithm for solving inclusions of the form $0\\in \\sum_i (R_i^A)^* A_i R_i^A y + \\sum_j (R_j^B)^* B_j R_j^B y$, where each $A_i$ is maximal monotone, each $B_j$ is cocoercive, and the $R_i^A, R_j^B$ are linear selection operators that couple the unknown $y$ to the operators. The central claim is that, under an ordering condition on the coupling pattern, the algorithm converges weakly to a solution and can be implemented by forward substitution over the individual resolvents, evaluating each operator once per iteration. The paper also provides a semidefinite programming framework for choosing the matrix parameters that shape the splitting, enabling decentralized execution, diagonal scaling, and prescribed communication patterns. A sympathetic reader should care because this turns the choice of splitting parameters into a design decision that can accelerate convergence and reduce memory and communication, not just a proof device. The paper demonstrates the acceleration numerically and applies the method to a multi-stage stochastic weapon target assignment problem.","feed_headline":"CABRA provably splits coupled monotone inclusions","feed_subtitle":"Matrix parameters are chosen by SDP to give decentralized execution and diagonal scaling, accelerating convergence.","key_machinery":"The load-bearing machinery is a per-subvector set of matrix parameters $Z_k, W_k, Q_k, K_k$ with derived operators $D_k=\\operatorname{diag}(Z_k)$, $L_k=-\\operatorname{tri}(Z_k)$, $W_k=M_k^\\top M_k$, and $U_k=(Q_k^\\top-K_k)^\\top \\operatorname{diag}(\\beta_k)^{-1}(Q_k^\\top-K_k)$, satisfying the structural conditions (11) and the coupling-cutoff conditions (14). After lifting and permutation, these matrices produce operators $D_A, L_A, Q_A, K_A, M_A$ on the lifted space; Lemma 6 shows $L_A$ is strictly block lower triangular and Lemma 7 shows $Q_A B K_A$ is also strictly lower triangular, which makes the resolvent equation computable by forward substitution, evaluating each $A_i$ exactly once per iteration. Lemma 2 establishes that $Q_P B K_P + \\tfrac{1}{4}U$ is maximal monotone, which feeds into Lemma 3: the iteration $T(z)=z+\\gamma M_A x$ is $\\tfrac{\\gamma}{2-\\alpha/2}$-averaged nonexpansive. That averaged nonexpansivity, together with the fixed-point equivalence of Lemma 1, is what produces the weak convergence in Theorem 1.","core_discovery":"CABRA is a matrix-parametrized forward-backward resolvent splitting that solves the coupled inclusion by iterating only on a lifted $z$-space while computing each resolvent $J_{\\alpha D^{-1} A}$ via forward substitution. Theorem 1 states that if the solution set is nonempty, the $z$-iterates converge weakly to a fixed point $z^*$ and the $x$-iterates converge weakly to $x^* = S(z^*) = R_A y^*$ for some solution $y^*$, and Lemma 1 establishes the exact equivalence between zeros of the inclusion and fixed points of the iteration map $T$. The convergence proof rests on showing that $T$ is averaged nonexpansive, using the monotonicity of $Q_P B K_P + \\tfrac{1}{4}U$ (Lemma 2) and the parameter conditions $Z \\succeq W$, $Z \\succeq U$, and $\\operatorname{null}(W)=\\operatorname{null}(Z)=\\operatorname{span}(\\mathbf{1})$. The paper further claims that any matrices feasible for its SDP (38) satisfy the required conditions, so the framework can design parameters for parallel execution, diagonal scaling, and communication structure, and that numerically these choices accelerate convergence compared with the uncoupled Algorithm 1, even when the selection operators are the identity.","pith_inferences":["Beyond the paper: the ordering condition (13) suggests that problems with cyclic coupling graphs cannot be handled directly; a natural extension would be to introduce delay or memory of past iterates, effectively unrolling the cycle, which is not covered by the convergence proof.","Beyond the paper: the diagonal scaling experiments indicate the matrix parameters can act as preconditioners tuned to operator outputs; this opens a concrete research direction of choosing parameters by estimating local Lipschitz or cocoercivity constants, which the paper does not develop.","Beyond the paper: in the weapon-target application the one-scalar-vector communication step may extend to other multi-stage stochastic programs with non-anticipativity constraints, since the same selection-operator structure appears whenever scenario-tree branches are coupled through shared stage variables."],"forward_implications":["For any coupling graph that can be ordered so that condition (13) holds, CABRA converges weakly to a solution from any starting point, with one resolvent evaluation per operator per iteration.","The SDP (38) produces valid matrix parameters for parallel execution, diagonal scaling, or any convex constraint set, so the convergence guarantees transfer to each designed parameter set.","When selection operators are not the identity, CABRA uses less memory than Algorithm 1 because each resolvent argument lives only in the relevant subvector space.","Diagonal scaling alone can accelerate convergence: in the halfspace example, scaled matrices converge in two iterations rather than sixteen.","For the stochastic weapon target assignment relaxation, CABRA splits over weapon platforms and sends only $|E\\times S|$ scalars per iteration, converging faster than Algorithm 1.","If the unproven parameter choice $\\alpha=10$ used in the numerical weapon-target test is valid, even larger step sizes may be possible beyond the proven range, though this is not established in the paper."],"supporting_citations":[{"why":"Supplies the base adaptable forward-backward splitting algorithm and the necessary/sufficient matrix conditions that CABRA generalizes to include coupled linear selection operators.","marker":"[1]"},{"why":"An independently developed variant of the same matrix-parametrized splitting family, used as the comparison baseline that CABRA extends.","marker":"[10]"},{"why":"Provides the standard results on resolvents of maximal monotone operators, averaged nonexpansive operators, and weak convergence that the proof of Theorem 1 relies on.","marker":"[7]"},{"why":"Establishes frugal resolvent splitting with minimal lifting for sums of monotone operators, the foundation for the matrix-parametrized framing used here.","marker":"[12]"},{"why":"Introduces the family of frugal and decentralized resolvent splittings defined by matrix parameters that CABRA extends.","marker":"[20]"},{"why":"Introduces the semidefinite programming approach to matrix parameter selection that the paper's SDP framework (38) builds on.","marker":"[6]"},{"why":"Establishes the minimal lifting and frugality concepts that motivate the single-evaluation-per-operator design of CABRA.","marker":"[17]"},{"why":"Extends frugal splitting to sums of maximal monotone and cocoercive operators, the setting CABRA addresses with coupling operators.","marker":"[15]"},{"why":"Provides graph-based frugal forward-backward splittings for the same mixed monotone/cocoercive setting, used as a related approach that CABRA generalizes with matrix parameters.","marker":"[4]"}],"fun_headline_variants":["CABRA: Splitting coupled monotone inclusions faster","Matrix-tuned resolvent splitting accelerates convergence","SDP-designed parameters speed up monotone splitting","CABRA: parallel splitting for coupled monotone inclusions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Every cocoercive operator must receive all its inputs from earlier resolvents than the resolvents that need its output; if the coupling pattern cannot be ordered this way, the algorithm's convergence guarantee does not apply.","fun_headline_variants_meta":{"raw":{"variants":["CABRA: Splitting coupled monotone inclusions faster","Matrix-tuned resolvent splitting accelerates convergence","SDP-designed parameters speed up monotone splitting","CABRA: parallel splitting for coupled monotone inclusions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000658,"raw_usage":{"total_tokens":3036,"prompt_tokens":997,"completion_tokens":2039,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":613,"completion_tokens_details":{"reasoning_tokens":1977}},"tokens_in":613,"tokens_out":2039,"duration_ms":13954,"temperature":1.0,"reasoning_tokens":1977,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:07:59.877448+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a problem with $K^A_1=\\{1\\}$, $K^A_2=\\{1,2\\}$, and $K^B_1=\\{1,2\\}$, so that $\\bar{i}_1 = i_{\\bar{1}} = 2$ and condition (13) fails. Implementing Algorithm 2 with any feasible matrices, the forward substitution (5) will need $x_2$ to compute the $B_1$ term in the first resolvent, so either the iterate is undefined or the algorithm diverges. A direct check that Lemma 7's conclusion fails—that $Q_A B K_A$ is not strictly lower triangular—would settle that the ordering condition is necessary for the stated guarantees.","supporting_citations":[{"cited_title":"Springer","cited_arxiv_id":null,"evidence_quote":"Provides the standard results on resolvents of maximal monotone operators, averaged nonexpansive operators, and weak convergence that the proof of Theorem 1 relies on."},{"cited_title":"Mathematical Programming 201(1-2):231–262","cited_arxiv_id":null,"evidence_quote":"Establishes frugal resolvent splitting with minimal lifting for sums of monotone operators, the foundation for the matrix-parametrized framing used here."},{"cited_title":"Optimization Letters pp 1–19 A Appendix A.1 Supporting Lemmas Lemma 4","cited_arxiv_id":null,"evidence_quote":"Introduces the family of frugal and decentralized resolvent splittings defined by matrix parameters that CABRA extends."},{"cited_title":"Optimal Design of Resolvent Splitting Algorithms","cited_arxiv_id":"2407.16159","evidence_quote":"Introduces the semidefinite programming approach to matrix parameter selection that the paper's SDP framework (38) builds on."},{"cited_title":"Mathematical Programming 182(1- 2):233–273","cited_arxiv_id":null,"evidence_quote":"Establishes the minimal lifting and frugality concepts that motivate the single-evaluation-per-operator design of CABRA."},{"cited_title":"SIAM Journal on Optimization 34(2):1595–1621","cited_arxiv_id":null,"evidence_quote":"Extends frugal splitting to sums of maximal monotone and cocoercive operators, the setting CABRA addresses with coupling operators."}],"review_version":1}