Spatial Adaptation in Trend Filtering
Preprint
Abstract
We study trend filtering, a relatively recent method for univariate nonparametric regression. For a given integer $r \geq 1$, the trend filtering estimator of order $r$ is defined as the minimizer of the sum of squared errors when we constrain (or penalize) the sum of the absolute discrete derivatives of order $r$ over the input points. For $r = 1$, the estimator reduces to total variation regularization which has received much attention in the statistics and image processing literature. In this paper, we study the performance of the trend filtering estimator for every $r \geq 1$, both in the constrained and penalized forms. Our main results show that the estimator is optimally spatially adaptive. Specifically, we prove that, in spite of being a nonparametric estimator, when the underlying function is a (discrete) spline with few "knots", the risk (under the global squared error loss) of the trend filtering estimator (with an appropriate choice of the tuning parameter) achieves the parametric $n^{-1}$-rate, up to a logarithmic (multiplicative) factor. Our results also include high probability statements on the loss and are stated in sharp oracle form, i.e., our results apply to misspecification and have leading constant one for the misspecified term. Moreover, some of the metric entropy results used in this paper, derived using connections to fat shattering, are of independent interest.
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- On Concentration for (Regularized) Empirical Risk MinimizationSankhya A, 2017
- Sharp MSE Bounds for Proximal DenoisingFoundations of Computational Mathematics, 2015
- Living on the edge: phase transitions in convex programs with random dataInformation and Inference: A Journal of the IMA, 2014
- Corrupted Sensing: Novel Guarantees for Separating Structured SignalsIEEE Transactions on Information Theory, 2014
- Multiple Change-Point Estimation With a Total Variation PenaltyJournal of the American Statistical Association, 2010
- Splines in Higher Order TV RegularizationInternational Journal of Computer Vision, 2006
- Spatially adaptive smoothing splinesBiometrika, 2006
- Spatially Adaptive Regression Splines and Accurate Knot Selection SchemesJournal of the American Statistical Association, 2001
- Nonlinear total variation based noise removal algorithmsPhysica D: Nonlinear Phenomena, 1992
- Discrete Splines via Mathematical ProgrammingSIAM Journal on Control, 1971