Source-linked AI summary
Split Bregman method for large scale fused Lasso
Gui-Bo Ye, Xiaohui Xie
TL;DR
General fused Lasso is difficult to solve at scale because its regularization is nonsmooth and nonseparable, while existing solvers are limited to small or medium problems or a special case. The paper develops split Bregman algorithms for fused Lasso variants and proves convergence properties. Its experiments report faster performance than existing solvers, especially for large-p, small-n problems.
Problem
General fused Lasso is computationally challenging because its objective is nonsmooth and nonseparable, and existing solvers handle only small or medium problems or the identity-predictor special case.
Source: §1 · pp. 1–2Method
The paper derives split Bregman algorithms using an augmented Lagrangian for generalized fused Lasso, standard fused Lasso, FLSA, and fused Lasso support vector classification.
Source: §1 · p. 2, §4 · p. 13Results
SBFLasso consistently runs at least ten times faster than CVX in tested cases and is significantly faster than SQOPT for large p.
Source: §3.1.1 · p. 8Takeaways & Limitations
Preliminary experiments indicate efficiency for large-scale fused Lasso problems, especially those with large p and small n.
Source: §4 · p. 13PATHFLSA requires a piecewise-linear solution path in λ2, a condition that generally fails for fused and generalized fused Lasso, so it cannot solve those cases.
Source: §3.1.2 · p. 10
Abstract
from arXiv · showhide
rdering of regression or classification coefficients occurs in many real-world applications. Fused Lasso exploits this ordering by explicitly regularizing the differences between neighboring coefficients through an $\ell_1$ norm regularizer. However, due to nonseparability and nonsmoothness of the regularization term, solving the fused Lasso problem is computationally demanding. Existing solvers can only deal with problems of small or medium size, or a special case of the fused Lasso problem in which the predictor matrix is identity matrix. In this paper, we propose an iterative algorithm based on split Bregman method to solve a class of large-scale fused Lasso problems, including a generalized fused Lasso and a fused Lasso support vector classifier. We derive our algorithm using augmented Lagrangian method and prove its convergence properties. The performance of our method is tested on both artificial data and real-world applications including proteomic data from mass spectrometry and genomic data from array CGH. We demonstrate that our method is many times faster than the existing solvers, and show that it is especially efficient for large p, small n problems.
1. Introduction
Fused Lasso uses naturally ordered coefficients by penalizing neighboring differences, but its nonsmooth, nonseparable objective makes general problems difficult to solve at scale. The paper introduces a split Bregman approach for general fused Lasso and evaluates its performance on real-world applications.
1. Introduction
- Fused Lasso extends Lasso by penalizing differences between neighboring coefficients, encouraging both sparse coefficients and smooth neighboring values.The method assumes a natural ordering of coefficients.Source: §1 · p. 1
- Natural ordering in genomic and proteomic variables motivates fused Lasso applications, including detecting DNA copy-number variations and selecting proteomic features.Examples include chromosomal features ordered by location and mass-spectrometry fragments ordered by mass-to-charge ratio.Source: §1 · pp. 1–2
- Existing convex-optimization solvers introduce many variables and constraints, limiting practical fused Lasso problems to small or medium sizes.Coordinate descent also lacks guaranteed convergence because the difference penalty makes the variables nonseparable.Source: §1 · p. 2
- The paper proposes split Bregman iteration for general fused Lasso and derives algorithms from the augmented Lagrangian, with convergence properties and numerical evaluation.The paper also describes implementation details and reports that its Matlab algorithms are freely available from the authors.Source: §1 · p. 2
2. Algorithms
The algorithms reformulate fused Lasso problems using auxiliary variables and an augmented Lagrangian, then apply split Bregman iterations. Specialized linear-system structure yields efficient solvers for standard fused Lasso and FLSA, while an additional variable handles the SVM hinge loss.
2.1. Split Bregman iteration for a generalized fused Lasso problem
- For the generalized fused Lasso, split Bregman alternates primal and dual updates after splitting coefficient sparsity and differences into separate auxiliary variables.The split transfers the ℓ1 nondifferentiability from β to decoupled auxiliary variables; their minimizations use soft thresholding, while the β update depends on the error function.Source: §2.1 · p. 3
- Under convex V, positive regularization parameters, a solution, and 0 < δ1 ≤ μ1 and 0 < δ2 ≤ μ2, Algorithm 1's objective values converge to the optimum.The method uses one alternation of the primal minimizations per outer iteration rather than solving the primal problem fully.Source: §2.1 · p. 4
2.2. Split Bregman for the standard fused Lasso (SBFLasso)
- For standard fused Lasso, the β update is a linear system; PCG uses a structured preconditioner and converges in fewer than n steps.The paper reports that in numerical implementation PCG converged in a few steps, substantially fewer than n.Source: §2.2 · p. 5
2.3. Split Bregman for FLSA (SBFLSA)
- For FLSA, the tridiagonal positive-definite system yields a split Bregman solver requiring O(p) operations.FLSA is the special case in which the predictor matrix is the identity.Source: §2.3 · p. 5
2.4. Iterative algorithm for fused Lasso Support Vector Classifier (SBFLSVM)
- For fused Lasso SVM classification, the algorithm introduces an auxiliary variable to handle the nondifferentiable hinge loss and derives Algorithm 2.The paper states that Algorithm 2 has a convergence property under stated conditions, including positive regularization parameters and step sizes bounded by their penalty parameters.Source: §2.4 · pp. 5, 7
3. Experimental Results
Across artificial and real-world tests, the split Bregman solvers were evaluated against existing optimization methods, with runtime advantages especially evident for large-p problems. The experiments also report performance on FLSA, mass-spectrometry, and CGH data.
3. Experimental Results
- The experiments compare SBFLasso with SQOPT and CVX for general fused Lasso, and SBFLSA with PATHFLSA for FLSA.Timing trials used artificial data and real-world genomics and proteomics applications.Source: §3 · p. 7
3.1.1. Solving fused Lasso
- At n = 200 and p = 20000, SBFLasso solved the fused Lasso problem in about 30 seconds versus about 800 seconds for SQOPT, and was about 20 times faster on large-p problems.SBFLasso consistently outperformed CVX by at least tenfold; CVX ran out of memory on large-p problems.Source: §3.1.1 · p. 8, Table 1 · p. 9
- SBFLasso's CPU times were roughly linear in both n and p, with Figure 2 plotting timings averaged over 500 runs.The figure varies p while fixing n = 200, and varies n while fixing p = 5000.Source: §3.1.1 · p. 8, Figure 2 · p. 10
- Splitting the coefficient and difference penalties makes the minimization problems separable, and soft thresholding yields sparse solutions without postprocessing.The paper contrasts this with CVX and SQOPT, whose solutions require a thresholding step to achieve sparsity.Source: §3.1.1 · p. 8, Figure 1 · p. 9
3.1.2. Solving FLSA
- SBFLSA performed similarly to PATHFLSA in almost all tested FLSA cases, and both were thousands of times faster than SQOPT for large-p problems.PATHFLSA additionally generates solutions across a regularization-parameter path, but requires a piecewise-linear solution path and does not apply to general or generalized fused Lasso.Source: §3.1.2 · p. 10, Table 2 · p. 10
3.2. Mass spectrometry data
- On mass-spectrometry data, SBFLasso was about ten times faster than CVX and SQOPT in almost all cases, while producing similar coefficients, a sparser solution, and a slightly lower objective than CVX.The experiment used 3,000 sampled m/z sites to predict sample labels.Source: §3.2 · p. 11, Table 3 · p. 11
3.3. Comparative genomic hybridization (CGH) data
- On glioblastoma array-CGH data, SBFLSA was about 100 times faster than SQOPT and CVX, with performance comparable to the specialized path algorithm.The inferred copy numbers showed gains in two nearby chromosomal regions.Source: §3.3 · p. 12, Table 4 · p. 12
4. Discussion
Fused Lasso uses an ℓ1 penalty on differences between ordered neighboring coefficients, but its nonsmooth, nonseparable objective makes it difficult to solve at scale. The paper presents a convergent split Bregman algorithm for several fused Lasso variants and reports efficiency especially for large-p, small-n problems.
4. Discussion
- Existing solvers handle only small or medium fused Lasso problems because the objective is nonsmooth and nonseparable.They reformulate the problem with many auxiliary variables and constraints.Source: §4 · p. 13
- The authors derive a convergent split Bregman algorithm for standard fused Lasso, FLSA, and fused Lasso support vector classification.Preliminary experiments test SBFLasso and SBFLSA.Source: §4 · p. 13
- Preliminary experiments show efficiency especially for large-p, small-n problems found in real-world applications.Source: §4 · p. 13
- The algorithm is described as easy to implement and adaptable to varied fused Lasso problems with minor modifications, unlike the domain-specific path algorithm.The authors expect its simplicity and generality to support use in other ℓ1 regularization problems.Source: §4 · p. 13
A.1. Convergence analysis of Algorithm 1
The proof establishes convergence of Algorithm 1’s objective and, when the solution is unique, convergence of the coefficient iterates to that solution.
A.1. Convergence analysis of Algorithm 1
- The proof uses first-order optimality conditions and convex subgradient inequalities to show the relevant terms are nonnegative.It applies subgradients for V and the two ℓ1 penalties, with 0 < δ1 ≤ μ1 and 0 < δ2 ≤ μ2.Source: §A.1 · pp. 15, 17
- Algorithm 1’s objective converges to the optimal value, and its constraint residuals vanish.The residuals are ||β^k − a^k||_2 and ||Lβ^k − b^k||_2.Source: §A.1 · p. 17
- If the minimizer is unique, the iterates β^k converge to it; the proof argues by contradiction using objective convergence and convexity.The uniqueness condition is stated for problem (2).Source: §A.1 · p. 17
A.2. Convergence analysis of Algorithm 2
The proof extends the convergence argument to Algorithm 2, accounting for the bias term and hinge loss. It establishes convergence of the objective under the stated convex subproblem conditions.
A.2. Convergence analysis of Algorithm 2
- First-order optimality conditions for the convex subproblems provide the relations used to compare each iteration with a fixed point.The proof introduces auxiliary variables for the coefficient, fused coefficients, and hinge-loss constraints.Source: §A.2 · p. 18
- The proof concludes that Algorithm 2 has the convergence result in (21), with the proof of (22) following the same line as Theorem 1.The authors note that the extra bias term and hinge loss make the proof’s terms more complicated.Source: §A.2 · pp. 18, 20
- Subgradient monotonicity makes the terms in (58) nonnegative, enabling the proof to bound them separately.The argument uses subgradients of the ℓ1 terms and the hinge-loss term.Source: §A.2 · pp. 18, 20
A.3.1. Update of β
The β update requires solving a linear system that remains suitable for preconditioned conjugate gradients because its matrix combines a tridiagonal component with a low-rank component.
A.3.1. Update of β
- The linear system for the β update can be solved efficiently by PCG.The system is slightly different from (14), but the authors state PCG still solves it efficiently.Source: §A.3.1 · pp. 20–21
- The β update’s linear system includes the fused-difference operator through the term L^T L.The displayed matrix also includes the identity and terms involving X and the labels.Source: §A.3.1 · pp. 20–21
- The matrix structure remains tractable because one component is tridiagonal and another is low rank.The text identifies these structures for the system in (59).Source: §A.3.1 · p. 21
A.3.2. Proof of Proposition 1
The proposition identifies the subdifferential of the positive-part function, including its interval of valid subgradients at zero.
A.3.2. Proof of Proposition 1
- The subdifferential characterization yields the equation whose unique solution is sλ.Uniqueness follows from the strong convexity of the associated squared-distance objective.Source: §A.3.2 · p. 21
- For x = 0, the subdifferential of x+ is the interval [0, 1].For x > 0 it contains the gradient, and for x < 0 it is 0.Source: §A.3.2 · p. 21
- The proof obtains the stated result by combining equations (60) and (61).Source: §A.3.2 · p. 21