# Spatially Adaptive Online Prediction of Piecewise Regular Functions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 41 references that are in the map.
- First posted on arXiv 30 Mar 2022.

## Builds on (most cited first, 17 of 17)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions](https://mlsanity.com/paper/1301.6677/) (2013)
- [Adaptive piecewise polynomial estimation via trend filtering](https://mlsanity.com/paper/1304.2986/) (2013)
- [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021)
- [Online Forecasting of Total-Variation-bounded Sequences](https://mlsanity.com/paper/1906.03364/) (2019)
- [Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers](https://mlsanity.com/paper/1605.08400/) (2016)
- [A Chaining Algorithm for Online Nonparametric Regression](https://mlsanity.com/paper/1502.07697/) (2015)
- [Multivariate extensions of isotonic regression and total variation denoising via entire monotonicity and Hardy-Krause variation](https://mlsanity.com/paper/1903.01395/) (2019)
- [Adaptive Online Estimation of Piecewise Polynomial Trends](https://mlsanity.com/paper/2010.00073/) (2020)
- [Adaptive Estimation of Multivariate Piecewise Polynomials and Bounded Variation Functions by Optimal Decision Trees](https://mlsanity.com/paper/1911.11562/) (2019)
- [Online Isotonic Regression](https://mlsanity.com/paper/1603.04190/) (2016)
- [An Optimal Reduction of TV-Denoising to Adaptive Online Learning](https://mlsanity.com/paper/2101.09438/) (2021)
- [Locally-Adaptive Nonparametric Online Learning](https://mlsanity.com/paper/2002.01882/) (2020)
- [New Risk Bounds for 2D Total Variation Denoising](https://mlsanity.com/paper/1902.01215/) (2019)
- [Divided Differences, Falling Factorials, and Discrete Splines: Another Look at Trend Filtering and Related Problems](https://mlsanity.com/paper/2003.03886/) (2020)
- [MARS via LASSO](https://mlsanity.com/paper/2111.11694/) (2021)

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

- [Optimal Dynamic Regret in LQR Control](https://mlsanity.com/paper/2206.09257/) (2022)

## Abstract (arXiv)

We consider the problem of estimating piecewise regular functions in an online setting, i.e., the data arrive sequentially and at any round our task is to predict the value of the true function at the next revealed point using the available data from past predictions. We propose a suitably modified version of a recently developed online learning algorithm called the sleeping experts aggregation algorithm. We show that this estimator satisfies oracle risk bounds simultaneously for all local regions of the domain. As concrete instantiations of the expert aggregation algorithm proposed here, we study an online mean aggregation and an online linear regression aggregation algorithm where experts correspond to the set of dyadic subrectangles of the domain. The resulting algorithms are near linear time computable in the sample size. We specifically focus on the performance of these online algorithms in the context of estimating piecewise polynomial and bounded variation function classes in the fixed design setup. The simultaneous oracle risk bounds we obtain for these estimators in this context provide new and improved (in certain aspects) guarantees even in the batch setting and are not available for the state of the art batch learning estimators.