Pathwise coordinate optimization

Abstract

We consider ``one-at-a-time'' coordinate-wise descent algorithms for a class of convex optimization problems. An algorithm of this kind has been proposed for the $L_1$-penalized regression (lasso) in the literature, but it seems to have been largely ignored. Indeed, it seems that coordinate-wise algorithms are not often used in convex optimization. We show that this algorithm is very competitive with the well-known LARS (or homotopy) procedure in large lasso problems, and that it can be applied to related methods such as the garotte and elastic net. It turns out that coordinate-wise descent does not work in the ``fused lasso,'' however, so we derive a generalized algorithm that yields the solution in much less time that a standard convex optimizer. Finally, we generalize the procedure to the two-dimensional fused lasso, and demonstrate its performance on some image smoothing problems.

Published in at http://dx.doi.org/10.1214/07-AOAS131 the Annals of Applied Statistics (http://www.imstat.org/aoas/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (11)

• Rejoinder to "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$

Cited by in corpus (321)

• Second-generation PLINK: rising to the challenge of larger and richer datasets
• Simultaneous analysis of Lasso and Dantzig selector
• Challenges of Big Data Analysis
• Coordinate descent algorithms for nonconvex penalized regression, with applications to biological feature selection
• A significance test for the lasso
• Sparse permutation invariant covariance estimation
• The solution path of the generalized lasso
• Coordinate descent algorithms for lasso penalized regression
• The huge Package for High-dimensional Undirected Graph Estimation in R
• Model Selection in Linear Mixed Models
• A Selective Review of Group Selection in High-Dimensional Models
• Group descent algorithms for nonconvex penalized linear and logistic regression models with grouped predictors
• Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation
• Newtonized Orthogonal Matching Pursuit: Frequency Estimation over the Continuum
• Smoothing proximal gradient method for general structured sparse regression
• Least angle and ${\ell }_1$ penalized regression: A review
• L1-Penalization for Mixture Regression Models
• Penalized Composite Quasi-Likelihood for Ultrahigh-Dimensional Variable Selection
• Safe Feature Elimination in Sparse Supervised Learning
• A stochastic gradient approach on compressive sensing signal reconstruction based on adaptive filtering framework
• Probabilistic Mid- and Long-Term Electricity Price Forecasting
• Estimating time-varying networks
• Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso
• Properties and refinements of the fused lasso
• Sparse estimation of large covariance matrices via a nested Lasso penalty
• Variable selection and regression analysis for graph-structured covariates with an application to genomics
• Regularization for Cox's proportional hazards model with NP-dimensionality
• The group fused Lasso for multiple change-point detection
• Forecasting Electricity Spot Prices using Lasso: On Capturing the Autoregressive Intraday Structure
• The screening and ranking algorithm to detect DNA copy number variations
• Tree-guided group lasso for multi-response regression with structured sparsity, with an application to eQTL mapping
• Lasso Screening Rules via Dual Polytope Projection
• Electricity Price Forecasting using Sale and Purchase Curves: The X-Model
• On Identification of Distribution Grids
• Safe Feature Elimination for the LASSO and Sparse Supervised Learning Problems
• Doubly Robust Smoothing of Dynamical Processes via Outlier Sparsity Constraints
• A Unified Successive Pseudo-Convex Approximation Framework
• Missing values: sparse inverse covariance estimation and an extension to sparse regression
• Convex Biclustering
• Regularized Ordinal Regression and the ordinalNet R Package
• The sparse Laplacian shrinkage estimator for high-dimensional regression
• Sparse Volterra and Polynomial Regression Models: Recoverability and Estimation
• Smoothing Proximal Gradient Method for General Structured Sparse Learning
• Generalized Methods and Solvers for Noise Removal from Piecewise Constant Signals
• Forecasting wind power - Modeling periodic and non-linear effects under conditional heteroscedasticity
• Modular proximal optimization for multidimensional total-variation regularization
• The MM Alternative to EM
• Kernelized Supervised Dictionary Learning
• High-Dimensional Sparse Additive Hazards Regression
• From Sparse Signals to Sparse Residuals for Robust Sensing
• Simultaneous Variable and Covariance Selection with the Multivariate Spike-and-Slab Lasso
• Distilling Accurate Descriptors from Multi-Source Experimental Data for Discovering Highly Active Perovskite OER Catalysts
• Regularized Estimation of Piecewise Constant Gaussian Graphical Models: The Group-Fused Graphical Lasso
• Anchor regression: heterogeneous data meets causality
• Sparse inverse covariance estimation with the lasso
• Robust Clustering Using Outlier-Sparsity Regularization
• Sparse Regression: Scalable algorithms and empirical performance
• Mind the duality gap: safer rules for the Lasso
• A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions
• A New High-Dimensional Time Series Approach for Wind Speed, Wind Direction and Air Pressure Forecasting
• An efficient Hessian based algorithm for solving large-scale sparse group Lasso problems
• Robust Nonparametric Regression via Sparsity Control with Application to Load Curve Data Cleansing
• Improved variable selection with Forward-Lasso adaptive shrinkage
• High dimensional thresholded regression and shrinkage effect
• Learning Large-Scale Bayesian Networks with the sparsebn Package
• Concave Penalized Estimation of Sparse Gaussian Bayesian Networks
• FDR-Control in Multiscale Change-point Segmentation
• Regression on manifolds: Estimation of the exterior derivative
• Convex Modeling of Interactions with Strong Heredity
• A new scope of penalized empirical likelihood with high-dimensional estimating equations
• Feature selection guided by structural information
• Online Hyperparameter-Free Sparse Estimation Method
• A Selective Overview of Variable Selection in High Dimensional Feature Space (Invited Review Article)
• Feature Clustering for Accelerating Parallel Coordinate Descent
• Variable selection for general index models via sliced inverse regression
• A majorization-minimization approach to variable selection using spike and slab priors
• Regularized 3D functional regression for brain image data via Haar wavelets
• Symmetric Bilinear Regression for Signal Subgraph Estimation
• Stability Selection
• Dynamic Network Cartography
• Inferring sparse Gaussian graphical models with latent structure
• Supervised Dictionary Learning and Sparse Representation-A Review
• Asymptotic equivalence of regularization methods in thresholded parameter space
• The shooting S-estimator for robust regression
• Convex and non-convex regularization methods for spatial point processes intensity estimation
• Adaptive Filter for Automatic Identification of Multiple Faults in a Noisy OTDR Profile
• Sparse principal component regression for generalized linear models
• GAP Safe Screening Rules for Sparse-Group-Lasso
• Robust and Sparse Regression via $\gamma$-divergence
• SPADES and mixture models
• Multicategory vertex discriminant analysis for high-dimensional data
• Stochastic Subsampling for Factorizing Huge Matrices
• Sparsity considerations for dependent observations
• Covariate Selection in High-Dimensional Generalized Linear Models With Measurement Error
• Robust Calibration of Radio Interferometers in Non-Gaussian Environment
• Robust Parametric Classification and Variable Selection by a Minimum Distance Criterion
• Forecasting the abnormal events at well drilling with machine learning
• Reconstructing DNA copy number by penalized estimation and imputation
• Hybrid ISTA: Unfolding ISTA With Convergence Guarantees Using Free-Form Deep Neural Networks
• Projected Nesterov's Proximal-Gradient Algorithm for Sparse Signal Reconstruction with a Convex Constraint
• On the Finite Time Convergence of Cyclic Coordinate Descent Methods
• Estimating the error variance in a high-dimensional linear model
• Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection
• A Path Algorithm for Constrained Estimation
• The Influence Function of Penalized Regression Estimators
• CRPS Learning
• Efficient Smoothed Concomitant Lasso Estimation for High Dimensional Regression
• Iteratively reweighted adaptive lasso for conditional heteroscedastic time series with applications to AR-ARCH type processes
• Penalized Estimation of Directed Acyclic Graphs From Discrete Data
• Solution Path Clustering with Adaptive Concave Penalty
• Machine learning technique using the signature method for automated quality control of the Argo profiles
• Non-Concave Penalization in Linear Mixed-Effects Models and Regularized Selection of Fixed Effects
• Hybrid safe-strong rules for efficient optimization in lasso-type problems
• Model-Consistent Sparse Estimation through the Bootstrap
• Bayesian Fused Lasso regression for dynamic binary networks
• Learning on Hypergraphs with Sparsity
• Scaling Up Coordinate Descent Algorithms for Large ${\ell }_1$ Regularization Problems
• Monte Carlo Simulation for Lasso-Type Problems by Estimator Augmentation
• Restarting the accelerated coordinate descent method with a rough strong convexity estimate
• Sparse regulatory networks
• Efficient Learning of Sparse Conditional Random Fields for Supervised Sequence Labelling
• Primitives for Dynamic Big Model Parallelism
• Short- to Mid-term Day-Ahead Electricity Price Forecasting Using Futures
• Structured Convex Optimization under Submodular Constraints
• Learning Mixed Graphical Models
• Bayesian generalized fused lasso modeling via NEG distribution
• Distance Metric Learning for Graph Structured Data
• Multiple Change-point Detection: a Selective Overview
• Sure Independence Screening for Ultra-High Dimensional Feature Space
• Selection of variables and decision boundaries for functional data via bi-level selection
• A Generalized Least Squares Matrix Decomposition
• Learning networks from high dimensional binary data: An application to genomic instability data
• Greedy algorithms for prediction
• Robust subset selection
• Path Following and Empirical Bayes Model Selection for Sparse Regression
• A coordinate-wise optimization algorithm for the Fused Lasso
• On pattern recovery of the fused Lasso
• High-dimensional variable selection via low-dimensional adaptive learning
• A path algorithm for the Fused Lasso Signal Approximator
• Joint Fairness Model with Applications to Risk Predictions for Under-represented Populations
• Screening Rules for Lasso with Non-Convex Sparse Regularizers
• Large-scale randomized-coordinate descent methods with non-separable linear constraints
• Sparse multi-view matrix factorisation: a multivariate approach to multiple tissue comparisons
• A PRESS statistic for two-block partial least squares regression
• Suboptimal Solution Path Algorithm for Support Vector Machine
• Joint estimation of sparse multivariate regression and conditional graphical models
• The restricted consistency property of leave-$n_v$-out cross-validation for high-dimensional variable selection
• The Group Square-Root Lasso: Theoretical Properties and Fast Algorithms
• Pathwise Coordinate Optimization for Sparse Learning: Algorithm and Theory
• On the total variation regularized estimator over a class of tree graphs
• I-LAMM for Sparse Learning: Simultaneous Control of Algorithmic Complexity and Statistical Error
• An Overview on the Estimation of Large Covariance and Precision Matrices
• A Fused Latent and Graphical Model for Multivariate Binary Data
• Exploration of heterogeneous treatment effects via concave fusion
• Online Learning for Matrix Factorization and Sparse Coding
• A Computational Framework for Multivariate Convex Regression and its Variants
• Dual Extrapolation for Sparse Generalized Linear Models
• Efficient algorithm to select tuning parameters in sparse regression modeling with regularization
• Dictionary LASSO: Guaranteed Sparse Recovery under Linear Transformation
• Joint Association Graph Screening and Decomposition for Large-scale Linear Dynamical Systems
• From safe screening rules to working sets for faster Lasso-type solvers
• Parallel integrative learning for large-scale multi-response regression with incomplete outcomes
• Sparse estimation via nonconcave penalized likelihood in a factor analysis model
• Sparse principal component regression via singular value decomposition approach
• Exact Post-Selection Inference for Changepoint Detection and Other Generalized Lasso Problems
• A Survey of Tuning Parameter Selection for High-dimensional Regression
• Variational Optimization
• A Fast and Scalable Polyatomic Frank-Wolfe Algorithm for the LASSO
• Safe Grid Search with Optimal Complexity
• Strong rules for nonconvex penalties and their implications for efficient algorithms in high-dimensional regression
• Fixed-point and coordinate descent algorithms for regularized kernel methods
• On the Complexity of the Weighted Fused Lasso
• A Scalable Algorithm for Gaussian Graphical Models with Change-Points
• Solving the OSCAR and SLOPE Models Using a Semismooth Newton-Based Augmented Lagrangian Method
• Exponential Series Approaches for Nonparametric Graphical Models
• Estimation of an Order Book Dependent Hawkes Process for Large Datasets
• Asymptotic Properties of Lasso+mLS and Lasso+Ridge in Sparse High-dimensional Linear Regression
• Binarsity: a penalization for one-hot encoded features in linear supervised learning
• The geometry of least squares in the 21st century
• Iterative Hard Thresholding for Model Selection in Genome-Wide Association Studies
• Stable Feature Selection from Brain sMRI
• Network-Guided Biomarker Discovery
• Selective Image Super-Resolution
• Correlated Feature Selection with Extended Exclusive Group Lasso
• Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squares
• A scalable hierarchical lasso for gene-environment interactions
• Easily parallelizable and distributable class of algorithms for structured sparsity, with optimal acceleration
• Regression shrinkage and grouping of highly correlated predictors with HORSES
• Random coordinate descent methods for nonseparable composite optimization
• Application of compressed sensing to genome wide association studies and genomic selection
• On Fast Convergence of Proximal Algorithms for SQRT-Lasso Optimization: Don't Worry About Its Nonsmooth Loss Function
• Learning step sizes for unfolded sparse coding
• Improving Sales Forecasting Accuracy: A Tensor Factorization Approach with Demand Awareness
• Graphical Elastic Net and Target Matrices: Fast Algorithms and Software for Sparse Precision Matrix Estimation
• Penalized Maximum Tangent Likelihood Estimation and Robust Variable Selection
• An Investigation of Methods for Handling Missing Data with Penalized Regression
• Parallel Calibration for Sensor Array Radio Interferometers
• Comparisons of penalized least squares methods by simulations
• Penalized Sparse Covariance Regression with High Dimensional Covariates
• Sparse and Low-bias Estimation of High Dimensional Vector Autoregressive Models
• Group-sparse SVD Models and Their Applications in Biological Data
• A Laplace Mixture Representation of the Horseshoe and Some Implications
• How have German University Tuition Fees Affected Enrollment Rates: Robust Model Selection and Design-based Inference in High-Dimensions
• Online Debiased Lasso for Streaming Data
• The Strong Screening Rule for SLOPE
• Model Selection for High Dimensional Quadratic Regression via Regularization
• Post-selection inference with HSIC-Lasso
• Spurious predictions with random time series: The Lasso in the context of paleoclimatic reconstructions. Discussion of: A statistical analysis of multiple temperature proxies: Are reconstructions of surface temperatures over the last 1000 years reliable?
• An Algorithm for Nonlinear, Nonparametric Model Choice and Prediction
• Sparse Estimation of Multivariate Poisson Log-Normal Models from Count Data
• Dimension Reduction Using Rule Ensemble Machine Learning Methods: A Numerical Study of Three Ensemble Methods
• OEM for least squares problems
• Inference for possibly high-dimensional inhomogeneous Gibbs point processes
• Model identification and local linear convergence of coordinate descent
• Structure retrieval from 4D-STEM: statistical analysis of potential pitfalls in high-dimensional data
• An Efficient Linearly Convergent Regularized Proximal Point Algorithm for Fused Multiple Graphical Lasso Problems
• An adaptive shortest-solution guided decimation approach to sparse high-dimensional linear regression
• SNAP: A semismooth Newton algorithm for pathwise optimization with optimal local convergence rate and oracle properties
• Learning high-dimensional graphical models with regularized quadratic scoring
• Decoupling Shrinkage and Selection for the Bayesian Quantile Regression
• PULasso: High-dimensional variable selection with presence-only data
• Fused-Lasso Regularized Cholesky Factors of Large Nonstationary Covariance Matrices of Longitudinal Data
• Nonparametric Reduced-Rank Regression for Multi-SNP, Multi-Trait Association Mapping
• Agriculture Commodity Arrival Prediction using Remote Sensing Data: Insights and Beyond
• Semismooth Newton Coordinate Descent Algorithm for Elastic-Net Penalized Huber Loss Regression and Quantile Regression
• A Gauss-Seidel Iterative Thresholding Algorithm for lq Regularized Least Squares Regression
• Bayesian Lasso Posterior Sampling via Parallelized Measure Transport
• On the Theoretical Guarantees for Parameter Estimation of Gaussian Random Field Models: A Sparse Precision Matrix Approach
• Coordinate Descent with Online Adaptation of Coordinate Frequencies
• A General Framework for Fast Stagewise Algorithms
• Likelihood Adaptively Modified Penalties
• A Cyclic Coordinate Descent Algorithm for lq Regularization
• Sparse Group Selection Through Co-Adaptive Penalties
• Penalized Regression Models for the NBA
• Uplift Regression: The R Package tools4uplift
• Network-regularized Sparse Logistic Regression Models for Clinical Risk Prediction and Biomarker Discovery
• Sparse Laplacian Shrinkage with the Graphical Lasso Estimator for Regression Problems
• High-dimensional Fused Lasso Regression using Majorization-Minimization and Parallel Processing
• Whole-brain Prediction Analysis with GraphNet
• An algorithmic view of ${\ell }_2$ regularization and some path-following algorithms
• A Dual Symmetric Gauss-Seidel Alternating Direction Method of Multipliers for Hyperspectral Sparse Unmixing
• A Semi-Smooth Newton Algorithm for High-Dimensional Nonconvex Sparse Learning
• Selective Inference and Learning Mixed Graphical Models
• Independent screening for single-index hazard rate models with ultra-high dimensional features
• ROS Regression: Integrating Regularization and Optimal Scaling Regression
• ${\ell }_1$ Adaptive Trend Filter via Fast Coordinate Descent
• New Proximal Newton-Type Methods for Convex Optimization
• ET-Lasso: A New Efficient Tuning of Lasso-type Regularization for High-Dimensional Data
• The Terminating-Random Experiments Selector: Fast High-Dimensional Variable Selection with False Discovery Rate Control
• Median regression with differential privacy
• Evaluating the Performance of BSBL Methodology for EEG Source Localization On a Realistic Head Model
• Sparse partial least squares for on-line variable selection in multivariate data streams
• Estimation of oblique structure via penalized likelihood factor analysis
• Bayesian Analysis for miRNA and mRNA Interactions Using Expression Data
• Certifying clusters from sum-of-norms clustering
• Robust and Adaptive Algorithms for Online Portfolio Selection
• A simple and efficient algorithm for fused lasso signal approximator with convex loss function
• LASSO ISOtone for High Dimensional Additive Isotonic Regression
• Accelerated Gradient Methods for Sparse Statistical Learning with Nonconvex Penalties
• A dynamic programming approach for generalized nearly isotonic optimization
• Thresholding-based Iterative Selection Procedures for Model Selection and Shrinkage
• Image-Based Prognostics Using Penalized Tensor Regression
• Homogeneity Pursuit in Single Index Models based Panel Data Analysis
• Semi-supervised Dictionary Learning Based on Hilbert-Schmidt Independence Criterion
• Another Look at DWD: Thrifty Algorithm and Bayes Risk Consistency in RKHS
• Using the "Hidden" Genome to Improve Classification of Cancer Types
• Soft Rule Ensembles for Statistical Learning
• Streaming regularization parameter selection via stochastic gradient descent
• SOFAR: large-scale association network learning
• A Twin Neural Model for Uplift
• EEG source localization using a sparsity prior based on Brodmann areas
• Estimation of Large Precision Matrices Through Block Penalization
• A network of spiking neurons for computing sparse representations in an energy efficient way
• Scalable Double Regularization for 3D Nano-CT Reconstruction
• Sparse Group Fused Lasso for Model Segmentation
• Sparse estimation of parameter support sets for generalized vector autoregressions by resampling and model aggregation
• On Newton Screening
• Energy Disaggregation with Semi-supervised Sparse Coding
• An Iterative Algorithm for Fitting Nonconvex Penalized Generalized Linear Models with Grouped Predictors
• Variable Selection in Regression-based Estimation of Dynamic Treatment Regimes
• Penalized Variable Selection in Multi-Parameter Regression Survival Modelling
• Joint Linear Trend Recovery Using L1 Regularization
• Distributional Consistency of Lasso by Perturbation Bootstrap
• FALDOI: A new minimization strategy for large displacement variational optical flow
• Path-based Iterative Reconstruction (PBIR) for X-ray Computed Tomography
• Who Gets the Job and How are They Paid? Machine Learning Application on H-1B Case Data
• Cyclic Coordinate Update Algorithms for Fixed-Point Problems: Analysis and Applications
• Sparse Learning over Infinite Subgraph Features
• Efficient proximal gradient algorithms for joint graphical lasso
• New Approaches to Identify Gene-by-Gene Interactions in Genome Wide Association Studies
• Supervised Multiscale Dimension Reduction for Spatial Interaction Networks
• Frequentist Shrinkage under Inequality Constraints
• Lasso and equivalent quadratic penalized models
• Adaptive support driven Bayesian reweighted algorithm for sparse signal recovery
• Lasso Regression: Estimation and Shrinkage via Limit of Gibbs Sampling
• Interquantile Shrinkage in Spatial Quantile Autoregressive Regression models
• Structure-Aware Dynamic Scheduler for Parallel Machine Learning
• Adaptive regularization for Lasso models in the context of non-stationary data streams
• Hybrid Tree-based Models for Insurance Claims
• Structure and Algorithm for Path of Solutions to a Class of Fused Lasso Problems
• yaglm: a Python package for fitting and tuning generalized linear models that supports structured, adaptive and non-convex penalties
• Convex Latent Effect Logit Model via Sparse and Low-rank Decomposition
• Estimating high-dimensional Markov-switching VARs
• Efficient and robust high-dimensional sparse logistic regression via nonlinear primal-dual hybrid gradient algorithms
• Sparse Distance Weighted Discrimination
• On an improvement of LASSO by scaling
• A stochastic computing architecture for iterative estimation
• APPLE: Approximate Path for Penalized Likelihood Estimators
• Sparsity by Worst-Case Penalties
• Subspace clustering of high-dimensional data: a predictive approach
• A generic coordinate descent solver for nonsmooth convex optimization
• Least Absolute Gradient Selector: Statistical Regression via Pseudo-Hard Thresholding
• Fast Identification of Biological Pathways Associated with a Quantitative Trait Using Group Lasso with Overlaps
• Alternating Linearization for Structured Regularization Problems
• Reconstructing DNA copy number by joint segmentation of multiple sequences
• CS-ROMER: A novel compressed sensing framework for Faraday depth reconstruction
• Algorithmic Bayesian Group Gibbs Selection
• Adaptive Bi-Level Variable Selection of Conditional Main Effects for Generalized Linear Models
• An Algorithm for Graph-Fused Lasso Based on Graph Decomposition
• Sparse Trace Norm Regularization
• Conditional Sparse Coding and Grouped Multivariate Regression