High-Dimensional Fused Lasso Regression Using Majorization–Minimization and Parallel Processing

In this article, we propose a majorization–minimization (MM) algorithm for high-dimensional fused lasso regression (FLR) suitable for parallelization using graphics processing units (GPUs). The MM algorithm is stable and flexible as it can solve the FLR problems with various types of design matrices and penalty structures within a few tens of iterations. We also show that the convergence of the proposed algorithm is guaranteed. We conduct numerical studies to compare our algorithm with other existing algorithms, demonstrating that the proposed MM algorithm is competitive in many settings including the two-dimensional FLR with arbitrary design matrices. The merit of GPU parallelization is also exhibited. Supplementary materials are available online.

• Publication year

  2013

• Venue

  Journal of Computational and Graphical Statistics

• Publication date

  2013-06-09

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1080/10618600.2013.878662arXiv 1306.1970
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Introductory Lectures on Convex Optimization - A Basic Course

  2014cited by this paper
• On the Optimal Step-size Selection for the Alternating Direction Method of Multipliers*

  2012cited by this paper
• Pairwise Fused Lasso

  2011cited by this paper
• Alternating linearization for structured regularization problems

  2011cited by this paper
• CUDA Application Design and Development

  2011cited by this paper
• Programming Massively Parallel Processors. A Hands-on Approach

  2010influential reference
• Smoothing proximal gradient method for general structured sparse regression

  2010influential reference
• Graphics Processing Units and High-Dimensional Optimization.

  2010cited by this paper
• Fast tridiagonal solvers on the GPU

  2010cited by this paper
• Proceedings of the 2nd IFAC Workshop on Distributed Estimation and Control in Networked Systems

  2010cited by this paper
• An efficient algorithm for a class of fused lasso problems

  2010cited by this paper
• The solution path of the generalized lasso

  2010influential reference
• Split Bregman method for large scale fused Lasso

  2010influential reference
• A Path Algorithm for the Fused Lasso Signal Approximator

  2009cited by this paper
• 1 Trend Filtering

  2009cited by this paper
• Sparse regression with exact clustering

  2008cited by this paper
• GPU Computing

  2008cited by this paper
• PATHWISE COORDINATE OPTIMIZATION

  2007influential reference
• Gradient methods for minimizing composite objective function

  2007cited by this paper
• Smooth minimization of non-smooth functions

  2005cited by this paper
• Sparsity and smoothness via the fused lasso

  2005cited by this paper
• PARAMETER CONVERGENCE FOR EM AND MM ALGORITHMS

  2005influential reference
• Variable Selection using MM Algorithms.

  2005cited by this paper
• USER’S GUIDE FOR SNOPT 5.3: A FORTRAN PACKAGE FOR LARGE-SCALE NONLINEAR PROGRAMMING

  2002cited by this paper
• Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization

  2001cited by this paper
• Optimization Transfer Using Surrogate Objective Functions

  2000cited by this paper
• Applied Numerical Linear Algebra

  1997influential reference
• Computer organization and design (2nd ed.): the hardware/software interface

  1997cited by this paper
• Regression Shrinkage and Selection via the Lasso

  1996cited by this paper
• ON THE CONVERGENCE PROPERTIES OF THE EM ALGORITHM

  1983cited by this paper
• A dual approach to solving nonlinear programming problems by unconstrained optimization

  1973cited by this paper
• An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations

  1973cited by this paper
• Nonlinear Programming: A Unified Approach.

  1970cited by this paper
• Multiplier and gradient methods

  1969influential reference
• A Fast Direct Solution of Poisson's Equation Using Fourier Analysis

  1965cited by this paper
• Maximal Flow Through a Network

  1956cited by this paper
• © Institute of Mathematical Statistics, 2004 LEAST ANGLE REGRESSION

  year unknowncited by this paper

• Simultaneous detection of change points and outliers

  2026cites this paper
• A fixed- time neurodynamic approach for fused lasso problems

  2025cites this paper
• Factor Augmented Matrix Regression

  2025cites this paper
• A graph decomposition-based approach for the graph-fused lasso

  2024cites this paper
• Joint Learning from Heterogeneous Rank Data

  2024cites this paper
• Multi-block alternating direction method of multipliers for ultrahigh dimensional quantile fused regression

  2024cites this paper
• A unified consensus-based parallel algorithm for high-dimensional regression with combined regularizations

  2024cites this paper
• A unified consensus-based parallel ADMM algorithm for high-dimensional regression with combined regularizations

  2023cites this paper
• Multi-block linearized alternating direction method for sparse fused Lasso modeling problems

  2023cites this paper
• Characterization of the solutions set of the generalized LASSO problems for non-full rank cases

  2023cites this paper
• Wilcoxon-type multivariate cluster elastic net

  2022cites this paper
• Penalized polygram regression

  2022cites this paper
• A Graph Decomposition-based ADMM Approach for the Graph-fused Lasso

  2021cites this paper
• Nonconvex Optimization via MM Algorithms: Convergence Theory

  2021cites this paper
• Accelerated gradient methods for sparse statistical learning with nonconvex penalties

  2020cites this paper
• Simultaneous spatial smoothing and outlier detection using penalized regression, with application to childhood obesity surveillance from electronic health records

  2020cites this paper
• High-Performance Statistical Computing in the Computing Environments of the 2020s.

  2020cites this paper
• Logistic regression with total variation regularization

  2020cites this paper
• MM Algorithms for Distance Covariance based Sufficient Dimension Reduction and Sufficient Variable Selection

  2019cites this paper
• Modified path algorithm of fused Lasso signal approximator for consistent recovery of change points

  2019cites this paper
• A Compact Neural Network for Fused Lasso Signal Approximator

  2019cites this paper
• An Algorithm for Graph-Fused Lasso Based on Graph Decomposition

  2019cites this paper
• Acceleration of Sparse Vector Autoregressive Modeling Using GPUs

  2019cites this paper
• Three Essays on Regularization and Machine Learning

  2019cites this paper
• Penalty-based spatial smoothing and outlier detection for childhood obesity surveillance from electronic health records

  2018cites this paper
• A Least Squares Method for Detecting Multiple Change Points in a Univariate Time Series

  2018cites this paper
• Easily Parallelizable and Distributable Class of Algorithms for Structured Sparsity, with Optimal Acceleration

  2017cites this paper
• Bayesian Fused Lasso Regression for Dynamic Binary Networks

  2017cites this paper
• Large-Scale Structured Sparsity via Parallel Fused Lasso on Multiple GPUs

  2017influential citation
• An MM-Based Algorithm for ${\ell }_{1}$ -Regularized Least-Squares Estimation With an Application to Ground Penetrating Radar Image Reconstruction

  2016cites this paper
• Segmentation of Counting Processes and Dynamical Models

  2016cites this paper
• Detection of multiple change points using penalized least square methods: a comparative study between ℓ0and ℓ1penalty

  2016cites this paper
• ASYMPTOTICALLY EFFICIENT PARAMETER ESTIMATION IN HIDDEN MARKOV SPATIO-TEMPORAL RANDOM FIELDS

  2015cites this paper
• Some properties of generalized fused lasso and its applications to high dimensional data

  2015cites this paper
• Some contributions to statistics and machine learning

  2015cites this paper
• Learning the Intensity of Time Events With Change-Points

  2015cites this paper
• Introduction to general purpose GPU computing

  2013cites this paper
• of Computational and Graphical Statistics

  2012cites this paper
• Journal of Statistical Planning and Inference

  year unknowncites this paper