Smoothing Proximal Gradient Method for General Structured Sparse Learning

Xi Chen, Qihang Lin, Seyoung Kim, Jaime G. Carbonell, Eric P. Xing
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:133-142, 2011.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-chen11a, title = {Smoothing Proximal Gradient Method for General Structured Sparse Learning}, author = {Chen, Xi and Lin, Qihang and Kim, Seyoung and Carbonell, Jaime G. and Xing, Eric P.}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {133--142}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/chen11a/chen11a.pdf}, url = {https://proceedings.mlr.press/r9/chen11a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Smoothing Proximal Gradient Method for General Structured Sparse Learning %A Xi Chen %A Qihang Lin %A Seyoung Kim %A Jaime G. Carbonell %A Eric P. Xing %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-chen11a %I PMLR %P 133--142 %U https://proceedings.mlr.press/r9/chen11a.html %V R9 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
Chen, X., Lin, Q., Kim, S., Carbonell, J.G. & Xing, E.P.. (2011). Smoothing Proximal Gradient Method for General Structured Sparse Learning. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:133-142 Available from https://proceedings.mlr.press/r9/chen11a.html. Reissued by PMLR on 04 October 2026.

Related Material