# Adaptive Online Estimation of Piecewise Polynomial Trends

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2020.

## Built on by (most cited first, 11 of 11)

- [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)
- [Adapting to Continuous Covariate Shift via Online Density Ratio Estimation](https://mlsanity.com/paper/2302.02552/) (2023)
- [Unconstrained Dynamic Regret via Sparse Coding](https://mlsanity.com/paper/2301.13349/) (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)
- [Second Order Path Variationals in Non-Stationary Online Learning](https://mlsanity.com/paper/2205.01921/) (2022)
- [Optimal Dynamic Regret in LQR Control](https://mlsanity.com/paper/2206.09257/) (2022)
- [Nonparametric Density Estimation under Distribution Drift](https://mlsanity.com/paper/2302.02460/) (2023)
- [Adaptive Estimation and Learning under Temporal Distribution Shift](https://mlsanity.com/paper/2505.15803/) (2025)
- [Spatially Adaptive Online Prediction of Piecewise Regular Functions](https://mlsanity.com/paper/2203.16587/) (2022)

## Abstract (arXiv)

We consider the framework of non-stationary stochastic optimization [Besbes et al, 2015] with squared error losses and noisy gradient feedback where the dynamic regret of an online learner against a time varying comparator sequence is studied. Motivated from the theory of non-parametric regression, we introduce a new variational constraint that enforces the comparator sequence to belong to a discrete kth order Total Variation ball of radius Cn. This variational constraint models comparators that have piece-wise polynomial structure which has many relevant practical applications [Tibshirani, 2014]. By establishing connections to the theory of wavelet based non-parametric regression, we design a polynomial time algorithm that achieves the nearly optimal dynamic regret of tildeO(n^frac12k+3Cn^frac22k+3). The proposed policy is adaptive to the unknown radius Cn. Further, we show that the same policy is minimax optimal for several other non-parametric families of interest.