Fast and Flexible ADMM Algorithms for Trend Filtering

By Aaditya Ramdas, Robert Tibshirani. 2014

130 citations recorded by the source corpus.

This article presents a fast and robust algorithm for trend filtering, a recently developed nonparametric regression tool. It has been shown that, for estimating functions whose derivatives are of bounded variation, trend filtering achieves the minimax optimal error rate, while other popular methods like smoothing splines and kernels do not. Standing in the way of a more widespread practical adoption, however, is a lack of scalable and numerically stable algorithms for fitting trend filtering estimates. This article presents a highly efficient, specialized alternating direction method of multipliers (ADMM) routine for trend filtering. Our algorithm is competitive with the specialized interior point methods that are currently in use, and yet is far more numerically robust. Furthermore, the proposed ADMM implementation is very simple, and, importantly, it is flexible enough to extend to many interesting related problems, such as sparse trend filtering and isotonic trend filtering. Software for our method is freely available, in both the C and R languages.

Subfields: Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Generalized Sparse Additive Models (2019, background): “…penalty, (13) can be solved exactly in 2 n operations for k = 0 [Johnson, 2013], or iteratively in roughly O (( k + 1) n ) operations for k ≥ 1 [Ramdas and Tibshirani, 2015]; with the convex indicator of an M -dimensional linear subspace, (13) can be solved in O ( M 2 n ) operations using…”
Additive models with trend filtering (2017, methodology): “For the univariate trend filtering solver, we used the trendfilter function in the glmgen package, which is an implementation of the fast ADMM algorithm given in Ramdas and Tibshirani [2016]. For the univariate smoothing spline solver, we used the smooth.”
Fused Lasso Additive Model (2014, background): “The problem of estimating piecewise trends of any order between a single predictor and response has been previously explored (Kim et al. 2009; Ramdas and Tibshirani 2014; Tibshirani 2014).”
Deep learning for short-term traffic flow prediction (2016, methodology): “A computationally efficient algorithms for trend filtering with differentiation operator of any order D (k) was recently proposed by Ramdas and Tibshirani [2015]. 3 Chicago Traffic Flow During Special Events To illustrate our methodology, we use data from twenty-one loop-detectors installed on a nor”