# A Chaining Algorithm for Online Nonparametric Regression

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2015.

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

- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [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)
- [Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spaces](https://mlsanity.com/paper/2207.05849/) (2022)
- [Unconstrained Dynamic Regret via Sparse Coding](https://mlsanity.com/paper/2301.13349/) (2023)
- [Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms](https://mlsanity.com/paper/2305.19570/) (2023)
- [Second Order Path Variationals in Non-Stationary Online Learning](https://mlsanity.com/paper/2205.01921/) (2022)
- [Online nonparametric regression with Sobolev kernels](https://mlsanity.com/paper/2102.03594/) (2021)
- [Infinite Action Contextual Bandits with Reusable Data Exhaust](https://mlsanity.com/paper/2302.08551/) (2023)
- [Spatially Adaptive Online Prediction of Piecewise Regular Functions](https://mlsanity.com/paper/2203.16587/) (2022)
- [Minimax-optimal and Locally-adaptive Online Nonparametric Regression](https://mlsanity.com/paper/2410.03363/) (2024)
- [Minimax Adaptive Online Nonparametric Regression over Besov Spaces](https://mlsanity.com/paper/2505.19741/) (2025)
- [Online Realizable Regression and Applications for ReLU Networks](https://mlsanity.com/paper/2602.19172/) (2026)
- [Online nearest neighbor classification](https://mlsanity.com/paper/2307.01170/) (2023)
- [Dynamic Regret for Online Regression in RKHS via Discounted VAW and Subspace Approximation](https://mlsanity.com/paper/2604.25021/) (2026)

## Abstract (arXiv)

We consider the problem of online nonparametric regression with arbitrary deterministic sequences. Using ideas from the chaining technique, we design an algorithm that achieves a Dudley-type regret bound similar to the one obtained in a non-constructive fashion by Rakhlin and Sridharan (2014). Our regret bound is expressed in terms of the metric entropy in the sup norm, which yields optimal guarantees when the metric and sequential entropies are of the same order of magnitude. In particular our algorithm is the first one that achieves optimal rates for online regression over H"older balls. In addition we show for this example how to adapt our chaining algorithm to get a reasonable computational efficiency with similar regret guarantees (up to a log factor).