Worst-case Error Bounds for Online Learning of Smooth Functions

Online learning is a model of machine learning where the learner is trained on sequential feedback. We investigate worst-case error for the online learning of real functions that have certain smoothness constraints. Suppose that Fq is the class of all absolutely continuous functions f: [0, 1] rightarrow ℝ such that |f'|q ≤ 1, and operatornameoptp(Fq) is the best possible upper bound on the sum of the pth powers of absolute prediction errors for any number of trials guaranteed by any learner. We show that for any δ, ε ∈ (0, 1), operatornameopt1+δ (F1+ε) = O(min(δ, ε)-1). Combined with the previous results of Kimber and Long (1995) and Geneson and Zhou (2023), we achieve a complete characterization of the values of p, q ≥ 1 that result in operatornameoptp(Fq) being finite, a problem open for nearly 30 years. We study the learning scenarios of smooth functions that also belong to certain special families of functions, such as polynomials. We prove a conjecture by Geneson and Zhou (2023) that it is not any easier to learn a polynomial in Fq than it is to learn any general function in Fq. We also define a noisy model for the online learning of smooth functions, where the learner may receive incorrect feedback up to η ≥ 1 times, denoting the worst-case error bound as operatornameoptnfp, η (Fq). We prove that operatornameoptnfp, η (Fq) is finite if and only if operatornameoptp(Fq) is. Moreover, we prove for all p, q ≥ 2 and η ≥ 1 that operatornameoptnfp, η (Fq) = Theta (η).