Pith. sign in

REVIEW 4 major objections 7 minor 33 references

An Algorithm for Graph-Fused Lasso Based on Graph Decomposition

T0 review · 4 major / 7 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 1908.02370 v1 pith:QKXAX447 submitted 2019-08-06 math.OC stat.CO

Feng Yu , Yi Yang , Teng Zhang This is my paper · ORCID
classification math.OCstat.CO MSC 90C2565K05
keywords graph-fusedlassoalternatingdirectionmethodofmultiplierstotalvariationgraphdecompositionmatchingnetworknonsmoothconvexoptimizationDouglas-Rachfordsplitting
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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$.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 7 minor

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.

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 (4)
  1. [Section 2.5, Theorem 2.3 and its application to GFL] 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.
  2. [Section 5.3, proof of Theorem 2.3] 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.
  3. [Section 2.5, construction of C1] 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.
  4. [Figure 1] 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.
minor comments (7)
  1. [Section 3.1] In the simulation setup, 'if 1≤23≤33' appears to be a typo for '23≤i≤33'; please correct the index range.
  2. [Section 3] 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.
  3. [Section 2.1 and Eq. (1)] 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.
  4. [Section 2.2, Algorithm 1 Step 2] 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'.
  5. [Section 4] 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.
  6. [Section 3] 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.
  7. [Section 2.4, Lemma 2.2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the algorithm is derived directly from the ADMM formulation of the graph-fused lasso objective, and the convergence comparison is an internal rate analysis rather than a restatement of inputs.

full rationale

The paper derives Algorithm 1 by splitting the GFL objective (7) into two components and applying ADMM; the algorithm is therefore constructed from the objective itself, not from any claimed output. The claimed per-iteration computational advantage is supported by an explicit arithmetic count of multiplications and additions in Section 2.4, comparing Algorithm 1 with E0 nonempty against the network lasso special case E0 = empty; this is a direct cost comparison, not a fitted or renamed prediction. The convergence-rate comparison in Section 2.5 is based on Theorem 2.3, which states a local convergence rate under an explicit affine-subdifferential assumption. The theorem is proved internally via the Douglas-Rachford equivalence; it is not assumed as the conclusion. The application of the theorem to GFL relies on a regularity assumption about the subdifferential being locally affine, which is asserted rather than established for the nonsmooth total-variation terms; however, an unsupported or questionable assumption is a correctness or validity concern, not a circularity. No parameter is fitted to the target result, no self-citation chain is load-bearing, and no existing result is repackaged as new. The paper does cite other work for background and comparisons, but the central derivation is self-contained and not equivalent to its inputs by construction. Therefore the circularity score is 0.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The algorithm introduces no new physical or statistical entities. It relies on standard convex optimization facts and on two technical lemmas whose proofs are incomplete: the preconditioned ADMM equivalence (Lemma 5.1) and the local affine-subdifferential convergence-rate model (Theorem 2.3). The main tuning degree of freedom is rho, selected by grid search in the experiments.

free parameters (1)
  • ADMM penalty parameter rho = grid-selected per experiment; no automatic selection rule
    Convergence speed in Section 3 is compared at each algorithm's best rho. The proposed method's advantage is therefore conditional on favorable rho tuning, and no principled method for choosing rho is provided.
assumptions (4)
  • standard math Standard ADMM convergence theory for convex problems with closed proper convex objectives and feasibility.
    Invoked implicitly in Sections 2.2 and 2.3 when the reformulated constrained problems are solved by alternating updates. The paper does not state the precise convergence conditions.
  • ad hoc to paper Lemma 5.1: preconditioned ADMM for min f(x)+g(y) subject to Ax+By=c is equivalent to standard ADMM on the augmented problem with constraints [Ax+By, C1x, C2y]=[c,z,w].
    The proof in Section 5.2 is sketchy: the cancellation of dual terms is asserted and the factor-of-two in rho for Lemma 2.1 is only stated. This equivalence is load-bearing for the correctness of Algorithm 1.
  • ad hoc to paper Theorem 2.3 assumes that around the solution, local subdifferentials of the objective components are affine, so that the ADMM iteration becomes a linear map with convergence rate c(rho).
    Section 2.5 and proof 5.3. The paper does not identify conditions under which nonsmooth GFL subdifferentials are affine or under which the linearized rate is valid.
  • standard math Closed-form formula in Lemma 2.2 for the two-vertex fused lasso subproblem.
    Used in Step 1 of Algorithm 1; stated without proof and considered standard in the graph-fused lasso literature.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An Algorithm for Graph-Fused Lasso Based on Graph Decomposition." pith.science (2026). https://pith.science/paper/QKXAX447

@misc{pith2026190802370,
  author       = {Pith},
  title        = {Pith review of: An Algorithm for Graph-Fused Lasso Based on Graph Decomposition},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QKXAX447}},
  note         = {Machine review of arXiv:1908.02370}
}
read the original abstract

