Adaptive Online Estimation of Piecewise Polynomial Trends

Motivated from the theory of non-parametric regression, we introduce a \emph{new variational constraint} that enforces the comparator sequence to belong to a discrete k {th} order Total Variation ball of radius C_n . This variational constraint models comparators that have piece-wise polynomial structure which has many relevant practical applications [Tibshirani2015]. The proposed policy is \emph{adaptive to the unknown radius} C_n . Further, we show that the same policy is minimax optimal for several other non-parametric families of interest.