# Online learning of smooth functions on ℝ

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 14 references that are in the map.
- First posted on arXiv 4 Apr 2026.

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

- [A note on the price of bandit feedback for mistake-bounded online learning](https://mlsanity.com/paper/2101.06891/) (2021)
- [Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs](https://mlsanity.com/paper/2402.07453/) (2024)
- [Sharp bounds on the price of bandit feedback for several models of mistake-bounded online learning](https://mlsanity.com/paper/2209.01366/) (2022)
- [Online Learning of Smooth Functions](https://mlsanity.com/paper/2301.01434/) (2023)
- [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)

## Abstract (arXiv)

We study adversarial online learning of real-valued functions on ℝ. In each round the learner is queried at xt∈ℝ, predicts hat yt, and then observes the true value f(xt); performance is measured by cumulative p-loss sumt≥ 1|hat yt-f(xt)|p. For the class [ Gq=Biglf:ℝ→ℝ absolutely continuous: intℝ|f'(x)|q,dx≤ 1Bigr, ] we show that the standard model becomes ill-posed on ℝ: for every p≥ 1 and q>1, an adversary can force infinite loss. Motivated by this obstruction, we analyze three modified learning scenarios that limit the influence of queries that are far from previously observed inputs. In Scenario 1 the adversary must choose each new query within distance 1 of some past query. In Scenario 2 the adversary may query anywhere, but the learner is penalized only on rounds whose query lies within distance 1 of a past query. In Scenario 3 the loss in round t is multiplied by a weight g(minj<t|xt-xj|). We obtain sharp characterizations for Scenarios 1-2 in several regimes. For Scenario 3 we identify a clean threshold phenomenon: if g decays too slowly, then the adversary can force infinite weighted loss. In contrast, for rapidly decaying weights such as g(z)=e-cz we obtain finite and sharp guarantees in the quadratic case p=q=2. Finally, we study a natural multivariable slice generalization Gq,d of Gq on ℝd and show a sharp dichotomy: while the one-dimensional case admits finite opt-values in certain regimes, for every d≥ 2 the slice class Gq,d is too permissive, and even under Scenarios 1-3 an adversary can force infinite loss.