This work proposes a new algorithm for solving the graph-fused lasso (GFL), a method for parameter estimation that operates under the assumption that the signal tends to be locally constant over a predefined graph structure. The proposed method applies the alternating direction method of multipliers (ADMM) algorithm and is based on the decomposition of the objective function into two components. While ADMM has been widely used in this problem, existing works such as network lasso decompose the objective function into the loss function component and the total variation penalty component. In comparison, this work proposes to decompose the objective function into two components, where one component is the loss function plus part of the total variation penalty, and the other component is the remaining total variation penalty. Compared with the network lasso algorithm, this method has a smaller computational cost per iteration and converges faster in most simulations numerically.

Figures

Figures reproduced from arXiv: 1908.02370 by the authors.

Figure 1
Figure 1. Comparison of the theoretical local convergence rates between Algorithm 1, the [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Comparison the convergence rates under the 1D chain graph setting with [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Visualization of a two-dimensional grid graph of size 10 [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Comparison the convergence rates under the 2D grid graph setting with [PITH_FULL_IMAGE:figures/full_fig_p014_4.png]
Figure 5
Figure 5. Figure 5: Comparison the convergence rates for the Chicago crime dataset with [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]
Figure 3
Figure 3. Figure 3: The convergence rates are shown in Figure 4, which shows that Algorithm 1 has [PITH_FULL_IMAGE:figures/full_fig_p015_3.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 26 canonical work pages

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address author booktitle chapter edition editor howpublished institution journal key month note number organization pages publisher school series title type url volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1 'mid.sentence := ...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in " " * FUNCTION format....

  3. [3]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in " " * FUNCTION format....

  4. [4]

    , " * write output.state after.block = add.period write newline

    ENTRY address author booktitle chapter edition editor howpublished institution journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1 'mid.sentence := #2 '...

  5. [5]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in " " * FUNCTION format....

  6. [6]

    Arnold, T. B. and R. J. Tibshirani (2016). Efficient implementations of the generalized lasso dual path algorithm. Journal of Computational and Graphical Statistics\/ 25\/ (1), 1--27

    work page 2016

  7. [7]

    Barbero, A. and S. Sra (2014). Modular proximal optimization for multidimensional total-variation regularization

    work page 2014

  8. [8]

    and J.-P

    Bleakley, K. and J.-P. Vert (2011, June). The group fused Lasso for multiple change-point detection . working paper or preprint

    work page 2011

Show all 33 references
  1. [9]

    Parikh, E

    Boyd, S., N. Parikh, E. Chu, B. Peleato, and J. Eckstein (2011, January). Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn.\/ 3\/ (1), 1--122

    2011

  2. [10]

    Chambolle, A. and J. Darbon (2009). On total variation minimization and surface evolution using parametric maximum flows. International Journal of Computer Vision\/ 84\/ (3)

    2009

  3. [11]

    Chen, X., Q. Lin, S. Kim, J. G. Carbonell, and E. P. Xing (2012, 06). Smoothing proximal gradient method for general structured sparse regression. Ann. Appl. Stat.\/ 6\/ (2), 719--752

    2012

  4. [12]

    (2013, Nov)

    Condat, L. (2013, Nov). A direct algorithm for 1-d total variation denoising. IEEE Signal Processing Letters\/ 20\/ (11), 1054--1057

    2013

  5. [13]

    Davies, P. L. and A. Kovac (2001, 02). Local extremes, runs, strings and multiresolution. Ann. Statist.\/ 29\/ (1), 1--65

    2001

  6. [14]

    Eckstein, J. and D. P. Bertsekas (1992, Apr). On the douglas---rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming\/ 55\/ (1), 293--318

    1992

  7. [15]

    Hastie, H

    Friedman, J., T. Hastie, H. Höfling, and R. Tibshirani (2007, 12). Pathwise coordinate optimization. Ann. Appl. Stat.\/ 1\/ (2), 302--332

    2007

  8. [16]

    Leskovec, and S

    Hallac, D., J. Leskovec, and S. Boyd (2015, aug). Network Lasso: Clustering and Optimization in Large Graphs. KDD : proceedings. International Conference on Knowledge Discovery & Data Mining\/ 2015 , 387--396

    2015

  9. [17]

    Johnson, N. A. (2013). A dynamic programming algorithm for the fused lasso and l 0-segmentation. Journal of Computational and Graphical Statistics\/ 22\/ (2), 246--260

    2013

  10. [18]

    Pock, and M

    Kolmogorov, V., T. Pock, and M. Rolinek (2016). Total variation on a tree. SIAM Journal on Imaging Sciences\/ 9\/ (2), 605--636

    2016

  11. [19]

    Kovac, A. and A. D. A. C. Smith (2011). Nonparametric regression on a graph. Journal of Computational and Graphical Statistics\/ 20\/ (2), 432--447

    2011

  12. [20]

    Landrieu, L. and G. Obozinski (2017). Cut pursuit: Fast algorithms to learn piecewise constant functions on general weighted graphs. SIAM Journal on Imaging Sciences\/ 10\/ (4), 1724--1766

    2017

  13. [21]

    Pham, and A

    Lin, X., M. Pham, and A. Ruszczynski (2014). Alternating linearization for structured regularization problems. 15 , 3447--3481

    2014

  14. [22]

    Yuan, and J

    Liu, J., L. Yuan, and J. Ye (2010). An efficient algorithm for a class of fused lasso problems. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , KDD '10, New York, NY, USA, pp.\ 323--332. ACM

    2010

  15. [23]

    Ramdas, A. and R. J. Tibshirani (2015, August). Fast and Flexible ADMM Algorithms for Trend Filtering . Journal of Computational and Graphical Statistics\/ 25\/ (3), 839--858

    2015

  16. [24]

    Rudin, L. I., S. Osher, and E. Fatemi (1992). Nonlinear total variation based noise removal algorithms. Physica D: Nonlinear Phenomena\/ 60\/ (1), 259 -- 268

    1992

  17. [25]

    Tansey, W. and J. G. Scott (2015, may). A Fast and Flexible Algorithm for the Graph-Fused Lasso

    2015

  18. [26]

    Saunders, S

    Tibshirani, R., M. Saunders, S. Rosset, J. Zhu, and K. Knight (2005). Sparsity and smoothness via the fused lasso. Journal of the Royal Statistical Society Series B\/ , 91--108

    2005

  19. [27]

    Wahlberg, B., S. Boyd, M. Annergren, and Y. Wang (2012). An admm algorithm for a class of total variation regularized estimation problems. In Preprints of the 16th IFAC Symposium on System Identification , pp.\ 83--88. QC 20121112

    2012

  20. [28]

    Xu, Z., M. A. T. Figueiredo, and T. Goldstein (2017). Adaptive admm with spectral penalty parameter selection. In AISTATS

    2017

  21. [29]

    Ye, G.-B. and X. Xie (2011). Split bregman method for large scale fused lasso. Computational Statistics & Data Analysis\/ 55\/ (4), 1552 -- 1569

    2011

  22. [30]

    Yu, D., J.-H. Won, T. Lee, J. Lim, and S. Yoon (2015). High-dimensional fused lasso regression using majorization-minimization and parallel processing. Journal of Computational and Graphical Statistics\/ 24\/ (1), 121--153

    2015

  23. [31]

    Zhu, Y. (2017). An augmented admm algorithm with application to the generalized lasso problem. Journal of Computational and Graphical Statistics\/ 26\/ (1), 195--204

    2017

  24. [32]

    , " * write output.state after.block = add.period write newline

    ENTRY address author booktitle chapter edition editor howpublished institution journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence a...

  25. [33]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

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