Online Learning of Smooth Functions

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.