# Sharper bounds for online learning of smooth functions of a single variable

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 12 references that are in the map.
- First posted on arXiv 30 May 2021.

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

- [Online Learning of Smooth Functions](https://mlsanity.com/paper/2301.01434/) (2023)

## Abstract (arXiv)

We investigate the generalization of the mistake-bound model to continuous real-valued single variable functions. Let Fq be the class of absolutely continuous functions f: [0, 1] rightarrow ℝ with ||f'||q ≤ 1, and define optp(Fq) as the best possible bound on the worst-case sum of the pth powers of the absolute prediction errors over any number of trials. Kimber and Long (Theoretical Computer Science, 1995) proved for q ≥ 2 that optp(Fq) = 1 when p ≥ 2 and optp(Fq) = ∞ when p = 1. For 1 < p < 2 with p = 1+ε, the only known bound was optp(Fq) = O(ε-1) from the same paper. We show for all ε ∈ (0, 1) and q ≥ 2 that opt1+ε(Fq) = Theta(ε^-frac12), where the constants in the bound do not depend on q. We also show that opt1+ε(F∞) = Theta(ε^-frac12).