Title: Adaptive Risk Bounds in Univariate Total Variation Denoising and Trend Filtering,
Abstract: We study trend filtering, a relatively recent method for univariate
nonparametric regression. For a given positive integer $r$, the $r$-th order
trend filtering estimator is defined as the minimizer of the sum of squared
errors when we constrain (or penalize) the sum of the absolute $r$-th order
discrete derivatives of the fitted function at the design 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 positive
integer $r$, both in the constrained and penalized forms. Our main results show
that in the strong sparsity setting 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 therefore provide support for the use of
trend filtering, for every $r$, in the strong sparsity setting.