Worst-case Error Bounds for Online Learning of Smooth Functions

Abstract

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 ℱ_q is the class of all absolutely continuous functions f: [0,1] →ℝ such that f’_q ≤ 1, and opt_p(ℱ_q) is the best possible upper bound on the sum of the p^th powers of absolute prediction errors for any number of trials guaranteed by any learner. We show that for any δ, ϵ∈ (0,1), opt_1+δ(ℱ_1+ϵ) = 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 opt_p(ℱ_q) 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 ℱ_q than it is to learn any general function in ℱ_q. 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 opt^nf_p,η(ℱ_q). We prove that opt^nf_p,η(ℱ_q) is finite if and only if opt_p(ℱ_q) is. Moreover, we prove for all p, q ≥ 2 and η≥ 1 that opt^nf_p,η(ℱ_q) = Θ(η).