Smoothing Proximal Gradient Method for General Structured Sparse Learning

Abstract

We study the problem of learning high dimensional regression models regularized by a structured-sparsity-inducing penalty that encodes prior structural information on either input or output sides. We consider two widely adopted types of such penalties as our motivating examples: 1) overlapping group lasso penalty, based on the l1/l2 mixed-norm penalty, and 2) graph-guided fusion penalty. For both types of penalties, due to their non-separability, developing an efficient optimization method has remained a challenging problem. In this paper, we propose a general optimization approach, called smoothing proximal gradient method, which can solve the structured sparse regression problems with a smooth convex loss and a wide spectrum of structured-sparsity-inducing penalties. Our approach is based on a general smoothing technique of Nesterov. It achieves a convergence rate faster than the standard first-order method, subgradient method, and is much more scalable than the most widely used interior-point method. Numerical results are reported to demonstrate the efficiency and scalability of the proposed method.

arXiv admin note: substantial text overlap with arXiv:1005.4717

References in corpus (4)

• Pathwise coordinate optimization
• The composite absolute penalties family for grouped and hierarchical variable selection
• Multi-Task Feature Learning Via Efficient l2,1-Norm Minimization
• Fast Overlapping Group Lasso

Cited by in corpus (12)

• Tree-guided group lasso for multi-response regression with structured sparsity, with an application to eQTL mapping
• Can Image-Level Labels Replace Pixel-Level Labels for Image Parsing
• Multi-modal Face Pose Estimation with Multi-task Manifold Deep Learning
• Supervised Feature Selection in Graphs with Path Coding Penalties and Network Flows
• Convex Multitask Learning with Flexible Task Clusters
• Image classification by visual bag-of-words refinement and reduction
• Robust Image Analysis by L1-Norm Semi-supervised Learning
• Latent Semantic Learning with Structured Sparse Representation for Human Action Recognition
• Optimal Computational Trade-Off of Inexact Proximal Methods
• Petuum: A New Platform for Distributed Machine Learning on Big Data
• Semi-Stochastic Frank-Wolfe Algorithms with Away-Steps for Block-Coordinate Structure Problems
• Pairwise Constraint Propagation on Multi-View Data