Online learning of smooth functions on ℝ

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.