Fast Newton methods for the group fused lasso

Matt Wytock Carnegie Mellon University, J. Zico Kolter Carnegie Mellon University, Suvrit Sra Carnegie Mellon University
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:216-225, 2014.

Abstract

We present a new algorithmic approach to the group fused lasso, a convex model that approx- imates a multi-dimensional signal via an ap- proximately piecewise-constant signal. This model has found many applications in mul- tiple change point detection, signal compres- sion, and total variation denoising, though existing algorithms typically using first-order or alternating minimization schemes. In this paper we instead develop a specialized pro- jected Newton method, combined with a pri- mal active set approach, which we show to be substantially faster that existing methods. Furthermore, we present two applications that use this algorithm as a fast subroutine for a more complex outer loop: segmenting linear regression models for time series data, and color image denoising. We show that on these problems the proposed method performs very well, solving the problems faster than state- of-the-art methods and to higher accuracy.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-university14f, title = {Fast {N}ewton methods for the group fused lasso}, author = {University, Matt Wytock Carnegie Mellon and University, J. Zico Kolter Carnegie Mellon and University, Suvrit Sra Carnegie Mellon}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {216--225}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/university14f/university14f.pdf}, url = {https://proceedings.mlr.press/r12/university14f.html}, abstract = {We present a new algorithmic approach to the group fused lasso, a convex model that approx- imates a multi-dimensional signal via an ap- proximately piecewise-constant signal. This model has found many applications in mul- tiple change point detection, signal compres- sion, and total variation denoising, though existing algorithms typically using first-order or alternating minimization schemes. In this paper we instead develop a specialized pro- jected Newton method, combined with a pri- mal active set approach, which we show to be substantially faster that existing methods. Furthermore, we present two applications that use this algorithm as a fast subroutine for a more complex outer loop: segmenting linear regression models for time series data, and color image denoising. We show that on these problems the proposed method performs very well, solving the problems faster than state- of-the-art methods and to higher accuracy.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Fast Newton methods for the group fused lasso %A Matt Wytock Carnegie Mellon University %A J. Zico Kolter Carnegie Mellon University %A Suvrit Sra Carnegie Mellon University %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-university14f %I PMLR %P 216--225 %U https://proceedings.mlr.press/r12/university14f.html %V R12 %X We present a new algorithmic approach to the group fused lasso, a convex model that approx- imates a multi-dimensional signal via an ap- proximately piecewise-constant signal. This model has found many applications in mul- tiple change point detection, signal compres- sion, and total variation denoising, though existing algorithms typically using first-order or alternating minimization schemes. In this paper we instead develop a specialized pro- jected Newton method, combined with a pri- mal active set approach, which we show to be substantially faster that existing methods. Furthermore, we present two applications that use this algorithm as a fast subroutine for a more complex outer loop: segmenting linear regression models for time series data, and color image denoising. We show that on these problems the proposed method performs very well, solving the problems faster than state- of-the-art methods and to higher accuracy. %Z Reissued by PMLR on 04 October 2026.
APA
University, M.W.C.M., University, J.Z.K.C.M. & University, S.S.C.M.. (2014). Fast Newton methods for the group fused lasso. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:216-225 Available from https://proceedings.mlr.press/r12/university14f.html. Reissued by PMLR on 04 October 2026.

Related Material