Adaptive piecewise polynomial estimation via trend filtering

By Robert Tibshirani. 2013

422 citations recorded by the source corpus.

We study trend filtering, a recently proposed tool of Kim et al. [SIAM Rev. 51 (2009) 339-360] for nonparametric regression. The trend filtering estimate is defined as the minimizer of a penalized least squares criterion, in which the penalty term sums the absolute $k$th order discrete derivatives over the input points. Perhaps not surprisingly, trend filtering estimates appear to have the structure of $k$th degree spline functions, with adaptively chosen knot points (we say ``appear'' here as trend filtering estimates are not really functions over continuous domains, and are only defined over the discrete set of inputs). This brings to mind comparisons to other nonparametric regression tools that also produce adaptive splines; in particular, we compare trend filtering to smoothing splines, which penalize the sum of squared derivatives across input points, and to locally adaptive regression splines [Ann. Statist. 25 (1997) 387-413], which penalize the total variation of the $k$th derivative. Empirically, we discover that trend filtering estimates adapt to the local level of smoothness much better than smoothing splines, and further, they exhibit a remarkable similarity to locally adaptive regression splines. We also provide theoretical support for these empirical findings; most notably, we prove that (with the right choice of tuning parameter) the trend filtering estimate converges to the true underlying function at the minimax rate for functions whose $k$th derivative is of bounded variation. This is done via an asymptotic pairing of trend filtering and locally adaptive regression splines, which have already been shown to converge at the minimax rate [Ann. Statist. 25 (1997) 387-413]. At the core of this argument is a new result tying together the fitted values of two lasso problems that share the same outcome vector, but have different predictor matrices.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Numerical Methods & Scientific Computing

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

In Numerical Methods & Scientific Computing

Citations in the corpus

Additive models with trend filtering (2017, methodology): “In univariate nonparametric regression, the localized nature of the total variation regularizer used by trend filtering has been shown to produce estimates with superior local adaptivity to those from smoothing splines (and linear smoothers, more generally) (Tibshirani 2014).”
Statistical Learning with Sparsity: The Lasso and Generalizations (2015, background): “The penalty can be modified (Tibshirani2 2014) to accommodate arbitrary (ordered) positions xi as follows:”
Doubly penalized estimation in additive regression with high-dimensional data (2019, methodology): “But when the design points are evenly spaced, it achieves the minimax rate of convergence over functions of bounded variation for general m ≥ 1, similarly as TV splines Tibshirani, 2014.”
Proximal Algorithms in Statistics and Machine Learning (2015, methodology): “A common regularized approach is to use lasso and elastic net, see Tibshirani [1996] and in Zou and Hastie [2005], respectively.”
The Falling Factorial Basis and Its Statistical Applications (2014, background): “…th order falling factorial basis matrix H ( k ) ∈ R n × n , over arbitrary sorted inputs x 1 , . . . x n , multiplication by H ( k ) and ( H ( k ) ) − 1 can each be computed in O ( nk ) in-place operations with Algorithm 1 Multiplication by H ( k ) Input: Vector to be multiplied y ∈ R n , order k…”
Fast and Flexible ADMM Algorithms for Trend Filtering (2014, methodology): “Tibshirani (2014) focuses on understanding trend ﬁltering estimates and their statistical properties, and relies on externally derived algorithms for comparisons of computational eﬃciency.”
Exact post-selection inference for the generalized lasso path (2018, background): “Trend ﬁltering can be seen as an extension of the 1d fused lasso for ﬁtting higher-order piecewise polynomials [32, 21, 35].”
Detecting Changes in Slope With an L0 Penalty (2017, methodology): “φ̂1:n, and this has m changes in slope, then using the fact that for trend-filtering a segmentation with m changes in slope has an effective degrees of freedom that ism + 2 (Tibshirani 2014), the BIC value is”
Interpretability is Harder in the Multiclass Setting: Axiomatic Interpretability for Multiclass Additive Models (2018, background): “…are traditionally fitted using splines (Eilers and Marx 1996); other base learners include trees (Lou, Caruana, and Gehrke 2012), trend filtering (Tibshirani 2014), etc. Comparing between several GAM fitting procedures, Binder and Tutz found that boosting performs well particularly in…”