# Adaptive piecewise polynomial estimation via trend filtering

arXiv: https://arxiv.org/abs/1304.2986 · HTML: https://mlsanity.com/paper/1304.2986/

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Apr 2013.

## Built on by (most cited first, 30 of 47)

- [Elastic Graph Neural Networks](https://mlsanity.com/paper/2107.06996/) (2021)
- [Graph Trend Filtering Networks for Recommendations](https://mlsanity.com/paper/2108.05552/) (2021)
- [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021)
- [Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond](https://mlsanity.com/paper/2201.08905/) (2022)
- [Benchopt: Reproducible, efficient and collaborative optimization benchmarks](https://mlsanity.com/paper/2206.13424/) (2022)
- [Automatic differentiation of nonsmooth iterative algorithms](https://mlsanity.com/paper/2206.00457/) (2022)
- [Data fission: splitting a single data point](https://mlsanity.com/paper/2112.11079/) (2021)
- [Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms](https://mlsanity.com/paper/2305.19570/) (2023)
- [Deep Learning meets Nonparametric Regression: Are Weight-Decayed DNNs Locally Adaptive?](https://mlsanity.com/paper/2204.09664/) (2022)
- [An Optimal Reduction of TV-Denoising to Adaptive Online Learning](https://mlsanity.com/paper/2101.09438/) (2021)
- [MixLinear: Extreme Low Resource Multivariate Time Series Forecasting with 0.1K Parameters](https://mlsanity.com/paper/2410.02081/) (2024)
- [Second Order Path Variationals in Non-Stationary Online Learning](https://mlsanity.com/paper/2205.01921/) (2022)
- [A Priori Denoising Strategies for Sparse Identification of Nonlinear Dynamical Systems: A Comparative Study](https://mlsanity.com/paper/2201.12683/) (2022)
- [Multivariate Trend Filtering for Lattice Data](https://mlsanity.com/paper/2112.14758/) (2021)
- [A Gift from Label Smoothing: Robust Training with Adaptive Label Smoothing via Auxiliary Classifier under Label Noise](https://mlsanity.com/paper/2206.07277/) (2022)
- [Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms](https://mlsanity.com/paper/2305.15988/) (2023)
- [Smoothing ADMM for Sparse-Penalized Quantile Regression with Non-Convex Penalties](https://mlsanity.com/paper/2309.03094/) (2023)
- [TRACE: Trajectory Recovery for Continuous Mechanism Evolution in Causal Representation Learning](https://mlsanity.com/paper/2601.21135/) (2026)
- [CP-PINNs: Data-Driven Changepoints Detection in PDEs Using Online Optimized Physics-Informed Neural Networks](https://mlsanity.com/paper/2208.08626/) (2022)
- [The Voronoigram: Minimax Estimation of Bounded Variation Functions From Scattered Data](https://mlsanity.com/paper/2212.14514/) (2022)
- [Deep Neural Networks are Adaptive to Function Regularity and Data Distribution in Approximation and Estimation](https://mlsanity.com/paper/2406.05320/) (2024)
- [Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations](https://mlsanity.com/paper/2111.04681/) (2021)
- [Variance estimation in graphs with the fused lasso](https://mlsanity.com/paper/2207.12638/) (2022)
- [HMM for Discovering Decision-Making Dynamics Using Reinforcement Learning Experiments](https://mlsanity.com/paper/2401.13929/) (2024)
- [Nonsmooth Nonparametric Regression via Fractional Laplacian Eigenmaps](https://mlsanity.com/paper/2402.14985/) (2024)
- [Adaptive Estimation and Learning under Temporal Distribution Shift](https://mlsanity.com/paper/2505.15803/) (2025)
- [A Cross Validation Framework for Signal Denoising with Applications to Trend Filtering, Dyadic CART and Beyond](https://mlsanity.com/paper/2201.02654/) (2022)
- [Spatially Adaptive Online Prediction of Piecewise Regular Functions](https://mlsanity.com/paper/2203.16587/) (2022)
- [Deep P-Spline: Theory, Fast Tuning, and Application](https://mlsanity.com/paper/2501.01376/) (2025)
- [Highly Adaptive Principal Component Regression](https://mlsanity.com/paper/2602.10613/) (2026)

## Abstract (arXiv)

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 kth order discrete derivatives over the input points. Perhaps not surprisingly, trend filtering estimates appear to have the structure of kth 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 kth 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 kth 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.