Prediction bounds for (higher order) total variation regularized least squares

We establish oracle inequalities for the least squares estimator $\hat f$ with penalty on the total variation of $\hat f$ or on its higher order differences. Our main tool is an interpolating vector that leads to upper bounds for the effective sparsity. This allows one to show that the penalty on the $k^{\text{th}}$ order differences leads to an estimator $\hat f$ that can adapt to the number of jumps in the $(k-1)^{\text{th}}$ order differences. We present the details for $k=2, \ 3$ and expose a framework for deriving the result for general $k\in \mathbb{N}$.