Adaptive piecewise polynomial estimation via trend filtering

Abstract

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.

Published in at http://dx.doi.org/10.1214/13-AOS1189 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• Piecewise linear regularized solution paths
• Degrees of freedom in lasso problems

Cited by in corpus (26)

• Flexible Modeling of Epidemics with an Empirical Bayes Framework
• Fast and Flexible ADMM Algorithms for Trend Filtering
• Dynamic Shrinkage Processes
• Detecting multiple generalized change-points by isolating single ones
• Less is more: balancing noise reduction and data retention in fMRI with data-driven scrubbing
• Vector-Valued Graph Trend Filtering with Non-Convex Penalties
• Weighted Bayesian Bootstrap for Scalable Bayes
• On the estimation of variance parameters in non-standard generalised linear mixed models: Application to penalised smoothing
• Sparse HP Filter: Finding Kinks in the COVID-19 Contact Rate
• Trend Filtering -- I. A Modern Statistical Tool for Time-Domain Astronomy and Astronomical Spectroscopy
• Predicting B Cell Receptor Substitution Profiles Using Public Repertoire Data
• New Risk Bounds for 2D Total Variation Denoising
• Adaptive Estimation of Multivariate Piecewise Polynomials and Bounded Variation Functions by Optimal Decision Trees
• Nonparametric Regression with Adaptive Truncation via a Convex Hierarchical Penalty
• Trend Filtering -- II. Denoising Astronomical Signals with Varying Degrees of Smoothness
• A Variational View on Statistical Multiscale Estimation
• P-splines with an l1 penalty for repeated measures
• Detecting Abrupt Changes in the Presence of Local Fluctuations and Autocorrelated Noise
• MARS via LASSO
• Exponential Family Trend Filtering on Lattices
• Improving Power by Conditioning on Less in Post-selection Inference for Changepoints
• Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations
• Structured regularization based velocity structure estimation in local earthquake tomography for the adaptation to velocity discontinuities
• Simultaneous detection and estimation of trait associations with genomic phenotypes
• Markov-switching State Space Models for Uncovering Musical Interpretation
• An empirical study of neural networks for trend detection in time series