An Augmented ADMM Algorithm With Application to the Generalized Lasso Problem

ABSTRACT

In this article, we present a fast and stable algorithm for solving a class of optimization problems that arise in many statistical estimation procedures, such as sparse fused lasso over a graph, convex clustering, and trend filtering, among others. We propose a so-called augmented alternating direction methods of multipliers (ADMM) algorithm to solve this class of problems. Compared to a standard ADMM algorithm, our proposal significantly reduces the computational cost at each iteration while maintaining roughly the same overall convergence speed. We also consider a new varying penalty scheme for the ADMM algorithm, which could further accelerate the convergence, especially when solving a sequence of problems with tuning parameters of different scales. Extensive numerical experiments on the sparse fused lasso problem show that the proposed algorithm is more efficient than the standard ADMM and two other existing state-of-the-art specialized algorithms. Finally, we discuss a possible extension and some interesting connections to two well-known algorithms. Supplementary materials for the article are available online.

KEYWORDS:

• Alternating direction methods of multipliers
• Generalized lasso
• Large-scale nonsmooth convex optimization

Acknowledgments

This research was supported by a start-up fund from The Ohio State University. Special thanks to Peter Craigmile for reading the manuscript and giving invaluable comments on the work. The author thanks the editor, the associate editor, and two anonymous referees for constructive comments.