{"id":"dd44b23e-e338-4695-9596-3248578cdc82","arxiv_id":"1908.02370","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A graph-decomposition ADMM algorithm for graph-fused lasso moves part of the total-variation penalty into the x-update, giving smaller per-iteration cost and faster empirical convergence than network lasso.","lead":"The authors propose a new way to split the graph-fused lasso optimization problem inside the ADMM algorithm, putting part of the smoothness penalty into the main variable update. The result is an ADMM variant that often needs fewer iterations and less work per iteration than the popular network lasso method.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.3's affine-subdifferential assumption is not satisfied by the nonsmooth GFL objective, so the theoretical convergence-rate comparison in Figure 1 is unsupported.","rationale":"The reader's weakest-assumption analysis identifies exactly the load-bearing gap: the local convergence-rate theorem assumed an affine subdifferential that the nonsmooth GFL objective does not have at the solutions of interest. My reading of the paper confirms this is the main point where the theoretical claim of faster convergence rests on an unproven and generally false premise. The algorithm itself appears internally consistent: the edge-matching split is valid, the ADMM updates are derived correctly, and the per-iteration complexity comparison is plausible for the squared-loss case. The numerical experiments are suggestive but lack error bars and code, so they cannot independently carry the general claim. Because the concern does not overturn the empirical possibility that Algorithm 1 is faster, but it does undermine the theoretical support, the conditional verdict remains appropriate. No additional fatal flaw was found in the derivation of the ADMM updates or the equivalence lemmas.","tokens_in":11451,"tokens_out":32831,"duration_ms":335600,"concrete_test":"Use the 1D chain example from Section 2.5 with a solution that has at least one E1 edge with x_s=x_t. Numerically compute the local contraction factor of Algorithm 1 by initializing a small perturbation of the exact solution and measuring the ratio of successive errors in the ADMM iterates. Compare this measured rate with the c(ρ) predicted by Theorem 2.3 under any proposed interpretation of C2^{-1} (e.g., pseudoinverse or a 1/∞ limiting convention). If the measured rate differs from the predicted c(ρ), or if the theorem has no well-defined C2^{-1} for this input, the theoretical comparison in Figure 1 is unsupported. As a secondary check, rerun the Section 3 simulations with 100 random seeds and report median and interquartile ranges of objective-error curves to test the 'most simulations' claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract's central claim is that Algorithm 1 has smaller cost per iteration and converges faster than network lasso. The smaller per-iteration cost is credible, but the 'converges faster' claim is only rigorously supported by Theorem 2.3 in Section 2.5. That theorem assumes that, around the solution, ∂f1(x)=C1x+c1 and ∂f2(x)=C2x+c2 are affine. For the GFL objective, f2 contains terms λ||z_st- z_ts||, which are not differentiable at points where z_st=z_ts; a typical GFL solution has many edges with equal values. The paper's own construction of C2 sets the corresponding 2p×2p blocks to zero (Section 2.5), making C2 singular and C2^{-1} undefined in the formula for c(ρ). Thus the c(ρ) curves in Figure 1, which are used to argue that Algorithm 1 converges faster, are not justified by the stated theorem. The experiments in Section 3 are suggestive, but without a valid rate analysis, error bars, or code, they support the claim only for the tested configurations, not as a general theoretical conclusion.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a new ADMM algorithm for graph-fused lasso that splits the edge set into a matching E0 and the remaining edges E1, placing the E0 total-variation terms in the x-update and the E1 terms in the z-update. A preconditioned ADMM reformulation is introduced in Section 2.3 that reduces the number of auxiliary variables relative to network lasso, and Section 2.4 gives an explicit per-iteration cost comparison. The central claim is that the new algorithm has lower per-iteration cost than network lasso and converges faster, supported by a local convergence-rate theorem (Theorem 2.3), a numerical comparison of the theoretical spectral radius c(rho) in Figure 1, and simulations on chain graphs, grids, and a Chicago crime dataset.","tokens_in":11760,"tokens_out":4522,"duration_ms":51103,"significance":"If the claims are established, the algorithm would be a practically useful improvement over network lasso for graph-fused lasso, with a smaller per-iteration arithmetic cost and competitive or better iteration counts. The graph-decomposition idea and the preconditioned equivalent ADMM form are interesting and the per-iteration cost analysis is explicit. However, the theoretical convergence-rate comparison is not sound: Theorem 2.3 assumes affine local subdifferentials, which does not hold for the nonsmooth GFL objective, and the resulting spectral-radius curves in Figure 1 are therefore unsupported. The numerical experiments are suggestive but do not fill this theoretical gap. The contribution is conditionally valuable if the rate analysis is repaired or the faster-convergence claim is appropriately weakened.","major_comments":[{"comment":"Theorem 2.3 assumes that around the solution the subdifferentials of the two objective components are affine, i.e., ∂f1(x)=C1x+c1 and ∂f2(x)=C2x+c2. This assumption is not satisfied by the GFL objective. For the component f2 containing λ‖z_st−z_ts‖, at any edge where z_st=z_ts — which is typical at a piecewise-constant GFL solution — the subdifferential is a set-valued ball and is not a single-valued affine function. Accordingly, the paper's own construction of C2 in Section 2.5 sets the corresponding 2p×2p blocks to zero, making C2 singular. The convergence-rate formula c(ρ) uses C2^{-1}, so the expression is undefined and Figure 1's theoretical rate comparison is not justified by the stated theorem.","section":"Section 2.5, Theorem 2.3 and its application to GFL"},{"comment":"The proof asserts that 'locally around the optimal solution' the proximal operators become linear with ∂f(x)=A2C2^{-1}A2^T x + c1 and similarly for the other component. This is exactly the affine-subdifferential assumption, which is not proven for the nonsmooth GFL problem. No separate argument is given for why the nonsmooth terms can be replaced by a linear map near the solution, and no convergence proof for the actual nonsmooth iteration is supplied. Thus the claimed O(c(rho)^k) local convergence rate for Algorithm 1 is not established.","section":"Section 5.3, proof of Theorem 2.3"},{"comment":"In the construction of C1, the paper defines T(i,j)=∞I when x_i^*=x_j^* for (i,j)∈E0, and then uses this infinite matrix in C1 and in the rate formula. No interpretation of infinite blocks is provided, and it is not clear how the subsequent eigenvalue computation, which requires finite matrices, can be performed or what the spectral radius means in that case. This is another obstruction to the stated theoretical comparison.","section":"Section 2.5, construction of C1"},{"comment":"Even setting aside the undefined C2^{-1}, the comparison in Figure 1 is not reproducible from the text: for the three settings the authors state only the locations i where x_i^*≠x_{i+1}^*, not the actual vector values of x_i^*. Without those values, the claimed c(ρ) curves cannot be independently verified. More importantly, since C2 is singular for solutions with any equal-edge endpoint values, the plotted curves cannot be the result of applying Theorem 2.3 as stated.","section":"Figure 1"}],"minor_comments":[{"comment":"In the simulation setup, 'if 1≤23≤33' appears to be a typo for '23≤i≤33'; please correct the index range.","section":"Section 3.1"},{"comment":"The experiments are reported as single curves without error bars or repeated trials, so the statement that Algorithm 1 'converges faster in most simulations' is only illustrated for the displayed runs. Adding standard errors or a summary over multiple random noise draws would strengthen the numerical claim.","section":"Section 3"},{"comment":"In Eq. (1) the total-variation term is written as ‖xr−xs‖, but the rest of the paper uses indices (s,t) with variables x_s and x_t; the notation should be made consistent.","section":"Section 2.1 and Eq. (1)"},{"comment":"Step 2 states 'For any i∈V and does not belong to any edges in E0', which is grammatically unclear; it should read 'For any i∈V that does not belong to any edge in E0'.","section":"Section 2.2, Algorithm 1 Step 2"},{"comment":"The conclusion says the algorithm has 'a similar complexity per iteration' compared with network lasso, while the abstract and Section 2.4 claim a smaller computational cost. These statements should be reconciled.","section":"Section 4"},{"comment":"The sentence 'there do not exists an optimal choice for settings (Xu et al., 2017)' is malformed; please rephrase to state that no universally optimal penalty parameter is known.","section":"Section 3"},{"comment":"Lemma 2.2 is stated without proof, with only a reference to earlier work. Since this lemma is used in the x-update and the cost analysis, providing a short proof or a precise citation with a theorem number would be helpful.","section":"Section 2.4, Lemma 2.2"}],"recommendation":"major_revision","confidential_remarks":"The central theoretical claim about faster convergence is currently unsupported because Theorem 2.3 relies on an affine-subdifferential assumption that fails for the nonsmooth GFL objective. The per-iteration cost improvement and the numerical demonstrations are credible, but the paper should either supply a valid local convergence analysis that handles nonsmoothness, or substantially weaken the 'converges faster' claim to an empirical observation. With that change, the algorithmic contribution would be publishable; in its present form the rate comparison in Figure 1 and the related text should not be presented as proven."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The one thing you should know: this paper has a genuinely new algorithmic trick, and the complexity analysis for per-iteration cost is convincing. The catch is that the paper's theoretical convergence-rate claims rest on an assumption that the nonsmooth GFL objective does not satisfy, so the theory is not sound as written. I agree with the stress-test note; it lands on reading the paper.\n\nWhat's new: the authors partition edges into a matching E0 and the rest E1, moving part of the TV penalty into the x-update. This reduces the number of auxiliary z variables compared to network lasso (only E1 edges need them), and the per-iteration cost analysis in Section 2.4 is clear and correct. The explicit pair-update in Lemma 2.2 is useful, and the equivalence between the preconditioned and standard ADMM forms (Lemma 2.1) is plausible. The experiments, while limited, do show faster convergence in several settings, including a real Chicago crime dataset.\n\nThe soft spot: Theorem 2.3 assumes that around the solution the subdifferentials of the two objective components are affine, ∂f1(x)=C1x+c1 and ∂f2(x)=C2x+c2. For the GFL objective, f2 contains terms like λ||z_st − z_ts||, which are nondifferentiable at any solution where z_st = z_ts. The paper's own construction of C2 sets those blocks to zero, which makes C2 singular. The formula for c(ρ) involves C2^{-1}, so it is not even well-defined. Hence the c(ρ) curves in Figure 1, which are used to argue that Algorithm 1 converges faster, are unsupported. The experiments in Section 3 are suggestive but lack error bars, code, or even seed details; they support the claim only for the tested configurations, not as a general theoretical conclusion.\n\nThis is a paper with a good algorithmic contribution and a shaky theoretical framework. The per-iteration complexity improvement is real, and the numerical comparisons are suggestive. But the convergence-rate theory needs major repair: either prove the affine-subdifferential property for a restricted class (e.g., when all solution edge differences are nonzero), or reframe the paper as an empirical algorithm with only complexity guarantees. I would send this to peer review, but with a clear request for a rigorous convergence analysis and reproducible experiments including uncertainty quantification.\n\nWho this is for: researchers working on fast ADMM solvers for graph-fused lasso, and practitioners with large graph-structured problems. It deserves a serious referee, but heavy revision before acceptance.","headline":"The edge-matching split is a real algorithmic idea and the per-iteration cost reduction is solid, but the convergence-rate theorem relies on an assumption the nonsmooth GFL objective does not satisfy, so the theory is unsupported.","tokens_in":12203,"tokens_out":2878,"would_cite":true,"duration_ms":32672,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that a new ADMM algorithm, based on splitting the graph-fused lasso objective into a loss-plus-matching-penalty part and a remaining-edge-penalty part, solves the same problem as network lasso with smaller per-iteration…","keywords":["graph-fused lasso","alternating direction method of multipliers","total variation","graph decomposition","matching","network lasso","nonsmooth convex optimization","Douglas-Rachford splitting"],"falsifier":"Run the algorithm and network lasso on a small chain graph whose solution has equal values across an edge in $E_0$, so the subdifferential of that penalty term is a set rather than a single affine map; measure the empirical contraction ratio of the objective error and compare it with the spectral radius $c(\\rho)$ from Theorem 2.3. A mismatch would show that the affine-subdifferential assumption, on which the theoretical convergence comparison rests, fails in a case the algorithm is designed to handle.","tokens_in":11240,"feed_emoji":"⚙️","tokens_out":7424,"duration_ms":72759,"temperature":0.7,"pith_summary":"This paper proposes a new alternating-direction method of multipliers (ADMM) for graph-fused lasso, which estimates a signal that is piecewise constant over a graph. Instead of splitting the objective into the loss and the full total-variation penalty, as network lasso does, the paper splits the edge set into a matching $E_0$ and the remaining edges $E_1$: the loss plus the penalty on $E_0$ forms one component, and the penalty on $E_1$ forms the other. Only edges in $E_1$ need auxiliary $z$ variables, so each iteration is cheaper, and the paper argues through a local convergence-rate theorem and numerical experiments that the method usually converges faster than network lasso. If right, it gives a drop-in replacement for a widely used estimator on arbitrary graphs with vector-valued signals.","feed_headline":"New ADMM split cuts cost and iterations for graph-fused lasso","feed_subtitle":"Keeping part of the penalty inside the x-update removes dummy variables and speeds up convergence in tests.","key_machinery":"The load-bearing structure is the edge decomposition $E = E_0 \\cup E_1$ in which $E_0$ is a matching, meaning no two of its edges share a vertex. This makes the $x$-subproblem separable into independent two-vertex problems with the closed form given in Lemma 2.2, and it leaves only the $E_1$ edges with auxiliary variables and dual variables. Lemma 2.1 shows that the preconditioned ADMM updates of Section 2.3 are equivalent to the original split with doubled penalty parameter, and Theorem 2.3 turns local convergence into the spectral radius $c(\\rho)$ of a linearized Douglas-Rachford operator, which is what the paper compares against network lasso.","core_discovery":"The central claim is that the same graph-fused lasso solution can be obtained by an ADMM that leaves part of the total-variation penalty inside the $x$-update. The paper proves the equivalence between the direct split and a preconditioned ADMM formulation, gives closed-form updates for edges in $E_0$, and applies a general local convergence theorem (Theorem 2.3) showing the contraction rate is the spectral radius $c(\\rho)$ of a linearized Douglas-Rachford operator. In chain-graph examples this $c(\\rho)$ is smaller for the proposed split than for network lasso, and in simulations on chains, a 64x64 grid, and a 2162-vertex Chicago crime graph the proposed algorithm converges in fewer iterations while spending less arithmetic per iteration. The method applies to any graph and any $p\\ge 1$.","pith_inferences":["The paper uses one greedy matching, but $E_0$ is a design choice; a testable extension is whether maximum-cardinality matchings, or matchings aligned with large signal jumps, shrink $c(\\rho)$ further.","The theoretical comparison relies on affine subdifferentials, so at solutions with tied values the numerical experiments carry the argument; a reader can separately test the observed contraction rate in such cases.","The sketch combining this edge split with trail decomposition (for $p=1$) points to a family of hybrid algorithms, but the paper does not implement them, so their benefit is an open question.","Because the comparison is only against network lasso, the paper does not address whether the split beats specialized finite-step solvers on chains or grids; assessing that would require a separate benchmark."],"forward_implications":["The per-iteration arithmetic drops because only $2|E_1|$ auxiliary copies and duals are needed, not $2|E|$.","The algorithm applies to arbitrary graphs and vector-valued signals, preserving network lasso's generality.","In the 1D chain simulations, with $\\rho$ tuned optimally for each method, the proposed algorithm converges about twice as fast as network lasso.","On a 64x64 grid and on the Chicago crime graph, it converges at least as fast as network lasso while costing less per iteration.","The same splitting idea transfers to trend filtering by grouping second-difference terms into two parts, as the conclusion outlines."],"supporting_citations":[{"why":"Supplies the network lasso baseline: the ADMM split with $E_0=\\emptyset$, $E_1=E$, whose per-iteration cost and convergence the proposed method is compared against.","marker":"(Hallac et al., 2015)"},{"why":"Provides a prior modified ADMM with reduced per-update cost but slower convergence, framing the cost-convergence trade-off the paper targets.","marker":"(Zhu, 2017)"},{"why":"Gives the trail-decomposition ADMM for $p=1$ that the paper contrasts and can combine with its own splitting.","marker":"(Tansey and Scott, 2015)"},{"why":"Offers a modular proximal and Douglas-Rachford decomposition for total-variation regularization, a precedent for decomposition-based splitting.","marker":"(Barbero and Sra, 2014)"},{"why":"Establishes the equivalence between ADMM and Douglas-Rachford splitting, which the proof of Theorem 2.3 relies on.","marker":"(Eckstein and Bertsekas, 1992)"},{"why":"Provides the ADMM framework and penalty-parameter balancing strategies used in the experiments.","marker":"(Boyd et al., 2011)"},{"why":"Supplies the trend-filtering ADMM setting that the conclusion names as a target extension of the proposed splitting.","marker":"(Ramdas and Tibshirani, 2015)"}],"fun_headline_variants":["ADMM with partial penalty split speeds graph-fused lasso","Cheaper ADMM iterations for graph-fused lasso converge faster","Graph decomposition ADMM cuts cost per iteration and iterations","New ADMM split reduces cost and iterations for graph-fused lasso","Faster graph-fused lasso via partial penalty in ADMM update"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The theoretical speed comparison assumes that near the solution the subgradient of each objective piece is a single affine function ($\\partial f_1(x)=C_1x+c_1$, $\\partial f_2(x)=C_2x+c_2$); for the nonsmooth graph-fused lasso objective this is asserted rather than proved, so the reported spectral-radius advantage may not describe actual iterates at ties.","fun_headline_variants_meta":{"raw":{"variants":["ADMM with partial penalty split speeds graph-fused lasso","Cheaper ADMM iterations for graph-fused lasso converge faster","Graph decomposition ADMM cuts cost per iteration and iterations","New ADMM split reduces cost and iterations for graph-fused lasso","Faster graph-fused lasso via partial penalty in ADMM update"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000164,"raw_usage":{"total_tokens":1205,"prompt_tokens":860,"completion_tokens":345,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":476,"completion_tokens_details":{"reasoning_tokens":256}},"tokens_in":476,"tokens_out":345,"duration_ms":4041,"temperature":1.0,"reasoning_tokens":256,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:47:18.983254+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the algorithm and network lasso on a small chain graph whose solution has equal values across an edge in $E_0$, so the subdifferential of that penalty term is a set rather than a single affine map; measure the empirical contraction ratio of the objective error and compare it with the spectral radius $c(\\rho)$ from Theorem 2.3. A mismatch would show that the affine-subdifferential assumption, on which the theoretical convergence comparison rests, fails in a case the algorithm is designed to handle.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the trail-decomposition ADMM for $p=1$ that the paper contrasts and can combine with its own splitting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Offers a modular proximal and Douglas-Rachford decomposition for total-variation regularization, a precedent for decomposition-based splitting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the equivalence between ADMM and Douglas-Rachford splitting, which the proof of Theorem 2.3 relies on."},{"cited_title":"Parikh, E","cited_arxiv_id":null,"evidence_quote":"Provides the ADMM framework and penalty-parameter balancing strategies used in the experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the trend-filtering ADMM setting that the conclusion names as a target extension of the proposed splitting."},{"cited_title":"Leskovec, and S","cited_arxiv_id":null,"evidence_quote":"Supplies the network lasso baseline: the ADMM split with $E_0=\\emptyset$, $E_1=E$, whose per-iteration cost and convergence the proposed method is compared against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides a prior modified ADMM with reduced per-update cost but slower convergence, framing the cost-convergence trade-off the paper targets."}],"review_version":1}