# Online Learning of Smooth Functions

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 14 references that are in the map.
- First posted on arXiv 4 Jan 2023.

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

- [Sharper bounds for online learning of smooth functions of a single variable](https://mlsanity.com/paper/2105.14648/) (2021)

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

- [Bounds on the price of feedback for mistake-bounded online learning](https://mlsanity.com/paper/2401.05794/) (2024)
- [Mistake-bounded online learning with operation caps](https://mlsanity.com/paper/2509.03892/) (2025)
- [Worst-case Error Bounds for Online Learning of Smooth Functions](https://mlsanity.com/paper/2502.16388/) (2025)
- [Online learning of smooth functions on ℝ](https://mlsanity.com/paper/2604.03525/) (2026)

## Abstract (arXiv)

In this paper, we study the online learning of real-valued functions where the hidden function is known to have certain smoothness properties. Specifically, for q ≥ 1, let mathcal Fq be the class of absolutely continuous functions f: [0,1] → mathbb R such that |f'|q ≤ 1. For q ≥ 1 and d ∈ mathbb Z^+, let mathcal Fq,d be the class of functions f: [0,1]d → mathbb R such that any function g: [0,1] → mathbb R formed by fixing all but one parameter of f is in mathcal Fq. For any class of real-valued functions mathcal F and p>0, let optp(mathcal F) be the best upper bound on the sum of pth powers of absolute prediction errors that a learner can guarantee in the worst case. In the single-variable setup, we find new bounds for optp(mathcal Fq) that are sharp up to a constant factor. We show for all varepsilon ∈ (0, 1) that opt1+varepsilon(F∞) = Theta(varepsilon^-frac12) and opt1+varepsilon(Fq) = Theta(varepsilon^-frac12) for all q ≥ 2. We also show for varepsilon ∈ (0,1) that opt2(mathcal F1+varepsilon)=Theta(varepsilon-1). In addition, we obtain new exact results by proving that optp(mathcal Fq)=1 for q ∈ (1,2) and p ≥ 2+frac1q-1. In the multi-variable setup, we establish inequalities relating optp(mathcal Fq,d) to optp(mathcal Fq) and show that optp(mathcal F∞,d) is infinite when p<d and finite when p>d. We also obtain sharp bounds on learning mathcal F∞,d for p < d when the number of trials is bounded.