Source-linked AI summary
Smoothing proximal gradient method for general structured sparse regression
Xi Chen, Qihang Lin, Seyoung Kim, Jaime G. Carbonell, Eric P. Xing
TL;DR
High-dimensional structured regression needs penalties that encode relationships among inputs or outputs, but overlapping and graph-based penalties are nonsmooth and nonseparable. The paper proposes SPG, which smooths the complex structured penalty and applies a proximal-gradient method; it reports O(1/ε) convergence, broader applicability, and scalability advantages over interior-point methods. The method is demonstrated on simulated and real genetic data.
Problem
Structured sparse regression requires efficient optimization for nonsmooth, nonseparable penalties that encode prior structure on inputs or outputs.
Method
SPG smooths the complex structured penalty, decouples nonseparable terms through dual norms, and solves the smoothed problem with FISTA.
Results
SPG achieves an O(1/ε) convergence rate and applies to smooth convex losses with a broad family of structured penalties, including uni- and multi-task settings.
Takeaways & Limitations
SPG provides a first-order framework for structured sparse regression that is scalable to high-dimensional problems and supports exact zeros through an ℓ1 penalty.
Takeaways & Limitations
Further acceleration remains an open direction because the ℓ1 penalty makes the relevant operator nondifferentiable, complicating Jacobian approximation.
Abstract
from arXiv · showhide
We study the problem of estimating high-dimensional regression models regularized by a structured sparsity-inducing penalty that encodes prior structural information on either the input or output variables. We consider two widely adopted types of penalties of this kind as motivating examples: (1) the general overlapping-group-lasso penalty, generalized from the group-lasso penalty; and (2) the graph-guided-fused-lasso penalty, generalized from the fused-lasso penalty. For both types of penalties, due to their nonseparability and nonsmoothness, developing an efficient optimization method remains a challenging problem. In this paper we propose a general optimization approach, the smoothing proximal gradient (SPG) method, which can solve structured sparse regression problems with any smooth convex loss under a wide spectrum of structured sparsity-inducing penalties. Our approach combines a smoothing technique with an effective proximal gradient method. It achieves a convergence rate significantly faster than the standard first-order methods, subgradient methods, and is much more scalable than the most widely used interior-point methods. The efficiency and scalability of our method are demonstrated on both simulation experiments and real genetic data sets.
1. Introduction.
Complex structured sparsity penalties capture relationships that standard lasso cannot, but their nonseparability makes efficient optimization difficult. The paper introduces SPG, a broadly applicable smoothed first-order approach for these problems.
- Motivation: Standard lasso cannot capture structural information among input variables, motivating structured sparsity penalties.Extensions exploit groups, pairwise similarities, and output structures to encourage related variables to be selected jointly.
- Motivation: Overlapping-group and graph-guided-fused penalties extend group lasso and fused lasso to more complex variable structures.The former permits variables to belong to multiple groups, while the latter applies fusion across graph edges.
- Proposed approach: SPG decouples nonseparable terms through dual norms, smooths the structured penalty, and solves the resulting surrogate with FISTA.The framework targets smooth convex losses with nonsmooth, nonseparable structured penalties.
- Scope and advantages: SPG applies to broad structured-sparsity problems, including uni- and multi-task regression with structures on inputs, outputs, or both.It is a first-order gradient-based method and can support warm restarts along a regularization path.
- Theoretical and computational advantages: SPG achieves an O(1/ε) convergence rate, compared with O(1/ε^2) for the standard subgradient method.The method is also described as more scalable than interior-point methods for SOCP or QP.
2. Background: Linear regression regularized by structured sparsity-inducing penalties.
Structured sparsity penalties incorporate group or pairwise relationships into linear regression, extending lasso beyond unstructured variable selection. The section defines overlapping-group-lasso and graph-guided-fused-lasso penalties as the main examples.
- Linear regression setting: Linear regression models high-dimensional inputs and seeks a small set of relevant variables influencing the response.The model uses observations {x_n,y_n} and coefficients β to relate inputs to outputs.
- Linear regression setting: Lasso combines squared-error loss with an ℓ1-norm penalty whose regularization parameter controls coefficient sparsity.The ℓ1 penalty encourages sparse coefficient estimates but does not encode relationships among inputs.
- Overlapping-group-lasso penalty: The overlapping-group-lasso penalty jointly shrinks coefficients within predefined, possibly overlapping groups.Its ℓ1/ℓ2 mixed norm supports group-level selection, while additional ℓ1 regularization can provide sparsity within groups.
- Graph-guided-fused-lasso penalty: The graph-guided-fused-lasso penalty uses weighted graph edges to encourage fusion between coefficients of related features.The sign of an edge weight determines whether positively or negatively related inputs tend toward the same or opposite output directions.
- Graph-guided-fused-lasso penalty: When all edge weights equal 1 and the graph is a chain, graph-guided fused lasso becomes the standard fused-lasso penalty.Thus, the graph formulation generalizes the chain-structured case.
3. Smoothing proximal gradient.
SPG reformulates complex structured sparsity penalties through dual norms, smooths the resulting maximization form, and optimizes the remaining simple nonsmooth term with proximal gradients. The method offers faster convergence than subgradient methods while retaining scalability for large structured regression problems.
- Penalty reformulation: SPG decouples nonseparable structured penalties through dual norms and reformulates overlapping-group-lasso and graph-guided-fused-lasso penalties into a common maximization form.The common formulation enables one optimization approach to handle both penalty types.
- Scope: The method applies to smooth convex losses with nonsmooth, nonseparable structured penalties in uni- and multi-task regression.Structures may occur on inputs, outputs, or both.
- Smooth approximation: SPG smooths the structured penalty by introducing a positive parameter µ, producing a convex differentiable approximation whose maximum gap from the original penalty is µD.The smoothing parameter controls approximation accuracy, with D equal to |G|/2 for overlapping groups and |E|/2 for graph-guided fusion.
- Optimization: The smoothed objective is optimized with FISTA while retaining the simple nonsmooth ℓ1 penalty, which can produce exact zeros for irrelevant features.This avoids the truncation post-processing required by methods that smooth the entire penalty.
- Time complexity: SPG has subgradient-like per-iteration costs but is more scalable than interior-point methods because those methods require substantially greater computation and memory.For regression gradients, the stated costs are O(J^2) when J < N with precomputation and O(JN) when J > N.
4. Related optimization methods.
Existing methods address structured penalties through proximal-gradient, active-set, path, and other first-order strategies, but their applicability, convergence guarantees, or scalability can be limited for general structures and high-dimensional designs.
- Connections with MM: Smoothing-based optimization is related to MM, but SPG constructs one smooth lower-bound approximation with bounded gap before applying proximal-gradient descent.MM instead iteratively constructs and minimizes an upper-bounding surrogate.
- Overlapping-group-lasso methods: Existing first-order methods often target specific subclasses of overlapping-group-lasso penalties and focus on exactly solving the proximal operator.Examples include projection methods, tree-structured coordinate ascent, and quadratic min-cost network flow.
- Overlapping-group-lasso methods: For arbitrary overlaps with the ℓ1/ℓ∞ penalty, network-flow-based optimization has O(1/ε) convergence but can incur high per-iteration complexity.Its worst-case network-flow cost is reported as at least O(|V||E|).
- Overlapping-group-lasso methods: For arbitrary overlaps with the ℓ1/ℓ2 penalty, the paper reports that its method has a superior convergence rate to the other compared methods.The comparison is summarized in Table 2.
- Overlapping-group-lasso methods: Active-set approaches can formulate overlapping-group subproblems as SOCPs or auxiliary-variable convex problems, but both routes may be computationally expensive.The auxiliary-variable route uses alternating gradient descent.
- Graph-guided-fused-lasso methods: For graph-guided fused lasso, general-graph proximal approximations lack guaranteed convergence, while path algorithms solve an entire regularization path.Path methods can be efficient when X has full column rank, whereas high-dimensional settings may require costly preprocessing.
5. Extensions to multi-task regression with structures on outputs.
The paper extends SPG to multi-task regression with structured penalties on outputs, covering shared input designs, overlapping output groups, and graph-guided output fusion. The resulting method retains O(1/ε) convergence while offering per-iteration complexity linear in the relevant output-structure size.
- Extension and formulation: SPG extends straightforwardly to sparse multi-task regression when nonsmooth, nonseparable structure is imposed on outputs.The extension addresses the same optimization difficulties encountered with structured penalties on inputs.
- Extension and formulation: The multi-task model uses X ∈ R^N×J for inputs, Y ∈ R^N×K for outputs, and B ∈ R^J×K for regression coefficients across K outputs.Each output follows y_k = Xβ_k + ε_k under a linear regression model.
- Structured penalties on outputs: The overlapping-group-lasso extension groups coefficients across output variables, with prior multi-task mixed-norm and tree-structured penalties as special cases.Each output group is drawn from a collection of subsets of the K outputs.
- Structured penalties on outputs: The graph-guided-fused-lasso extension applies a graph over the K outputs and reformulates its penalty using auxiliary variables and a matrix inner product.The construction parallels the input-structured formulation while replacing input indices with output indices.
- SPG optimization: The smoothed multi-task penalty is convex and smooth, with its gradient obtained from the optimal auxiliary-variable solution.The smoothing and gradient construction follow the techniques used earlier in the paper.
- SPG optimization: O(1/ε) convergence is obtained by substituting the smoothed penalty into the multi-task objective and applying Algorithm 1.For multi-task regression, SPG per-iteration complexity is linear in max(|K|, P_g∈G|g|) or max(|K|, |E|), while IPM complexity is at least cubic in K.
6. Experiment.
The experiments evaluate SPG on structured sparse regression, comparing it with FOBOS and interior-point methods in simulations and applying it to genetic data. SPG is reported as scalable and efficient, while structured penalties improve recovery and pathway-level interpretability.
- Simulation study I: Overlapping group lasso: SPG and FOBOS are orders of magnitude more efficient and scalable than IPM for SOCP, with SPG faster than FOBOS across almost all tested problem sizes.For larger J and N, SOCP results could not be collected.
- Simulation study I: Overlapping group lasso: SPG’s computational time does not increase with N in linear regression because its per-iteration complexity is independent of N.The experiments vary J, N, and γ while recording CPU time and objective value.
- Simulation study I: Overlapping group lasso: First-order methods are preferable for large-scale problems, but IPM solutions are more accurate and first-order methods struggle to match IPM precision at ε = 10^-6.The paper notes that ε = 10^-3 is often sufficiently accurate in applications, whereas IPM is limited to small or moderate-scale problems.
- Simulation study II: Multi-task graph-guided fused lasso: Graph-guided fused lasso produces fewer false positives and clearer block structures than lasso and ℓ1/ℓ2 multi-task regression when recovering structured regression patterns.The comparison uses absolute estimated coefficients across outputs and inputs.
- Real data analysis: Pathway analysis of breast cancer data: The overlapping-group-lasso model achieves a 29.23% balanced error rate with 696 selected genes belonging to 125 pathways.This result is obtained along the regularization path in the breast-cancer analysis.
- Real data analysis: Pathway analysis of breast cancer data: Incorporating pathway structure selects fewer, more functionally coherent pathways, whereas the ℓ1-norm baseline scatters selected genes across many pathways.The structured model’s selected pathways were also examined through functional enrichment analysis.
7. Conclusions and future work.
The paper identifies future work around improving empirical performance while preserving analyzable convergence, and around extending SPG with stochastic optimization guarantees.
- Reducing μ over iterations improves empirical results but makes the convergence rate harder to analyze.
- An online version based on stochastic gradient descent can be derived because SPG uses only gradient information.
- Proving a regret bound for the stochastic online version requires further investigation.
- Incorporating additional acceleration techniques is difficult because the ℓ1-norm penalty makes the fixed-point operator nondifferentiable.
- A potential strategy is to use a semi-smooth Newton method to address the nonsmooth fixed-point operator.
APPENDIX
The appendix develops the smoothing construction and its optimization guarantees, including conjugacy, smoothness, projection subproblems, and convergence bounds for the proximal-gradient algorithm.
- The Fenchel conjugate is introduced as part of the proof framework for analyzing the smoothed objective.
- The conjugate of the smoothing function is smooth, so the resulting smoothed objective f_μ(β) is smooth.
- Strong convexity of the smoothing function makes the maximizer unique, allowing Danskin’s theorem to derive the gradient of the smoothed function.
- The structured projection calculation decomposes into |G| independent Euclidean projections onto ℓ2-balls.
- The proximal-gradient analysis uses a lemma for convex smooth h(β) with Lipschitz-continuous gradient and an ℓ1 penalty.
- The appendix bounds the approximation and optimization errors to derive the iteration bound in equation (3.16).